Blart 0.2.0 released: Fastest Adaptive Radix Tree (ART) implementation, type safe and more

60 points FTW_gb09

For the last few years I have been obsessed with Adaptive Radix Trees and decide to write one myself. But in the process I found a great implementation by declanvk called blart and decided to contribute to it.

TL;DR: We have a new versions which is way faster (probably the fastest ART implementation out there).

New features:

  • Way faster, up to 50% in all operations (The 0.1.0 was already faster than the original C version). To achieve this a lot of optimization and simd was used.
  • Extremely type safe for dealing with different key types (prefixable keys, key ordering, composing keys).
  • Drop in replacement for HashMap/BTreeMap.
  • Entry api.
  • Fuzzy search for keys using Levenshtein distance (300k keys with an edit distance of 3 in around 1.2ms). This is faster than using Levenshtein Automata and it's not immutable.
  • Prefix search for the keys.
  • Configurable prefix length used as header in the nodes.