Closed iand closed 1 year ago
Imported the xor trie into key/trie
. I only imported the immutable version and I didn't bring over unions/intersections. We can add all those in the future if we need to. Rearranged the API a little to my taste and reworked all the tests.
The imported trie with extra data field meant I could drop the map between key and node in the triert
Error checking is in preparation for https://github.com/plprobelab/go-kademlia/pull/51#issuecomment-1621703741 if we decide to take that route
PTAL
Recent changes:
Initial benchmarks:
goos: linux
goarch: amd64
pkg: github.com/plprobelab/go-kademlia/key/trie
cpu: 13th Gen Intel(R) Core(TM) i7-13650HX
BenchmarkBuildTrieMutable/1000-20 5368 239713 ns/op 1286779 ns/key 186240 B/op 2910 allocs/op
BenchmarkBuildTrieMutable/10000-20 278 4296195 ns/op 119433 ns/key 1836428 B/op 28694 allocs/op
BenchmarkBuildTrieMutable/100000-20 39 29098613 ns/op 11348 ns/key 18480013 B/op 288750 allocs/op
BenchmarkBuildTrieImmutable/1000-20 2350 692483 ns/op 1627331 ns/key 787776 B/op 12309 allocs/op
BenchmarkBuildTrieImmutable/10000-20 96 13987724 ns/op 134282 ns/key 9982505 B/op 155976 allocs/op
BenchmarkBuildTrieImmutable/100000-20 10 103134639 ns/op 10313 ns/key 121270315 B/op 1894848 allocs/op
BenchmarkAddMutable/1000-20 25603 47707 ns/op 4885774 ns/key 46465 B/op 726 allocs/op
BenchmarkAddMutable/10000-20 806 1463271 ns/op 471757 ns/key 466178 B/op 7284 allocs/op
BenchmarkAddMutable/100000-20 100 10893145 ns/op 43572 ns/key 4603648 B/op 71932 allocs/op
BenchmarkAddImmutable/1000-20 9826 232817 ns/op 9150635 ns/key 232640 B/op 3635 allocs/op
BenchmarkAddImmutable/10000-20 297 3863193 ns/op 458946 ns/key 2744902 B/op 42889 allocs/op
BenchmarkAddImmutable/100000-20 52 23498035 ns/op 48876 ns/key 32888064 B/op 513876 allocs/op
BenchmarkRemoveMutable/1000-20 37214 34692 ns/op 5164169 ns/key 0 B/op 0 allocs/op
BenchmarkRemoveMutable/10000-20 960 1309283 ns/op 502763 ns/key 4 B/op 0 allocs/op
BenchmarkRemoveMutable/100000-20 100 10223293 ns/op 40893 ns/key 1 B/op 0 allocs/op
BenchmarkRemoveImmutable/1000-20 8344 249415 ns/op 8324454 ns/key 194496 B/op 3039 allocs/op
BenchmarkRemoveImmutable/10000-20 284 4433920 ns/op 503692 ns/key 2476353 B/op 38693 allocs/op
BenchmarkRemoveImmutable/100000-20 42 28681932 ns/op 48186 ns/key 29994752 B/op 468668 allocs/op
BenchmarkFindPositive/1000-20 18115773 63.32 ns/op 0 B/op 0 allocs/op
BenchmarkFindPositive/10000-20 11876832 95.95 ns/op 0 B/op 0 allocs/op
BenchmarkFindPositive/100000-20 5064666 232.6 ns/op 0 B/op 0 allocs/op
BenchmarkFindNegative/1000-20 35327665 34.01 ns/op 0 B/op 0 allocs/op
BenchmarkFindNegative/10000-20 15040240 75.56 ns/op 0 B/op 0 allocs/op
BenchmarkFindNegative/100000-20 6080850 198.8 ns/op 0 B/op 0 allocs/op
goos: linux
goarch: amd64
pkg: github.com/plprobelab/go-kademlia/routing/triert
cpu: 13th Gen Intel(R) Core(TM) i7-13650HX
BenchmarkBuildTable/1000-20 6938 272436 ns/op 1890159 ns/node 185072 B/op 2892 allocs/op
BenchmarkBuildTable/10000-20 256 4579850 ns/op 117244 ns/node 1836924 B/op 28702 allocs/op
BenchmarkBuildTable/100000-20 40 9681654 ns/op 11873 ns/node 18486147 B/op 288846 allocs/op
BenchmarkFindPositive/1000-20 20827332 55.88 ns/op 0 B/op 0 allocs/op
BenchmarkFindPositive/10000-20 14346126 83.10 ns/op 0 B/op 0 allocs/op
BenchmarkFindPositive/100000-20 6442490 189.8 ns/op 0 B/op 0 allocs/op
BenchmarkFindNegative/1000-20 35187136 33.13 ns/op 0 B/op 0 allocs/op
BenchmarkFindNegative/10000-20 15310812 73.62 ns/op 0 B/op 0 allocs/op
BenchmarkFindNegative/100000-20 6700594 181.9 ns/op 0 B/op 0 allocs/op
BenchmarkNearestPeers/1000-20 318604 5927 ns/op 5965 B/op 44 allocs/op
BenchmarkNearestPeers/10000-20 129309 9016 ns/op 5970 B/op 44 allocs/op
BenchmarkNearestPeers/100000-20 229111 5404 ns/op 5983 B/op 44 allocs/op
BenchmarkChurn/1000-20 5453337 199.6 ns/op 64 B/op 1 allocs/op
BenchmarkChurn/10000-20 3280557 375.0 ns/op 63 B/op 0 allocs/op
BenchmarkChurn/100000-20 3017536 388.5 ns/op 65 B/op 1 allocs/op
Windows/macos tests are still flaky. I think this is quic related.
Fixes #44
Trie-backed routing table, safe for concurrent use. Refresh capabilities will come with #45
Notes for follow up:
[]byte
~