is allocate really this slow?

[Wizumwalt]

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?

 

[Oliver Wong]

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

 

[Wizumwalt]

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));

 

[Thomas Hawtin]

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

 

[Chris Smith]

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.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Oliver Wong]

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

 

[Roedy Green]

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.

 

[Roedy Green]

If you can't get hold of a profiler

see http://mindprod.com/jgloss/profiler.html

 

[jan V]

I'm thinking the problem might be in the for statement using j where I

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.

 

[Oliver Wong]

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.

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

 

[Chris Uppal]

[...] 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

 

[Hemal Pandya]

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.

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?

 

[Jan V.]

Don't guess, profile.

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?

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.

 

[Oliver Wong]

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?

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

 

[jan V]

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).