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>
Blocking a user prevents them from interacting with repositories, such as opening or commenting on pull requests or issues. Learn more about blocking a user.
📋 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)
c42a606perf: optimize subnet rule matching with BART9738565fix: 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:
Trade-offs:
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:
Files:
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
kis 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.