[PR #204] [MERGED] perf(netstack2): optimize subnet rule matching with BART #1878

New Issue

GiteaMirror · 2026-04-27T22:34:29-05:00

GiteaMirror commented

2026-04-27 22:34:29 -05:00

📋 Pull Request Information

Original PR: https://github.com/fosrl/newt/pull/204
Author: @LaurenceJJones
Created: 12/16/2025
Status: ✅ Merged
Merged: 3/3/2026
Merged by: @oschwartz10612

Base: dev ← Head: optimize-subnet-lookup-bart

📝 Commits (2)

c42a606 perf: optimize subnet rule matching with BART
9738565 fix: address code review issues for BART subnet lookup

📊 Changes

4 files changed (+206 additions, -109 deletions)

View changed files

📝 go.mod (+1 -0)
📝 go.sum (+2 -0)
📝 netstack2/proxy.go (+0 -109)
➕ netstack2/subnet_lookup.go (+203 -0)

📄 Description

Community Contribution License Agreement

By creating this pull request, I grant the project maintainers an unlimited,
perpetual license to use, modify, and redistribute these contributions under any terms they
choose, including both the AGPLv3 and the Fossorial Commercial license terms. I
represent that I have the right to grant this license for all contributed content.

Description

Replace O(n) map-based subnet rule matching with BART (Binary Aggregated Range Tree) using Supernets() for O(log n) prefix matching.

Performance improvements:

39x faster for no-match cases (critical for firewall/security)
1.9x faster for adding rules
Better scaling characteristics

Trade-offs:

Small rule sets (10-100): 1.2-1.4x slower for matches (20-30ns overhead)
Large rule sets (100+): 1.3x faster
No-match: 39x faster (original checks all rules, BART uses O(log n) tree lookup)

The no-match performance is particularly important for security/firewall scenarios where many packets are rejected. BART can determine 'no match' in ~7 tree operations vs checking all 100+ rules.

Dependencies:

Added: github.com/gaissmai/bart v0.26.0

Files:

netstack2/subnet_lookup.go: New BART-based implementation
netstack2/proxy.go: Removed old map-based implementation, updated to use BART

How to test?

Performance when routing through netstack2, the older implementation was O(n) meaning as subnets rules / routes increase the time depending on where the rule was in the slice would mean extra overhead. Switching to BART the matching is now O(k) where k is number of bytes in the address this means the performance is similar for 1-10 rules vs 100+ rules.

however a important key stats is that lower amount of rules do see a degradation in perf about 20-30ns overhead compared to the former O(n) simply because iterating over 10 rules can be performant, but when taking into the bigger picture and if we want to route maybe lots and lots of different rules then BART is a good choice.

_{🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.}

## 📋 Pull Request Information **Original PR:** https://github.com/fosrl/newt/pull/204 **Author:** [@LaurenceJJones](https://github.com/LaurenceJJones) **Created:** 12/16/2025 **Status:** ✅ Merged **Merged:** 3/3/2026 **Merged by:** [@oschwartz10612](https://github.com/oschwartz10612) **Base:** `dev` ← **Head:** `optimize-subnet-lookup-bart` --- ### 📝 Commits (2) - [`c42a606`](https://github.com/fosrl/newt/commit/c42a606bbd22facb8235bf05919edbfa2e784a3f) perf: optimize subnet rule matching with BART - [`9738565`](https://github.com/fosrl/newt/commit/9738565a3a218ff2a70b90cf068955caed949ea4) fix: address code review issues for BART subnet lookup ### 📊 Changes **4 files changed** (+206 additions, -109 deletions) <details> <summary>View changed files</summary> 📝 `go.mod` (+1 -0) 📝 `go.sum` (+2 -0) 📝 `netstack2/proxy.go` (+0 -109) ➕ `netstack2/subnet_lookup.go` (+203 -0) </details> ### 📄 Description ## Community Contribution License Agreement By creating this pull request, I grant the project maintainers an unlimited, perpetual license to use, modify, and redistribute these contributions under any terms they choose, including both the AGPLv3 and the Fossorial Commercial license terms. I represent that I have the right to grant this license for all contributed content. ## Description Replace O(n) map-based subnet rule matching with BART (Binary Aggregated Range Tree) using Supernets() for O(log n) prefix matching. Performance improvements: - 39x faster for no-match cases (critical for firewall/security) - 1.9x faster for adding rules - Better scaling characteristics Trade-offs: - Small rule sets (10-100): 1.2-1.4x slower for matches (20-30ns overhead) - Large rule sets (100+): 1.3x faster - No-match: 39x faster (original checks all rules, BART uses O(log n) tree lookup) The no-match performance is particularly important for security/firewall scenarios where many packets are rejected. BART can determine 'no match' in ~7 tree operations vs checking all 100+ rules. Dependencies: - Added: github.com/gaissmai/bart v0.26.0 Files: - netstack2/subnet_lookup.go: New BART-based implementation - netstack2/proxy.go: Removed old map-based implementation, updated to use BART ## How to test? Performance when routing through netstack2, the older implementation was O(n) meaning as subnets rules / routes increase the time depending on where the rule was in the slice would mean extra overhead. Switching to BART the matching is now O(k) where `k` is number of bytes in the address this means the performance is similar for 1-10 rules vs 100+ rules. **however** a important key stats is that lower amount of rules do see a degradation in perf about 20-30ns overhead compared to the former O(n) simply because iterating over 10 rules can be performant, but when taking into the bigger picture and if we want to route maybe lots and lots of different rules then BART is a good choice. --- <sub>🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.</sub>

GiteaMirror added the pull-request label 2026-04-27 22:34:29 -05:00

GiteaMirror closed this issue

2026-04-27 22:34:30 -05:00

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: github-starred/newt#1878