5 ms·

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

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 character if old bit mask == current bit mask window is not unique, move to the next window (otherwise window is so far unique)

rep_lodsb 4y ago
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.
- DannyBee 4y ago
  My guess is, it’s still faster to just check whether hashset.insert returns false. Since most windows are not unique early exit will likely beat faster processing.
  - dahfizz 4y ago
    I doubt the hashmap would beat the XOR method from the article. Hashmaps means allocations, and it means hashing. Hashing is going to be at least as much work as XORing a couple values in the mask. Hashmaps also means chasing pointers all over memory and ruining your cache. You can add an early return to the OPs XOR method by just checking if the char is already in the bit mask. This will be faster if the word size is large.
    - DannyBee 4y ago
      the domain/range is fixed, so you don't have to allocate, actually, because you can have a fixed sized table and perfect hash :) That said, I agree you can make the bit munging faster in the end, i'm just saying i don't think the speed up is anywhere near the improvement from early-exiting.
      - rep_lodsb 4y ago
        Even if the hashmap library knew that the only valid keys were 'a' .. 'z', it wouldn't be magically faster. The best it could do is use basically the same code as a hand-rolled implementation. Bit operations and shifts take a single clock cycle, and the mask can be stored in a register throughout the entire loop. If "early exit" brings any improvement, I don't see why the best wouldn't be to combine the two solutions instead of choosing one or the other.
        dahfizz 4y ago
        > Even if the hashmap library knew that the only valid keys were 'a' .. 'z', it wouldn't be magically faster. The best it could do is use basically the same code as a hand-rolled implementation. This is known as a perfect hash[1]. knowing that you will never have collisions does allow for a faster implementation. The hash map can be backed by an array which will never need to be resized, and you don't have to fiddle with linked lists to chain collisions. You're correct though, that this is something you will have to implement yourself. Library hashmaps are going to trade performance for general usefulness. [1] https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function
  - gpderetta 4y ago
    For small windows it is possible that an early exit might be counterproductive as it exercises the branch predictor. One would have to test ti see where the cutoff is, but often doing extra work is faster. Edit: but this is discussed elsethread. A fixed size run also helps with vectorization.
- meindnoch 4y ago
  You can combine the two XORs: new_mask = old_mask XOR old_char XOR new_char count += signum(new_mask - old_mask) Where signum(x) = (x > 0) - (x < 0)
  - rep_lodsb 4y ago
    If the old and new char are different, two bits will have changed state and comparing the old and new mask will have unreliable results. e.g. old mask = 011100 new mask = 001111, numerically less even though it has one more bit set
    - meindnoch 4y ago
      Dangit! I concede…
meindnoch 4y ago
And how do you remove the character leaving the window on the left? I don’t think this solution works the way you think it does…
- DannyBee 4y ago
  Yes, I wrote it too quickly you would have to xor characters in and out instead. I doubt it is worth it vs popcnt at that point It doesn’t change the fact that problem is incremental, and most importantly you can early exit windows as soon as you discover a single non-unique character. You don't have to wait till the end of the window. They don’t implement this for hash set, for example. Since most (n>1) windows are not unique (well, more accurately the probability of the window being unique decreases as the size of the window approaches the number of possible characters), early exit from windows will likely beat bit munging except for small windows, until you get into SIMD solutions.
  - rep_lodsb 4y ago
    Bit operations are fast, branches are slow.
    - DannyBee 4y ago
      Well, yes, but most of these branches can be if-converted into conditional moves anyway if you want. So they are data dependencies and not control ones. There are still some control ones. Beyond that, let me be super clear: Imagine the following six versions: 1. One window at a time processing. No early exit, no bit munging. 2. One window at a time processing. No early exit, bit munging. 3. One window at a time processing. You don't use direct bit munging, but you early exit the window when you hit the non-unique character, and skip the window forward to the first instance of that non-unique character. IE given "hmma<something>", n=4, you early exit at the second m, and skip processing windows forward to right after the first m (since no window prior to that can be unique, as they will all hit the double m) 4. One window at a time processing, bit munging, same otherwise as #3 5. Sliding window processing, no bit munging 6. Sliding window processing, bit munging. The speedup between the 1-2 vs 3-6 is much greater than 5 vs 6 and 3 vs 4. You could probably make 3 pretty darn competitive with 6, and 4 could probably beat 6 with SIMD (IE processing multiple windows in parallel really fast, and maybe wasting work, vs guaranteeing you only do the minimum work to find a unique window)

rep_lodsb 4y ago

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.

DannyBee 4y ago
My guess is, it’s still faster to just check whether hashset.insert returns false. Since most windows are not unique early exit will likely beat faster processing.
- dahfizz 4y ago
  I doubt the hashmap would beat the XOR method from the article. Hashmaps means allocations, and it means hashing. Hashing is going to be at least as much work as XORing a couple values in the mask. Hashmaps also means chasing pointers all over memory and ruining your cache. You can add an early return to the OPs XOR method by just checking if the char is already in the bit mask. This will be faster if the word size is large.
  - DannyBee 4y ago
    the domain/range is fixed, so you don't have to allocate, actually, because you can have a fixed sized table and perfect hash :) That said, I agree you can make the bit munging faster in the end, i'm just saying i don't think the speed up is anywhere near the improvement from early-exiting.
    - rep_lodsb 4y ago
      Even if the hashmap library knew that the only valid keys were 'a' .. 'z', it wouldn't be magically faster. The best it could do is use basically the same code as a hand-rolled implementation. Bit operations and shifts take a single clock cycle, and the mask can be stored in a register throughout the entire loop. If "early exit" brings any improvement, I don't see why the best wouldn't be to combine the two solutions instead of choosing one or the other.
      - dahfizz 4y ago
        > Even if the hashmap library knew that the only valid keys were 'a' .. 'z', it wouldn't be magically faster. The best it could do is use basically the same code as a hand-rolled implementation. This is known as a perfect hash[1]. knowing that you will never have collisions does allow for a faster implementation. The hash map can be backed by an array which will never need to be resized, and you don't have to fiddle with linked lists to chain collisions. You're correct though, that this is something you will have to implement yourself. Library hashmaps are going to trade performance for general usefulness. [1] https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function
- gpderetta 4y ago
  For small windows it is possible that an early exit might be counterproductive as it exercises the branch predictor. One would have to test ti see where the cutoff is, but often doing extra work is faster. Edit: but this is discussed elsethread. A fixed size run also helps with vectorization.
meindnoch 4y ago
You can combine the two XORs: new_mask = old_mask XOR old_char XOR new_char count += signum(new_mask - old_mask) Where signum(x) = (x > 0) - (x < 0)
- rep_lodsb 4y ago
  If the old and new char are different, two bits will have changed state and comparing the old and new mask will have unreliable results. e.g. old mask = 011100 new mask = 001111, numerically less even though it has one more bit set
  - meindnoch 4y ago
    Dangit! I concede…

meindnoch 4y ago

And how do you remove the character leaving the window on the left? I don’t think this solution works the way you think it does…

DannyBee 4y ago
Yes, I wrote it too quickly you would have to xor characters in and out instead. I doubt it is worth it vs popcnt at that point It doesn’t change the fact that problem is incremental, and most importantly you can early exit windows as soon as you discover a single non-unique character. You don't have to wait till the end of the window. They don’t implement this for hash set, for example. Since most (n>1) windows are not unique (well, more accurately the probability of the window being unique decreases as the size of the window approaches the number of possible characters), early exit from windows will likely beat bit munging except for small windows, until you get into SIMD solutions.
- rep_lodsb 4y ago
  Bit operations are fast, branches are slow.
  - DannyBee 4y ago
    Well, yes, but most of these branches can be if-converted into conditional moves anyway if you want. So they are data dependencies and not control ones. There are still some control ones. Beyond that, let me be super clear: Imagine the following six versions: 1. One window at a time processing. No early exit, no bit munging. 2. One window at a time processing. No early exit, bit munging. 3. One window at a time processing. You don't use direct bit munging, but you early exit the window when you hit the non-unique character, and skip the window forward to the first instance of that non-unique character. IE given "hmma<something>", n=4, you early exit at the second m, and skip processing windows forward to right after the first m (since no window prior to that can be unique, as they will all hit the double m) 4. One window at a time processing, bit munging, same otherwise as #3 5. Sliding window processing, no bit munging 6. Sliding window processing, bit munging. The speedup between the 1-2 vs 3-6 is much greater than 5 vs 6 and 3 vs 4. You could probably make 3 pretty darn competitive with 6, and 4 could probably beat 6 with SIMD (IE processing multiple windows in parallel really fast, and maybe wasting work, vs guaranteeing you only do the minimum work to find a unique window)