This week's book giveaway is in the Server-Side JavaScript and NodeJS forum.
We're giving away four copies of Node.js Design Patterns: Design and implement production-grade Node.js applications using proven patterns and techniques and have Mario Casciaro & Luciano Mammino on-line!
See this thread for details.
Win a copy of Node.js Design Patterns: Design and implement production-grade Node.js applications using proven patterns and techniques this week in the Server-Side JavaScript and NodeJS forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

Yay or Nay: Counter in For-each Loop

 
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote: . . . because it only works for even/odd. . . .

No it works for any j which can be defined exactly by 2ⁿ − 1 where n is any non‑negative integer smaller than the number of bits in the two's complement number i.
(i & j) == 0
You can test for divisibility by 1, 2, 4, 8, 16, …
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The & operator gives slightly faster execution but it is very restricted in its right operand, as I showed a few minutes ago. It also has the interesting feature that it never returns a negative result, so you can use it to find an array index.
 
Saloon Keeper
Posts: 13282
292
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:No it works for any j which can be defined exactly by 2ⁿ − 1 where n is any non‑negative integer smaller than the number of bits in the two's complement number i.



I considered mentioning that, but I was too lazy

Regardless, I would argue that the remainder after division is an inherent trait of integers, and so (i % 2 == 0) will *always* yield whether i is even, whereas (i & 1 == 0) depends on the system's underlying representation of integers. I don't think the minimal speed improvement is worth breaking the Priciple of Least Astonishment
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Whether you are astonished depends mainly on whether you have used it before. The problem is not that people use it to find even numbers, but that they use
i % j == 1
to find odd numbers and that is when things go wrong because 50% of odd i will produce −1 from that expression. If you have == 0 or != 0 you are on safe grounds again.
The reason HashMap uses & i internally is that it never returns a negative result so there is no risk of an out of bounds Exception. It constrains the implementation always to double the size of the backing array when resizing is required.
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The only integer representation I have heard about where (i & 1) == 1 doesn't work is one's complement.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Regardless, I would argue that the remainder after division is an inherent trait of integers, and so (i % 2 == 0) will *always* yield whether i is even, whereas (i & 1 == 0) depends on the system's underlying representation of integers. I don't think the minimal speed improvement is worth breaking the Priciple of Least Astonishment


I'll chime in with Campbell here. Is:
(i & 1) == 1
really less complicated than:
Math.abs(i % 2) == 1
?

Moreover if, as you rightly suggest, you put the implementation in a well-named method; does it really matter which one you choose, as long as it works?

Winston
 
Stephan van Hulst
Saloon Keeper
Posts: 13282
292
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Alright, I give
 
Master Rancher
Posts: 4035
54
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hm, I would have gone with

At least, before using Math.abs().
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
At least the one value where Math#abs doesn't change the sign is unlikely to be a remainder.
Maybe i % 2 == 0 is optimised to (i & 1) == 0??
 
Mike Simmons
Master Rancher
Posts: 4035
54
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:At least the one value where Math#abs doesn't change the sign is unlikely to be a remainder.


I'm not sure what you mean here, sorry.

Campbell Ritchie wrote:Maybe i % 2 == 0 is optimised to (i & 1) == 0??



Micro-optimization fun ahead...

A quick test on my MacBook suggests this is not the case. The latter is notably faster. I guess it's too specialized a case - they can't replace i % 2 with i & 1 in general, unless they can guarantee that i is non-negative. Or if, as in this case, they're comparing the result with 0.


The code using "(n % 2) != 0" is about three times slower than when I replace it with "(n & 1) != 0". And "(n & 1) == 1" is slightly faster, which surprised me - I would have thought comparison against 0 was faster.

Note that the array is there to ensure that there's a wide range of inputs, but we don't include the time to generate that in the test. So that there shouldn't be any optimization based on the inputs.

This was using Oracle's 1.8.0 JDK, Java HotSpot(TM) 64-Bit Server VM, 25.0-b70, on an elderly MacBook. YMMV.
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Nice bit of detective work
A division (which includes the remainder operation) probably takes 32 clock cycles on a 32‑bit machine, whereas the & operation probably takes 1 clock cycle.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:The code using "(n % 2) != 0" is about three times slower than when I replace it with "(n & 1) != 0". And "(n & 1) == 1" is slightly faster, which surprised me - I would have thought comparison against 0 was faster.


Me too. And to be honest, I'm surprised it's only three times slower; although when you get down to levels like this, it's quite possible that the method call itself (unless the code can be inlined) makes up a hefty part of the overall time.

A while ago I was creating a Bits utility class to do some of the things that this wonderul page reminded me about, and I was staggered at just how much time you can save by avoiding any sort of branching.

Winston
 
Bartender
Posts: 4633
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hmm... don't like stepping in like a thief in the night, but I'm somewhat puzzled.

I've seen (even recently) many topics where the general consensus was:

"don't use optimizations just for the sake of optimizations, clarity of code is much more ... (et cetera)"

or that optimization caused more misery than sheer stupidity, and sayings alike.

Now I see a topic getting off topic, and I see even a link to some very low tricks concerning bit shuffling, to save a
couple of micro seconds.

So, I'm a bit puzzled about the consistency of replies.

Well, just me

Greetz,
Piet
 
Mike Simmons
Master Rancher
Posts: 4035
54
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I had the impression that the general point about premature optimization had already been made. And that the original poster had a satisfactory answer to their question. In light of that, I don't see the harm in some further discussion. The truth is, sometimes these optimizations are actually useful, even though the vast majority of the time, they aren't. In the event a programmer ever looks though JDK source for common library classes, they may see stuff like this. The admonitions of Knuth and others should not be taken as a ban on any further discussion, in my opinion.
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
And there is good reason why that sort of thing is used in classes, which I mentioned (Good grief!) 48 hours ago.
 
Mike Simmons
Master Rancher
Posts: 4035
54
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Going back to "micro-optimization fun ahead"...

Winston Gutkowski wrote:

Mike Simmons wrote:The code using "(n % 2) != 0" is about three times slower than when I replace it with "(n & 1) != 0". And "(n & 1) == 1" is slightly faster, which surprised me - I would have thought comparison against 0 was faster.


Me too. And to be honest, I'm surprised it's only three times slower; although when you get down to levels like this, it's quite possible that the method call itself (unless the code can be inlined) makes up a hefty part of the overall time.


In my test, I did inline the code. Though just now I put it back in a method call, and it only made things a little slower, about 10%. But yeah, in other performance tests, I've definitely seen bigger (negative) effects from extracting code to a separate (and well-named) method. So I tried to keep that out of my test entirely. It's unfortunate, since we all seem to agree that an isOdd() method is the way to go here, from a readability standpoint. But sometimes that sort of thing slows you down too much.

Winston Gutkowski wrote:A while ago I was creating a Bits utility class to do some of the things that this wonderul page reminded me about, and I was staggered at just how much time you can save by avoiding any sort of branching.


Yeah, that's another one. In my test shown above, I can speed things up by a factor of about four, by getting rid of the "if" thus:

The catch is, that only works if your only objective is to count the odd numbers, but not collect them. To collect them, you need an if statement. And, of course, an array or Collection, and calls to add elements to that array or Collection. Which all slows down performance further, and the difference between % and & will probably become negligible again.

In general, performance optimizations like this only make a difference when there's nothing else in the loop. Which happens occasionally. But change the problem statement a little bit, and you get different code with different characteristics.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:Yeah, that's another one. In my test shown above, I can speed things up by a factor of about four, by getting rid of the "if"


Actually, I was thinking more about the actual "result" code itself.

Take the abs() function. There are two basic ways to do it:
n < 0 ? -n : n; (the "obvious" way)
and
(n + (n >> 31)) ^ (n >> 31)
and the second is consistently quicker on my machine than the first (timed over 2^31 calls for both positive and negative numbers) . Not by much, and not every time, but generally. And there are other cases where eliminating conditional checks makes even more of a difference.

And @Piet: You're absolutely right. As Mike says, this is just for fun. However, bit-twiddling definitely does still have its place - just one example being in hash code calculations. I've also created a Group class which can hold an array of up to 32 or 64 objects, using an int or long as a "gate". This makes it very easy to make it Thread-safe with minimal synchronization, and methods like hasElementAt(n) are blisteringly fast, viz:
(contentsMask & (Integer.MIN_VALUE >>> n)) != 0;
and isEmpty()?
contentsMask == 0;

Winston
 
Bartender
Posts: 1810
28
jQuery Netbeans IDE Eclipse IDE Firefox Browser MySQL Database Chrome Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Kat Rollo wrote:We'll most likely go with Java 8 after the release of Java 9, because that's how companies do it he says.


Your prof has a point. I'm upgrading our servers from Java 6 to 7 next week and we're still on servlet 2.5. We'll likely use that for at least a year before we consider going to Java 8. But this, this company stays behind the technology curve in a lot of ways. Just this year we upgraded Office from 2003 to 365.

We even still have a few production machines running DOS with applications written in BASIC. Stop laughing, I have to support this stuff.
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote: . . .
I'm not sure what you mean here, sorry.
. . .

I know it was a long time ago, but I missed that comment. Sorry.

The result of the % operation is always smaller in magnitude than its right operand. So it is impossible to get 0x8000_0000 (=−2147483648) as the result of a remainder operation.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic