libbpf-bootstrap
libbpf-bootstrap copied to clipboard
examples/c: add hashing and naive substring search algo
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.