• Tom Jackson's avatar
    Fixing find_first_of O(n) case · c7e6c224
    Tom Jackson authored
    Summary:
    The `memchr()`-based `find_first_of()` behaves extremely badly when it's used in a loop and the input string doesn't contain all the needles. This was discovered when a reasonable line-breaking routine tried to use it to break lines by a mix of '\r' and '\n'. The entire remainder of the file was scanned each time a line was read.
    
    Before:
    
    ```
    CountDelimsBase                    1.26s   794.86m
    CountDelimsNoSSE         100.03%   1.26s   795.12m
    CountDelimsStd         40501.63%   3.11ms  321.93
    CountDelimsMemchr         98.31%   1.28s   781.41m
    CountDelimsByteSet     23162.41%   5.43ms  184.11
    ```
    
    After:
    
    ```
    CountDelimsBase                   3.20ms  312.08 <-- Base impl no longer considers memchr
    CountDelimsNoSSE         102.37%  3.13ms  319.47
    CountDelimsStd           103.19%  3.11ms  322.05
    CountDelimsMemchr          0.25%  1.27s   788.39m
    CountDelimsByteSet        59.68%  5.37ms  186.27
    ```
    
    Test Plan: Benchmarks
    
    Reviewed By: njormrod@fb.com
    
    Subscribers: folly-diffs@, yfeldblum
    
    FB internal diff: D1823536
    
    Signature: t1:1823536:1423081687:bb2ec8cdea477ee9b9c8d8ad2bfdecdc52657515
    c7e6c224
RangeTest.cpp 32.3 KB