Rare project developers

[mc36 <>]

hi,

i'm done with the c stuff too, here it is:
https://github.com/mc36/freeRouter/blob/master/misc/native/tree.h

carmen, if you upgrade your dpdk router with the latest stuff
then imho you'll have wire speed not just v4 but on v6 too..
it would be nice to see once in a vc! :)

regards,
cs



On 12/29/21 10:18, mc36 wrote:
> 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#