Walkthrough

Refactors the buildTree function in router.go from a two-pass algorithm to a single-pass approach per method, introducing per-route treePaths computation and consolidated tsMap initialization. Routes are appended directly to buckets with special handling for global routes. Also adds a new benchmark for tree rebuilding operations.

Changes

Estimated code review effort

🎯 4 (Complex) | ⏱️ ~45–60 minutes

• buildTree algorithm transition: Verify two-pass to single-pass conversion preserves routing correctness and functional equivalence
• Global route handling: Confirm treePath == 0 routes are properly appended to all existing buckets
• Data structure population: Validate tsMap initialization and treeStack[method] assignment in consolidated flow
• Edge cases: Test boundary conditions with mixed global and prefixed routes
• Benchmark validity: Ensure benchmark accurately measures rebuild performance without artificial bottlenecks

Possibly related PRs

• ♻️Refactor: replace treePath with treePathHash in DefaultCtx to reduce memory usage #3368: Modifies router.buildTree and treeStack/tsMap keying using integer treePath keys and global bucket 0 handling
• 🚀 Improve routing treeBuild flow #3456: Alters router.go's routing tree construction and bucket assignment logic in buildTree
• ✨ feat: Add support for RebuildTree #3074: Touches router tree rebuilding logic with RebuildTree implementation and related tests

Suggested labels

🧹 Updates, v3, ⚡️ Performance

Suggested reviewers

• sixcolors
• efectn

Poem

🐰 One pass, not two, through routing's way,
Buckets bloom where treePaths play,
Global routes hop every lane,
Faster trees, less refrain,
Efficient hops through fiber's domain! ✨

Pre-merge checks and finishing touches

Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

_{Comment @coderabbitai help to get the list of available commands and usage tips.}

Summary of Changes

Hello @gaby, I'm Gemini Code Assist¹! I'm currently reviewing this pull request and will post my feedback shortly. In the meantime, here's a summary to help you and other reviewers quickly get up to speed!

This pull request focuses on improving the efficiency and memory management of the routing tree construction within the application. It refactors the buildTree function to simplify bucket allocation and ensure precise preallocation of data structures. Additionally, a new benchmark is added to track the performance of the tree rebuilding operation, providing a baseline for future optimizations.

Highlights

• Optimized Tree Bucket Allocation: The logic for allocating routing buckets has been refactored to directly use prefix counts and global routes, eliminating the need for an intermediate capacity map and streamlining the process.
• Improved Slice Preallocation: The treeStack slices for both global and per-prefix routes are now accurately preallocated with their required capacities during the tree rebuilding process, enhancing memory efficiency.
• New Performance Benchmark: A new benchmark, Benchmark_App_RebuildTree, has been introduced to measure and monitor the performance of the App.RebuildTree function.

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 91.66%. Comparing base (76576dc) to head (ee1466c).
⚠️ Report is 19 commits behind head on main.

@@            Coverage Diff             @@
##             main    #3895      +/-   ##
==========================================
- Coverage   91.71%   91.66%   -0.05%     
==========================================
  Files         115      115              
  Lines        9967     9982      +15     
==========================================
+ Hits         9141     9150       +9     
- Misses        527      532       +5     
- Partials      299      300       +1     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

@gaby the range benchmark checks are failing because of the data type

I need to debug the local version. Unfortunately, we don't have any tests that check the internal structure, so we can't be sure that nothing has been applied incorrectly here.

its almost the same

perfect

just the "0" is a different dataType
is this "0" even needed ?

@ksw2000 Is the entry for 0 still necessary? I don't think it's used anymore, but I'm not sure.

I think I added that back then for routes that have less than 3 characters or the root "/" route.