api7 / lua-resty-radixtree

Adaptive Radix Trees implemented in Lua / LuaJIT
https://api7.ai/
Apache License 2.0
257 stars 61 forks source link

perf: add rax_tree_up() to iterate the routes tree #136

Closed haoyang1994 closed 9 months ago

haoyang1994 commented 1 year ago

As mentioned in #119 .

radix_tree_prev() has a poor performance when the routes raxTree is very large and the path to match can not be matched within the tree. Adding a new function rax_tree_up() to iterate the raxTree, which jumps to the parent node everytime instead of scanning all nodes smaller than the current in the tree.

Here is the benchmark results on my machine: Using rax_tree_up: resty -I=./lib -I=./deps/share/lua/5.1 benchmark/match-prefix.lua case 1: route matched matched res: 500 route count: 100000 match times: 1000 time used : 0.0010001659393311 sec QPS : 999834

case 2: route not matched matched res: route count: 100000 match times: 1000 time used : 0 sec QPS : inf

Using rax_tree_prev: resty -I=./lib -I=./deps/share/lua/5.1 benchmark/match-prefix.lua case 1: route matched matched res: 500 route count: 100000 match times: 1000 time used : 0 sec QPS : inf

case 2: route not matched matched res: route count: 100000 match times: 1000 time used : 3.4909999370575 sec QPS : 286

CLAassistant commented 1 year ago

CLA assistant check
All committers have signed the CLA.

monkeyDluffy6017 commented 1 year ago

Thanks for your contribution, we will check this pr later

membphis commented 9 months ago

@haoyang1994 I made a test with your PR, I got a better performance than before, thx for your contribution

pls sign the license/cla, then we can use CI to test your new code before we try to merge your code

haoyang1994 commented 9 months ago

@membphis Hi, this is my first time using CLA. Does this mean I have signed? But it looks that the CLA checking is still pending. image

membphis commented 9 months ago

still waiting for you sign

image
haoyang1994 commented 9 months ago

Hi @membphis, CLA's ready.

I mixed up email accounts, which resulted in the commits not being associated with my github account properly.