 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / September 2005is allocate really this slow?
I'm trying to cut down the time it takes to do the following task. It currently takes about 25 seconds to do. If anyone has any tips on what could cut this down considerably, any help much appreciated. --- // elements is a hashmap of 10000 shapes containing 7100 Triangles. ... for (Iterator iter = elements.values().iterator(); iter.hasNext();) { Element elem = (Element)iter.next(); if (elem.getShape() == TRIANGLE) { doStuff(elem); } } public void doStuff(Element tri) { for (int j = 0; j < 3; j++) { // here I allocate a data structure using new for each triangle edge // has 4 set() methods to newly allocated data structure } doMoreStuff(NewDataStructures[] ds) } public void doMoreStuff(NewDataStructures[] ds) { // this isn't included in method above because I have // to have my 3 new data structures built first before // I can set data to them. for (int k = 0; k < 3; k++) { // ds[k].set(...); // has 3 set methods like above } } I'm thinking the problem might be in the for statement using j where I allocate a new data structure (class) for each edge of my triangle. Is allocating a new object the slowest statement in this code? > I'm trying to cut down the time it takes to do the following task. It > currently takes about 25 seconds to do. If anyone has any tips on what > could cut this down considerably, any help much appreciated. [snip] > I'm thinking the problem might be in the for statement using j where I > allocate a new data structure (class) for each edge of my triangle. Is > allocating a new object the slowest statement in this code? Don't guess, profile. Get a profiler and run it against your code to determine exactly what is taking so long in your code. You may be surprised. - Oliver Well, in the code above, I've got this code wrapped around my initial for statement, but there's so many smaller loops inside that I didn't get the time from then because they only loop 3 times and there are so many, that I didn't think that would help me much to see lots of little ms times, if it can even measure those correctly. long t1 = System.currentTimeMillis(); for (Iterator iter = elements.values().iterator(); iter.hasNext();) { .... } long t2 = System.currentTimeMillis(); System.out.println("time: " + (t2 - t1)); > Well, in the code above, I've got this code wrapped around my initial > for statement, but there's so many smaller loops inside that I didn't > get the time from then because they only loop 3 times and there are so > many, that I didn't think that would help me much to see lots of little > ms times, if it can even measure those correctly. A profiler, such as OptimizeIt or JProbe for example, would solve this problem for you. That's what Oliver was suggesting. It is possible that garbage collection (a necessary consequence of allocation) is using time. Other things are also likely culprits. You haven't even posted a runnable sample, so no one can give you a good answer. Programmers are notoriously bad at guessing performance problems by intuition. If you can't get hold of a profiler, then a decent step would be to run the app with -Xverbose:gc and see how long the VM reports that garbage collection is taking.  Signaturewww.designacourse.com The Easiest Way To Train Anyone... Anywhere. Chris Smith - Lead Software Developer/Technical Trainer MindIQ Corporation > A profiler, such as OptimizeIt or JProbe for example, would solve this > problem for you. That's what Oliver was suggesting. Yes, exactly. You (Wizumwalt) said you use Eclipse, right? I think there are some free ones available on SourceForge that integrate well with Eclipse. > Programmers are notoriously bad at guessing performance > problems by intuition. To give you a concrete example of this, I wrote a Role Playing Game engine about as sophisticated as the SNES games from the late 80s early 90s (e.g. Chrono Trigger, Secret of Mana, etc.). Frame Rates were slightly choppy (20-30fps), and I figured this was because I was allowing multiple layers of alpha-blended parallax scrolling backgrounds. Looks beautiful, but really killing my CPU. Or so I thought. When I actually profiled the code, it turns out what was slowing the game down so much was that I was rendering ALL the sprites, not jus the ones visible on screen. There were only like a dozen sprites or so on the map I was testing on, so I don't understand why this would slow the engine down so much, but it did. I added an if statement to check if a sprite was visible before rendering it, and then the frame rates shot up in the 120fps range. So again, don't *GUESS* what the problem is; profile it to be sure. - Oliver >If you can't get hold of a profiler see http://mindprod.com/jgloss/profiler.html SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Again taking new Java programming contracts. > > I'm thinking the problem might be in the for statement using j where I > > allocate a new data structure (class) for each edge of my triangle. Is > > allocating a new object the slowest statement in this code? > > Don't guess, profile. Yes, that's a good first reaction.. but in the OP's case, maybe all the profiling in the world won't give him the key insight that his data structure (HashMap?) may be to blame. Profiling tells you where the bottleneck is, but it won't tell you whether your data structures are totally inappropriate or not. >> Don't guess, profile. > [quoted text clipped - 3 lines] > bottleneck is, but it won't tell you whether your data structures are > totally inappropriate or not. That's true, but if the profiler shows that the bottle neck is occuring in a portion of the code where the HashMap isn't even visible, then the OP won't even have to strain his/her mind trying to figure out a better data structure. Programmers are notoriously bad at guessing where the bottleneck is, so I recommend that programmers avoid guessing whenever possible and actually use tools (e.g. a profiler) to determine where the bottleneck is. - Oliver > [...] but in the OP's case, maybe all the > profiling in the world won't give him the key insight that his data > structure (HashMap?) may be to blame. Profiling tells you where the > bottleneck is, but it won't tell you whether your data structures are > totally inappropriate or not. I'm not sure whether you are suggesting that the HashMap may actually be the cause of the OP's problems, but it seems /very/ unlikely to me that there's any connection at all. All s/he's doing in this context is looping over its elements which is not ever an expensive operation. -- chris > > > I'm thinking the problem might be in the for statement using j where I > > > allocate a new data structure (class) for each edge of my triangle. Is [quoted text clipped - 7 lines] > bottleneck is, but it won't tell you whether your data structures are > totally inappropriate or not. If the profiler tells me that HashMap.get() is bottleneck then I can infer that either the get method needs more efficient implementation or that HashMap is not appropriate data structure. Am I missing something? > > > Don't guess, profile. > > [quoted text clipped - 9 lines] > > Am I missing something? A profiler will always point you to the bottleneck (there's almost always just 1 bottleneck, very, very rarely do you have two competing bottlenecks of equal "diameter")... the danger with this is that you may blindly say "OK, here's the bottleneck, now let's optimize this code". When in reality that code should not be called at all, i.e. the bottleneck is an illusion created by having picked poor data strucutures, or worse, a poor architecture. If we forget about the HashMap for a second, you can imagine medium-to-large systems where lots of people work on various parts, and someone using a profiler.... and then what? Does that developer have enough knowledge of the whole system to be able to make the above distinction? Is the problem data structures or architecture, or are they fine and can we proceed to widening that bottleneck? My claim is that the majority will jump to optimize the bottleneck away, without first having stepped back to ask the more fundamental question. This problem is in the same highly problematic category of process failures as using XML when you shouldn't. It leads to gross, gross wasting of resources, since the developer or team commits to spending time and money on something that they shouldn't be doing AT ALL. > A profiler will always point you to the bottleneck (there's almost always > just 1 bottleneck, very, very rarely do you have two competing bottlenecks [quoted text clipped - 13 lines] > widening > that bottleneck? Good points. Here's what I think would happen in an ideal situation. Without profiling, all you have are guesses, and so people will just be shifting the blame around. If it takes a few minutes for the print dialog to show up, the architect might claim that that's an implementation detail, not her responsability. The profiler would probably actually help in pinpointing that the problem lies when manipulating this particular data structure. The low-level developer doesn't know enough to know if he can just change the data structure to something else without breaking everything, but he knows enough to determine what the asymptotic limits of the data structure are. That's useful information. The developer thenjumps in to try to optimize it right away. Of course, because of the data structure in use, he can't get much better than O(n^2), so he reports to the technical lead that "The good news I found the bottleneck. The bad news is I can prove that our code cannot beat O(n^2) so essentially we can't fix it." The technical lead then brings this information to the head designer or architect (or whatever her job title is), who DOES have a high level understanding of the whole system, but doesn't know the low level details of how everything is implemented. She then is responsible for determining what system-wide changes can be made to improve the performance. If another data structure could bring running time down to O(n log(n)), it's up to her to determine that. In practice, maybe no one really knows how the whole system works at a high level, or the person who did doesn't work at the company anymore. But I don't think using a profiler can't really hinder development; rather, it provides useful information, and it's up to us to use that information in an intelligent manner. - Oliver > But I don't think using a profiler can't really hinder development; rather, it > provides useful information, and it's up to us to use that information in an > intelligent manner. I totally agree. That's an observation that applies to so many other contexts. We can never "switch off" our brain, even while we're carrying out highly technical work (which may give the impression to outsiders that our brain is in top gear all the time, when in fact the opposite would be true). Always remain critical, and be prepared to review the evidence before you. That's part of the critical thinking philosophy (http://en.wikipedia.org/wiki/Critical_thinking). > I'm trying to cut down the time it takes to do the following task. It > currently takes about 25 seconds to do. If anyone has any tips on what > could cut this down considerably, any help much appreciated. > // elements is a hashmap of 10000 shapes containing 7100 Triangles. So we are talking 7100/25 = 284 triangles/second. Guess at a one and a bit GHz processor give 4,000,000 cycles/triangle. > for (int j = 0; j < 3; j++) { > // here I allocate a data structure using new for each triangle > edge > // has 4 set() methods to newly allocated data structure > } I reckon on around 40 cycles per short object allocation. (Exact number is going to vary quite a bit. Particularly if some objects have intermediate lifetimes.) So assuming 3 simple objects and an array, one or two hundred cycles shouldn't be a problem. If allocation really is a problem you might like to try setting -Xms to stop garbage collections that only happen to stop increasing in memory usage. (for instance, java -Xms64m -Xmx64m MyProg). > I'm thinking the problem might be in the for statement using j where I > allocate a new data structure (class) for each edge of my triangle. Is > allocating a new object the slowest statement in this code? It's rather difficult to tell without you showing more code. Try cutting bits out and see if it goes significantly faster. My guess is that you've got some loop in there you are not showing us. Perhaps List.contains. I don't know. Tom Hawtin SignatureUnemployed English Java programmer http://jroller.com/page/tackline/ > Is >allocating a new object the slowest statement in this code? We can't tell unless you post real code, preferably an SSCCE see http://mindprod.com/jgloss/sscce.html In the process of creating the SSCCE you might accidentally answer your own question. You can temporarily remove a hunk of code to see if it is the problem. SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Again taking new Java programming contracts. Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.