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

171–180 of 181 posts

Re: A neat XOR trick

#171

Post by thomasahle »

bsza wrote: post #169
thomasahle wrote: post #163

Earlier quoted context omitted.

Perhaps we are both right. I usually think of the Word RAM Model in which W is assumed to be at least logn. See https://en.m.wikipedia.org/wiki/Word_RAM#Model This is a nice model because you don't have to assume things like "infinite pointer sizes", and because the algorithms that work well in practice (such as using bit tricks) also work well in the theory. If you don't work in the word ram model you also wouldn't…

We're still at O(N * W) time. It might be possible to implement xor using only +, - and bit shifts (though I'm not seeing any obvious way to do so), but count_ones stays a bottleneck; I'm pretty sure you can't do that in O(1) even on a word RAM machine. Not to mention, a machine where addition takes O(1) time is a massive cheat - at least definitely not what most people have in mind when talking about computational c…

> but count_ones stays a bottleneck; I'm pretty sure you can't do that in O(1) even on a word RAM machine

It's actually easy to do logn bit operations in O(1) time on the kind of machine you are talking about too. Just make a table with the result of all (lg n)/2 bit inputs. Such a table only takes sqrt(n) memory and time to create, and since you seem to accept O(1) table lookups you now have count_ones in two lookups.

Similarly it's easy to make small tables that allow you to do arbitrary binary operations on (lg n)/4 bit strings.

> at least definitely not what most people have in mind when talking about computational complexity.

I'm pretty sure if you look in CLRS or any standard text book of algorithms, they allow lgn bit operations in constant time. Every heard people saying "Sorting takes O(n logn) time"? They are clearly assuming comparing two numbers can be done in constant time.

Also look at any lecture notes from actual CS researchers, like this: http://www.cs.cmu.edu/~odonnell/toolkit13/Lecture05.pdf

> Doesn’t that imply that we need w ≥ log n?

> Answer: Yes! And that’s a standard assumption! The first time you see this it may seem totally weird: you’re assuming the computer hardware size depends on the input size?! That seems to make no sense. But once you calm down, it’s actually quite logical and cool. Of course you want a single pointer to fit into a word. You should just think of w as a parameter of the model, and w ≥ log n as an assumption.

Re: A neat XOR trick

#172

Post by MaxBarraclough »

mangamadaiyan wrote: post #139
jhoechtl wrote: post #20

> There's no moral to the story, other than "xor is cool" The moral is knowledge is king and no matter how much iron you throw at a problem a well-designed algorithm will beat it.

Cache misses, TLB flushes, and pipeline stalls would beg to differ with you.

Not really, no. For plenty of problems, the most efficient known algorithms will easily outperform a naive algorithm, even if running on drastically inferior hardware. 'Drastically' in this context can mean the slower approach taking billions of times longer.

Wikipedia gives an example. [0] Many courses on algorithms and/or complexity theory emphasise such examples in their introductions.

That said I don't know why jhoechtl thought that was the moral of this blog post, which doesn't illustrate that point at all.

[0] https://en.wikipedia.org/wiki/Computational_complexity#Use_i...

Re: A neat XOR trick

#173

Post by kjs3 »

_a_a_a_ wrote: post #142
kjs3 wrote: post #130

Earlier quoted context omitted.

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

> The usefulness of popcnt, et al, in cryptography was known at least as far back as Alan Turing Ok. Why?????????????? @gpderetta is correct at least in quoting hacker's delight where it was also said to be rumoured the NSA wanted popcount but it was unclear to HD's author why they wanted it.

Why??????????????

It accelerates the calculation of the Hamming weight of a vector or string. Hamming weight is useful lots of places in crypto, like helping frequency analysis, or observed power consumption attacks against crypto systems. It's useful in many other disciplines as well.

Re: A neat XOR trick

#174

Post by mangamadaiyan »

MaxBarraclough wrote: post #172
mangamadaiyan wrote: post #139

Earlier quoted context omitted.

Cache misses, TLB flushes, and pipeline stalls would beg to differ with you.

Not really, no. For plenty of problems, the most efficient known algorithms will easily outperform a naive algorithm, even if running on drastically inferior hardware. 'Drastically' in this context can mean the slower approach taking billions of times longer. Wikipedia gives an example. [0] Many courses on algorithms and/or complexity theory emphasise such examples in their introductions. That said I don't know why j…

Mea culpa.

All I was trying to say is that beyond a point, it's not _just_ the algorithm, you need to pay attention to mechanical sympathy.

Do well-designed algorithms outperform naive algorithms? Almost always. Is designing the algorithm well sufficient? I'd think not.

Re: A neat XOR trick

#175

Post by bsza »

thomasahle wrote: post #171
bsza wrote: post #169

Earlier quoted context omitted.

We're still at O(N * W) time. It might be possible to implement xor using only +, - and bit shifts (though I'm not seeing any obvious way to do so), but count_ones stays a bottleneck; I'm pretty sure you can't do that in O(1) even on a word RAM machine. Not to mention, a machine where addition takes O(1) time is a massive cheat - at least definitely not what most people have in mind when talking about computational c…

> but count_ones stays a bottleneck; I'm pretty sure you can't do that in O(1) even on a word RAM machine It's actually easy to do logn bit operations in O(1) time on the kind of machine you are talking about too. Just make a table with the result of all (lg n)/2 bit inputs. Such a table only takes sqrt(n) memory and time to create, and since you seem to accept O(1) table lookups you now have count_ones in two lookup…

> Every heard people saying "Sorting takes O(n logn) time"? They are clearly assuming comparing two numbers can be done in constant time.

Where n is the number of items. Not the number of digits! And we don't normally talk about "time" when discussing sorting algorithms in the first place. We talk about number of comparisons (precisely because we have no clue how big the items are!).

> Just make a table with the result of all (lg n)/2 bit inputs

We're interested in the number of ones in a C-bit integer, where C is the size of the character set (and incidentally the maximum acceptable value of the window size W). Simply counting the ones bit by bit costs O(C) time. Making a lookup table for all (C/2)-bit numbers - as you seem to suggest - costs O(2^(C/2)) time and space. And the algorithm we wanted to improve runs in O(N * C) time.

Look, I'm trying to decipher what your point is, but you seem to be confusing the size of the input space with the size of the input. So AFAIC, this is as much attention as this algorithm deserves. It's a nice party trick, but nothing more.

Re: A neat XOR trick

#176

Post by thomasahle »

bsza wrote: post #175
thomasahle wrote: post #171

Earlier quoted context omitted.

> but count_ones stays a bottleneck; I'm pretty sure you can't do that in O(1) even on a word RAM machine It's actually easy to do logn bit operations in O(1) time on the kind of machine you are talking about too. Just make a table with the result of all (lg n)/2 bit inputs. Such a table only takes sqrt(n) memory and time to create, and since you seem to accept O(1) table lookups you now have count_ones in two lookup…

> Every heard people saying "Sorting takes O(n logn) time"? They are clearly assuming comparing two numbers can be done in constant time. Where n is the number of items . Not the number of digits! And we don't normally talk about "time" when discussing sorting algorithms in the first place. We talk about number of comparisons (precisely because we have no clue how big the items are!). > Just make a table with the res…

> And we don't normally talk about "time" when discussing sorting algorithms

Sure you might be a purist and talk about comparisons, but I'm pretty sure if you Google it most people would talk about time. And "n logn" is exactly the amount of time it takes to sort n word-length integers in Word RAM.

> We're interested in the number of ones in a C-bit integer

You're not really engaging with the point that you can make a table in sqrt(n) time that allows counting the bits in logn bit strings in constant time. That means the final algorthm runs in O(NC/logN) time.

This is definitely not a party trick, as you would know if you've ever written a program using these methods. Now with AVX instructions it's more important than ever.

You also didn't engage with O'Donnells lecture notes. I can find you many more text books explaining why this is the right assumption to make, in case you don't like the reasons I've given above.

Re: A neat XOR trick

#177

Post by snvzz »

moloch-hai wrote: post #147
snvzz wrote: post #55

Earlier quoted context omitted.

>RISC-V Doesn't B have a POPCNT? B is mandatory in RVA22.

Can you buy any RISC-V embodiment that implements such an instruction? It seems to be extremely optional.

It is part of B extension, so it should be available in the VisionFive2 (now being shipped), which has the newer version of SiFive U74 that has B.

Re: A neat XOR trick

#178

Post by snvzz »

Vt71fcAqt7 wrote: post #152
moloch-hai wrote: post #147

Earlier quoted context omitted.

Can you buy any RISC-V embodiment that implements such an instruction? It seems to be extremely optional.

B is pretty recent, but Sifive p650 will have it https://www.sifive.com/cores/performance-p650 Heres another: https://www.andestech.com/en/2022/12/08/andes-technology-unv... I expect all future Linux cores to have it

>I expect all future Linux cores to have it

All RVA22 profile cores will, as RVA22 requires B extension.

>Sifive p650 will have it

Current versions of U74 also have it. And a U74 with B is already shipping in VisionFive 2.

Re: A neat XOR trick

#179

Post by remram »

thomasahle wrote: post #109
at_compile_time wrote: post #102

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.

In that case, you might still want to use a similar trick as a first pass (like a bloom filter), and go over the window that is potentially unique again with the HashSet. This should still be faster than using the HashSet for all windows.

https://en.wikipedia.org/wiki/Bloom_filter

Re: A neat XOR trick

#180

Post by CRConrad »

MaxBarraclough wrote: post #172
mangamadaiyan wrote: post #139

Earlier quoted context omitted.

Cache misses, TLB flushes, and pipeline stalls would beg to differ with you.

Not really, no. For plenty of problems, the most efficient known algorithms will easily outperform a naive algorithm, even if running on drastically inferior hardware. 'Drastically' in this context can mean the slower approach taking billions of times longer. Wikipedia gives an example. [0] Many courses on algorithms and/or complexity theory emphasise such examples in their introductions. That said I don't know why j…

> 'Drastically' in this context can mean the slower approach taking billions of times longer.

Standupmaths - "Someone improved my code by 40,832,277,770%": https://www.youtube.com/watch?v=c33AZBnRHks (OK, 41 billion percent is only 0.41 billion times better, but still.)

Post reply on HN