Hash table index for O(1) packet history lookups#9499
Merged
Conversation
Contributor
There was a problem hiding this comment.
Pull request overview
This pull request adds an open-addressing hash table as a secondary index to PacketHistory, improving packet lookup performance from O(n) to O(1). The hash table uses linear probing with a 0.5 load factor and backward-shift deletion, complementing the existing recentPackets array without changing its eviction logic.
Changes:
- Added hash table implementation with O(1) lookups for packet deduplication
- Introduced
checkRelayers()batch method to optimize multiple relayer checks - Added
MESHTASTIC_EXCLUDE_PKT_HISTORY_HASHflag for minimal builds - Comprehensive test suite with 48 unit tests covering all PacketHistory functionality
Reviewed changes
Copilot reviewed 6 out of 6 changed files in this pull request and generated 3 comments.
Show a summary per file
| File | Description |
|---|---|
src/mesh/PacketHistory.h |
Added hash table data structures and checkRelayers() method declaration |
src/mesh/PacketHistory.cpp |
Implemented hash functions (insert, remove, rebuild, slot), updated find() to use hash index, integrated hash maintenance in insert() |
src/meshUtils.h |
Added nextPowerOf2() utility for calculating hash table capacity |
src/mesh/NextHopRouter.cpp |
Updated to use checkRelayers() for batch lookup optimization |
src/configuration.h |
Added MESHTASTIC_EXCLUDE_PKT_HISTORY_HASH to minimal build exclusions |
test/test_packet_history/test_main.cpp |
Comprehensive test suite with 48 tests covering initialization, deduplication, eviction, relayer tracking, merge logic, and hash stress tests |
Co-authored-by: Copilot <175728472+Copilot@users.noreply.github.com>
jp-bennett
approved these changes
Feb 2, 2026
Collaborator
There was a problem hiding this comment.
I was ready to throw things when I saw it was 1000+ lines of new code, but very pleasantly surprised to see the majority are in the test cases. Code looks clean and the idea makes sense. The 2k hurts a bit, but other than that looks OK.
Edit: Maybe also needs to wait for 2.8? This one worries me less than the NodeDB sorting code.
mariotti
pushed a commit
to mariotti/firmware
that referenced
this pull request
May 6, 2026
* Use hash table for O(1) lookup of recently seen packets * Eliminate a packet lookup during deduplication * Infinite loop checks for find and remove * Consolidate conditional compilation * Exclude hash table from minimal build * Additional comment on hash table capacity * Unit tests for packet history changes * Update incorrect comment about size clamp Co-authored-by: Copilot <175728472+Copilot@users.noreply.github.com> * Const --------- Co-authored-by: Copilot <175728472+Copilot@users.noreply.github.com> Co-authored-by: Ben Meadors <benmmeadors@gmail.com>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
PacketHistory::find() does a linear scan over the entire recent packet history array every time a packet comes in. This works, but it's O(n) and gets called on every received packet, sometimes twice in the same code path (NextHopRouter was calling wasRelayer() twice for the same packet record).
This PR adds an open-addressing hash table as a side index into the existing recentPackets array, making lookups O(1). The hash uses linear probing with a load factor ≤ 0.5 and backward-shift deletion instead of tombstones, so it holds up well under the constant eviction churn. The rest of the packet history logic (eviction, relayer tracking, merge) is untouched, the hash is just an index sitting alongside it.
Also added checkRelayers() to batch the two wasRelayer() calls in the ACK path into a single lookup, and gated the whole hash table implementation behind MESHTASTIC_EXCLUDE_PKT_HISTORY_HASH so it's excluded from minimal builds.
Added 48 unit tests covering the full PacketHistory surface.
Memory cost is ~2 KB for the default history size of 256 packets. Benchmarks on unit tests show this is about 100x faster on nRF52 and 40x faster on ESP32. That translates to minimal real world improvements, but does give a lot of headroom for routers handling much larger meshes and in future DoS prevention checks. There are also likely minimal battery improvements, but less time spent computing is more time spent sleeping, so it can't hurt.
🤝 Attestations