4 ms·

I would consider Daniel Lemire (the main author) quite an authority within practical use of vectorization (SIMD). He is a computer science professor at Universi

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/ https://roaringbitmap.org/ [2] https://lemire.me/en/#publications https://lemire.me/en/#publications

michaelmior 6y ago
He's a great guy to work with. Also, in addition to being very efficient, his code (and papers) are also quite readable.
secondcoming 6y ago
Roaring Bitmaps look very useful, I need get around to porting it to C++ some day
- onefuncman 6y ago
  You mean like https://github.com/RoaringBitmap/CRoaring https://github.com/RoaringBitmap/CRoaring ?
  - secondcoming 6y ago
    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.
sillysaurusx 6y ago
Heh, I like the tagline: "Grab one of our research papers". It's very readable, too! https://arxiv.org/pdf/1603.06549.pdf 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 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 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.
- twic 6y ago
  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.
  - nicoburns 6y ago
    There is an implementation of Judy arrays in Rust: https://github.com/adevore/rudy https://github.com/adevore/rudy Not sure how complete / usable it is.
    - twic 6y ago
      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/300f2cc7842f6329a76fff012056f54bf6a37424/src/util/locksteparray.rs#L81 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.
      - quicknir 6y ago
        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.
naxlxaww 6y ago
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?
- ggrrhh_ta 6y ago
  Do you mean the code in http://www.netlib.org/fp/ http://www.netlib.org/fp/ under dtoa.c? (for strtod)... It appears from https://lemire.me/blog/2020/03/10/fast-float-parsing-in-practice/ 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?
  - maglap 6y ago
    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.
    - ggrrhh_ta 6y ago
      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.
    - ggrrhh_ta 6y ago
      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.
cbsmith 6y ago
I literally love everything Lemire does.

michaelmior 6y ago

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

secondcoming 6y ago

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

onefuncman 6y ago
You mean like https://github.com/RoaringBitmap/CRoaring https://github.com/RoaringBitmap/CRoaring ?
- secondcoming 6y ago
  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.

sillysaurusx 6y ago

Heh, I like the tagline: "Grab one of our research papers". It's very readable, too! https://arxiv.org/pdf/1603.06549.pdf 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 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 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.

twic 6y ago
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.
- nicoburns 6y ago
  There is an implementation of Judy arrays in Rust: https://github.com/adevore/rudy https://github.com/adevore/rudy Not sure how complete / usable it is.
  - twic 6y ago
    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/300f2cc7842f6329a76fff012056f54bf6a37424/src/util/locksteparray.rs#L81 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.
    - quicknir 6y ago
      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.

naxlxaww 6y ago

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?

ggrrhh_ta 6y ago
Do you mean the code in http://www.netlib.org/fp/ http://www.netlib.org/fp/ under dtoa.c? (for strtod)... It appears from https://lemire.me/blog/2020/03/10/fast-float-parsing-in-practice/ 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?
- maglap 6y ago
  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.
  - ggrrhh_ta 6y ago
    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.
  - ggrrhh_ta 6y ago
    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.

cbsmith 6y ago

I literally love everything Lemire does.