Win a copy of Functional Reactive Programming this week in the Other Languages forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Which would be better?

 
Chris Davis
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Which of these two examples would be faster/most efficient?





My thought is the first because I don't have to update an int value to do the compare, but I'm not sure if there is any additional overhead from comparing the value directly from the array or not?

Thanks,
Chris
 
Vlado Zajac
Ranch Hand
Posts: 245
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't think the difference is significant. And it depends on platform, compiler and JVM.
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I fully agree with Vlado.

I'd probably go with the second example, move the declaration of intValue into the loop and give it a more expressive name. If only because it reduces duplication...
 
David Harkness
Ranch Hand
Posts: 1646
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Chris Davis:
Which of these two examples would be faster/most efficient?

The first example will likely do bounds checking on the array multiple times (for the 2 and 3 cases). However, JVMs and JITs are getting better at optimization and could see that since i doesn't change in the loop, it could create its own temporary variable. Using the second example forces this, though.

For if-else-if constructs like that, use switch instead.

I don't know about Java, but C compilers turn switches into an indexed jump table. The array will be accessed once, and a lookup is done to find the case block to run rather than multiple comparisons.

At this point, however, you're optimizing for the tiniest of gains. You can make far more progress by looking at the algorithm as a whole and the design of your system. Shaving a millisecond here or there won't have nearly as great an effect as using a HashMap versus walking a List in a loop (general example).
 
Chris Davis
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the quick/descriptive replies.

The actual code this is in reference to uses an array of objects that I've created (Will hold around 25,000 of them in extreme cases, which is why I'm concerned about performance) and will need to compare an int value in each object. (I was a little lazy with my example I guess, sorry). I just want to confirm that there isn't really any performance decrease in referencing the object and the int within it directly from the array instead of creating a new object to hold the one in the array.

Thanks again,
Chris
[ August 24, 2004: Message edited by: Chris Davis ]
 
David Harkness
Ranch Hand
Posts: 1646
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Chris Davis:
I just want to confirm that there isn't really any performance decrease in referencing the object and the int within it directly from the array instead of creating a new object to hold the one in the array.

The difference is if you access the same array element multiple times. Every array element access involves bounds checking. This is minor, but in a tight loop across 25,000 elements, if you do many tests (versus just three) the differences will start to add up.

As for what I said about your algorithm, lets say that instead of comparing each element against three possible values you are actually comparing it against 100 values. In this case I would recommend switching the comparison to a lookup from a Map using Integers rather than ints. Using a TreeMap, for instance, would involve at most 6 comparisons to find the correct value [lookup is O(log n)].
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
a) a switch should be faster than a TreeMap - not only in c, but in java too.
b) Bounds-checking could be eliminated by an optimizer.
c) 25000 different cases?
d) Write a test.

I wrote a benchmark-wrapper, to compare code-snipplets (more for fun), but for 3 cases, calling them 100,000 times or 1,000,000 times makes no big difference - the surrounding code consumes most of the time, or the optimizer made a big job. (I compare 2 possibilities with 2 jvm's (1.4.2, 1.5.0-beta2) and two options (java Test/ java -server Test).
And of course I don't have much joy in generating 25,000 cases.

But as soon as some real work is done in the innermost brackets, your question becomes meaningless.

A very raw calculation: The selection of the right statement is done 3,000,000 times in 0.1 sec.
If a faster solution would lead to 6,000,000 times in 0.1 sec, it would look great for first view.
But if the real work for 3,000,000 times would take 10 sec., the difference would be 10.1 to 10.2 sec. for 3,000,000 times.

All together now: "Premature optimization is the root of all evil" (D. Knuth)
[ August 24, 2004: Message edited by: Stefan Wagner ]
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Chris Davis:
The actual code this is in reference to uses an array of objects that I've created (Will hold around 25,000 of them in extreme cases, which is why I'm concerned about performance) and will need to compare an int value in each object.


I understand your concern, but to be an effective developer, you need to overcome it. That is, don't ignore it, but nevertheless *first* implement a solution optimized for code maintenance. *Then* allow yourself to be concerned and *try* wether it's fast enough. If you find that it isn't, use a profiler to find the bottleneck (it likely isn't the array access) and optimize it away.

Hope this helps...
 
Chris Davis
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks guys.

Stefan, do you have an example of what you mean by "Bounds-checking could be eliminated by an optimizer"?

Thanks for your time and effort in looking into this. I thought I might be concerned about nothing, but wanted to be sure.

-Chris
[ August 25, 2004: Message edited by: Chris Davis ]
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No - I don't have a reference.
I read it somewhere - but where?

But look at the code:

If the array isn't changed inside the for-loop, we can see both, that no bounds-violation will occour.
And so should a good compiler

I have seen suggestions, to write a for-loop this way:

to evaluate the length only once, but even this is - so am I told - optimized away in the original code, which is a bit more readable.

Own measurements didn't show a difference in such loops.
[ August 26, 2004: Message edited by: Stefan Wagner ]
 
Adeel Ansari
Ranch Hand
Posts: 2874
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
could we sort all the elements of the array, using quick sort algo. then perform the binary search.

just a suggestion for a better performance, isn't it?
 
Rahul Juneja
Ranch Hand
Posts: 425
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Second will be faster

Array lookup may impact the performance.

While 1st will be efficient as it will take less memory.

Thanks,
Rahul Juneja
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Rahul Juneja:
Second will be faster


How do you know - have you tried it?

Seriously, I don't think this statement makes sense without even adding which JVM you use...


Array lookup may impact the performance.


Or it may not...


While 1st will be efficient as it will take less memory.


Possibly - though perhaps not. The local variable might be use an otherwise unused processor register, for example. That wouldn't cost any memory at all.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic