Rare project developers

[mc36 <>]

hi,

simon, jordi, thanks for the patricia tree, radix trie, whatsoever idea last 
time during the vc...
(both of you already in the http://www.freertr.net/greet.html so it was not 
updated for now:)

i just had some time playing with it, for now, just in the java and i have 
stuff:
https://github.com/mc36/freeRouter/commit/6f585a928a88679f781cfb1786d7ff60d9c0f080
it's two versions from the start, the v1 code uses the java's built-in 
treemap,
whereas v2 uses a simplified version exclusively from my own... the v2 
basically
follow this idea: 
https://www.lewuathe.com/longest-prefix-match-with-trie-tree.html

below are the test measures with both v1 and v2... the first column names the 
afi,
the next 3 columns are the raw mode get/find/lookup, the final 3 columns are 
the
after tree construction get/find/lpm... only the lpm method got altered for 
now,
so we have to concentrate to the rl and ol columns in both runs, as it shows 
the
effect... one can quickly notice that clns addresses perform way slowed 
compared
to the others, this is because the size of them... :) in average, the gain 
huge:

     |       v1        |       v2
ipv4 | 338983->2564102 | 342465->4761904
ipv6 | 303030->1923076 | 296735->2000000

as you can spot, v2 performs way better for ipv4 and a bit better for ipv6,
and nevertheless to say that it's much smaller code because the tree node
can have zero value and it have consequences: a bit higher memory usage
but much much easier node insertion and deletion, and ~deterministic lookup 
speed...

so for now, nothing left but doing the same to the p4emu codebase in pure c...

regards,
cs



-------------------------- v1:
sid#test routing raw opt
testing net.freertr.addr.addrClns-2048:  10000000 rg  751879 rf  112866 rl  
7142857 og  1315789 of  606060 ol
testing net.freertr.addr.addrIsis-48:  14285714 rg  1694915 rf  322580 rl  
14285714 og  2857142 of  2222222 ol
testing net.freertr.addr.addrEui-64:  16666666 rg  2777777 rf  308641 rl  
14285714 og  2439024 of  2000000 ol
testing net.freertr.addr.addrMac-48:  14285714 rg  2380952 rf  332225 rl  
14285714 og  2941176 of  2439024 ol
testing net.freertr.addr.addrIpx-80:  14285714 rg  2777777 rf  298507 rl  
14285714 og  2702702 of  2083333 ol
testing net.freertr.addr.addrIPv4-32:  14285714 rg  2941176 rf  338983 rl  
14285714 og  2631578 of  2564102 ol
testing net.freertr.addr.addrIPv6-128:  14285714 rg  2325581 rf  303030 rl  
14285714 og  2564102 of  1923076 ol
testing net.freertr.addr.addrIP-128:  14285714 rg  2500000 rf  305810 rl  
16666666 og  2777777 of  2272727 ol
sid#

-------------------------- v2:
sid#test routing raw opt
testing net.freertr.addr.addrClns-2048:  16666666 rg  1408450 rf  114678 rl  
16666666 og  1408450 of  173310 ol
testing net.freertr.addr.addrIsis-48:  14285714 rg  2777777 rf  291545 rl  
14285714 og  2631578 of  3703703 ol
testing net.freertr.addr.addrEui-64:  16666666 rg  2702702 rf  305810 rl  
14285714 og  2777777 of  2941176 ol
testing net.freertr.addr.addrMac-48:  16666666 rg  2857142 rf  333333 rl  
14285714 og  2857142 of  3846153 ol
testing net.freertr.addr.addrIpx-80:  16666666 rg  2173913 rf  280898 rl  
14285714 og  2702702 of  2500000 ol
testing net.freertr.addr.addrIPv4-32:  16666666 rg  2857142 rf  342465 rl  
14285714 og  2941176 of  4761904 ol
testing net.freertr.addr.addrIPv6-128:  14285714 rg  2857142 rf  303951 rl  
14285714 og  2777777 of  1960784 ol
testing net.freertr.addr.addrIP-128:  16666666 rg  2127659 rf  296735 rl  
14285714 og  2631578 of  2000000 ol
sid#