I’m glad to announce the first release of
art, an implementation of the Adaptive Radix Tree in OCaml. The goal of this library is to provide a data-structure such as
Map.S (and keep the order) with performances of
For the lookup operation, we are slightly faster than the
Hashtbl.t. The main advantage comparing to
Hashtbl.t is the ability to use
minimum or to
iter over the whole data-structure with a certain order.
On details, benchmarks use a normal distribution of
strings about their lengths. As a practical example where
art will be better than
Hashtbl.t is when you want to index several words (such as email addresses).
Of course, the library provide a fuzzer and tests have a coverage of: 91.93 %
Read Optimized Write Exclusion - ROWEX
Even if it’s not a part of the package, the distribution comes with lock-free implementation of
rowex. This implementation comes from a research paper about data-structure and atomic operations.
ROWEX provides a persistent implementation which manipulates a file to store the whole data-structure. The goal is to provide an indexer free to be manipulated by several processes in parallel.
Currently, the implementation of ROWEX in OCaml is not well-tested and it is no distributed. It does not take the advantage of ocaml-multicore (but it should) but outcomes are good and the development will be more focus on this part.
So feel free to play with it a bit .