grenad VS simdutf8

I tried new inserting algorithms on the sorter to reduce the amount of time spent sorting but didn’t find anything better than that, would you have any idea? I gave up trying better inserting algorithms by declaring that doing one final in-memory sort was more effective that doing a lot of comparison to try inserting keys in the right order…

I have finalized the latest release of grenad which introduce a lookup struct called a Cursor. Grenad is a library that provides tools to sort, merge, write, and read immutable key-value pairs.

I worked on my grenad library: a library used to sort, merge, write, and read key-value pairs, used in MeiliSearch for the new indexing system. I added a lot of documentation to the crate and done a lot of improvement by reducing the amount of copied memory when merging key-value pairs.

I was wondering if you could maybe point me to any blog post regarding the segment merging? I am using my grenad library, which is a simplification of my MTBL Rust port. This is a key-value store with some useful sorter helping functions, using a merge function, some compression parameters... Works great but could maybe be improved.

That's not enough to make it interesting. There's already a porting of it in rust (https://github.com/rusticstuff/simdutf8), and inclusion in the stdlib has already been discussed: the problem is that you can't use simd in all supported targets and conditional compilation/detection is also very tricky.

No, libcore uses simple branching code at the moment, see https://github.com/rust-lang/rust/issues/68455. The issue is still actively being worked on. Note, it's not a simple drop in, and there seem to be even faster algorithms. For now there is https://github.com/rusticstuff/simdutf8.

I will work on simdutf8, either

Now I have to benchmark again, it might be negligable. See also the discussion for this pull request.

Check the benchmarks section (https://github.com/rusticstuff/simdutf8#Benchmarks), second table. simdutf8 is up to 28 % faster on my Comet Lake CPU. However with pure ASCII clang does something magical with simdjson and it beats my implementation by a lot. GCC-compiled simdjson is slower all around except for a few outliers with short byte sequences.

The algorithm is the one from simdjson, the main difference is that it uses an extra step in the beginning to align reads to the SIMD block size.

ARM SIMD intrinsics are currently unstable and many are not yet implemented. But work to add them is ongoing and it should be possible. I will look into it. See issue #1

Yes, it is now also listed in the References section. The only difference is that it does 32-byte-aligned reads which proves to be a bit faster even on modern architectures since it is the SIMD register width and reads do not cross cachelines. Also, the compat API flavor checks every 64-byte block if invalid data has been encountered and calculates the error position using std::str::from_utf8().