Awesome

Archived

NOTICE - I don't see the value in maintaining this any more as it has become a burden and I don't see any value when there is armon/libart which is more robust and proven. Also zig's std.StringHashMap() out-performs this implementation by around 2x in the benchmarks below.

If anyone sees value in this project, can convince me of it and wishes to maintain it, please open an issue and I'll be glad to un-archive and add you as a maintainer.

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 (8, 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 requires null terminated string slices ([:0]const u8).

Developed and tested against zig's latest master version. The zig version when this readme was updated was 0.11.0-dev.3834+d98147414.

Use with the zig package manager

// build.zig.zon
.{
    .name = "my lib",
    .version = "0.0.1",

    .dependencies = .{
        .art = .{
            .url = "https://github.com/travisstaloch/art.zig/archive/e8866a9f5b29a5b40db215e2242a8e265ccf300c.tar.gz",
            .hash = "1220d4b11d054408f1026fcdb026ef44939120e9a11a1ca2963a1c66e5adf3639ab6",
        },
    }
}

// build.zig
const art_dep = b.dependency("art", .{});
const art_mod = art_dep.module("art");
exe.addModule("art", art_mod);

// example zig app
const art = @import("art");

pub fn main() !void {
    const A = art.Art(usize);
    var a = A.init(&std.heap.page_allocator);
    _ = try a.insert("foo", 0);
}

Test

$ zig build test -Doptimize=ReleaseSafe

Run repl

$ zig run src/art.zig -lc

REPL

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

zig build bench

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:

.../zig/art.zig $ zig build bench
StringHashMap
insert 15ms, search 4ms, delete 2ms, combined 22ms
Art
insert 21ms, search 10ms, delete 13ms, combined 45ms

vs armon/libart

WARNING - this benchmark is old and flawed. Most of its time is spent reading lines from files which hides the performance of radix trees. Thanks to @iacore for helping me realize this.

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