Net::BART - Balanced Routing Tables for Perl

Fast IPv4/IPv6 longest-prefix-match (LPM) routing table lookups for Perl, available in two flavors:

Net::BART — pure Perl, zero dependencies
Net::BART::XS — C implementation via XS, 4-5x faster than Net::Patricia

Based on the Go implementation gaissmai/bart, which builds on Knuth's ART (Allotment Routing Tables) algorithm.

Synopsis

# Pure Perl — works everywhere, no compiler needed
use Net::BART;
my $table = Net::BART->new;

# XS/C — same API, maximum performance
use Net::BART::XS;
my $table = Net::BART::XS->new;

# Insert prefixes with associated values
$table->insert("10.0.0.0/8",       "private-rfc1918");
$table->insert("10.1.0.0/16",      "office-network");
$table->insert("10.1.42.0/24",     "dev-team");
$table->insert("0.0.0.0/0",        "default-gw");
$table->insert("2001:db8::/32",    "documentation");

# Longest-prefix match
my ($val, $ok) = $table->lookup("10.1.42.7");
# $val = "dev-team", $ok = 1

my ($val, $ok) = $table->lookup("10.1.99.1");
# $val = "office-network", $ok = 1

# Exact match
my ($val, $ok) = $table->get("10.1.0.0/16");
# $val = "office-network", $ok = 1

# Fast containment check
$table->contains("10.1.42.7");  # 1
$table->contains("172.16.0.1"); # 1 (matches default route)

# Delete
my ($old, $ok) = $table->delete("10.1.42.0/24");
# $old = "dev-team", $ok = 1

# Walk all prefixes (Net::BART only)
$table->walk(sub {
    my ($prefix, $value) = @_;
    print "$prefix => $value\n";
});

# Counts
printf "Total: %d (IPv4: %d, IPv6: %d)\n",
    $table->size, $table->size4, $table->size6;

Installation

Net::BART (pure Perl) requires no installation — add lib/ to @INC:

perl -Ilib your_script.pl

Net::BART::XS requires a C compiler:

cd lib/Net/BART && perl Makefile.PL && make && make test

Then add both lib/ and the blib paths to @INC:

perl -Ilib -Ilib/Net/BART/blib/arch -Ilib/Net/BART/blib/lib your_script.pl

Requires Perl 5.10+ with 64-bit integer support.

API

Both Net::BART and Net::BART::XS share the same API:

| Method | Description | Returns | |--------|-------------|---------| | ->new | Create empty routing table | object | | ->insert($prefix, $val) | Insert/update a CIDR prefix | 1 if new, 0 if updated | | ->lookup($ip) | Longest-prefix match | ($value, 1) or (undef, 0) | | ->contains($ip) | Any prefix contains this IP? | 1 or 0 | | ->get($prefix) | Exact prefix match | ($value, 1) or (undef, 0) | | ->delete($prefix) | Remove a prefix | ($old_value, 1) or (undef, 0) | | ->size / ->size4 / ->size6 | Prefix count | integer | | ->walk($cb) | Iterate all prefixes (Net::BART only) | void |

Prefix formats: "10.0.0.0/8", "2001:db8::/32", "0.0.0.0/0", "::/0"

IP formats: "10.1.2.3", "2001:db8::1" (for lookup/contains)

Performance

Lookup Comparison — All Implementations (ops/sec, 100K prefixes)

Benchmarked with random IPv4 prefixes, 50K lookups per run, best of 3. Go BART is the reference implementation (v0.26.1).

  Go BART (pre-parsed)  ████████████████████████████████████████████████  15,517K   0.06 µs
  Go BART (from string) ████████████████████████                          7,899K   0.13 µs
  Net::BART::XS         ██████                                            1,992K   0.50 µs
  Net::Patricia          █▌                                                 477K   2.10 µs
  Net::BART (pure Perl)  ▎                                                   98K  10.20 µs

Full Comparison at 100K Prefixes — Latency per Operation

| Operation | Go (pre-parsed) | Go (strings) | Net::BART::XS | Net::Patricia | Net::BART | |-----------|:---------------:|:------------:|:--------------:|:-------------:|:---------:| | Insert | 0.26 µs | 0.43 µs | 0.78 µs | 3.1 µs | 14.8 µs | | Lookup | 0.06 µs | 0.13 µs | 0.50 µs | 2.1 µs | 10.2 µs | | Contains | 0.008 µs | 0.04 µs | 0.35 µs | n/a | 4.6 µs | | Get/Exact | 0.07 µs | 0.12 µs | 0.54 µs | 2.6 µs | 11.0 µs | | Delete | 0.50 µs | — | 1.29 µs | 5.8 µs | 29.3 µs |

Lookup Scaling Across Table Sizes (ops/sec)

| Table size | Go (pre-parsed) | Go (strings) | Net::BART::XS | Net::Patricia | Net::BART | |:----------:|:---------------:|:------------:|:--------------:|:-------------:|:---------:| | 100 | 25,653K | 21,759K | 3,186K | 719K | 310K | | 1K | 50,257K | 18,348K | 3,047K | 687K | 179K | | 10K | 50,972K | 6,388K | 2,818K | 660K | 149K | | 100K | 15,517K | 7,899K | 1,992K | 477K | 98K |

Perl-Only Comparison at 100K Prefixes

| Operation | Net::Patricia (C) | Net::BART (Perl) | Net::BART::XS (C) | XS vs Patricia | |-----------|-------------------:|-----------------:|-------------------:|:--------------:| | Insert | 318K ops/s | 68K ops/s | 1,274K/s | 4.0x | | Lookup | 477K ops/s | 98K ops/s | 1,992K/s | 4.2x | | Contains | n/a | 218K ops/s | 2,878K/s | n/a | | Get/Exact | 388K ops/s | 91K ops/s | 1,865K/s | 4.8x | | Delete | 173K ops/s | 34K ops/s | 777K/s | 4.5x |

All Perl implementations produce identical results (cross-checked with 10K random lookups).

See PERFORMANCE.md for the complete analysis.

Why Is Go Faster Than C/XS?

The Go BART implementation is 4-8x faster than Net::BART::XS for lookup, despite both using the same algorithm in compiled languages. The gap comes from:

Zero-cost value types. Go's netip.Addr is a stack-allocated value with no heap allocation, while Perl XS must wrap every value in a heap-allocated SV with reference counting.
Generics. bart.Table[int] is monomorphized at compile time — no void* casts or type dispatch at runtime.
No refcount overhead. Go's garbage collector handles memory in bulk; Perl requires per-operation SvREFCNT_inc/SvREFCNT_dec.
Contains at 8ns/op in Go is essentially a few cache hits — the entire hot path stays in registers with zero allocation.

Why Is Net::BART::XS Faster Than Net::Patricia?

8-bit stride multibit trie — IPv4 traverses at most 4 nodes vs up to 32 in a patricia trie
O(1) LPM per node — precomputed ancestor bitsets + bitwise AND, not pointer-chasing
Hardware intrinsics — POPCNT and LZCNT instructions for rank/bit-find in single cycles
Cache-friendly — popcount-compressed sparse arrays pack data tightly

Choosing an Implementation

How It Works

BART is a multibit trie with a fixed stride of 8 bits. Each IP address is decomposed into octets, and each octet indexes one level of the trie:

IPv4: at most 4 trie levels (one per octet)
IPv6: at most 16 trie levels (one per octet)

ART Index Mapping

Within each trie node, prefixes of length /0 through /7 (relative to the stride) are stored in a complete binary tree with indices 1-255:

Index 1:         /0 (default route within stride)
Indices 2-3:     /1 prefixes
Indices 4-7:     /2 prefixes
Indices 8-15:    /3 prefixes
Indices 16-31:   /4 prefixes
Indices 32-63:   /5 prefixes
Indices 64-127:  /6 prefixes
Indices 128-255: /7 prefixes

O(1) Longest-Prefix Match Per Node

A precomputed lookup table maps each index to its ancestor set in the binary tree. LPM at a node becomes a bitwise AND of the node's prefix bitset with the ancestor bitset, followed by finding the highest set bit — all O(1) operations.

Memory Efficiency

Popcount-compressed sparse arrays store only occupied slots. A 256-bit bitset tracks which indices are present, and a compact array holds only the values. Lookup is O(1): test the bit, compute rank via popcount, index into the array.

Path Compression

LeafNode: non-stride-aligned prefixes stored directly when no child exists
FringeNode: stride-aligned prefixes (/8, /16, /24, /32) stored without prefix data

Project Structure

lib/
  Net/
    BART.pm                    # Pure Perl implementation
    BART/
      Art.pm                   # ART index mapping functions
      BitSet256.pm             # 256-bit bitset (4 x uint64)
      LPM.pm                   # Precomputed ancestor lookup table
      Node.pm                  # BartNode, LeafNode, FringeNode
      SparseArray256.pm        # Popcount-compressed sparse array
      bart.h                   # C implementation of BART algorithm
      XS.xs                    # XS bindings
      XS.pm                    # XS Perl wrapper
      Makefile.PL              # Build script for XS module
t/
    01-bitset256.t             # BitSet256 unit tests
    02-sparse-array.t          # SparseArray256 unit tests
    03-art.t                   # ART index mapping tests
    04-table.t                 # Integration tests

Running Tests

# Pure Perl tests
prove -Ilib t/

# Build and test XS module
cd lib/Net/BART && perl Makefile.PL && make && make test

# Run three-way benchmark (requires Net::Patricia)
perl bench_all.pl

References

gaissmai/bart — Go implementation this port is based on
Knuth, D. E. — The Art of Computer Programming, Volume 4, Fascicle 7 — Allotment Routing Tables (ART)

License

Same terms as Perl itself.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	Go to GitHub issues (only if GitHub is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)