libbpf-bootstrap icon indicating copy to clipboard operation
libbpf-bootstrap copied to clipboard

examples/c: add hashing and naive substring search algo

Open anakryiko opened this issue 9 months ago • 0 comments

Also benchmark it a little. Performance obviously will depend on haystack and needle strings and so on, but hashing implementation seems to be on par with naive implementation for short strings, but is getting relatively faster as strings become longer and/or pattern match happens further into the string.

E.g., for searching "ra" in "abracadabra" (end of short string):

substr-2084331 [012] ..... 2514091.887184: bpf_trace_printk: BENCH HASHED 156 ns/iter substr-2084331 [012] ..... 2514091.891784: bpf_trace_printk: BENCH NAIVE 183 ns/iter

For searching "eaba" in "abacabadabacabaeabacabadabacaba" (middle of longer string):

substr-2082624 [015] ..... 2514066.577106: bpf_trace_printk: BENCH HASHED 289 ns/iter substr-2082624 [015] ..... 2514066.588243: bpf_trace_printk: BENCH NAIVE 445 ns/iter

But searching all occurences of "a" inside "abracadabra" (almost immediate match in rather short string):

substr-2111313 [078] ..... 2514466.822019: bpf_trace_printk: BENCH HASHED 259 ns/iter substr-2111313 [078] ..... 2514466.827745: bpf_trace_printk: BENCH NAIVE 228 ns/iter

Overall, hashed variant seems best from practical point of view.

anakryiko avatar Mar 11 '25 21:03 anakryiko