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