Features
This library provides a zig implementation of the Adaptive Radix Tree or ART. The ART operates similar to a traditional radix tree but avoids the wasted space of internal nodes by changing the node size. It makes use of 4 node sizes (4, 16, 48, 256), and can guarantee that the overhead is no more than 52 bytes per key, though in practice it is much lower. As a radix tree, it provides the following:
- O(k) operations. In many cases, this can be faster than a hash table since the hash function is an O(k) operation, and hash tables have very poor cache locality.
- Minimum / Maximum value lookups
- Prefix compression
- Ordered iteration
- Prefix based iteration
NOTES:
taken from armon/libart
the memory footprint described here is unverified
Usage
See src/test_art.zig
Important Notes
This library accepts zig string slices ([:0]const u8) which means they are required to be null terminated.
Build
# creates zig-cache/lib/libart.a
# debug
$ zig build
# release
$ zig build -Drelease-safe # or release-fast or release-smallTest
$ zig build testRun repl
$ zig run src/art.zig -lcREPL
The repl is very simple and responds to these commands:
- :q - quit
- key - adds 'key' with value = tree.size
- key number - adds key with value = parse(number)
- d:key - deletes key
- :r - reset (destroy and then init) the tree
A representation of the tree will be printed after each operation.
Benchmarks
This simple benchark consists of inserting, searching for and deleting each line from testdata/words.txt (235886 lines). Benchmarks are compiled with --release-fast.
vs StringHashMap
(from zig's standard library) can be found here src/test_art.zig.
The results of the benchark on my machine:
Art insert 507ms, search 481ms, delete 495ms, combined 1484ms
StringHashMap insert 487ms, search 482ms, delete 485ms, combined 1456ms
| Operation | % difference |
|---|---|
| insert | 04.1% slower |
| search | 00.2% faster |
| delete | 02.0% slower |
| combined | 01.9% slower |
vs armon/libart
Can be found src/clibart.zig
art.zig insert 505ms, search 482ms, delete 494ms, combined 1481ms
art.c insert 494ms, search 481ms, delete 484ms, combined 1459ms
| Operation | % difference |
|---|---|
| insert | 2.22% slower |
| search | 0.20% slower |
| delete | 2.06% slower |
| combined | 1.50% slower |