Remove unnecessary branch in Range::find_first_of(Range,size_t)

Summary:
Added benchmarks.

Before:

folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
string length 10:
FindFirstOfRange                                             1.36ns  733.07M
FindFirstOfOffsetRange                                       2.15ns  464.16M
============================================================================
string length 256:
FindFirstOfRange                                             1.36ns  733.07M
FindFirstOfOffsetRange                                       1.42ns  704.22M
============================================================================
string length 10240:
FindFirstOfRange                                             1.36ns  733.07M
FindFirstOfOffsetRange                                       3.72ns  268.70M
============================================================================
string length 10485760:
FindFirstOfRange                                             1.36ns  733.07M
FindFirstOfOffsetRange                                       5.00ns  199.96M

After:

string length 10:
FindFirstOfRange                                             1.36ns  732.92M
FindFirstOfOffsetRange                                       1.36ns  732.61M
============================================================================
string length 256:
FindFirstOfRange                                             1.36ns  732.93M
FindFirstOfOffsetRange                                       1.38ns  727.16M
============================================================================
string length 10240:
FindFirstOfRange                                             1.36ns  732.93M
FindFirstOfOffsetRange                                       1.79ns  558.40M
============================================================================
string length 10485760:
FindFirstOfRange                                             1.36ns  732.93M
FindFirstOfOffsetRange                                       2.73ns  366.44M

Test Plan: fbconfig folly && fbmake runtests

Reviewed By: delong.j@fb.com

FB internal diff: D660125
trivial typo

Summary: I wouldn't even bother reporting this if github didn't make it so easy!

Test Plan: .

Reviewed By: soren@fb.com

FB internal diff: D660136
Make sure the op does not change the sign of the operand

Summary: .

Test Plan: .

Reviewed By: soren@fb.com

FB internal diff: D660143

Blame Revision:
Fixed a potential deadlock in folly::RWSpinLock

Summary:
The current UpgradedHolder implementation may lead to a deadlock when upgrading from a reader lock, because it is blocking.

A reader that has failed to set the UPGRADED bit may block the
winner (upgrader) that has successfully set the UPGRADED bit, while
waiting to upgrade in an infinite loop without releasing its own
reader lock. The upgrader needs to wait for all reader locks to be
released before it can move forward.

This is the code pattern:

{
ReadHolder reader(lock);
UpgradedHolder upgrader(std::move(reader));
WriteHolder writer(std::move(upgrader));
}

To avoid this to happen, removed UpgradedHolder(ReadHolder&&)
constructor and the function that impelments it
unlock_shared_and_lock_upgrade. This would require a programmer explicitly
release a read lock before acquiring an upgrade lock, therefore
avoid the above mentioned deadlock.

In addition, the current folly::RWSpinLock::try_lock_shared()
implementation does not check the UPGRADED bit at all. The UPGRADED bit can be used to avoid starving writers.  This diff fixed this by correctly checking the UPGRADED bit.

Test Plan:
Passed folly unit tests.
Tested in a Facebook service that uses the
folly::RWSpinLock::UpgradedHolder.

Reviewed By: xliux@fb.com

FB internal diff: D659875
Make dynamic::object callable with initializer lists

Summary:
Using perfect forwarding here prevents the ability to create
dynamic arrays.

Test Plan: Added unit test case that compiles now with this.

Reviewed By: tudorb@fb.com

FB internal diff: D660662
Make sure there is no signed int overflow

Summary: use proper type for index.

Test Plan: .

Reviewed By: tudorb@fb.com

FB internal diff: D660142
Fixed mistake with Makefile.am for spooky tests.

Summary: Tests not compiling due to a copy and paste error in Makefile.am.

Test Plan: .

Reviewed By: tudorb@fb.com

FB internal diff: D660138
Get rid of some gcc-ism's in Portability.h

Summary:
handle at least clang. It will be better to turn this into
configure check, though.

Test Plan: .

Reviewed By: tudorb@fb.com

FB internal diff: D660139
Unbreak folly.

Summary: Extra '#' in there.

Test Plan: fbconfig nagios/plugins && fbmake opt

Reviewed By: carl.moran1@fb.com

FB internal diff: D660977
unbreak fbstring<wchar_t> default constructor (!!!)

Test Plan: folly/test/fbstring_test in debug mode

Reviewed By: sdoroshenko@fb.com

FB internal diff: D661622
Make folly/fbstring test wchar compatible

Summary:
(This is a preliminary diff only)

Existing tests will be run again with a folly::basic_fbstring<wchar_t> object.

I have (temporarily) commented out tests that dont work yet.

Test Plan: Test code update only

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D669151
folly/comprehensions - fixing exceptions

Summary:
need to open up the visibility of std::exception, otherwise
try..catch(const std::exception& e) won't work for these cases.

Test Plan: unit tests from D670355

Reviewed By: delong.j@fb.com

FB internal diff: D670633
Make FindFirstOf[Offset]Range benchmarks traverse haystack.

Summary:
Doh. Thank you Mike for pointing this out.
Renamed "needle" to "needles" and added DCHECK to clarify the semantics.

Test Plan: Ran benchmark.

Reviewed By: mmcurtiss@fb.com

FB internal diff: D672154
fbstring: avoid including Likely.h

Summary:
Including Likely.h causes issues when import fbstring into
libstdc++, so provide internal definitions for these macros that
we can undef afterwards.

Test Plan: built folly

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D675366
Speed-up StringPiece::find_first_of()

Summary:
Wrote an SSE4.2-optimized version of find_first_of (>10x faster in
some cases).  For cases where SSE4.2 is not supported, rewrote
find_first_of to use Aho/Hopcroft/Ullman's "sparse, lazy" set (which
is faster than std::find_first_of in most cases).

Note that the overhead of ifunc (especially the lack of inlining)
means that the new implementations could be slightly slower for
super-tiny strings, but the inflection point is around 3-4 characters
in haystack, which seems reasonable.

Test Plan:
Added tests and benchmarks:

string length 1:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                         5.91ns  169.16M
FindSingleCharRange                              130.02%     4.55ns  219.95M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     11.37ns   87.98M
FindFirstOf2NeedlesNoSSE                         108.69%    10.46ns   95.63M
FindFirstOf2NeedlesStd                           147.04%     7.73ns  129.37M
FindFirstOf2NeedlesMemchr                         57.66%    19.71ns   50.73M
FindFirstOf2NeedlesByteSet                        83.32%    13.64ns   73.30M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     10.91ns   91.64M
FindFirstOf4NeedlesNoSSE                          88.87%    12.28ns   81.45M
FindFirstOf4NeedlesStd                           114.28%     9.55ns  104.73M
FindFirstOf4NeedlesMemchr                         34.77%    31.38ns   31.87M
FindFirstOf4NeedlesByteSet                        60.00%    18.19ns   54.98M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     10.91ns   91.64M
FindFirstOf8NeedlesNoSSE                          48.00%    22.73ns   43.99M
FindFirstOf8NeedlesStd                            54.54%    20.01ns   49.99M
FindFirstOf8NeedlesMemchr                         16.27%    67.06ns   14.91M
FindFirstOf8NeedlesByteSet                        39.99%    27.28ns   36.65M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    10.91ns   91.64M
FindFirstOf16NeedlesNoSSE                         33.33%    32.74ns   30.54M
FindFirstOf16NeedlesStd                           36.36%    30.01ns   33.32M
FindFirstOf16NeedlesMemchr                        10.25%   106.42ns    9.40M
FindFirstOf16NeedlesByteSet                       24.00%    45.46ns   22.00M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                    18.91ns   52.89M
FindFirstOf32NeedlesNoSSE                         21.00%    90.02ns   11.11M
FindFirstOf32NeedlesStd                           39.99%    47.28ns   21.15M
FindFirstOf32NeedlesMemchr                         8.48%   223.04ns    4.48M
FindFirstOf32NeedlesByteSet                       22.35%    84.60ns   11.82M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                    25.92ns   38.58M
FindFirstOf64NeedlesNoSSE                         17.45%   148.51ns    6.73M
FindFirstOf64NeedlesStd                           33.93%    76.39ns   13.09M
FindFirstOf64NeedlesMemchr                         6.07%   426.94ns    2.34M
FindFirstOf64NeedlesByteSet                       18.10%   143.22ns    6.98M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       23.28ns   42.95M
FindFirstOfRandomNoSSE                            88.96%    26.17ns   38.21M
FindFirstOfRandomStd                             112.78%    20.64ns   48.44M
FindFirstOfRandomMemchr                           35.68%    65.24ns   15.33M
FindFirstOfRandomByteSet                          62.62%    37.18ns   26.90M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      12.73ns   78.54M
----------------------------------------------------------------------------
============================================================================
string length 8:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                         7.05ns  141.75M
FindSingleCharRange                               50.05%    14.10ns   70.95M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     11.37ns   87.98M
FindFirstOf2NeedlesNoSSE                          53.04%    21.43ns   46.67M
FindFirstOf2NeedlesStd                            37.87%    30.01ns   33.32M
FindFirstOf2NeedlesMemchr                         54.81%    20.74ns   48.22M
FindFirstOf2NeedlesByteSet                        33.78%    33.65ns   29.72M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     10.91ns   91.64M
FindFirstOf4NeedlesNoSSE                          25.53%    42.74ns   23.40M
FindFirstOf4NeedlesStd                            24.49%    44.56ns   22.44M
FindFirstOf4NeedlesMemchr                         33.66%    32.42ns   30.85M
FindFirstOf4NeedlesByteSet                        28.57%    38.19ns   26.18M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     10.91ns   91.64M
FindFirstOf8NeedlesNoSSE                          21.05%    51.84ns   19.29M
FindFirstOf8NeedlesStd                            13.56%    80.48ns   12.43M
FindFirstOf8NeedlesMemchr                         17.32%    62.99ns   15.88M
FindFirstOf8NeedlesByteSet                        23.08%    47.28ns   21.15M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    10.91ns   91.64M
FindFirstOf16NeedlesNoSSE                         15.58%    70.02ns   14.28M
FindFirstOf16NeedlesStd                            7.23%   150.84ns    6.63M
FindFirstOf16NeedlesMemchr                         9.52%   114.63ns    8.72M
FindFirstOf16NeedlesByteSet                       16.67%    65.47ns   15.27M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                    18.91ns   52.89M
FindFirstOf32NeedlesNoSSE                         18.42%   102.62ns    9.74M
FindFirstOf32NeedlesStd                            7.08%   266.97ns    3.75M
FindFirstOf32NeedlesMemchr                         8.43%   224.41ns    4.46M
FindFirstOf32NeedlesByteSet                       19.29%    98.00ns   10.20M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                    25.92ns   38.58M
FindFirstOf64NeedlesNoSSE                         16.13%   160.73ns    6.22M
FindFirstOf64NeedlesStd                            4.58%   565.53ns    1.77M
FindFirstOf64NeedlesMemchr                         6.05%   428.22ns    2.34M
FindFirstOf64NeedlesByteSet                       16.58%   156.33ns    6.40M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       23.28ns   42.96M
FindFirstOfRandomNoSSE                            44.00%    52.91ns   18.90M
FindFirstOfRandomStd                              24.62%    94.56ns   10.58M
FindFirstOfRandomMemchr                           30.88%    75.38ns   13.27M
FindFirstOfRandomByteSet                          43.33%    53.72ns   18.62M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      12.73ns   78.54M
----------------------------------------------------------------------------
============================================================================
string length 10:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                         7.06ns  141.61M
FindSingleCharRange                               41.98%    16.82ns   59.44M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     11.37ns   87.98M
FindFirstOf2NeedlesNoSSE                          52.05%    21.84ns   45.79M
FindFirstOf2NeedlesStd                            31.25%    36.37ns   27.49M
FindFirstOf2NeedlesMemchr                         52.48%    21.66ns   46.17M
FindFirstOf2NeedlesByteSet                        29.07%    39.10ns   25.57M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     10.91ns   91.64M
FindFirstOf4NeedlesNoSSE                          28.93%    37.71ns   26.52M
FindFirstOf4NeedlesStd                            20.00%    54.57ns   18.33M
FindFirstOf4NeedlesMemchr                         30.39%    35.91ns   27.85M
FindFirstOf4NeedlesByteSet                        25.00%    43.65ns   22.91M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     10.91ns   91.64M
FindFirstOf8NeedlesNoSSE                          17.02%    64.12ns   15.60M
FindFirstOf8NeedlesStd                            11.16%    97.77ns   10.23M
FindFirstOf8NeedlesMemchr                         17.52%    62.30ns   16.05M
FindFirstOf8NeedlesByteSet                        25.00%    43.65ns   22.91M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    10.91ns   91.64M
FindFirstOf16NeedlesNoSSE                         16.28%    67.02ns   14.92M
FindFirstOf16NeedlesStd                            5.98%   182.32ns    5.48M
FindFirstOf16NeedlesMemchr                         9.09%   120.06ns    8.33M
FindFirstOf16NeedlesByteSet                       17.65%    61.84ns   16.17M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                    19.10ns   52.36M
FindFirstOf32NeedlesNoSSE                         17.91%   106.63ns    9.38M
FindFirstOf32NeedlesStd                            5.79%   329.70ns    3.03M
FindFirstOf32NeedlesMemchr                         7.89%   241.91ns    4.13M
FindFirstOf32NeedlesByteSet                       18.92%   100.95ns    9.91M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                    26.15ns   38.24M
FindFirstOf64NeedlesNoSSE                         15.84%   165.05ns    6.06M
FindFirstOf64NeedlesStd                            3.71%   704.28ns    1.42M
FindFirstOf64NeedlesMemchr                         5.49%   476.63ns    2.10M
FindFirstOf64NeedlesByteSet                       16.48%   158.68ns    6.30M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       22.83ns   43.81M
FindFirstOfRandomNoSSE                            43.25%    52.78ns   18.95M
FindFirstOfRandomStd                              22.33%   102.23ns    9.78M
FindFirstOfRandomMemchr                           31.61%    72.23ns   13.85M
FindFirstOfRandomByteSet                          41.64%    54.82ns   18.24M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      12.73ns   78.54M
----------------------------------------------------------------------------
============================================================================
string length 16:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                         7.06ns  141.72M
FindSingleCharRange                               28.21%    25.01ns   39.98M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     15.91ns   62.84M
FindFirstOf2NeedlesNoSSE                          72.89%    21.84ns   45.80M
FindFirstOf2NeedlesStd                            28.68%    55.48ns   18.02M
FindFirstOf2NeedlesMemchr                         74.47%    21.37ns   46.79M
FindFirstOf2NeedlesByteSet                        23.34%    68.19ns   14.66M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     15.46ns   64.68M
FindFirstOf4NeedlesNoSSE                          40.77%    37.92ns   26.37M
FindFirstOf4NeedlesStd                            18.28%    84.59ns   11.82M
FindFirstOf4NeedlesMemchr                         42.97%    35.97ns   27.80M
FindFirstOf4NeedlesByteSet                        25.76%    60.02ns   16.66M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     15.46ns   64.68M
FindFirstOf8NeedlesNoSSE                          24.03%    64.34ns   15.54M
FindFirstOf8NeedlesStd                             9.74%   158.74ns    6.30M
FindFirstOf8NeedlesMemchr                         24.55%    62.98ns   15.88M
FindFirstOf8NeedlesByteSet                        28.33%    54.57ns   18.33M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    15.46ns   64.68M
FindFirstOf16NeedlesNoSSE                         19.83%    77.98ns   12.82M
FindFirstOf16NeedlesStd                            5.56%   277.82ns    3.60M
FindFirstOf16NeedlesMemchr                        12.95%   119.35ns    8.38M
FindFirstOf16NeedlesByteSet                       21.25%    72.75ns   13.75M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                    32.80ns   30.49M
FindFirstOf32NeedlesNoSSE                         27.86%   117.69ns    8.50M
FindFirstOf32NeedlesStd                            6.33%   517.97ns    1.93M
FindFirstOf32NeedlesMemchr                        13.72%   239.09ns    4.18M
FindFirstOf32NeedlesByteSet                       29.06%   112.85ns    8.86M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                    46.83ns   21.35M
FindFirstOf64NeedlesNoSSE                         26.68%   175.50ns    5.70M
FindFirstOf64NeedlesStd                            4.20%     1.11us  897.48K
FindFirstOf64NeedlesMemchr                        10.04%   466.39ns    2.14M
FindFirstOf64NeedlesByteSet                       27.47%   170.50ns    5.87M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       23.41ns   42.72M
FindFirstOfRandomNoSSE                            38.00%    61.61ns   16.23M
FindFirstOfRandomStd                              13.91%   168.34ns    5.94M
FindFirstOfRandomMemchr                           29.03%    80.64ns   12.40M
FindFirstOfRandomByteSet                          33.31%    70.28ns   14.23M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      15.12ns   66.15M
----------------------------------------------------------------------------
============================================================================
string length 32:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                         8.23ns  121.52M
FindSingleCharRange                               17.57%    46.83ns   21.35M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     20.46ns   48.88M
FindFirstOf2NeedlesNoSSE                          82.29%    24.86ns   40.22M
FindFirstOf2NeedlesStd                            17.69%   115.65ns    8.65M
FindFirstOf2NeedlesMemchr                         85.17%    24.02ns   41.63M
FindFirstOf2NeedlesByteSet                        28.19%    72.58ns   13.78M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     20.01ns   49.99M
FindFirstOf4NeedlesNoSSE                          48.57%    41.19ns   24.28M
FindFirstOf4NeedlesStd                            11.52%   173.72ns    5.76M
FindFirstOf4NeedlesMemchr                         50.55%    39.58ns   25.27M
FindFirstOf4NeedlesByteSet                        26.33%    75.99ns   13.16M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     20.01ns   49.99M
FindFirstOf8NeedlesNoSSE                          26.94%    74.27ns   13.46M
FindFirstOf8NeedlesStd                             6.73%   297.31ns    3.36M
FindFirstOf8NeedlesMemchr                         27.44%    72.90ns   13.72M
FindFirstOf8NeedlesByteSet                        23.91%    83.66ns   11.95M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    20.01ns   49.99M
FindFirstOf16NeedlesNoSSE                         18.37%   108.92ns    9.18M
FindFirstOf16NeedlesStd                            3.75%   532.80ns    1.88M
FindFirstOf16NeedlesMemchr                        14.53%   137.71ns    7.26M
FindFirstOf16NeedlesByteSet                       19.55%   102.32ns    9.77M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                    45.92ns   21.78M
FindFirstOf32NeedlesNoSSE                         31.17%   147.32ns    6.79M
FindFirstOf32NeedlesStd                            4.50%     1.02us  980.43K
FindFirstOf32NeedlesMemchr                        16.13%   284.64ns    3.51M
FindFirstOf32NeedlesByteSet                       32.63%   140.73ns    7.11M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                    68.20ns   14.66M
FindFirstOf64NeedlesNoSSE                         29.97%   227.55ns    4.39M
FindFirstOf64NeedlesStd                            3.08%     2.21us  452.08K
FindFirstOf64NeedlesMemchr                        12.51%   545.17ns    1.83M
FindFirstOf64NeedlesByteSet                       30.74%   221.86ns    4.51M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       29.99ns   33.35M
FindFirstOfRandomNoSSE                            45.10%    66.49ns   15.04M
FindFirstOfRandomStd                              10.28%   291.67ns    3.43M
FindFirstOfRandomMemchr                           34.56%    86.76ns   11.53M
FindFirstOfRandomByteSet                          28.64%   104.72ns    9.55M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      19.55ns   51.15M
----------------------------------------------------------------------------
============================================================================
string length 64:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                        10.91ns   91.65M
FindSingleCharRange                               13.26%    82.29ns   12.15M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     29.56ns   33.83M
FindFirstOf2NeedlesNoSSE                         100.77%    29.33ns   34.09M
FindFirstOf2NeedlesStd                            13.59%   217.44ns    4.60M
FindFirstOf2NeedlesMemchr                        104.83%    28.19ns   35.47M
FindFirstOf2NeedlesByteSet                        22.01%   134.28ns    7.45M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     29.10ns   34.36M
FindFirstOf4NeedlesNoSSE                          56.14%    51.84ns   19.29M
FindFirstOf4NeedlesStd                             8.72%   333.84ns    3.00M
FindFirstOf4NeedlesMemchr                         58.18%    50.02ns   19.99M
FindFirstOf4NeedlesByteSet                        19.73%   147.48ns    6.78M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     29.10ns   34.36M
FindFirstOf8NeedlesNoSSE                          30.48%    95.48ns   10.47M
FindFirstOf8NeedlesStd                             5.07%   573.76ns    1.74M
FindFirstOf8NeedlesMemchr                         30.92%    94.11ns   10.63M
FindFirstOf8NeedlesByteSet                        19.26%   151.13ns    6.62M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    29.10ns   34.36M
FindFirstOf16NeedlesNoSSE                         15.84%   183.68ns    5.44M
FindFirstOf16NeedlesStd                            2.79%     1.04us  959.63K
FindFirstOf16NeedlesMemchr                        16.04%   181.41ns    5.51M
FindFirstOf16NeedlesByteSet                       16.54%   175.95ns    5.68M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                    73.21ns   13.66M
FindFirstOf32NeedlesNoSSE                         32.76%   223.49ns    4.47M
FindFirstOf32NeedlesStd                            3.62%     2.02us  494.08K
FindFirstOf32NeedlesMemchr                        19.49%   375.70ns    2.66M
FindFirstOf32NeedlesByteSet                       33.45%   218.87ns    4.57M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                   109.95ns    9.09M
FindFirstOf64NeedlesNoSSE                         38.99%   282.01ns    3.55M
FindFirstOf64NeedlesStd                            2.49%     4.41us  226.78K
FindFirstOf64NeedlesMemchr                        15.21%   723.03ns    1.38M
FindFirstOf64NeedlesByteSet                       39.68%   277.13ns    3.61M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       40.57ns   24.65M
FindFirstOfRandomNoSSE                            47.65%    85.15ns   11.74M
FindFirstOfRandomStd                               7.62%   532.10ns    1.88M
FindFirstOfRandomMemchr                           39.23%   103.43ns    9.67M
FindFirstOfRandomByteSet                          22.95%   176.82ns    5.66M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      28.65ns   34.91M
----------------------------------------------------------------------------
============================================================================
string length 128:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                        16.37ns   61.09M
FindSingleCharRange                               11.62%   140.85ns    7.10M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     47.74ns   20.95M
FindFirstOf2NeedlesNoSSE                         118.64%    40.24ns   24.85M
FindFirstOf2NeedlesStd                            11.33%   421.18ns    2.37M
FindFirstOf2NeedlesMemchr                        120.68%    39.56ns   25.28M
FindFirstOf2NeedlesByteSet                        21.47%   222.36ns    4.50M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     47.28ns   21.15M
FindFirstOf4NeedlesNoSSE                          63.80%    74.11ns   13.49M
FindFirstOf4NeedlesStd                             7.23%   653.94ns    1.53M
FindFirstOf4NeedlesMemchr                         65.40%    72.30ns   13.83M
FindFirstOf4NeedlesByteSet                        19.96%   236.85ns    4.22M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     47.28ns   21.15M
FindFirstOf8NeedlesNoSSE                          33.87%   139.59ns    7.16M
FindFirstOf8NeedlesStd                             4.20%     1.13us  887.82K
FindFirstOf8NeedlesMemchr                         34.43%   137.32ns    7.28M
FindFirstOf8NeedlesByteSet                        18.98%   249.17ns    4.01M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    47.28ns   21.15M
FindFirstOf16NeedlesNoSSE                         16.83%   281.00ns    3.56M
FindFirstOf16NeedlesStd                            2.30%     2.06us  485.36K
FindFirstOf16NeedlesMemchr                        16.98%   278.50ns    3.59M
FindFirstOf16NeedlesByteSet                       15.75%   300.13ns    3.33M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                   128.45ns    7.79M
FindFirstOf32NeedlesNoSSE                         37.09%   346.28ns    2.89M
FindFirstOf32NeedlesStd                            3.19%     4.03us  248.02K
FindFirstOf32NeedlesMemchr                        23.13%   555.26ns    1.80M
FindFirstOf32NeedlesByteSet                       37.74%   340.32ns    2.94M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                   193.23ns    5.18M
FindFirstOf64NeedlesNoSSE                         47.76%   404.60ns    2.47M
FindFirstOf64NeedlesStd                            2.20%     8.80us  113.61K
FindFirstOf64NeedlesMemchr                        17.91%     1.08us  926.70K
FindFirstOf64NeedlesByteSet                       48.35%   399.64ns    2.50M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       59.66ns   16.76M
FindFirstOfRandomNoSSE                            53.67%   111.17ns    9.00M
FindFirstOfRandomStd                               6.41%   930.67ns    1.07M
FindFirstOfRandomMemchr                           46.01%   129.68ns    7.71M
FindFirstOfRandomByteSet                          19.80%   301.38ns    3.32M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      46.83ns   21.35M
----------------------------------------------------------------------------
============================================================================
string length 256:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                        27.28ns   36.65M
FindSingleCharRange                               10.62%   256.90ns    3.89M
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                     61.39ns   16.29M
FindFirstOf2NeedlesNoSSE                          99.28%    61.84ns   16.17M
FindFirstOf2NeedlesStd                             7.41%   828.62ns    1.21M
FindFirstOf2NeedlesMemchr                        100.01%    61.39ns   16.29M
FindFirstOf2NeedlesByteSet                        15.36%   399.65ns    2.50M
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                     83.65ns   11.95M
FindFirstOf4NeedlesNoSSE                          71.03%   117.77ns    8.49M
FindFirstOf4NeedlesStd                             6.46%     1.29us  772.77K
FindFirstOf4NeedlesMemchr                         72.14%   115.95ns    8.62M
FindFirstOf4NeedlesByteSet                        20.66%   404.81ns    2.47M
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                     83.66ns   11.95M
FindFirstOf8NeedlesNoSSE                          35.38%   236.46ns    4.23M
FindFirstOf8NeedlesStd                             3.75%     2.23us  447.99K
FindFirstOf8NeedlesMemchr                         35.71%   234.26ns    4.27M
FindFirstOf8NeedlesByteSet                        20.13%   415.56ns    2.41M
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                    83.66ns   11.95M
FindFirstOf16NeedlesNoSSE                         18.04%   463.82ns    2.16M
FindFirstOf16NeedlesStd                            2.04%     4.10us  244.06K
FindFirstOf16NeedlesMemchr                        18.14%   461.09ns    2.17M
FindFirstOf16NeedlesByteSet                       14.81%   564.87ns    1.77M
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                   237.14ns    4.22M
FindFirstOf32NeedlesNoSSE                         38.92%   609.24ns    1.64M
FindFirstOf32NeedlesStd                            2.95%     8.05us  124.26K
FindFirstOf32NeedlesMemchr                        25.90%   915.44ns    1.09M
FindFirstOf32NeedlesByteSet                       39.21%   604.86ns    1.65M
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                   360.78ns    2.77M
FindFirstOf64NeedlesNoSSE                         54.03%   667.71ns    1.50M
FindFirstOf64NeedlesStd                            2.05%    17.59us   56.86K
FindFirstOf64NeedlesMemchr                        20.04%     1.80us  555.45K
FindFirstOf64NeedlesByteSet                       54.61%   660.63ns    1.51M
----------------------------------------------------------------------------
FindFirstOfRandomBase                                       98.24ns   10.18M
FindFirstOfRandomNoSSE                            47.37%   207.40ns    4.82M
FindFirstOfRandomStd                               5.24%     1.88us  533.28K
FindFirstOfRandomMemchr                           39.75%   247.14ns    4.05M
FindFirstOfRandomByteSet                          17.69%   555.45ns    1.80M
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                      62.75ns   15.94M
----------------------------------------------------------------------------
============================================================================
string length 10240:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                       613.80ns    1.63M
FindSingleCharRange                                6.57%     9.34us  107.12K
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                      1.23us  813.01K
FindFirstOf2NeedlesNoSSE                         100.01%     1.23us  813.07K
FindFirstOf2NeedlesStd                             3.77%    32.61us   30.67K
FindFirstOf2NeedlesMemchr                        100.08%     1.23us  813.67K
FindFirstOf2NeedlesByteSet                         8.65%    14.21us   70.37K
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                      2.94us  340.63K
FindFirstOf4NeedlesNoSSE                         119.61%     2.45us  407.44K
FindFirstOf4NeedlesStd                             5.73%    51.23us   19.52K
FindFirstOf4NeedlesMemchr                        119.77%     2.45us  407.97K
FindFirstOf4NeedlesByteSet                        20.66%    14.21us   70.38K
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                      2.94us  340.63K
FindFirstOf8NeedlesNoSSE                          59.95%     4.90us  204.21K
FindFirstOf8NeedlesStd                             3.32%    88.48us   11.30K
FindFirstOf8NeedlesMemchr                         59.96%     4.90us  204.25K
FindFirstOf8NeedlesByteSet                        20.68%    14.20us   70.43K
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                     2.94us  340.63K
FindFirstOf16NeedlesNoSSE                         29.98%     9.79us  102.13K
FindFirstOf16NeedlesStd                            1.80%   162.97us    6.14K
FindFirstOf16NeedlesMemchr                        29.98%     9.79us  102.11K
FindFirstOf16NeedlesByteSet                       20.65%    14.22us   70.33K
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                     8.77us  114.07K
FindFirstOf32NeedlesNoSSE                         44.71%    19.61us   51.00K
FindFirstOf32NeedlesStd                            2.73%   321.22us    3.11K
FindFirstOf32NeedlesMemchr                        43.44%    20.18us   49.55K
FindFirstOf32NeedlesByteSet                       44.67%    19.63us   50.95K
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                    13.43us   74.44K
FindFirstOf64NeedlesNoSSE                         68.26%    19.68us   50.81K
FindFirstOf64NeedlesStd                            1.91%   702.62us    1.42K
FindFirstOf64NeedlesMemchr                        33.81%    39.74us   25.17K
FindFirstOf64NeedlesByteSet                       68.25%    19.68us   50.81K
----------------------------------------------------------------------------
FindFirstOfRandomBase                                        3.01us  331.81K
FindFirstOfRandomNoSSE                            75.38%     4.00us  250.10K
FindFirstOfRandomStd                               6.81%    44.25us   22.60K
FindFirstOfRandomMemchr                           76.46%     3.94us  253.71K
FindFirstOfRandomByteSet                          15.01%    20.08us   49.81K
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                       1.23us  811.29K
----------------------------------------------------------------------------
============================================================================
string length 1048576:
============================================================================
folly/test/RangeFindBenchmark.cpp               relative  time/iter  iters/s
============================================================================
FindSingleCharMemchr                                        85.07us   11.76K
FindSingleCharRange                                8.92%   953.48us    1.05K
----------------------------------------------------------------------------
FindFirstOf2NeedlesBase                                    170.23us    5.87K
FindFirstOf2NeedlesNoSSE                         100.01%   170.21us    5.87K
FindFirstOf2NeedlesStd                             5.09%     3.34ms   299.18
FindFirstOf2NeedlesMemchr                        100.02%   170.20us    5.88K
FindFirstOf2NeedlesByteSet                        11.64%     1.46ms   683.69
----------------------------------------------------------------------------
FindFirstOf4NeedlesBase                                    298.04us    3.36K
FindFirstOf4NeedlesNoSSE                          87.48%   340.68us    2.94K
FindFirstOf4NeedlesStd                             5.68%     5.25ms   190.41
FindFirstOf4NeedlesMemchr                         87.53%   340.51us    2.94K
FindFirstOf4NeedlesByteSet                        20.37%     1.46ms   683.55
----------------------------------------------------------------------------
FindFirstOf8NeedlesBase                                    298.04us    3.36K
FindFirstOf8NeedlesNoSSE                          43.75%   681.27us    1.47K
FindFirstOf8NeedlesStd                             3.29%     9.07ms   110.24
FindFirstOf8NeedlesMemchr                         43.74%   681.36us    1.47K
FindFirstOf8NeedlesByteSet                        20.37%     1.46ms   683.55
----------------------------------------------------------------------------
FindFirstOf16NeedlesBase                                   298.03us    3.36K
FindFirstOf16NeedlesNoSSE                         21.83%     1.37ms   732.40
FindFirstOf16NeedlesStd                            1.78%    16.72ms    59.81
FindFirstOf16NeedlesMemchr                        21.83%     1.37ms   732.49
FindFirstOf16NeedlesByteSet                       20.37%     1.46ms   683.60
----------------------------------------------------------------------------
FindFirstOf32NeedlesBase                                   896.95us    1.11K
FindFirstOf32NeedlesNoSSE                         44.21%     2.03ms   492.89
FindFirstOf32NeedlesStd                            2.67%    33.53ms    29.82
FindFirstOf32NeedlesMemchr                        31.84%     2.82ms   354.97
FindFirstOf32NeedlesByteSet                       44.25%     2.03ms   493.31
----------------------------------------------------------------------------
FindFirstOf64NeedlesBase                                     1.38ms   725.72
FindFirstOf64NeedlesNoSSE                         67.96%     2.03ms   493.18
FindFirstOf64NeedlesStd                            1.90%    72.34ms    13.82
FindFirstOf64NeedlesMemchr                        24.82%     5.55ms   180.11
FindFirstOf64NeedlesByteSet                       67.97%     2.03ms   493.30
----------------------------------------------------------------------------
FindFirstOfRandomBase                                      657.10us    1.52K
FindFirstOfRandomNoSSE                            31.60%     2.08ms   480.94
FindFirstOfRandomStd                               2.05%    32.07ms    31.18
FindFirstOfRandomMemchr                           24.06%     2.73ms   366.13
FindFirstOfRandomByteSet                          31.56%     2.08ms   480.22
----------------------------------------------------------------------------
FindFirstOfOffsetRange                                     170.28us    5.87K
----------------------------------------------------------------------------
============================================================================

Reviewed By: philipp@fb.com

FB internal diff: D638500
Remove some unnecessary uses of LOG(FATAL) in folly

Summary:
ScopeGuard::execute will already call std::terminate if an
exception is thrown, as it's noexcept, and the case in
ConcurrentSkipList should be a check.

Test Plan:
Ran folly tests.  Will look at phabricator to see if
anything breaks downstream from removing glog/logging.h from
scopeguard.

Reviewed By: chip@fb.com

FB internal diff: D677038
Create a benchmark for ProducerConsumerQueue

Summary: This is a basic benchmark harness for testing ProducerConsumerQueue, which tests a single producer/consumer pair with and without CPU affinity set.  The change to ProducerConsumerQueue.h (not for committing) tests the effect of cache-aligning the read and write indices to reduce false sharing.

Test Plan: Run the benchmark with the cache alignment (un)commented.

Reviewed By: rituraj@fb.com

FB internal diff: D665948
graduate IOBuf out of folly/experimental

Summary: Move IOBuf and related code to folly/io.

Test Plan: fbconfig -r folly && fbmake runtests_opt, fbconfig unicorn/test && fbmake opt

Reviewed By: andrewcox@fb.com

FB internal diff: D678331
fix some of the warning/errors clang 3.1 reports

Summary: One step closer to build folly with clang

Test Plan:
fbconfig -r folly && fbmake opt -j32

to make sure gcc is still able to compile it

Reviewed By: tudorb@fb.com

FB internal diff: D677716
fix some of the warning/errors clang 3.1 reports - 2

Test Plan:
fbconfig -r folly && fbmake opt -j32

to make sure gcc is still able to compile it

Reviewed By: tudorb@fb.com

FB internal diff: D678500