Hacker News Reader

Comment by kasperni | Hacker News Reader

I would consider Daniel Lemire (the main author) quite an authority within practical use of vectorization (SIMD). He is a computer science professor at Université du Québec. And is also behind the popular Roaring Bitmaps project [1]. You can check out his publication list here [2].

[1] https://roaringbitmap.org/

[2] https://lemire.me/en/#publications

View on HN

Heh, I like the tagline: "Grab one of our research papers". It's very readable, too! https://arxiv.org/pdf/1603.06549.pdf

Looks like the last active discussion of Roaring Bitmaps was 6 years ago: https://news.ycombinator.com/item?id=8796997 possibly when it was first introduced. Interesting comments!

> How do these compare space and performance wise with Judy arrays, which are 256-ary trees whose nodes also distinguish between sparse and dense subsets? https://en.wikipedia.org/wiki/Judy_array

Good question, since the patent on them won't expire until Nov 29, 2020.

Judy arrays seem to be much less known. Looks like today will be Datastructure Thursday; lots of neat stuff to dig into.

The showstopper with Judy arrays, for me, was that they require a lot of hairy fine control over memory layout to implement (it's been years since i looked at this, so please excuse the lack of detail). You can do that in C, but not in no-sharp-edges languages like Java, which i was using at the time. It would even be quite a headache in Rust.

It doesn't help that the documentation is very weird.

There is an implementation of Judy arrays in Rust: https://github.com/adevore/rudy Not sure how complete / usable it is.

The docs say it's largely complete.

As an example of a headache, one node type in Judy has a count, followed by that many index bytes, followed by the same number of pointers. In Rust, that would naturally be a struct with two variable-sized fields, which isn't possible, so it's done by defining a struct generic over a pair of array types:

https://github.com/adevore/rudy/blob/300f2cc7842f6329a76fff0...

It looks to me like this is only ever instantiated for 2, 7, or 31 elements, whereas i think for original Judy, it can be any size up to 31 elements (maybe?). Handling a genuinely variable length in Rust would be rather gnarly, because there have to be different types for each length.

I would assume that within unsafe you could simply do the same kinds of shenanigans you would do in C++, e.g. you have a fixed size struct that is just the "header", it's only created on the heap, and it's immediately followed by the variable amount of data which you get access to by casting. If you couldn't do this in unsafe rust this seems like a pretty huge limitation.

Yes, you could.

I used to work at a small-ish (but very profitable) European company whose "crown jewel", in terms of in-house developed technology, was a distributed in-memory search/database engine, written in hand-crafted, multi-threaded C by a true coding wizard and industry veteran. It used Judy arrays at its heart for the very first filtering/processing stage of queries, and did so to amazing effect. It's quite spectacular what you could and can do with libjudy if you use it wisely :)

I always wondered if relatively recent changes in x86 CPU µarchs broke some of the assumptions that made libjudy perform this great even on Pentium-class hardware, and if the de facto only complete implementation (that I happen to be aware of) could be improved as a consequence, if those changes (i.e., hugely increased cache sizes, etc.) were considered.

What were you working on?

He's a great guy to work with. Also, in addition to being very efficient, his code (and papers) are also quite readable.

Roaring Bitmaps look very useful, I need get around to porting it to C++ some day

You mean like https://github.com/RoaringBitmap/CRoaring ?

That's just a wrapper over the C interface. When I last looked at using Roaring Bitmaps I was going to use it in shared memory, which would mean removing explicit calls to malloc etc, and supplying allocators instead.

I literally love everything Lemire does.

He certainly knows how to promote his software, always getting way more attention than "usual" open source authors.

What about his floating point conversion software that is basically David Gay's?

Do you mean the code in http://www.netlib.org/fp/ under dtoa.c? (for strtod)... It appears from https://lemire.me/blog/2020/03/10/fast-float-parsing-in-prac... that he doesn't even claim to have had the idea for the floating point conversion code... What is the connection?

The casual reader of his blogs (like many on HN apparently) is likely to get the impression that he had the original ideas for much of his software.

His software has very few tests (especially for floating point), there's no paper for the method but nevertheless it apparently gets used at Google almost instantly.

So it looks as if there are connections that regular OSS authors don't have.

But well, because it's written and wrapped in a readily usable form, with a very permissible license. If there are concerns about the deserved credit, I found it good that it is voiced and he should make sure it credit goes to where it should. I want to know where the ideas originated from and also appreciate the value that Lemire's group adds to be it.

Actually, I did upvote your comment. After doing some research and looking into his blog, I realized that I though that things that he describes that appear in previous works give the impression that they are his ideas. The posts are great and a fantastic source of information, very valuable by themselves. I don't understand why wouldn't he just be more clear about the credit to others.

When I read his 'discovery' of fast modulo division [1], it immediately reminded me of the same technique discussed as an aside in this very interesting [2006] IBM SIMD paper [2].

I let him know about this and he added the last footnote in [1], but no update of his blog or related github page saying "hah, turns out this was a known method at least in IBM'. It left a slight bad impression in my mind.

So, yeah ..

[1]: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-...

See "2 Outline of Approach" section, last 2 paragraphs:

[2]: https://dominoweb.draco.res.ibm.com/reports/rc24100.pdf

Why did you put "discovery" in quotes, even though Lemire doesn't claim anywhere in that blog post to have discovered or invented the technique?

That's a fair point. Generally I am used to seeing a cite of original source on an elaboration, proof, or "let's dig into how it works" sort of writeups on algorithmic approaches. (Sometimes this is done even when the algorithm in question and source is well known.) Specially if the author is an academic.

Well; I read the blog post and I am disappointed at Lemire, actually.

Yes, it does not claim anywhere it is his invention - it starts the description of the algorithm with "The common solution", but if you read it, it really looks like the development of the technique as a whole is his; at the end one note says: "The technique described in this blog post is in used within Microsoft Arriba."

If no one had pointed out that it is not his, I would have thought that it was his, the blog post title is "A fast alternative to the fast modulo reduction", and not "How X's algorithm for fast modulo reduction works. My implementation".

Reply on news.ycombinator.com