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

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

Test Plan: Unit tests

Reviewed By: delong.j@fb.com

FB internal diff: D571810

Summary: For std::exception_ptr.

Test Plan: .

Reviewed By: davejwatson@fb.com

FB internal diff: D600345

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Test Plan: - used it

Reviewed By: delong.j@fb.com

FB internal diff: D569440

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

Test Plan: by hand

Reviewed By: philipp@fb.com

FB internal diff: D570233

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

Test Plan: stream_test, exception_tracer_test

Reviewed By: soren@fb.com

FB internal diff: D569476

Summary: Export histograms in a tab-separated format.

Test Plan: Used it.

Reviewed By: lucian@fb.com

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

Test Plan: by hand

Reviewed By: lucian@fb.com

FB internal diff: D555164

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

Summary: I'll pretend you reviewed this.

Test Plan: build

Reviewed By: simpkins@fb.com

FB internal diff: D562255

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

Test Plan: .

Reviewed By: soren@fb.com

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

Test Plan: stream_test

Reviewed By: delong.j@fb.com

FB internal diff: D463341

Test Plan: yes

Reviewed By: andrewjcg@fb.com

FB internal diff: D558628

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

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

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

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

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

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

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

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

Summary: To allow codemod changes.

Test Plan: ran test

Reviewed By: tudorb@fb.com

FB internal diff: D549516