Summary: When merging centroids together, we recalculate the mean and weight. This can sometimes lead to inaccuracy due to floating point arithmetic. In a bad scenario, this can actually lead to the digest being unsorted, which triggers assertions in the code. To fix this, sort the digest at the end of merge. Since this is bounded to 100 elements that are mostly sorted, this appears to be cheap according to benchmarks.

Reviewed By: yfeldblum

Differential Revision: D9213936

fbshipit-source-id: 5a2978a1b759b70206aef57245bef193aed65efd

Summary:
Blocking algorithm:
 Push:
1.  push
2.  increase the PTicket number
3.  put (PTicket << 1) to the corresponding place in futex array.
4.  if the original  futex value & 1  == 1,  wake up ()

Pop:
1.  increase the CTicket number
2.  spin if the corresponding CTicket futex is not ready
3.  set the right bit of the CTicket futex  to 1, wait on it.
4. pop

Add additional control to improve the accuracy:
For the top several levels (top 0 - 3 levels by default), it does not arbitrarily insert any node in the middle of the list. Thus guaranteeing no later coming lower priorities can be insert at the top levels (pruning strategy still valid for the top four levels). For the bottom levels (start from level 7 by default), if insertion requires to hold parent + child locks, it traverses the parent list to check whether the parent list has lower priority nodes than the new node. If the condition holds, insert the new node to the parent and get the last node in the parent list and insert it to the child list.

Reviewed By: magedm

Differential Revision: D9094903

fbshipit-source-id: fa4d31fb0c21da746570029e0e3b4b3fbeaa2024

Summary: This code is hot enough that this might matter. Though likely over-optimization.

Reviewed By: djwatson

Differential Revision: D9197636

fbshipit-source-id: d9e2a90410c03a73d1754d99c72967f5dcd96c0f

Summary: Production data shows that it performs significantly worse under common RequestContext load (few elements, clang lto compiled).

Reviewed By: djwatson

Differential Revision: D9182929

fbshipit-source-id: 0c638268d9b6cd2451b48ccc4e228faf90f0e18e

Summary: Currently, fbcode_builder assumes you're building code living in the facebook github org. If you try to do travis builds using a facebookincubator repo, an error occurs due to hard-coded assumptions about the org. This fixes that

Reviewed By: knekritz

Differential Revision: D9183307

fbshipit-source-id: 0a1ac399953485e84f0534cc0616765227088c80

Summary:
Overall plan to modify Future<T>::then to be r-value qualified and use Future<T>::thenTry or Future<T>::thenValue. The goal is to disambiguate folly::Future and to improve type and lifetime safety of Future and its methods.

Add a std::move that was missed in the folly benchmark.

Reviewed By: shixiao

Differential Revision: D9197265

fbshipit-source-id: d02ab7b0dc22f6465910a80b2d0af1b54fb7bde7

Summary: This update adds the name of the function which called the LOG() to the `LogMessage` object so that a custom formatter could use it to show method name with logs.

Reviewed By: simpkins

Differential Revision: D9071926

fbshipit-source-id: 9d5359d84cf2544371c6f1826f99d8b47a272dd1

Summary:
Apparently certain Android NDK does not support numeric conversion functions of
`basic_string`. Use folly/Conv instead.

Changes generated by `%s/std::to_string/to<std::string>/g`.

In addition, Android SDK's treatment of `long double` is inconsistent. Avoid
that in the tests for now.

Reviewed By: yfeldblum

Differential Revision: D9196009

fbshipit-source-id: 54a32c426a4beb6a0e2d7f95d6b30bf6d7cc67cf

Summary:
When we have a single thread handling both connections and requests, we end up
call the accept callback on the same thread. The code handling the
incoming connections does intend to short-circuit such connection
and not place them on EventBase's queue but it only checks only whether there is no
EventBase registerd for the accept callback. However, by default, we are
registering an EventBase for this callback so this short-circuit falls short
(yay puns).

Reviewed By: djwatson

Differential Revision: D8986246

fbshipit-source-id: 45b817669ae4fd908b39c93ae5b82bb9a14cc2ed

Summary: It's only two stores, but for move that ends up being a large percentage of the work it has to do.  Add initializers in the move constructor, so that we don't both default-initialize and then swap() inline.

Reviewed By: yfeldblum

Differential Revision: D8678422

fbshipit-source-id: 71b574145182ad3a4a3e9d0d824d83abe65fb6fa

Summary: The algorithm in the TDigest paper does not handle weird outliers very well. This diff changes the clamp logic to clamp between the prev and next centroids rather than min_ and max_. This gives much better results.

Reviewed By: yfeldblum

Differential Revision: D9192686

fbshipit-source-id: 171a7b7db5552802f91e6e95bb541a1b03c8821d

Summary:
Add a missing include in `folly/detail/FingerprintPolynomial.h` to fix the
modular build.

Reviewed By: andrewjcg

Differential Revision: D9182707

fbshipit-source-id: c498b10bd02f6528a62fce8145521a97755d6496

Summary: We have a surprisingly high number of unrelated dependencies on those 2 imports

Reviewed By: djwatson

Differential Revision: D9155350

fbshipit-source-id: e85e42934af8378cdc0db909d8a6afacb504df8f

Reviewed By: yfeldblum, palmtenor

Differential Revision: D9144908

fbshipit-source-id: 6201a4beaf1e2d2cf16c8e3986097a6e8e47c6f3

Summary: Per title

Reviewed By: mingtaoy

Differential Revision: D9159614

fbshipit-source-id: d26320587ae55b4415185206a7a6a5f8f38ff428

Summary:
- Several files have the executable bit set and do not need to.
Pull Request resolved: https://github.com/facebook/folly/pull/904

Differential Revision: D9177526

Pulled By: yfeldblum

fbshipit-source-id: 5dd5d5cfca5b184b42de4db4a052daaadfef2496

Summary:
Resubmitting as https://github.com/facebook/folly/pull/743 failed internal builds according to yfeldblum

Edit: as pointed out in the conversation below, this check needs to be gated for Boost versions [1.59, 1.64] as Boost 1.65 removed this method.
Closes https://github.com/facebook/folly/pull/745

Reviewed By: Orvid

Differential Revision: D6853821

Pulled By: yfeldblum

fbshipit-source-id: 2e0c8f425055ee82c317146c4c836c28f7130e9b

Summary:
Replace `folly/Histogram.h` by `folly/stats/Histogram.h`.  Use `auto` to declare type of `getNumBuckets`.
Pull Request resolved: https://github.com/facebook/folly/pull/892

Reviewed By: aary

Differential Revision: D9043331

Pulled By: yfeldblum

fbshipit-source-id: 51dc6164f78ab72b947327e31f198a33a56c5fc4

Summary:
Problem:
- There was a bug in a much older version of MSVC relating to
  accessing functions in an anonymous namespace with the workaround
  being to have an extra anonymous namespace.

Solution:
- Remove the workaround as the MSVC versions that Folly now targets
  (MSVC 2015 and MSVC 2017) should not have this bug.
Pull Request resolved: https://github.com/facebook/folly/pull/898

Reviewed By: aary

Differential Revision: D9176601

Pulled By: yfeldblum

fbshipit-source-id: 7db87d28f8968eb5b3ff9d9375777f997b060a59

Summary:
According to https://github.com/pytorch/pytorch/pull/6697, ARM64 clang from the
Android SDK does not define the newer `__ARM_NEON` macro (specified in the ARM
C language extensions 2.1:
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ihi0053d/index.html),
but rather, it uses `__ARM_NEON__`.

Portability should check for both until full deprecation?

Reviewed By: nbronson

Differential Revision: D9163276

fbshipit-source-id: db6407f85b21b0ad3e4d564c73ef3ca5d8a16c2f

Summary:
Add some missing headers required for
other oss projects.

These were not synced to the makefile.

Reviewed By: shixiao

Differential Revision: D9161271

fbshipit-source-id: 283042c35ac9f78fef24348e0d78b26ab8f2eeb8

Summary:
On architectures with SSE2 but not AVX2, the _mm_set1_epi8
intrinsic at the core of F14Table::findImpl expands to multiple
instructions.  One of those is a MOVD of either 4 or 8 byte width.
Only the bottom byte of that move actually affects the result, but
if a 1-byte needle has been spilled then this will be a 4 byte load.
GCC 5.5 has been observed to reload (or perhaps fuse a reload and a
narrow) needle using a MOVZX with a 1 byte load in parallel to the MOVD.
This combination causes a failure of store-to-load forwarding, which has
a big performance penalty (60 nanoseconds per find on a microbenchmark).
Keeping needle >= 4 bytes avoids the problem and also happens to result
in slightly more compact code.

Reviewed By: yfeldblum

Differential Revision: D9149727

fbshipit-source-id: 9e957207c23914da317e763eb944bf7dd43a5c51

Summary:
Change "If advanced debugging functionality is required" to "If advanced debugging functionality is required, use:" for consistency in README.md and to be more reader friendly.
Pull Request resolved: https://github.com/facebook/folly/pull/894

Reviewed By: shixiao

Differential Revision: D9094182

Pulled By: yfeldblum

fbshipit-source-id: 147d436aaee291104b67eab1e549554696740907

Summary:
Use folly Map14 for RequestData and boost flat_set for RequestData's callbacks.
See code comment to explain the choice.

Reviewed By: vipannalla

Differential Revision: D9147805

fbshipit-source-id: adc2d26a7a46c5b7381599ebf44d26fa07e9b775

Summary:
This fixes building of targets such as `folly:dynamic` that contain `F14Map.h`
includes with modules (`mode/dev-mod`). Previously they failed with the
following error:

```
folly/container/F14Map.h:37:10: error: use of private header from outside its
module: 'folly/container/F14Map-pre.h' [-Wprivate-header]
         ^
```

Reviewed By: shixiao

Differential Revision: D9144188

fbshipit-source-id: 0476f88ce2373c8b9fbf148a2e0532ff92b2477a

Summary:
For F14Vector containers, we assume that the size could fit in `uint32_t`,
i.e., the `InternalSizeType`. This diff fixes where we implicitly convert
(shorten) a `size_t` to `InternalSizeType`.

Reviewed By: nbronson

fbshipit-source-id: e970071dbde6394262a555facc8e2a24c6007f68

Summary:
Do not assume `dwarf.h` is contained within a subdirectory called `libdwarf` during CMake configure.

See https://github.com/facebook/folly/issues/788 for more detailed info.
Fixes: #788.
Pull Request resolved: https://github.com/facebook/folly/pull/790

Reviewed By: andrewjcg

Differential Revision: D9094892

Pulled By: yfeldblum

fbshipit-source-id: 6b5faf000e5ff4f85b2b93e43d12a911eb05b5ab

Summary: Avoid exponential cost of find in unodered set

Reviewed By: yfeldblum, shubhanshu04

Differential Revision: D9145024

fbshipit-source-id: e7949e967e078a8857962893581495d03e01f989

Back out "[folly] use heterogeneous lookup and mutation in folly::dynamic" and "[folly] use F14NodeMap in folly::dynamic"

Summary:
D8299863 and D8299800

Mostly backing out for xplat autoupdater. The TARGETS / DEFS got scrambled.

Differential Revision: D9139265

fbshipit-source-id: 78b0238370d4de4fdc363d0867dc46de3a572f58

Summary: I keep modifying this code, and I keep feeling like it would be more readable without std::swap. Thoughts?

Reviewed By: yfeldblum

Differential Revision: D9140662

fbshipit-source-id: a86862dbfd1c0caeb69cc66b215994a3d1dd0294

Summary: Add the new GSO related methods to MockAsyncUDPSocket

Reviewed By: yfeldblum

Differential Revision: D9136190

fbshipit-source-id: 5a2173caae8ac21fbb7532c21f9f6f7aaf227ce3

Summary:
N4387 lifted the restrictions on `pair` and `tuple` construction that the
element types must be implicitly convertible to the target element types. Prior
to GCC 6, this document was not implemented in libstdc++. There are other
subsequent fixes to address LWG2367, for exmaple.

The upstream implementation for N4387 is here:
https://github.com/gcc-mirror/gcc/commit/d3c64041b32b6962ad6b2d879231537a477631fb

This diff adds the `insert` overloads to work around these issues as well as
test coverage.

Note that the following overload still wouldn't work:
  m.insert({sp, x})
since the compiler is not able to deduce the element types without attempting
to construct a `pair`.

Reviewed By: yfeldblum, nbronson

Differential Revision: D9117504

fbshipit-source-id: c6fae625bf4d9518cb2b4bcc76465b004c4cd253

Summary:
Problem:
- `IP_RECVERR` symbol is not defined on Mac OS.
- A test expects this symbol to be found. But, in the case on Mac OS, the symbol is not found and hence will cause a hard compiler error.

Solution:
- `ifdef` the portion of the test that is relying on this symbol.
Pull Request resolved: https://github.com/facebook/folly/pull/899

Differential Revision: D9140373

Pulled By: yfeldblum

fbshipit-source-id: 127ab352cea790194171376ac809c23249883251

Summary: This is a unittest for an issue I fixed previously (but had to land ASAP).

Reviewed By: yfeldblum

Differential Revision: D9140622

fbshipit-source-id: 09dcb4206d2a09a57c2f2239a1aa217b124e88fd

Summary: Some of the RequestData's instances share same thread-local, and rely on strict ordering of unset/set

Reviewed By: djwatson

Differential Revision: D9138483

fbshipit-source-id: fba59a7f5619d54ed21d71a40fb2cc6ce0e93797

Summary: Disable GSO if FOLLY_HAVE_MSG_ERRQUEUE is not defined

Reviewed By: yfeldblum

Differential Revision: D9128837

fbshipit-source-id: 25977eb7f46ac57dca17c7956277f9f647357baa

Summary:
This diff allows `folly::dynamic` to lookup and mutate using any type that is
convertible to `StringPiece` (i.e., `const char*`, `std::string`, `fbstring`)
without having to construct a `dynamic` object (which requires copying the
string).

Currently dynamic string types uses fnv32 hash, which is OK since F14 is going
to do a mixing step anyway; we are changing this in D8304491.

Reviewed By: yfeldblum

Differential Revision: D8299863

fbshipit-source-id: a154bfe8f17e1d83968cdc1755ec54b6eed4299e

Summary:
F14NodeMap is a safe drop-in replacement for std::unordered_map. It is smaller
than std::unordered_map (32 bytes instead of 56 bytes) and has been shown
to be faster in many production use cases. This diff replaces the hash table
inside folly::dynamic. The effect is that sizeof(folly::dynamic) will drop from 64
bytes to 40 bytes, and use cases that use folly::dynamic as an object may also
get a CPU win.

Reviewed By: nbronson

Differential Revision: D8299800

fbshipit-source-id: abd0b034537c95f2ccbdf78fe5ae8fe9157f32ac

Summary:
In my use case, at least, it's very likely that most Fibers are sharing the same RequestContext.
This could save a lot of onSet/onUnset calls.
Unsafe?

Reviewed By: andriigrynenko

Differential Revision: D9115679

fbshipit-source-id: 216208dff509c61b9f20f324c3e648ec79ebbaf7

Summary: Public method to get `maxSize` for `TDigest`.

Reviewed By: yfeldblum

Differential Revision: D9124932

fbshipit-source-id: 1effab8900c3007f6a92d9d6c1d83189746f4ac6