[Perf|Hackathon] Save >=0.56% CPU time on home.php by improving string_find/strspn/strcspn
Summary:
string_find in zend_string.cpp used simple quadratic algorithm for finding
substring in a string. Replace it with optimized memmem() implementation
and make string_find CPU usage on home.php drop from 0.63% to 0.17%)
Avoid allocating memory for substring in f_strspn and f_strcspn and
improve their implementation by utilizing memchr(). These functions are
used mostly for tokenizing large inputs, most prominently in
XSSDetector, which is now 2x faster. The previous behavior was causing
its algorithm to be O(N^2), where N is the number of rendered HTML tags.
Result on home.php: f_strspn 0.10% -> 0.00%.
So, the total saving is 0.56% walltime, which is >= 0.56% CPU time.
Additionally, f_strcspn saves 0.91% CPU time on home.php for employees
(gatekeeped XSSDetector).
Since FBML parser also uses f_strcspn, it is expected that speedup of
FBML-based 3rd party apps will also be around 1%.
This function is also used by contact importer parsers. Affected contact
importer parsers should now be significantly faster for people with huge
contact lists.
Test Plan:
- tested current www in a sandbox compiled by both old and new version
- profiled using Google CPU profiler
- passes tests
Differential Revision: 216392
Reviewed By: qixin
Reviewers: qixin, qigao, myang, mwilliams
Commenters: mathewsb
CC: btrahan, mathewsb, qixin, amukherji, jan
Revert Plan:
OK