Fixing find_first_of O(n) case
authorTom Jackson <tjackson@fb.com>
Wed, 4 Feb 2015 20:51:11 +0000 (12:51 -0800)
committerSara Golemon <sgolemon@fb.com>
Wed, 11 Feb 2015 02:01:59 +0000 (18:01 -0800)
commitc7e6c224e1ca2fa9e27344acce8fe156c3435ed0
tree5252fca0fb48e140f94581f8c92436b9beae70e9
parentf4acb30800ccd46c5ec7bd42d4627cc59accb841
Fixing find_first_of O(n) case

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
folly/Range.cpp
folly/test/RangeFindBenchmark.cpp
folly/test/RangeTest.cpp