Live data from Hacker News

A neat XOR trick

mattkeeter.com

121–130 of 181 posts

Re: A neat XOR trick

#121
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.

Thank you. I was wondering the same thing and I think the article is overfocusing on "cool bit tricks" while this simple approach works just fine.

Without the cool bit trick, would it be worth publishing the article at all? I found it a novel approach to explore.

Re: A neat XOR trick

#122
This seems a bit overcomplicated to me.

Using a bitmap to track letters you've seen is a great idea. But the parity and counting gives me a headache. How about you start with a zero-size window at the start of the string, then iteratively try to grow it by moving the end forward until it's long enough, and if the character added would be a duplicate, moving the start forward until it's no longer a duplicate? Sort of inchworm-style movement.

I am not smart enough to write Rust, so here it is in Java:

    private static int run(String input, int windowSize) {
        int windowStart = 0; // start at the start
        int windowEnd = 0; // the window is initially zero-size
        int lettersSeen = 0; // a bitmap of letters we have seen

        while (windowEnd - windowStart = input.length()) throw new IllegalArgumentException("No unique window found");
            int letterToAdd = 1 
This is not quite optimal in terms of bit operations - i mask the bitmap in the inner loop condition, but you could just test letterToRemove against letterToAdd and break if they're the same. I think that's a bit less readable though.

Note that although this has two nested loops, they don't both independently range over the whole string, so this is not O(n^2). The outer loop moves windowEnd over the whole string, and the inner one moves windowStart over the whole string bit by bit. Each index visits each position in the string at most once.

Re: A neat XOR trick

#123

I've seen this use of constants inside big O notation in leetcode and 'informal' discussions. Is it pedantic to say that O(NM) == O(N) if M is a constant (in this case since it's bound by 26)? Or is this the current and expected usage?

It's correct to omit constants from big O, but in the article W is a distinct input variable so the usage is valid. The size of the window W is bound by N, not a constant 26.

Re: A neat XOR trick

#124

Earlier quoted context omitted.

>One issue with this technique is when the set of characters grow above 64, so you can no longer give each one a unique bit. You can xor arrays of integers.

Right, but if the universe of possible characters grow much larger than the window size (as it does in many applications), we want a method that only pays in terms of window size, not universe size.

So you use a sparse bitmap, ie a hash set. The size of the hash set is bounded to the size of the window, so this should be pretty efficient.

If you have a huge string, a huge alphabet, and also a huge window, then probabilistic techniques start to make sense. But let's not run while we can successfully walk!

Re: A neat XOR trick

#125
On a related note, almost any task around shuffling or shifting bits can be improved with xor. For example the straightforward way to remove bit i is

    mask = -1 > 1) & mask);
but with xor we can do it in one less instruction:

    mask = -1 > 1)) & mask) ^ x;

Re: A neat XOR trick

#126

Earlier quoted context omitted.

Sure, but now do 11 at a time with a similar algorithm (which was part 2 of the problem).

I've just submitted in order to see the second part, which just says "now look for 14 unique". I dont see the problem here, if you want a notation to express it, a macro for something like, 0 != 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 1 != 0, 2, 3, 4, 5, 6, 7, ... is straightforward, and could be parameterised on the window size.

That's fine, but it's O(n) in the window size whereas the xor trick is O(1).

Re: A neat XOR trick

#127

Earlier quoted context omitted.

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 exactl…

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.

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.

Re: A neat XOR trick

#128

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…

In practice if you want the popcount of anything larger than a couple registers you'll want to use vector instructions anyways though. There are a lot of operations that will speed up certain applications if made into their own instruction, not all of them need to be.

Re: A neat XOR trick

#129

Earlier quoted context omitted.

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.

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…

> 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

Re: A neat XOR trick

#130

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.

The usefulness of popcnt, et al, in cryptography was known at least as far back as Alan Turing. It wasn't 'kept out of' ISAs, if for no other reason than not all computer manufacturers were (are) American, so the NSA wouldn't have had much leverage to keep, say, Ferranti or Hitachi from including it in their computers.

The legend you're probably misremembering is the one where the NSA approached Seymor Cray at CDC while he was designing the 6600 super and 'suggested' that if he included a popcnt instruction in the ISA, the NSA would certainly look favorably on purchasing some. He did and they did (quite a few). This story is also possibly apocryphal.

Post reply on HN