6 ms·

> There's not enough info to figure out what's going on. If you only look at the article this is true. However, the source code is freely available: https://gi

> There's not enough info to figure out what's going on. If you only look at the article this is true. However, the source code is freely available: https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/tree/master/2021/01/06 https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/...

deleted 6y ago
[deleted]
africanboy 6y ago
I ran the benchmark on my system It's a 6 years old system, fastest times are in the 25ns range - 2-wise+ is 5% slower than 2-wise - 3-wise is 46% slower than 2-wise - 3-wise is 39% slower than 2-wise+ on the M1 - 2-wise+ is 40% slower than 2-wise - 3-wise is 46% slower than 2-wise - 3-wise is 4% slower than 2-wise+
- SekstiNi 6y ago
  Interesting, I ran it on my laptop (i7-7700HQ) with the following results: - 2-wise+ is 19% slower than 2-wise - 3-wise is 48% slower than 2-wise - 3-wise is 25% slower than 2-wise+ However, as mentioned in the post the numbers can vary a lot, and I noticed a maximum run-to-run difference of 23ms on two-wise.
- nottorp 6y ago
  Ouch. This is on my $2500 i5 mbpro from 2018. $ ./two_or_three N = 1000000000, 953.7 MB starting experiments. two : 53.3 ns two+ : 60.1 ns three: 78.6 ns bogus 1375316400 ------ 2+ 12% slower than 2 3-wise 47% slower than 2 3-wise 30% slower than 2+ ------- Ratios aside, that's an interesting speed leap when the article gets 9 ms for 2-wise. Mind, the laptop had lots of applications running, i didn't clear it up to do a proper benchmark, but still.
egnehots 6y ago
TLDR: he is using a random index with a big enough array
phkahler 6y ago
He's only got 3 million random[] numbers. Weather that's enough depends on the cache size. It also bothers me to read code like this where functions take parameters (like N) and never use them.
mrob 6y ago
I tried it on my old (2009) 2.5GHz Phenom II X4 905e (GCC 10.2.1 -O3, 64 bit) and got results almost perfectly matching the conventional wisdom: two : 97.4 ns two+ : 97.9 ns three: 145.8 ns

deleted 6y ago

[deleted]

africanboy 6y ago

I ran the benchmark on my system It's a 6 years old system, fastest times are in the 25ns range - 2-wise+ is 5% slower than 2-wise - 3-wise is 46% slower than 2-wise - 3-wise is 39% slower than 2-wise+ on the M1 - 2-wise+ is 40% slower than 2-wise - 3-wise is 46% slower than 2-wise - 3-wise is 4% slower than 2-wise+

SekstiNi 6y ago
Interesting, I ran it on my laptop (i7-7700HQ) with the following results: - 2-wise+ is 19% slower than 2-wise - 3-wise is 48% slower than 2-wise - 3-wise is 25% slower than 2-wise+ However, as mentioned in the post the numbers can vary a lot, and I noticed a maximum run-to-run difference of 23ms on two-wise.
nottorp 6y ago
Ouch. This is on my $2500 i5 mbpro from 2018. $ ./two_or_three N = 1000000000, 953.7 MB starting experiments. two : 53.3 ns two+ : 60.1 ns three: 78.6 ns bogus 1375316400 ------ 2+ 12% slower than 2 3-wise 47% slower than 2 3-wise 30% slower than 2+ ------- Ratios aside, that's an interesting speed leap when the article gets 9 ms for 2-wise. Mind, the laptop had lots of applications running, i didn't clear it up to do a proper benchmark, but still.

egnehots 6y ago

TLDR: he is using a random index with a big enough array

phkahler 6y ago

He's only got 3 million random[] numbers. Weather that's enough depends on the cache size. It also bothers me to read code like this where functions take parameters (like N) and never use them.

mrob 6y ago

I tried it on my old (2009) 2.5GHz Phenom II X4 905e (GCC 10.2.1 -O3, 64 bit) and got results almost perfectly matching the conventional wisdom: two : 97.4 ns two+ : 97.9 ns three: 145.8 ns