Replace ndpi_strnstr() implementation with an optimal one

[0xA50C1A1]

Please sign (check) the below before submitting the Pull Request:

• [x] I have signed the ntop Contributor License Agreement at https://github.com/ntop/legal/blob/main/individual-contributor-licence-agreement.md
• [x] I have read the contributing guide lines at https://github.com/ntop/nDPI/blob/dev/CONTRIBUTING.md
• [x] I have updated the documentation (in doc/) to reflect the changes made (if applicable)

2433 #2439

Describe changes:

I apologize for the buggy implementation I suggested last time. This time, I simply took the already quite optimal ndpi_memmem() code and reworked it to handle null-terminated strings. This implementation shows better results in the benchmark, even with the strlen and strnlen calls inside. I've thoroughly tested it, and your unit tests are passing correctly.

Main changes:

• Efficient substring search: The new implementation utilizes memchr to quickly locate the first character of the needle substring within the haystack. This avoids unnecessary character comparisons, leading to better performance, especially for long strings.
• Early exit: If the remainder of haystack is shorter than needle, then there's no point in doing unnecessary comparisons.
• Single loop: The new version uses a single loop to search for the needle

@IvanNardi @utoni what do you think, guys?

[utoni]

@0xA50C1A1 Did you do any performance tests again? Can you please rebase to the current dev branch?

[0xA50C1A1]

@0xA50C1A1 Did you do any performance tests again? Can you please rebase to the current dev branch?

Yea, I did. At worst the performance is on par with the old implementation, at best it can be 8 times faster.

[0xA50C1A1]

@utoni @IvanNardi

Worst case:

Test case - Haystack length: 256, Needle length: 20
Average time for ndpi_strnstr: 23.7631 ns
Average time for ndpi_strnstr_opt: 24.0066 ns
ndpi_strnstr is 1.01025 times faster than ndpi_strnstr_opt

Best case:

Test case - Haystack length: 1088, Needle length: 25
Average time for ndpi_strnstr: 317.312 ns
Average time for ndpi_strnstr_opt: 36.6706 ns
ndpi_strnstr_opt is 8.65305 times faster than ndpi_strnstr

[sonarcloud[bot]]

Quality Gate passed

Issues
0 New issues
0 Accepted issues

Measures
0 Security Hotspots
No data about Coverage
No data about Duplication

See analysis details on SonarCloud