remove folly/eventfd.h

Test Plan: compile: fbconfig folly/experimental/io/test thrift/test unicorn/io/test common/system_features common/concurrency && fbmake opt

Reviewed By: soren@fb.com

FB internal diff: D753552

Remove an unused variable in FormatValue<double>

Test Plan: Built a program that uses it

Reviewed By: tudorb@fb.com

FB internal diff: D753460

make sse4.2 functions in folly/Range.h build on -fb platform

Test Plan: fbconfig --platform=gcc-4.7.1-glibc-2.14.1-fb folly/test && fbmake runtests_opt

Reviewed By: oyamauchi@fb.com

FB internal diff: D749992

fix clang warnings in folly::Gen

Summary: Two clang warnings. It wants user defined consturctor for static initialization, and it wants fwd-declare to agree with full decleration in regards to struct v class.

Test Plan:
`fbconfig --clang --platform=gcc-4.7.1-glibc-2.14.1 folly/test/`

And make sure it doesn't break normal build.

Reviewed By: tulloch@fb.com

FB internal diff: D749857

Add read/write mode to ElfFile

Summary:
- Add a mode to ElfFile that allows opening the file for read/write
access via PROT_WRITE.

Test Plan:
- Used it in some other code

Reviewed By: simpkins@fb.com

FB internal diff: D740184

Handle non-Intel platforms in Range and CpuId

Summary:
Compile out the SSE versions of these functions in Range, based on a new
entry in folly-config.h.

The change to CpuId feels slightly iffy to me. It seems like it would be
more rigorous to make compiling CpuId.h on non-Intel an error, and force
clients to handle non-Intel platforms at the callsite. However, I think
that would be too susceptible to unintentional breakage on non-Intel
platforms, since most people (including automated systems) aren't
building and testing regularly on any. Falling back to saying "none of
these features exist on this processor" seems like a reasonable
alternative.

Test Plan:
fbmake runtests, with FOLLY_HAVE_EMMINTRIN_H set to 0 and 1.
Make sure the SSE functions are getting compiled in or out as
appropriate. ##autoreconf## and ##./configure## to regenerate
folly-config.h.

Reviewed By: delong.j@fb.com

FB internal diff: D746872

Add symbol name resolution and value retrieval

Summary:
- Add ElfFile::getSymbolByName(), which finds a Symbol object
corresponding to the symbol w/ the given name
- Add ElfFile::getSymbolValue(), which resolves the Symbol object to a
value in the mapped file, following pointers if necessary

Test Plan: - Unit tests

Reviewed By: simpkins@fb.com

FB internal diff: D740183

Enable Elf::at<T> only for POD data types

Summary:
- Make sure that the utility function Elf::at<T> only works for POD
datatypes, as it uses reinterpret_cast<T>.

Test Plan: - Unit tests

Reviewed By: simpkins@fb.com

FB internal diff: D748314

Move folly::symbolizer::systemError() into Exception.h

Summary:
- This is pretty similar to some stuff that we already have in
Exception.h. Move (and rename) it.

Test Plan: - Unit tests

Reviewed By: simpkins@fb.com

FB internal diff: D748313

Compile out GroupVarint on non-Intel

Summary:
Compile out instead of erroring.

In an ideal world, we'd have a fallback that would work across platforms
(i.e. no SSE, no unaligned 32-bit writes etc.) and compile some version
of GroupVarint in all environments. I actually tried this; the SSE stuff
is all behind #if __SSSE3__ already, so I thought it could work (modulo
the unaligned-writes problem). I ran into problems with the
SSSE3-vs.-not distinction that @simpkins alluded to in D652764, and
decided I'd rather not open that can of worms at the moment.

Test Plan:
fbmake runtests. Manually force the #ifs to false and make
sure fbmake runtests still passes (although GroupVarintTest is empty).

Reviewed By: delong.j@fb.com

FB internal diff: D747150

StlAllocator.h + MakeUnique.h -> Memory.h

Summary:
Go with the fat header approach. Merge these two into Memory.h. We could, potentially, include Malloc.h as well, but it fbstring header uses the once define for some special magic. Leave it alone for now.

An alternate approach might be moving all three leaner headers into a `memory/` subdir with `folly/Memory.h` just #including the three.

Test Plan:
fbconfig folly/tests && fbmake runtests_opt

Reviewed By: delong.j@fb.com

FB internal diff: D745873

HACK: Static detection of infinite sequences

Summary:
Certain operations should not be performed on infinite sequences
(e.g. sorting, left-folds, summation).  In some cases, we can
detect that a sequence is infinite at compile-time and provide
a static_assert to prevent such dangerous operations.

Test Plan:
Manually created cases where the operation should
be disallowed.  Compiler correctly raised an error.

Reviewed By: tjackson@fb.com

FB internal diff: D740011

Copyright 2012 -> 2013

Summary: See title.

Test Plan: Inspection.

Reviewed By: delong.j@fb.com

FB internal diff: D745883

IOBuf::getIov

Summary:
Generate an `fbvector` of `struct iovec` suitable for using with `writev` or
`sendmsg`.

This code is pretty straightforward, but Adam pointed out that something along
these lines has already been done in thrift, so I followed that code closely.
http://fburl.com/11586814

Test Plan:
fbmake runtests

I am using also this in a prototype and it's working there.

Reviewed By: agartrell@fb.com

FB internal diff: D744055

allow to dequeue the first IOBuf in an IOBufQueue

Summary: allow to dequeue the first IOBuf in an IOBufQueue

Test Plan: throughly tested with some dependent code in proxygen

Reviewed By: tudorb@fb.com

FB internal diff: D732484

Use aligned loads for Range::find_first_of

Summary:
Aligned loads are faster on some architectures. Let's refactor
qfind_first_of so that it uses aligned loads when possible.

Also modify the benchmarks to account for begin/end-of-string
logic.

Test Plan:
Tests pass. Updated benchmarks.  Generally seeing a 5-20%
speed-up, depending on the situation.

Reviewed By: philipp@fb.com

FB internal diff: D720369

Short-circuit operator== based on size()

Summary:
We don't do this today, but it looks like std::string does. For longer, similar strings, this is a big win.

Before:

```lang=text
============================================================================
./folly/test/FBStringTestBenchmarks.cpp.h       relative  time/iter  iters/s
============================================================================
BM_equality_string(65536)                                    5.13ms   194.87
BM_equality_fbstring(65536)                                 11.34ms    88.18
============================================================================
```

After:

```lang=text
============================================================================
./folly/test/FBStringTestBenchmarks.cpp.h       relative  time/iter  iters/s
============================================================================
BM_equality_string(65536)                                    5.01ms   199.74
BM_equality_fbstring(65536)                                  6.63ms   150.78
============================================================================
```

Test Plan: Benchmark, unit  tests

Reviewed By: tudorb@fb.com

FB internal diff: D737482

Fix unsplit(", ")

Summary: Otherwise you get errors like `error: array used as initializer ./folly/experimental/StringGen-inl.h: In constructor ‘folly::gen::detail::UnsplitBuffer<Delimiter, OutputBuffer>::UnsplitBuffer(const Delimiter&, OutputBuffer*) [with Delimiter = char [3] ...]`, since literal strings bind as reference to fixed-length character arrays. Providing an explicit overload for `const char*` fixes this.

Test Plan: Unit tests

Reviewed By: tulloch@fb.com

FB internal diff: D737117

adding is_non_positive traits

Summary:
template <typename SomeInt>
void foo(SomeInt x) {
// yields an error in clang when SomeInt is unsigned and -Werror is used
if(x <= 0) {
//...
}
}

Test Plan: added unit tests

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D735735

Make hash_combine accept a configurable hash function

Summary:
std::hash is not awesome and not configurable.  Typical cases you might want to customize are:
string: I happen to know that fnv isn't super awesome, for example, and that's what folly uses for std::hash fbstring.
pointers: you may want to hash the contents of the pointer instead of the address for certain types.

This is a very simple diff that lets you do that.  It provides StdHasher that passes through to std::hash and uses that for hash_combine, so this should be 100% backward compatible.

Test Plan: test_hash.  I will add another test for using a hasher besides StdHasher shortly.

Reviewed By: delong.j@fb.com

FB internal diff: D733899

Fixing namespace for GeneratorBuilder, more moves for Params

Summary:
GENERATOR was broken if you didn't `using namespace folly::gen`, and
we're still copying quite a few functors where we could move them.

Test Plan: Unit tests

Reviewed By: chaoyc@fb.com

FB internal diff: D731253

Add explicit assignment operator definitions to Optional

Summary:
See new test.  Under GCC 4.6 (which is what the folly tests build with) the old code works fine but under 4.7 building fails with:

folly/test/OptionalTest.cpp: In member function ‘virtual void Optional_AssignmentContained_Test::TestBody()’:
folly/test/OptionalTest.cpp:122:14: error: use of deleted function ‘ContainsOptional& ContainsOptional::operator=(const ContainsOptional&)’
folly/test/OptionalTest.cpp:106:21: note: ‘ContainsOptional& ContainsOptional::operator=(const ContainsOptional&)’ is implicitly deleted because the default definition would be ill-formed:
folly/test/OptionalTest.cpp:106:21: error: use of deleted function ‘folly::Optional<int>& folly::Optional<int>::operator=(const folly::Optional<int>&)’
In file included from folly/test/OptionalTest.cpp:17:0:
./folly/Optional.h:84:7: note: ‘folly::Optional<int>& folly::Optional<int>::operator=(const folly::Optional<int>&)’ is implicitly declared as deleted because ‘folly::Optional<int>’ declares a move constructor or move assignment operator
folly/test/OptionalTest.cpp:129:30: error: use of deleted function ‘ContainsOptional& ContainsOptional::operator=(ContainsOptional&&)’
folly/test/OptionalTest.cpp:108:21: note: ‘ContainsOptional& ContainsOptional::operator=(ContainsOptional&&)’ is implicitly deleted because the default definition would be ill-formed:
folly/test/OptionalTest.cpp:108:21: error: non-static data member ‘ContainsOptional::opt_’ does not have a move assignment operator or trivial copy assignment operator
folly/test/OptionalTest.cpp:137:14: error: use of deleted function ‘ContainsOptional& ContainsOptional::operator=(const ContainsOptional&)’

Test Plan:
(1) fbconfig folly/test && fbmake dbg && _build/dbg/folly/test/optional_test
(2) Remove folly/PLATFORM to build with gcc 4.7, then repeat (1).  Without the code fix, the new test fails to build.  With the fix, the test builds and runs fine.

Reviewed By: tjackson@fb.com

FB internal diff: D732402

folly (easy): Disable GCC-specific warning disabling hacks in clang

Summary:
When compiling folly with clang, the compiler warns about our
use of GCC-specific pragmas to silence incorrect compiler warnings:

folly/Optional.h:79:33: warning: unknown warning group '-Wpragmas', ignored [-Wunknown-pragmas]
folly/Optional.h:80:33: warning: unknown warning group '-Wmaybe-uninitialized', ignored [-Wunknown-pragmas]

Thankfully, those incorrect compiler warnings are not emitted by
clang, so we can just disable the pragmas in clang.

Test Plan:
Built folly in gcc and ran it through clang. Warning above
is gone.

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D733323

Add CHECK for out-of-range minRequests

Test Plan: async_io_test

Reviewed By: philipp@fb.com

FB internal diff: D730100

Remove File::tryOpen

Summary:
In hopes of keeping 'busywork' helpers out of folly, I've moved this
closer to the code that needed to do this.

Test Plan: Unit tests

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D729194

Blame Revision: D726916

File::tryOpen

Summary:
Now that we have truthy files, it would be nice to be able to simply
//try// opening files and return a possibly-initialized File.

Test Plan: Unit tests

Reviewed By: chaoyc@fb.com

FB internal diff: D726916

Truthy File

Summary:
File has a default constructor so it can be initialized late, but it
doesn't have a good canonical way to see if it's been initialized. This adds an
//explicit// operator bool so you can test files like `if (file) ...`.

Test Plan: Unit tests

Reviewed By: chaoyc@fb.com

FB internal diff: D726914

Add resizing constructor to folly::padded::Adaptor

Summary: Added Adaptor(size_t, const value_type&)

Test Plan: test added

Reviewed By: soren@fb.com

FB internal diff: D726358

Adding useful error message for File

Summary:
'open() failed' isn't too helpful. Seeing a filename there is. So I
added it.

Test Plan: Unit test

Reviewed By: mohittalwar@fb.com

FB internal diff: D725204

provide a flag to control the minimum number of iterations

Summary:
Add a --bm_min_iters flag to control the minimum number of iterations
that the benchmark code starts with on each epoch.

This can be used on benchmarks that test very cheap operations, but take
a long time to set up.  Otherwise the benchmark code may have to retry
many times before it hits a large enough number of iterations to get a
meaningful result, and each time it still pays the fixed setup cost.

This also helps with benchmarks when some of the setup cost cannot be
hidden with BenchmarkSuspender for some reason.  --bm_min_iters can be
set to a large enough value so that the extra startup cost will not
affect the measurements too much.

Test Plan:
Used this with the thread local stats benchmark.  During setup/cleanup,
this benchmark starts and synchronizes with many threads.  The entire
setup time cannot be reliably hidden with BenchmarkSuspender; the
synchronization between the threads takes a relatively long time
compared to the cost of the operation being benchmarked.  --bm_min_iters
allows a relatively high number of iterations to be used, masking this
cost.

Reviewed By: rajat@fb.com

FB internal diff: D723304

folly::make_optional

Summary:
Helper method for creating a folly::Optional<T> by just passing
in a T reference.  Analogous to boost::make_optional.

Test Plan: Added test case

Reviewed By: tjackson@fb.com

FB internal diff: D721762

MemoryMapping::data() returns StringPiece ::range() returns ByteRange

Summary: MemoryMapping::data() returns StringPiece ::range() returns ByteRange

Test Plan: tests

Reviewed By: philipp@fb.com

FB internal diff: D720985

Abstract ifunc support into a define

Summary:
There are platforms other than clang that don't support ifuncs. (The one
I'm concerned about is ARM.) I changed the ifdef __clang__ around the
ifunc attributes to be more abstract, so we can can pass in this flag on
the command line, or use autoconf to detect it.

Test Plan:
fbmake runtests. Manually define HAVE_IFUNC 0 and make sure the
popcount() and popcountll() functions get compiled as calls to
popcount_builtin.

Run autoreconf, ./configure, make sure the feature gets detected
properly by looking at config.h.

Reviewed By: andrewjcg@fb.com

FB internal diff: D712192

Renaming flag in MemoryMapping

Summary:
This flag conflicts with the flag with the same purpose in
`common/files/MemoryMappedFile.cpp`. Just renaming it for now.

Test Plan: Build

Reviewed By: lucian@fb.com

FB internal diff: D717067

MemoryMapping

Summary: MemoryMapping is a C++ wrapper object around mmap. It works with `folly::File`s, and provides bitwise-range access for reading and writing files.

Test Plan: Unit test

Reviewed By: lucian@fb.com

FB internal diff: D452384

folly: AsyncIO: add debuging helper

Summary: Change State to enum class, and add debugging helper to AsyncIOOp and AsyncIO.

Test Plan: n/a

Reviewed By: philipp@fb.com

FB internal diff: D715676

folly/{experimental => .}/File

Summary: Moving File into `/folly`.

Test Plan: Same unit tests, rebuild affected code outside folly.

Reviewed By: philipp@fb.com

FB internal diff: D714462

Fix SIGSEGV in StringPiece::find_first_of

Summary:
Our SSE version of find_first_of was reading past the end of
the StringPiece in some cases, which (very rarely) caused a seg-fault
when we were reading outside of our allotted virtual address space.

Modify the code to never read past the end of the underlying buffers
except when we think it's "safe" because we're still within the same
page. (ASSUMPTION: if a process is allowed to read a byte within a
page, then it is allowed to read _all_ bytes within that page.)

Test Plan:
Added tests that verify we won't go across page boundaries.

Sadly, this code hurts our benchmarks -- sometimes by up to 50% for
smaller strings.

Reviewed By: philipp@fb.com

FB internal diff: D707923

Blame Revision: D638500

Rework folly::AsyncIO interface to make it easier for other classes to use Op

Summary:
AsyncIOOp no longer requires derivation to be able to use callbacks; the
callback is passed in.  This makes composition easier (see AsyncIOQueue, added
in this diff).

Test Plan: async_io_test, test added

Reviewed By: lucian@fb.com

FB internal diff: D709648

fix comment

Test Plan: No

Reviewed By: philipp@fb.com

FB internal diff: D709795

value_ might be uninitialized

Summary: Compilation is failing in 'opt' build

Test Plan: compile

Reviewed By: andrewjcg@fb.com

FB internal diff: D707869

Define ALLOCM_LG_ALIGN

Test Plan: No

Reviewed By: philipp@fb.com

FB internal diff: D707792

Minor clang compiler fixes

Summary: Minor clang compiler fixes

Test Plan: - fbmake runtest

Reviewed By: andrewjcg@fb.com

FB internal diff: D707663

Make AsyncIO::capacity_ const

Summary: It is set once, and is never changed afterwards.

Test Plan: compiled, unit tests

Reviewed By: tudorb@fb.com

FB internal diff: D706125

Codemod time\(NULL\) to time(nullptr)

Summary: codemod with 'Yes to all'.

Test Plan: None really.

Reviewed By: abirchall@fb.com

FB internal diff: D693769

Fix subtle double-free in trimEnd; optionally pack IOBufQueue after append

Test Plan: folly/io/test, both dbg and opt, standalone and in valgrind

Reviewed By: philipp@fb.com

FB internal diff: D702755

all(), better any()

Summary: TSIA

Test Plan: Unit tests

Reviewed By: tulloch@fb.com

FB internal diff: D701890

fix typos

Test Plan: async_io_test

Reviewed By: lucian@fb.com

FB internal diff: D699175

Add some CursorBase::operator-() implementations

Summary:
- Add CursorBase::operator-() implementations for Cursor and BufType;
useful for figuring out the distance between two objects

Test Plan: - Used in some other code

Reviewed By: simpkins@fb.com

FB internal diff: D690046

assert on self move assignment

Test Plan: ran tests in dbg

Reviewed By: tudorb@fb.com

FB internal diff: D696964

AsyncIO: CHECK preconditions

Test Plan: async_io_test

Reviewed By: delong.j@fb.com

FB internal diff: D698919

AsyncIO in folly

Summary:
Interface extended and cleaned up.  Also, now
actually allows you to retrieve IO errors.  Also moved some useful functions
out of Subprocess.cpp into a separate header file.

Test Plan: async_io_test, subprocess_test

Reviewed By: philipp@fb.com

FB internal diff: D698412

unsplit

Summary:
1. Incorporates @tjackson's offline comments.
2. See docstrings and examples for basic usage.
3. The usecase this covers (for me and others) was where I have some map or
vector of elements, and I want to form a string representation of this (for
logging, fb303 exported values, etc.). Various uses have existed in fbcode (e.g.
UP2X shard representations), and this seemed like a useful utility.

Test Plan: unit tests.

Reviewed By: tjackson@fb.com

FB internal diff: D696794

Update example in folly::gen

Summary: asVector() doesn't exist.

Test Plan: Nope.

Reviewed By: tjackson@fb.com

FB internal diff: D697240

contains()

Summary: TSIA

Test Plan: Unit tests

Reviewed By: tulloch@fb.com

FB internal diff: D680177

folly/dynamic: fix explicit specializations after instantiation

Summary:
clang complains that the explicit specializations in dynamic.cpp
come after references in dynamic-inl.h.

Test Plan:
- built dyamic.o with clang
- built folly normally and ran unittests

Reviewed By: delong.j@fb.com

FB internal diff: D691081

adding some missing remove_reference in make_stl_allocator and is_simple_allocator

Summary: adding some missing remove_reference in make_stl_allocator and is_simple_allocator

Test Plan: unit tests

Reviewed By: jon.coens@fb.com

FB internal diff: D689524

Remove a bit of debug code in folly::Range

Summary:
Seems like we can drop this, as the case that motivated
adding it wouldn't have been caught by it.

Test Plan: Compiled folly/test.

Reviewed By: tudorb@fb.com

FB internal diff: D684200

fixing rwspinlock test Summary:

Summary:
gcc seems to treat this as declaration:

RWSpinLock::UpgradedHolder ug(
RWSpinLock::WriteHolder(
RWSpinLock::ReadHolder(&lock)));

Test Plan: add LOG(INFO) to make sure the holder converstions did get executed.

Reviewed By: marcelo.juchem@fb.com

FB internal diff: D688748

A few fixes for clang support

Summary: fixes for clang support

Test Plan:
rm -rf ~/fbcode/_build/* && fbconfig --clang folly/test && fbmake
rm -rf ~/fbcode/_build/* && fbconfig folly/test && fbmake
_bin/folly/test/format_test
_bin/folly/test/optional_test
_bin/folly/test/has_member_fn_traits_test

Reviewed By: tudorb@fb.com

FB internal diff: D688295

qfind_first_byte_of may suffer from global initialization order

Summary: ##static## handling adds ~2 more ns overhead per call (and the first call is kinda slow), but now the logic is correct now. Also inlined ##qfind_first_byte_of##.

Test Plan: unittests

Reviewed By: tudorb@fb.com

FB internal diff: D687947

Implementing unique/shared_ptr for custom allocators (like Arena) in folly

Summary:
- moving simple allocator *_ptr and convenience functions to folly
- getting rid of arena_new - it encourages manually constructing smart pointers when folly::allocate_* should be used instead
- using std::allocate_shared to construct shared_ptrs, thus properly using the allocator for the ref-counter too
- fixing forwarding of parameters in the convenience functions
- uniform allocation of smart pointers using both stl and non stl-like allocators

Test Plan:
- build + tests of existing client code
- basic unit tests for arena smart pointers

Reviewed By: delong.j@fb.com

FB internal diff: D672818

temporary get rid of ifunc in folly::Range

Summary:
See discussion in D638500.

valgrind 3.7 contains a bug that makes it hung up
(https://bugs.kde.org/show_bug.cgi?id=301204).

glibc 2.5.1 doesn't support ifunc.

In the future we should conditionally compile ifunc stuff (this is also
required to support clang).

Test Plan:
unittests, ran range_benchmark to confirm there is no
significant performance drop, this additional level of indirection adds overhead of ~1ns.

tested on CPUs with and without SSE4.2 support.

Reviewed By: mmcurtiss@fb.com

FB internal diff: D687351

Fix comment in folly::dynamic

Summary: That's all.

Test Plan: Nope.

Reviewed By: simpkins@fb.com

FB internal diff: D684144

Boost system is now needed

Summary: https://github.com/facebook/folly/pull/22

Test Plan: .

Reviewed By: andrewjcg@fb.com

FB internal diff: D683793

Add optional description which complains on newer versions of autoconf

Summary: https://github.com/facebook/folly/pull/22

Test Plan: none

Reviewed By: andrewjcg@fb.com

FB internal diff: D683791

open source Elias-Fano coding implementation

Test Plan: unittests

Reviewed By: mmcurtiss@fb.com

FB internal diff: D677750

set pid_=-1 after wait, actually implement pid()

Summary: minor issues in folly::Subprocess

Test Plan: subprocess_test

Reviewed By: philipp@fb.com

FB internal diff: D680959

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

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