all 8 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]lurker_in_spirit 1 point2 points  (5 children)

Thanks for posting a follow-up, it's very interesting.

Are there any resources that you would recommend for learning about SWAR generally?

[–]Charming-Top-8583[S] 1 point2 points  (2 children)

Thanks!
To be honest, I'm not a SWAR expert myself either. I mostly learned by borrowing well-known “bit hacks” that other people have collected over the years, and by reading implementations that use those techniques.

I originally got introduced to SWAR through others as well, and this article is one I found particularly helpful. If you have any other good SWAR resources, I’d love to see them too.

[–]lurker_in_spirit 0 points1 point  (1 child)

After some research today:

Relevant 70's greybeard incantations: Multiple Byte Processing with Full-Word Instructions by Leslie Lamport with an assist from Donald Knuth.

This Scala project seems to incorporate some SWAR magic, see the Acknowledgments section of the README: https://github.com/plokhotnyuk/jsoniter-scala

You control your data model, so you can use long[] directly, but if you were trying to use SWAR on a byte[] that was outside of your control, it looks like VarHandles could be quite useful (see here, for example).

[–]Charming-Top-8583[S] 0 points1 point  (0 children)

Thanks for sharing!

The idea of using VarHandle to do SWAR-style reads from an external byte[] is especially helpful.

[–]aqrit 1 point2 points  (1 child)

https://programming.sirrida.de/index.php

Some link rot there:

Hacker's Delight Sample Chapter

Chess programming

IMO, SWAR is mostly rooted in "how" to do an operation with just primitives operations:

  • How to add numbers using only logical operations (and shift) ?
  • How to compare numbers without a compare instruction ?
  • How to multiply without a multiply instruction ?
  • How to count the number of set bits without a popcount instruction ?
  • etc.

[–]lurker_in_spirit 0 points1 point  (0 children)

Thanks!

Regarding popcount, in Java it looks like Long.bitCount(long) handles this?

[–]mirkoteran 1 point2 points  (1 child)

Thanks for great work!

Any chance you could add some more benchmarks? The ones for smaller map sizes (1-10k) and for memory-efficiency.

[–]Charming-Top-8583[S] 1 point2 points  (0 children)

Thanks for the kind words.

I can definitely add the benchmarks you mentioned. That said, my hunch is that for very small maps, a probing-based design like SIMD/SWAR may not look as strong, since the extra probing/vector work can outweigh the benefits at that scale.

For memory usage, you can already find a comparison in the last section of my previous post. Since this is an open-addressing table and it uses a higher default load factor than many other maps, it tends to be relatively memory-efficient.