Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A neat XOR trick

mattkeeter.com

Post reply on HN
Print view View original

31–40 of 181 posts

Re: A neat XOR trick

#31

Post by DannyBee »

moloch-hai wrote: post #17

The moral is that POPCNT is critical to zillions of massive optimizations, and omitting it from base instruction sets, as has been done over and over and then later corrected, each time at great expense, is extremely foolish. The latest offender was RISC-V, but the overwhelming majority of x86 code is still compiled to a target version lacking it.

Well, actually, in this case, no, POPCNT is unnecessary here, since you don't actually have to count anything. you only need to know if the bitmask changed when you added a new character ;)

But otherwise, yes.

I spent quite a while optimizing GCC's bitmap operations years ago, including implementing some new sparse bitmap types, and the sparse bitmap types i implemented ended up dependent on the speed of popcnt and friends, so yes.

Re: A neat XOR trick

#32

Post by fifilura »

I think my intuition tells me that this is analogous to the convolutions you do in neural network image processing. Just that this is one dimensional.

Re: A neat XOR trick

#33

Post by gpderetta »

moloch-hai wrote: post #17

The moral is that POPCNT is critical to zillions of massive optimizations, and omitting it from base instruction sets, as has been done over and over and then later corrected, each time at great expense, is extremely foolish. The latest offender was RISC-V, but the overwhelming majority of x86 code is still compiled to a target version lacking it.

legend say that popcnt was the "NSA" instruction, was heavily used for cryptographic analysis and that was kept out of common instruction sets for a long time to give NSA an advantage.

It is probably just a legend though.

Re: A neat XOR trick

#34

Post by eru »

piersj225 wrote: post #27

You can also swap two variables without using a temp variable thanks to XOR https://stackoverflow.com/a/19618810

A note of caution: using that trick on modern hardware and/or languages is likely to be slower than just using the temporary variable. Because compilers and processors can see through the latter better than the XOR.

Re: A neat XOR trick

#35

Post by mihaic »

Am I the only one bothered that he didn't first optimize the HashSet solution to O(N)? When sliding the window, you increase the counter for the new element, decrease the counter for leaving element, and update for each element how many have their counter set to 1.

That makes a bit weaker the case for using popcount, since that actually is O(W/Wordsize), which happens to be O(1) in this case.

Re: A neat XOR trick

#36

Post by rep_lodsb »

piersj225 wrote: post #27

You can also swap two variables without using a temp variable thanks to XOR https://stackoverflow.com/a/19618810

Unless they are the same memory location!

http://underhanded-c.org/_page_id_16.html

x86 CPUs have a dedicated instruction to swap two registers, or a register with memory.

Re: A neat XOR trick

#37

Post by DannyBee »

mihaic wrote: post #35

Am I the only one bothered that he didn't first optimize the HashSet solution to O(N)? When sliding the window, you increase the counter for the new element, decrease the counter for leaving element, and update for each element how many have their counter set to 1. That makes a bit weaker the case for using popcount, since that actually is O(W/Wordsize), which happens to be O(1) in this case.

You don't even have to do this.

If HashSet.insert ever returns false, the character was already in the set, and the window is not unique, so you can early exit and move on. If you get through the window without insert returning false, it is unique. You don't need to do anything else (like check the length of the hash set at the end)

Re: A neat XOR trick

#38

Post by kadoban »

ladberg wrote: post #14
xnorswap wrote: post #2

I had considered this approach but the nature of AoC means it rewards real world time to solution rather than and kind of computation time, and a naive solution still runs fast enough that it more than makes up in time spent programming it. There's actually whole classes of problems which would be more interesting if the naive solution wasn't fast enough, for example even on day 7 (or was it 8?) naively exploring to…

If you aren't already familiar with it, you might find projecteuler.net fun!

codeforces.com or one of those is slightly more likely to be fun for programmers.

projecteuler.net is great, but it _very_ quickly becomes deep math.

Re: A neat XOR trick

#39

Post by nebulous1 »

DannyBee wrote: post #31
moloch-hai wrote: post #17

The moral is that POPCNT is critical to zillions of massive optimizations, and omitting it from base instruction sets, as has been done over and over and then later corrected, each time at great expense, is extremely foolish. The latest offender was RISC-V, but the overwhelming majority of x86 code is still compiled to a target version lacking it.

Well, actually, in this case, no, POPCNT is unnecessary here, since you don't actually have to count anything. you only need to know if the bitmask changed when you added a new character ;) But otherwise, yes. I spent quite a while optimizing GCC's bitmap operations years ago, including implementing some new sparse bitmap types, and the sparse bitmap types i implemented ended up dependent on the speed of popcnt and f…

it's not sufficient that the newest character in the window is unique? the older characters need to be unique too.

Re: A neat XOR trick

#40

Post by rep_lodsb »

DannyBee wrote: post #26

You don't need to count ones at all, because you can stop looking at a window as soon as you discover it's not unique. As a result, you only have to detect if the bitmask is changed from adding a new character, not how many one bits there are in it. (This is true in the hash-set version as well - if insert returned false you can move on). old bit mask = current bit mask current bit mask = current bit mask OR new char…

OR wouldn't work with a sliding window since it can't be inverted?

This should work:

  init bit mask and count of bits to 0
  for each new char:
    old = bit mask
    bit mask = bit mask XOR old char
    if bitmask > old then count++ else count--
    old = bit mask
    bit mask = bit mask XOR new char
    if bitmask > old then count++ else count--
    if count == window length: return match
The idea is that each XOR will always set or clear exactly one bit, so we can maintain a count of set bits.

But if there is a POPCNT instruction it would probably be faster to use it.

Post reply on HN