Page MenuHomeFreeBSD

radix_trie: speed up search loops

Authored by dougm on Jul 12 2023, 3:04 AM.
Referenced Files
Unknown Object (File)
Sun, Apr 7, 5:32 PM
Unknown Object (File)
Jan 18 2024, 1:02 AM
Unknown Object (File)
Jan 14 2024, 6:01 PM
Unknown Object (File)
Jan 14 2024, 4:11 AM
Unknown Object (File)
Jan 12 2024, 1:11 PM
Unknown Object (File)
Dec 17 2023, 3:09 AM
Unknown Object (File)
Dec 13 2023, 4:11 PM
Unknown Object (File)
Dec 13 2023, 2:37 AM



Combine three ways to speed up index-based searches in radix tries.

  1. Every path from trie root to the bottom ends in either a leaf or a NULL node. Every loop that walks a path from the root has to check both conditions with every iteration. Replace those NULL nodes with null-leaves, so that every loop can iterate until a leaf is encountered, and then distinguish null leaves from regular leaves once, outside the loop.

That only works for tries properly initialized; default, static zero-initialization no longer works.

  1. Every iteration invokes keybarr(), to see if the search is doomed to fail, and slot(), to determine how to continue. A simple calculation produces both results at once, eliminating some arithmetic and a branch point.
  1. There is a node field called 'clev'. It is always fetched and then multiplied by a constant. Saving the post-multiplication value instead saves an instruction per loop iteration.
Test Plan

I ran a buildworld test that counted calls and cycles spent in those calls, for for the original code and the code as modified by this change, for the vm_radix versions of lookup_ge, lookup_le, lookup, insert and remove:

Original stats;
52579.851u 1464.033s 59:18.83 1518.5% 73464+3095k 121044+34231io 110768pf+0w
vm.radix.lookup_le_cycles: 67380124177
vm.radix.lookup_le_calls: 341562871
vm.radix.lookup_le_cycles/call: 197.27004864354825
vm.radix.lookup_ge_cycles: 2243725226
vm.radix.lookup_ge_calls: 3545877
vm.radix.lookup_ge_cycles/call: 632.7701795634761
vm.radix.lookup_cycles: 51517315631
vm.radix.lookup_calls: 349324641
vm.radix.lookup_cycles/call: 147.47690138182952
vm.radix.remove_cycles: 9643973959
vm.radix.remove_calls: 79571853
vm.radix.remove_cycles/call: 121.19830813792912
vm.radix.insert_cycles: 77607446838
vm.radix.insert_calls: 345173648
vm.radix.insert_cycles/call: 224.83595514220715

Modified stats:
52604.110u 1459.569s 59:24.11 1516.8% 73467+3096k 121084+33732io 110823pf+0w
vm.radix.lookup_le_cycles: 58322122750
vm.radix.lookup_le_calls: 341562671
vm.radix.lookup_le_cycles/call: 170.75086858657338
vm.radix.lookup_ge_cycles: 1753102450
vm.radix.lookup_ge_calls: 3547268
vm.radix.lookup_ge_cycles/call: 494.21201048243324
vm.radix.lookup_cycles: 43031420200
vm.radix.lookup_calls: 349320580
vm.radix.lookup_cycles/call: 123.18604360498887
vm.radix.remove_cycles: 9311389818
vm.radix.remove_calls: 79574836
vm.radix.remove_cycles/call: 117.01425081165107
vm.radix.insert_cycles: 75758299926
vm.radix.insert_calls: 345174133
vm.radix.insert_cycles/call: 219.4784970344229

new/old lookup_le_cycles/call: 0.8655691513267025
new/old lookup_ge_cycles/call: 0.7810292369077367
new/old lookup_cycles/call: 0.8352904248106646
new/old remove_cycles/call: 0.9654775929585057
new/old insert_cycles/call: 0.976171702144367

Diff Detail

Lint Skipped
Tests Skipped

Event Timeline

dougm requested review of this revision.Jul 12 2023, 3:04 AM
dougm created this revision.
dougm retitled this revision from radix_trie: use null leaves to speed searches to radix_trie: null leaves, no keybarrs, speed searches.
dougm edited the summary of this revision. (Show Details)
dougm edited the test plan for this revision. (Show Details)
dougm retitled this revision from radix_trie: null leaves, no keybarrs, speed searches to radix_trie: speed up search loops.
dougm edited the summary of this revision. (Show Details)

restore a dropped underscore.

dougm edited the test plan for this revision. (Show Details)
dougm added a subscriber: pho.

Peter, can you test this? It requires testing on multiple platforms.

Peter, can you test this? It requires testing on multiple platforms.

Sure. I should be able to start testing this late tomorrow.

I ran tests with D40979.id124949.diff on both amd64 and i386. 8 hours on i386 and some 20 hours on amd64.

FreeBSD 14.0-CURRENT i386 1400093 #0 main-n264276-22dca7acf7756-dirty
FreeBSD 14.0-CURRENT #0 main-n264276-22dca7acf7756-dirty (amd64)

No problems observed.

Other than a few comment rewrites, everything here has been checked in already.