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

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

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

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

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

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

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

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 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

unbreak fbstring<wchar_t> default constructor (!!!)

Test Plan: folly/test/fbstring_test in debug mode

Reviewed By: sdoroshenko@fb.com

FB internal diff: D661622

Unbreak folly.

Summary: Extra '#' in there.

Test Plan: fbconfig nagios/plugins && fbmake opt

Reviewed By: carl.moran1@fb.com

FB internal diff: D660977

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

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

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

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

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 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:

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

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

Fix some clang compiler warnings/errors

Summary:
Fixes instances of the following problems:
error: offset of on non-POD type 'folly::fbstring_core<char>::RefCounted'
[-Werror,-Winvalid-offsetof]
Solution: Since the atomic is not a POD I used sizeof() instead to calculate
the offset

warning: C++11 requires lambda with omitted result type to consist of a single
return statement
Solution: Specify a return type

error: in-class initializer for static data member is not a constant expression
Solution: Move initializer

Test Plan: - Compiled folly and ran fbmake runtests

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D656963

Fix bug in Bits<T>::get / set

Summary:
Everything worked except for getting properly aligned full blocks
because 1ULL << 64 is invalid (the shift amount must be strictly less than
the value size in bits)

Test Plan: test added

Reviewed By: philipp@fb.com

FB internal diff: D657800

Silence -Wuninitialized in some cases

Test Plan: compiles

Reviewed By: philipp@fb.com

FB internal diff: D657623

folly::padded_sequence -> folly::padded

Summary: Mechanical.

Test Plan: fbconfig unicorn/test unicorn/diskindex3 unicorn/diskindex4/test common/datastruct:css_tree_test folly/test:padded_test dragon/test:posting_list_test && fbmake opt

Reviewed By: soren@fb.com

FB internal diff: D649539

Removing test code from `first`

Summary: TSIA

Test Plan: Unit tests

Reviewed By: kedarb@fb.com

FB internal diff: D652180

dummy results in stl_vector_test on gcc 4.6

Summary:
The test doesn't run when GCC < 4.7, however our test framework
needs some output anyways. I've added a placeholder test that does
nothing, but does cause something to be printed.

Test Plan: run fbmake runtests on folly/test/stl_tests/

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D652161

Add converter for containers of pairs

Summary:
Add specialized dynamic converter for containers of pairs,
which can convert from a list of pairs, or from a object

Test Plan: added a unit test

Reviewed By: njormrod@fb.com

FB internal diff: D650730

FBVector 2.0 - now standard compliant

Summary:
This is FBVector 2.0. It supports all of the original FBVector
optimizations and is standard compliant.
Accompanying this diff are two suites, StlVectorTest and Benchmark.
StlVectorTest runs an extensive battery of tests against a vector
implementation per the N3337 standard. In addition to checking normal
correctness, StlVectorTest checks the use of allocators, exception
safety, memory leaks, and type requirements.
Benchmark run a wide range of speed tests between std::vector, the
original fbvector, and the new fbvector.

Test Plan:
First test: run StlVectorTest.
Second test: run Benchmark.
Third test: compile and run some fbcode (e.g. multifeed/).

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D566719

Added two new traits and a way to specify them

Summary:
Added IsBits (has value semantics; can be copied by memcpy and
deleted by free. Implies IsRelocatable) and Is0Initializable (new (ptr)
T() is equivalent to memset(ptr, 0, sizeof(T))).
Converted the boost types for IsRelocatable to std types (now available
from <type_traits>).
Added a new way to specify IsRelocatable, IsBits, and Is0Initializable:
typedef std::true_type <property-name> in your class. No namespace
exiting required. This method also supports inheritance, and may be
overriden in base classes.
Added a test file to test Traits.

Test Plan:
Run new test file. Compile some real-world code (in my case,
multifeed).

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D610996

Fixing GENERATOR benchmark

Summary: I forgot fbmake runtests doesn't build all that's configured, oops.

Test Plan: Build folly/experimental/test, run benchmark.

Reviewed By: tudorb@fb.com

FB internal diff: D647191

fix GroupVarintDecoder::rest()

Summary:
It makes sense to return subpiece of the original data
from ##rest()##.

Test Plan: gv tests

Reviewed By: soren@fb.com

FB internal diff: D647179

Simplifying GENERATOR to be like ScopeGuard

Summary:
It was previously breaking any time a generator included a comma, which
is pretty stupid. Now, it's modelled after `ScopeGuard`, using a little operator
overloading to get rid of the trailing `)` and sidestepping preprocessor issues.

Test Plan: Unit tests

Reviewed By: tudorb@fb.com

FB internal diff: D646825

folly/PaddedSequence.h

Summary:
Code that aids in storing data aligned on block (possibly cache-line)
boundaries, perhaps with padding. There's class Node which represents one
block, and Iterator which, given an iterator to a container of Nodes, gives you
an iterator to the underlying elements.  There's also Adaptor, which converts a
sequence of Node into a sequence of underlying elements. (with enough
functionality to make it useful, although it's not fully STL compatible)

Split off from https://phabricator.fb.com/D641114

Also includes changes to make TypedIOBuf container-like so it can be used with padded_sequence::Adaptor.

I plan to rename this to Padded.h / folly::padded in a separate diff.

Test Plan: test added

Reviewed By: soren@fb.com

FB internal diff: D646249

tiny fbstring push_back(Char) optimization

Summary:
I noticed that push_back(Char) was slower for fbstring than
for std::string for long strings and found that I could make
it faster by inlining the call to mutable_data() and
exploit that it's always non-small and non-shared.

Benchmarks before:

./folly/test/FBStringTestBenchmarks.cpp.h       relative  time/iter  iters/s
BM_push_back_string(1)                                      69.42ns   14.41M
BM_push_back_string(23)                                    582.31ns    1.72M
BM_push_back_string(127)                                     1.47us  682.12K
BM_push_back_string(1024)                                    5.52us  181.07K
BM_push_back_fbstring(1)                                     9.55ns  104.74M
BM_push_back_fbstring(23)                                  212.45ns    4.71M
BM_push_back_fbstring(127)                                 864.00ns    1.16M
BM_push_back_fbstring(1024)                                  6.73us  148.52K

and after:

BM_push_back_fbstring(1)                                     9.55ns  104.74M
BM_push_back_fbstring(23)                                  212.45ns    4.71M
BM_push_back_fbstring(127)                                 783.08ns    1.28M
BM_push_back_fbstring(1024)                                  4.03us  248.05K

Test Plan: fbconfig folly/test && fbmake runtests

Reviewed By: tudorb@fb.com

FB internal diff: D646081

Added missing curly braces

Summary:
Added closing curly braces at 173.
Sorry, must make diff if it's a new commit.

Test Plan: nothing really

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D644925

Add samples to FBVector documentation

Summary: Added two samples of use for FBVector in docs

Test Plan: just check if FBVector.md looks good.

Reviewed By: njormrod@fb.com

FB internal diff: D636813

folly/stats - fix c++ spec compliance for call to template name

Summary:
This code is not strictly correct per c++ spec section 14.2.4:

> When the name of a member template specialization appears after . or -> in a
> postfix-expression or after a nested-name-specifier in a qualified-id, and the
> object or pointer expression of the postfix-expression or the
> nested-name-specifier in the qualified-id depends on a template parameter
> (14.6.2) but does not refer to a member of the current instantiation
> (14.6.2.1), the member template name must be prefixed by the keyword template.
> Otherwise the name is assumed to name a non-template.

This causes clang to complain, but gcc is lax about this, as usual.

Test Plan: compile stuff that use this.

Reviewed By: delong.j@fb.com

FB internal diff: D643515

folly/dynamic fix use of incomplete type in template definition

Summary:
the old code is ill-formed per spec (section 14.6.8):

> If a type used in a non-dependent name is incomplete at the point at which a
> template is defined but is complete at the point at which an instantiation is
> done, and if the completeness of that type affects whether or not the program
> is well-formed or affects the semantics of the program, the program is
> ill-formed; no diagnostic is required.

GCC is lax and allows this, clang gives an error.

Test Plan: compiles.

Reviewed By: delong.j@fb.com

FB internal diff: D643431

fix std::out_of_range calls to use real constructors

Summary:
curiously, std::out_of_range doesn't have a zero-argument constructor according
to the spec. This was causing issues in my clang setup...

Test Plan: compiles.

Reviewed By: delong.j@fb.com

FB internal diff: D643363

fix Traits.md

Test Plan: looked at the generated html in a browser

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D642998

Fix output of 128 bit integer to string conversion.

Summary:
Added specializations of folly::to<String> for __int128_t
and __uint128_t.

Test Plan: Added tests of the above to the integral to string tests.

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D636992

Add bytesUsed() to folly::Arena

Summary:
Returns number of bytes "really used by the user", i.e. number of bytes
allocated on the arena via calls to `allocate()`.

Test Plan: compiled, unit tests

Reviewed By: azzolini@fb.com

FB internal diff: D636976

Supressing GCC 4.7 warning for Optional

Summary:
Supressing the warning for GCC4.7, and supressing the error supressing
the warning in GCC4.6.

Test Plan: Compile, run unit tests on GCC4.6 and GCC4.7

Reviewed By: ldbrandy@fb.com

FB internal diff: D635982

use std::underlying_type to support enum classes

Summary:
Noticed these TODOs in Conv.h and decided to fix them.
Discovered that the underlying_type implementation also
covers enum classes, which didn't work with the pre-existing code.

Test Plan:
fbconfig -r folly --platform=gcc-4.7.1-glibc-2.14.1-fb
fbmake dbg _bin/folly/test/conv_test
_bin/folly/test/conv_test

--platform=gcc-4.6.2-glibc-2.13
fbmake dbg _bin/folly/test/conv_test
_bin/folly/test/conv_test

Reviewed By: tudorb@fb.com

FB internal diff: D634309

Fix IOBufQueue::preallocate for callers who really wanted a hard max

Summary: D633912 broke unicorn because it relied on preallocate having a hard max.  Add an optional hard max parameter and rename maxHint to newAllocationSize.  Pass the hard max in for unicorn

Test Plan: folly and unicorn unit tests

Reviewed By: tudorb@fb.com

FB internal diff: D634894

Return the maximum available space from IOBufQueue::preallocate

Summary: IOBufQueue::preallocate currently takes a min and max size, and will return to the caller a buffer with N writable bytes with min <= N <= max.  This is a bit wasteful, since there may be more than max bytes available at the end if the queue with no extra cost.  Now preallocate will return the full amount of contigious space to the caller, even if it is larger than the requested max.

Test Plan: folly and proxygen unit tests

Reviewed By: simpkins@fb.com

FB internal diff: D633912

add clone / insert methods

Summary:
cursor.clone() will clone a length of the chain.  insert(std::move(buf)) will splice in a length of chain
I want this to change thrift2 binary type to IOBuf: we will clone() the network data for zero-copy userspace data, and insert() it if the return value is a IOBuf.

Test Plan: added unittest

Reviewed By: afrind@fb.com

FB internal diff: D632073

add IOBuf::maybeCopyBuffer()

Summary:
Add a version of IOBuf::copyBuffer() which accepts a std::string, as
well as a maybeCopyBuffer() function which returns a null pointer if the
input string is empty.

In proxygen we have a few places where we construct an IOBuf from a
string configuration parameter, and we almost always want a null pointer
rather than an empty IOBuf chain if the string is empty.

Test Plan: Included unit tests for these new functions.

Reviewed By: tudorb@fb.com

FB internal diff: D630547

Removing unneeded eachAs() operators

Summary: ##byLine## already yields StringPieces, no neat to ##eachAs()## then.

Test Plan:
fbconfig folly/experimental/symbolizer folly/test folly/experimental/io folly/experimental/io/test tupperware/agent
fbmake opt

Reviewed By: tudorb@fb.com

FB internal diff: D630422

static constexpr in enclosing class + lambdas make compilers unhappy?

Test Plan: build

Reviewed By: dneiter@fb.com

FB internal diff: D630324

one more

Test Plan: build

Reviewed By: tjackson@fb.com

FB internal diff: D630280

fix ~File crash in debug mode

Test Plan: test added

Reviewed By: tjackson@fb.com

FB internal diff: D630163

unbreak build

Test Plan: build

Reviewed By: tjackson@fb.com

FB internal diff: D630266

Remove Stream

Summary:
Switch existing code to gen::byLine.  Also fix namespaces in
folly/experimental/(symbolizer|exception_tracer).

Test Plan:
fbconfig -r folly && fbmake runtests_opt, ran non-test folly
binaries by hand, fbgs for other uses (there aren't any)

Reviewed By: tjackson@fb.com

FB internal diff: D629576

split()

Summary: Normal split to complement resplit, and it's a bit faster than folly::split().

Test Plan: Unit tests, Benchmarks (result in code comment)

Reviewed By: tudorb@fb.com

FB internal diff: D629998

fix comments

Test Plan: no

Reviewed By: tjackson@fb.com

FB internal diff: D629502

add split operator

Summary:
Also added eachAs (cast each value as a given type) and eachTo (use folly::to
on each value)

Test Plan: test added

Reviewed By: tjackson@fb.com

FB internal diff: D628868

movify generators (but mostly operators)

Summary: Make things work with non-copyable generators.

Test Plan: folly/experimental/test

Reviewed By: tjackson@fb.com

FB internal diff: D628520

constexpr-ize folly/Bits.h

Summary:
Want to be able to call them from other constexpr functions
and from within static_assert()s.

Test Plan: compiled and ran folly tests

Reviewed By: tudorb@fb.com

FB internal diff: D627413

Fix example for folly::format

Summary: That's all.

Test Plan: .

Reviewed By: tjackson@fb.com

FB internal diff: D618824

Composed, for lightweight operator composition

Summary:
Sometimes it'll be handy to have a custom operator which is little more than the
composition of a few base operators. This makes that really easy to do, as shown
in examples, tests, and benchmarks.

Test Plan: Unit tests, benchmarks

Reviewed By: rsagula@fb.com

FB internal diff: D617152

Adding support for printing arbitrary pointers

Summary: We should be able to print ##Foo*##, even if we can't print ##Foo##.

Test Plan: Unit Tests.

Reviewed By: tudorb@fb.com

FB internal diff: D625977

Enabling format("{}", format(...))

Summary:
If your format string ends up being conditional, it's handy to be able to chain
together formatters.

Test Plan: Unit tests

Reviewed By: tudorb@fb.com

FB internal diff: D625502

add IOBuf::moveToFbString

Summary:
Convert a IOBuf chain into a fbstring, with zero copies in the common case
(unshared, unchained, no headroom) and one copy in all other cases.

Test Plan: tests added

Reviewed By: simpkins@fb.com

FB internal diff: D621210

Clang complains about errors in folly String-inl.h and FBString.h (P1825995)

Summary: fixing clang errors (used clang 3.1)

Test Plan: doh

Reviewed By: tudorb@fb.com

FB internal diff: D622593

Adding usage example for BENCHMARK_DRAW_LINE()

Summary:
Yes, I admit, I was dumb enough to try it in a benchmark's
body.

Test Plan: review

Reviewed By: tudorb@fb.com

FB internal diff: D622613

Augment DynamicConverter's is_container check

Summary:
DynamicConverter uses some simple heuristics to determine if a
class is a container. One of those tests was to check that the
constructor 'template <class Iterator> [container-name](Iterator first,
Iterator last)' was present. That test was performed by checking if the
class could be constructed by two parameters of some dummy class.

However, it is possible to restrict the template parameter such that it
only accepts iterators, and not any arbitrary dummy class. This would be
useful, for example, to solve overload ambiguity with constructors like
'vector(const T& val, size_type n)', where T and size_type are the same
(see N3337 23.2.3 item 14). It also (I believe) produces more meaningful
compiler errors when a non-iterator is supplied, since it errors at the
function callsite instead of inside the constructor itself.

The new FBVector implementation uses such a feature, and so checking for
[container-name](dummy, dummy) will fail. Hence the dummy class has been
upgraded to reverse_iterator<T*>, a valid iterator class which almost
certainly does not have a specialized contructor in any class (and hence
will not cause any visible change in class_is_container's value).

Test Plan:
Run DynamicConverterTest; it has tests for the correctness of
class_is_container.

Reviewed By: delong.j@fb.com

FB internal diff: D620607

ints used as flags (bitwise): so C

Summary:
Changed communicate() flags from int to a class.
Made Options and CommunicateFlags composable with |
Simplified API so you don't have to type Subprocess::Options().stdout(Subprocess::PIPE)

Test Plan: subprocess_test

Reviewed By: chip@fb.com

FB internal diff: D620186

Retry wait() on EINTR; clean up signal handling

Test Plan: subprocess_test

Reviewed By: delong.j@fb.com

FB internal diff: D619713

fix typos in comment; RV_* do not have to be public

Test Plan: subprocess_test

Reviewed By: chip@fb.com

FB internal diff: D619189

Subprocess library, modeled after python's subprocess module

Summary:
Surprised we don't have one.  The API is modeled after Python's
subprocess module, http://docs.python.org/2/library/subprocess.html

Inspired by
https://www.facebook.com/groups/fbcode/permalink/445399858830192/, plus
I needed this functionality now.

Test Plan: test added

Reviewed By: chip@fb.com

FB internal diff: D614056

[Conv] Remove __int128 overload

Summary: parseInt128 is only available for GCC 4.7 and above.

Test Plan: .

Reviewed By: igorzi@fb.com

FB internal diff: D618456

Blame Revision: rFBCODEeaec97e2991f

update function_benchmark to test exception handling

Summary:
Add benchmarks for throwing an exception versus returning
std::exception_ptr or other types of return values.

Throwing an exception is very expensive.  Calling std::make_exception_ptr()
without ever throwing is nearly as bad.

The exc_ptr_param_return tests were the ones I was most interested in.
(Accepting a std::exception_ptr* argument so the caller can indicate if they
want to receive an exception or not.)  This is fast if the caller doesn't care
about the exception value, but very slow if an error occurs and an
exception_ptr is required.

Test Plan:
======================================================================
folly/test/function_benchmark/main.cpp    relative  time/iter  iters/s
======================================================================
throw_exception                                        3.90us  256.25K
catch_no_exception                                     1.88ns  533.25M
return_exc_ptr                                         2.79us  357.85K
exc_ptr_param_return                                   2.83us  353.25K
exc_ptr_param_return_null                              2.25ns  444.38M
return_string                                         69.39ns   14.41M
return_string_noexcept                                69.39ns   14.41M
return_code                                            1.50ns  666.54M
return_code_noexcept                                   1.50ns  666.54M

Reviewed By: rajat@fb.com

FB internal diff: D616474

[Conv] MaxString specialization for __int128

Summary: Just that.

Test Plan: .

Reviewed By: igorzi@fb.com

FB internal diff: D613291

make folly::toJson retain non-ascii chars if encode_non_ascii is disabled

Summary:
folly::toJson as demonstrated by the test cases was wrongly encoding utf8 strings.
specifically, a utf8 char made up of x bytes was encodeded into x unicode chars.

for example, the char:
\u2665
which is made of 3 bytes:
\xe2\x99\xa5
was encoded correctly when using encode_non_ascii = true:
"\u2665"
but when encode_non_ascii = false, the json value was wrongly set as:
"\u00e2\u0099\u00a5"

because we use an signed char that wrongly detects non-readable chars with
ascii value > 127 as control chars with ascii value < 32 (\t, \n, etc.)

Test Plan: run the test

Reviewed By: delong.j@fb.com

FB internal diff: D612782

Optional bugfixes

Summary: Tests were run in 'opt', which masked issues alterted by asserts.

Test Plan: Unit tests

Reviewed By: delong.j@fb.com

FB internal diff: D611957

fixing double destruction of CSL::data_type

Summary:
the currently code calls both ~SkipListNode() and node->data_.~value_type()
causes double destructing the object.

Test Plan: adding dihde's testing code to a test case

Reviewed By: emailweixu@fb.com

FB internal diff: D612289

fix Benchmark docs

Summary: fix Benchmark docs

Test Plan: read

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D611820

folly::gen, or Comprehensions->Folly

Summary:
Moving Comprehensions library into Folly and refactoring its interface to be much more modular and composable. There are now two core abstractions:

# Generators: Standalone classes supporting ##apply()## and optionally ##foreach()##. These all inherit from ##GenImpl<T, Self>##.
# Operators: Standalone classes which, when composed with a generator, produce a new generator. These all inherit from ##OperatorImpl<Self>##.

These generators may be composed with ##operator|## overloads which only match ##const GenImpl<T, Self>&## on the left like ##gen | op##.  Additionally, generator may be consumed inline with ##gen | lambda## like ##gen | [](int x) { cout << x << endl; };##.

With this design, new operators may be added very simply without modifying the core library and templates are instantiated only exactly as needed.

Example:

```lang=cpp
auto sum = seq(1, 10) | filter(isPrime) | sum;
seq(1, 10) | [](int i) {
cout << i << endl;
};
```

Test Plan: Unit tests

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D542215

fbstring's front() and back() return by reference

Summary: C++11 added front() and back() that return by reference. fbstring also added front() and back() as non-standard convenience functions, which returned by value. This diff aligns fbstring with the standard.

Test Plan: added and ran unittest

Reviewed By: delong.j@fb.com

FB internal diff: D607574

Optional

Summary: Optional, like boost::optional, but with full rvalue support.

Test Plan: Unit tests

Reviewed By: delong.j@fb.com

FB internal diff: D571810

Add a folly::exceptionStr overload

Summary: For std::exception_ptr.

Test Plan: .

Reviewed By: davejwatson@fb.com

FB internal diff: D600345

Adding a general doc for traits provided in folly/Traits.h

Summary:
Understood how traits are implemented in folly/Traits.h and added
examples on how to use them.

Test Plan: no specific tests

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D546631

Add SpookyHashV2

Summary:
SpookyHashV2 is backwards incompatible with V1.  I renamed the existing
SpookyHash class to SpookyHashV1 (and fixed all uses); the new class is
called SpookyHashV2.

From http://burtleburtle.net/bob/hash/spooky.html:

Both V1 and V2 pass all the tests. V2 corrects two oversights in V1:

In the short hash, there was a d = length that should have been d += length,
which means some entropy got dropped on the floor. It passed the tests anyhow,
but fixing this probably means more distinct info from the message makes it
into the result.

The long hash always ended in mix()+end(), but only end() was needed. Removing
the extra call to mix() makes all long hashes faster by a small constant
amount.

Test Plan: test added; unicorn compiles

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D597173

Fix fbstring hash

Summary: '\0' may actually be part of string. We cannot assume its null terminated and should use another form of fnv32.

Test Plan: FBStringTest

Reviewed By: xliux@fb.com

FB internal diff: D595287

Just trying out one more combination

Summary:
It seems it is not std::bind which is slow but the construction of
std::function from std::bind that is slow.

Test Plan: ran benchmarks

Reviewed By: delong.j@fb.com

FB internal diff: D581967

Get total memory currently allocated by an Arena allocator

Summary: The Arena allocator knows how much memory it's using up, so create a function that allows clients to figure out how much it's using. Also create a unit test to sanity check this stuff.

Test Plan: folly/test/ArenaTest.cpp

Reviewed By: tudorb@fb.com

FB internal diff: D579399

folly/json: serialize \r and \n as \r and \n

Summary:
Background: we want to use folly::json but not change the way data is represented.
Since we need to store \r and \n in strings and the library we're currently using does this,
let's do it in folly too.

Test Plan: unit tests pass

Reviewed By: delong.j@fb.com

FB internal diff: D584960

Add DynamicConverters for const strings.

Summary: These are necessary for string-keyed maps, since maps const their keys.

Test Plan: I wrote a test.

Reviewed By: njormrod@fb.com

FB internal diff: D582283

Update folly/docs/Synchronized.md

Summary:
Fixed escaping bug where the `>` in `operator->` was
interpreted as starting a code block.  Folly github pull #15.

Test Plan: no

Reviewed By: njormrod@fb.com

FB internal diff: D582873

Add a FAQ item about dynamic strings

Summary:
After a conversation with njormrod I remembered why we didn't
do this.  Let's document it.

Test Plan: It's docs.

Reviewed By: njormrod@fb.com

FB internal diff: D582651

SpinLockArray

Summary:
Array of spinlocks where each one is padded to prevent false
sharing.

Useful for shard-based locking implementations in environments where
contention is unlikely.

Test Plan: ran tests in 'common'

Reviewed By: soren@fb.com

FB internal diff: D582149

Better unsigned to string conversion

Summary:
In https://phabricator.fb.com/D511928 Brian mentioned the current API for string append is insufficient for appending to a buffer. That made me curious about the relative performance of classic and table-based number to ASCII conversions.

The results were interesting as on the average (over all digit lengths) the table-based conversion was faster, but performance was lackluster (in the worst case half as fast as the classic implementation) for large numbers, I presume due to the cache misses incurred by the tables.

This diff proposes an improved unsigned-to-ASCII primitive that is much faster than both table-based (previous Folly) and classic primitive. The key is a fast digits10() implementation that precomputes the space required by the conversion. After that, the digits are issued in place, no more reverse required. The new routine is up to 14x faster than the classic implementation, depending on the number of digits (benchmarks in comments).

Adding a few people who may be interested in the matter. Brian, thanks for bringing this matter up; if this gets in you may want to use the folly routine in proxygen.

Test Plan: unittest and benchmarks.

Reviewed By: simpkins@fb.com

FB internal diff: D515572

Fix push_back() to shared fbstring bug.

Summary:
The following asserts:
fbstring str(1337, 'f');
fbstring cp = str;
cp.push_back('f');

This is problematic since ml_.capacity() != capacity() inside fbstring_core
for shared strings, which causes us not to un-share prior to push_back.

Test Plan: Existing tests, add unittest case.

Reviewed By: tudorb@fb.com

FB internal diff: D580267

folly: Range: implement find_first_of and optimize qfind(Range, char)

Summary:
implement ##find_first_of## and optimize ##Range.find(char)##

============================================================================
folly/test/RangeBenchmark.cpp                   relative  time/iter  iters/s
============================================================================
LongFindSingleCharDirect                                     2.76ms   362.63
LongFindSingleCharRange                           15.88%    17.37ms    57.58
ShortFindSingleCharDirect                                   53.41fs   18.72T
ShortFindSingleCharRange                           0.00%    29.22ns   34.22M
============================================================================

Test Plan:
- added new tests

- ran all folly tests

fbconfig -r folly/ && mkk runtests_opt

Reviewed By: tudorb@fb.com

FB internal diff: D576720

Syntactic sugar

Summary: This makes code easy to read for eyes used to unique/shared ptrs.

Test Plan: unit-tests

Reviewed By: delong.j@fb.com

FB internal diff: D575997

add pop_back to arrays

Summary: Add a pop_back() function to dynamic arrays.

Test Plan: - used it

Reviewed By: delong.j@fb.com

FB internal diff: D569440

folly/SmallLocks.h compiler warning

Summary: Couldn't get an HPHP extension to compile against this

Test Plan: compiled HPHP including folly/dynamic.h

Reviewed By: delong.j@fb.com

FB internal diff: D574364

Verbosify exception tracer dumps

Test Plan: by hand

Reviewed By: philipp@fb.com

FB internal diff: D570233

support -nan in conversion

Summary:
Folly supports -inf and nan but not -nan, instead it raised unexpected exceptions not handled in the upstream.

This diff is separated out from D569816 -- Diff1.

Test Plan: std::isnan(folly::to<double>(-nan))

Reviewed By: tudorb@fb.com

FB internal diff: D569939

Fix InpuByteStreamSplitter in debug mode.

Test Plan: stream_test, exception_tracer_test

Reviewed By: soren@fb.com

FB internal diff: D569476