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

Histogram function to write tab-separated values.

Summary: Export histograms in a tab-separated format.

Test Plan: Used it.

Reviewed By: lucian@fb.com

Minor huge pages library changes

Summary:
Moved to separate library instead of :io
Got rid of the mode argument when creating files -- umask is your friend
Separated getSize interface from create
Added FsUtil.h for some fs::path operations
Switched some interfaces to fs::path instead of string / StringPiece
Canonicalize paths so we don't care whether paths are absolute or
relative

Test Plan: fs_util_test, by hand

Reviewed By: philipp@fb.com

FB internal diff: D564465

Huge page library.

Test Plan: by hand

Reviewed By: lucian@fb.com

FB internal diff: D555164

fix build on: define own version of ALLOCM_LG_ALIGN

Summary:
On --platform=gcc-4.6.2-glibc-2.13-fb the build would fail because

fbcode/third-party/gcc-4.6.2-glibc-2.13-fb/libgcc/libgcc-4.6.2/b4e37bb/include/c++/4.6.2/bits/basic_fbstring_malloc.h

defines it's own version of ALLOCM_SUCCESS & co., but not ALLOCM_LG_ALIGN :(

The '#ifdef ALLOCM_SUCCESS' check in 'folly/Malloc.h' would pass even
though we didn't include jemalloc.

Test Plan: build it

Reviewed By: philipp@fb.com

FB internal diff: D562273

Unbreak build.

Summary: I'll pretend you reviewed this.

Test Plan: build

Reviewed By: simpkins@fb.com

FB internal diff: D562255

Move exception tracer library to folly/experimental

Summary:
This change is mostly mechanical (moving files, changing include paths,
etc).  I made some changes to TARGETS to make it easier for the library
to be linked in (instead of LD_PRELOADed)

Test Plan: by hand

Reviewed By: simpkins@fb.com

FB internal diff: D562196

Add ALLOCM_LG_ALIGN to Malloc.h

Test Plan: .

Reviewed By: soren@fb.com

Stream operations: file access, iteration, splitting.

Summary: Intended to complement and replace strings::byLine.

Test Plan: stream_test

Reviewed By: delong.j@fb.com

FB internal diff: D463341

Fix fedora / ubuntu build

Test Plan: yes

Reviewed By: andrewjcg@fb.com

FB internal diff: D558628

folly: simplify the stats avgHelper() function

Summary:
When the input type is a long double, perform division using long
double.  In all other cases, divide using double precision.

Also fix the EXPECT_EQ() usage in the test case.

Test Plan: fbconfig -r common/stats folly && fbmake runtests

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D555433

BucketedTimeSeries: fix type converison issues computing avg()

Summary:
D527040 had a bug in the code to compute the average: it incorrectly
performed unsigned division when ValueType was a signed integer type.
As a result, the average was reported incorrectly for stats with
negative values.

This makes the average code more intelligent when handling type
conversions: if the caller wants a floating point value, or if the input
type is floating point, floating point division is always returned.
Otherwise, if the input is a signed type, signed integer division is
performed.  Otherwise, unsigned integer division is performed.

Test Plan: beholdunittests

Reviewed By: lars@fb.com

FB internal diff: D553583

folly: add a simple benchmark for Histogram::addValue()

Summary:
I wrote this an an example for the BENCHMARK_NAMED_PARAM() comments in
D527040, and figured I might as well check it in as a real benchmark.

Test Plan:
Here's the output:

======================================================================
folly/test/HistogramBenchmark.cpp         relative  time/iter  iters/s
======================================================================
addValue(0_to_100)                                    15.43ns   64.81M
addValue(0_to_1000)                                   15.45ns   64.70M
addValue(5k_to_20k)                                   15.46ns   64.67M
======================================================================

Reviewed By: rajat@fb.com

FB internal diff: D552875

change shared_ptr<>* to raw pointer

Summary:
change shared_ptr<>* to raw pointer in
forwardIndex in RTIndex. This saves 16 bytes per
forward list (decrease from 88 to 72) and translates
to about 4-5% memory saving for RTIndex in ff tier.

Test Plan: unit test

Reviewed By: xliux@fb.com

FB internal diff: D551191

Add BucketedTimeSeries to folly

Summary:
Add the BucketedTimeSeries class to folly.  This tracks time series
counter data, using a circular buffer of buckets to expire old data
points as time progresses.

It supports querying the overall sum, count, average, and rate for the
duration of the time series, as well as estimating these values for
portions of the overall duration.

Test Plan: Unit tests included.

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D527040

one more simple folly::join optimization

Summary:
Before:

_bin/folly/test/string_test --benchmark --bm_regex=join --bm_min_usec=1000000
============================================================================
folly/test/StringTest.cpp                       relative  time/iter  iters/s
============================================================================
joinCharStr                                                  3.59us  278.29K
joinStrStr                                                   4.44us  225.09K
joinInt                                                     10.55us   94.76K
============================================================================

And after:

_bin/folly/test/string_test --benchmark --bm_regex=join --bm_min_usec=1000000
============================================================================
folly/test/StringTest.cpp                       relative  time/iter  iters/s
============================================================================
joinCharStr                                                  3.61us  277.01K
joinStrStr                                                   3.77us  264.97K
joinInt                                                      9.92us  100.81K
============================================================================

Test Plan: unittests, benchmark

Reviewed By: tudorb@fb.com

FB internal diff: D552364

Add Bob Jenkins's SpookyHash to folly.

Summary:
http://burtleburtle.net/bob/hash/spooky.html
The code is in the public domain, so republishing it as such is fine.
The code needed modifications (the test was designed to run on Windows
only; removed unhygienic typedefs; moved to folly::hash namespace)

Also updated Makefile.am files.

Test Plan: test added

Reviewed By: soren@fb.com

FB internal diff: D549572

isPowTwo

Summary:
a la Hacker's Delight.

Also, fix nonsensical nextPowTwo benchmark.

Test Plan: Added test and benchmark.

Reviewed By: tudorb@fb.com

FB internal diff: D551510

one more folly::join overload

Summary: To allow codemod changes.

Test Plan: ran test

Reviewed By: tudorb@fb.com

FB internal diff: D549516

Task #906853: Implement ThreadLocalServiceData and reduce lock contentions during channel counter update

Summary:
Cache the counter updates on thread local data structures and aggregate/publish
the data from a separate thread periodically. The ThreadLocalServiceData is
implemented on top of the TLStats data structures.

I am plannig to deploy a private build to production tomorrow to test this
change in production, but figured it might be better to send the diff out first
and get code review feedbacks at the same time.

Test Plan: Run and pass unit tests. Run end-to-end testings on sandbox. (TBD)
Deploy a private build to a production server and make sure the thrift call
latency is reduced.

Reviewed By: xin@fb.com

FB internal diff: D540239

folly: randomNumberSeed should be random wrt multiple threads

Summary:
Right now, it relies on process id rather than on thread id. Thus, it can
return the same seed when called from multiple threads over really short
period of time, and these unlucky threads will end up with identical "random"
sequences.

Test Plan: newly added test fails against trunk, passes against changes in the diff

Reviewed By: tudorb@fb.com

FB internal diff: D548129