Summary:
The sorting approach used in TDigest is inefficient because it is not leveraging the fact that there are k sorted subarrays. This diff leverages inplace_merge to improve performance.

The cost of merging k digests of size m used to be O(km * log(km)). It is now O(km * log(k)).

Reviewed By: anakryiko

Differential Revision: D7690143

fbshipit-source-id: 1307db153b3cae0bb952d4b872aede8c40ce292c

Summary:
The issue is that std::swap must have the same type for both parameters but the member .swap() for PolyVal takes Poly and then uses std::swap(*this, that).

the fix uses static_cast to change the Poly to a PolyVal for std::swap

Reviewed By: ericniebler

Differential Revision: D7730948

fbshipit-source-id: 8dd93fc3c86b87938a7c0c12ccb3b5209a593730

Summary: Further performance improvements to TDigest by diverging from the algorithm in the paper slightly, but in a manner that does not impact the results at all.

Reviewed By: anakryiko

Differential Revision: D7687476

fbshipit-source-id: f71884b0fb21c9e78418643b82b099b01e96e4c9

Summary:
[Folly] Fix build failures in `folly/io/async/test/AsyncUDPSocketTest.cpp`, which uses private gmock macros to try to override base-class member functions marked `noexcept`.

Using private macros belonging to another library is not the way to go.

Reviewed By: siyengar

Differential Revision: D7728285

fbshipit-source-id: 84c96826f25679dfb8dd0ec5e5985c3cc19f6e3d

Summary:
I suspect the algorithm in the tdigest paper is slightly off. Instead of setting boundaries at k = 1, 2, 3...d, it sets boundaries at k_last_elem + 1. This results in two issues:

1) It is possible to have more than d elements in the digest. Now, that is no longer possible, and we can properly reserve the right number of elements.
2) Additional floating point operations are computed than necessary.

Reviewed By: anakryiko

Differential Revision: D7654147

fbshipit-source-id: 131184d456353a9d936c4ed385e2b5e75d468676

Reviewed By: yfeldblum

Differential Revision: D7726522

fbshipit-source-id: fa5ad9fc29152b52c5256849c2822885acd49c23

Summary: [Folly] Cut dead reference to `executorLock_` in Futures test - this field was recently removed.

Reviewed By: LeeHowes

Differential Revision: D7725446

fbshipit-source-id: a522b66da77bbefeb69970bee20feea46dcc72a5

Summary:
`folly::lock()` is a deadlock safe way to acquire write
locks on many lockables or `folly::Synchronized` objects

```
lock(folly::wlock(one), folly::rlock(two), folly::wlock(three));
```

This executes the deadlock avoidance algorithm on a write lock for `one` and
`three` and a read lock for `two`.  ADL lookup is done for the `lock()`
function.

It can also work on arbitrary lockables and performs better than both
`std::lock()` and acquiring the mutexes in order

```
folly::lock(one, two, three);
```

There is a big performance improvement compared to simply acquiring locks
in the same order in the presence of contention.  The backoff algorithm tries
to adjust to contention and block on the mutex that it thinks is the best fit.

Benchmarks look promising

```
============================================================================
folly/test/SynchronizedBenchmark.cpp            relative  time/iter  iters/s
============================================================================
ThreeThreadsPathologicalFollyLock                            3.81us  262.24K
ThreeThreadsPathologicalStdLock                              5.34us  187.28K
ThreeThreadsPathologicalOrdered                              6.36us  157.28K
ThreeThreadsPathologicalCarefullyOrdered                     4.21us  237.29K
----------------------------------------------------------------------------
TwoThreadsTwoMutexesOrdered                                260.87ns    3.83M
TwoThreadsTwoMutexesSmart                                  161.28ns    6.20M
TwoThreadsTwoMutexesPersistent                             226.25ns    4.42M
----------------------------------------------------------------------------
TwoThreadsFourMutexesOrdered                               196.01ns    5.10M
TwoThreadsFourMutexesSmart                                 196.73ns    5.08M
TwoThreadsFourMutexesPersistent                            201.70ns    4.96M
----------------------------------------------------------------------------
TwoThreadsEightMutexesOrdered                              195.76ns    5.11M
TwoThreadsEightMutexesSmart                                187.90ns    5.32M
TwoThreadsEightMutexesPersistent                           199.21ns    5.02M
----------------------------------------------------------------------------
TwoThreadsSixteenMutexesOrdered                            203.91ns    4.90M
TwoThreadsSixteenMutexesSmart                              196.30ns    5.09M
TwoThreadsSixteenMutexesPersistent                         230.64ns    4.34M
----------------------------------------------------------------------------
FourThreadsTwoMutexesOrdered                               814.98ns    1.23M
FourThreadsTwoMutexesSmart                                 559.79ns    1.79M
FourThreadsTwoMutexesPersistent                            520.90ns    1.92M
----------------------------------------------------------------------------
FourThreadsFourMutexesOrdered                              456.04ns    2.19M
FourThreadsFourMutexesSmart                                391.69ns    2.55M
FourThreadsFourMutexesPersistent                           414.56ns    2.41M
----------------------------------------------------------------------------
FourThreadsEightMutexesOrdered                             392.20ns    2.55M
FourThreadsEightMutexesSmart                               277.89ns    3.60M
FourThreadsEightMutexesPersistent                          301.98ns    3.31M
----------------------------------------------------------------------------
FourThreadsSixteenMutexesOrdered                           356.36ns    2.81M
FourThreadsSixteenMutexesSmart                             291.40ns    3.43M
FourThreadsSixteenMutexesPersistent                        292.23ns    3.42M
----------------------------------------------------------------------------
EightThreadsTwoMutexesOrdered                                1.58us  634.85K
EightThreadsTwoMutexesSmart                                  1.58us  634.85K
EightThreadsTwoMutexesPersistent                             1.56us  639.93K
----------------------------------------------------------------------------
EightThreadsFourMutexesOrdered                               1.33us  753.45K
EightThreadsFourMutexesSmart                               794.36ns  936.34K
EightThreadsFourMutexesPersistent                          831.68ns    1.21M
----------------------------------------------------------------------------
EightThreadsEightMutexesOrdered                            791.52ns    1.26M
EightThreadsEightMutexesSmart                              548.05ns    1.51M
EightThreadsEightMutexesPersistent                         563.14ns    2.78M
----------------------------------------------------------------------------
EightThreadsSixteenMutexesOrdered                          785.40ns    2.11M
EightThreadsSixteenMutexesSmart                            541.27ns    1.60M
EightThreadsSixteenMutexesPersistent                       673.49ns    1.79M
----------------------------------------------------------------------------
SixteenThreadsTwoMutexesOrdered                              1.98us  505.83K
SixteenThreadsTwoMutexesSmart                                1.85us  541.06K
SixteenThreadsTwoMutexesPersistent                           3.13us  319.53K
----------------------------------------------------------------------------
SixteenThreadsFourMutexesOrdered                             2.46us  407.07K
SixteenThreadsFourMutexesSmart                               1.68us  594.47K
SixteenThreadsFourMutexesPersistent                          1.62us  617.22K
----------------------------------------------------------------------------
SixteenThreadsEightMutexesOrdered                            1.67us  597.45K
SixteenThreadsEightMutexesSmart                              1.62us  616.83K
SixteenThreadsEightMutexesPersistent                         1.57us  637.50K
----------------------------------------------------------------------------
SixteenThreadsSixteenMutexesOrdered                          1.20us  829.93K
SixteenThreadsSixteenMutexesSmart                            1.32us  757.03K
SixteenThreadsSixteenMutexesPersistent                       1.38us  726.75K
============================================================================
```

Reviewed By: djwatson

Differential Revision: D6673876

fbshipit-source-id: b57fdafb8fc2a42c74dc0279c051cc62976a4e07

Summary: [Folly] Avoid magic macros in Futures `FSM` - just use normal C++ types and functions instead.

Reviewed By: LeeHowes

Differential Revision: D7725582

fbshipit-source-id: 822e4ca6391a37dc4007833c975fe283cfe5105e

Summary: [Folly] Rename function to `tryUpdateState` in Futures `FSM` for clarity.

Reviewed By: LeeHowes

Differential Revision: D7725949

fbshipit-source-id: ccda21d990dbedfc4d0b86ab7cfb8eb68d93e429

Summary: [Folly] Use RAII `std::lock_guard` pattern in Futures `FSM` and `Core`.

Reviewed By: LeeHowes

Differential Revision: D7722808

fbshipit-source-id: e8a0d0ec1fee05cd723411f7b07f520dd56cdf22

Summary: [Folly] Let `Future::ensure` and `Future::onTimeout` invoke forwarded callbacks, just as `Future::then` and other callbacks are invoked.

Reviewed By: LeeHowes

Differential Revision: D7722762

fbshipit-source-id: 52b5fb6a9247d99718de808b0d28abba7dacdbd6

Summary:
Currently each of the lock proxies have distinct types and they are not
convertible from one to the other, for example the code below does not work

```
auto wlock = sync.wlock();
wlock.unlock();

auto ulock = sync.ulock();
wlock = ulock.moveFromUpgradeToWrite();
```

Reviewed By: yfeldblum

Differential Revision: D7658256

fbshipit-source-id: 1746a67193fc712fd4d4ff2ce41aa295f998211e

Summary: [Folly] Use exchange in `folly/Synchronized.h` as an example and to make the code there slightly shorter.

Reviewed By: aary

Differential Revision: D7722730

fbshipit-source-id: c594fc96cff11781b60a3848a860454bcf21c3ca

Summary: [Folly] Backport `std::exchange` to `folly/Utility.h`.

Reviewed By: aary

Differential Revision: D7722731

fbshipit-source-id: a4a68bfb9ec8b356b77f4a73bdadb7f2807d517f

Summary:
There was some code that optionally acquired a lock in a shared or exclusive
manner based on whether those methods were available for the mutex or not.
This was not used anywhere

Reviewed By: yfeldblum

Differential Revision: D7722906

fbshipit-source-id: b749527c13a1d980134cc23dea586c83a0b65e91

Reviewed By: yfeldblum

Differential Revision: D7721840

fbshipit-source-id: f816ba58da290e05d257447c42472d5fa99915e3

Summary:
As per title.
Closes https://github.com/facebook/folly/pull/827

Reviewed By: Orvid

Differential Revision: D7721855

Pulled By: yfeldblum

fbshipit-source-id: fe335dcfa83b4db04616e33e353fea52ebb2bbf2

Summary:
D7544180 introduced the `getAllocatedMemorySize` method. This diff adds it for
platforms where SSE2 instructions are not available.

Reviewed By: nbronson

Differential Revision: D7715573

fbshipit-source-id: af35f2dedf4a479895163d9dc18795ba397860f7

Summary:
`Optional` is often used for arguments and return values, and
when the function is inlined it is important to be able to perform
optimizations such as constant folding.

`launder` forces a load on every access to the `Optional` in GCC,
making it unsuitable for small hot functions. This is not specific to
the `asm` trick we use to backport `launder` to pre-GCC7: the same
code is generated in GCC7 with the builtin `std::launder`.

`launder` is needed for correctness, as replacing an object that
contains const or reference members in the same storage is
UB. However, it seems to be a benign UB that real compilers don't take
advantage of. In fact, the implementation of `std::optional` in both
libstdc++ and libc++ does not launder the storage:

https://github.com/gcc-mirror/gcc/blob/20d1a0756a0cf5072d0cdf3d2adab00063c224a7/libstdc%2B%2B-v3/include/std/optional#L881
https://github.com/llvm-mirror/libcxx/blob/8dd2afa20a01ee70e1a49c15de3de343aa8aa7d6/include/optional#L295

So it should be safe to follow these implementations and recover the
perf hit.

Reviewed By: luciang

Differential Revision: D7689228

fbshipit-source-id: 8283de56b0934583773a0d19f315ae7a8d556e8c

Differential Revision: D7663240

fbshipit-source-id: d7025eb220ff3f87b05988090297573377ca009a

Summary: Life-time of executor passed to subscribeVia can be tied to the previous stream. We have to eagerly subscribe to it to process onError/onComplete events and make sure we stop using that executor for any subsequent calls.

Reviewed By: phoad

Differential Revision: D7651264

fbshipit-source-id: c50090ff58a4835b439df2080e083a9302c40152

Summary:
long is 32-bit on 64-bit windows, unlike Linux, so 64-bit
integer constants should use the ULL suffix.

Reviewed By: mjhostet

Differential Revision: D7690572

fbshipit-source-id: a4d57555add63a4a88aceda1b02531eb8c5e1f0f

Summary:
When building with MSVC and vcpkg, dependencies come in both debug and release versions. Fix the searching logic to search for both names and handle them appropriately.

Also silence a few warnings under MSVC 2015 Update 3.

Reviewed By: yfeldblum

Differential Revision: D7683367

fbshipit-source-id: 662fcc7170b260f129610ed47b6afedbe20933b7

Summary:
Add a return value to BlockingQueue interface - add() returns true if
we were able to successfully handoff this work item to an existing thread.

Implementation is straightforward in LifoSem.

Reviewed By: magedm

Differential Revision: D7477279

fbshipit-source-id: 56ea17672a97ad722fd190baf0433ac68c440750

Summary:
The changes in this diff changes string comparisons using the compare method to
using equality operators.

Motivation:
- readability, simplifies code
- compare method is intended for sorting functions

This is clang check used: [Link Here](https://clang.llvm.org/extra/clang-tidy/checks/readability-string-compare.html)

Reviewed By: yfeldblum

Differential Revision: D7675353

fbshipit-source-id: dbe2ac120ac9513db489b4d18824f9d47e5b4eac

Summary:
This diff moves memory allocation & a bunch of std::moves and some shared_ptr
stuff outside the spinlock, resulting in much improved concurrency.

Reviewed By: yfeldblum

Differential Revision: D7674026

fbshipit-source-id: 37accb31e4dcd78330bcda587e16595512d4c5f8

Summary:
In code that accidentally sets an impossibly huge stack size
(RLIMIT_SIZE=-1, for example), MemoryIdler can unmap pages beyond the
stack that are still in use.  This diff causes that case to assert in
debug builds and disable memory idling in production.

Reviewed By: edwinsmith

Differential Revision: D7688511

fbshipit-source-id: 7ef4261aaa3273ac7edf9edf596c2ea504e35877

Summary:
prepare() blocks mostly just lock locks, but we don't know what order to lock - so similar
to std::lock, just iterate using try_lock until success.

Reviewed By: ot

Differential Revision: D7676738

fbshipit-source-id: 2e0d28e4829a3a21d361a5801383c1aad0d66757

Summary:
Summary of the changes
 ---
- Fix broken MSVC build:
  - Compiling `GenerateFingerprintTables.cpp` complained about missing header file `glog/logging.h`.
  - Targets `GenerateFingerprintTables` and `folly_fingerprint` don't specify `FOLLY_INCLUDE_DIRECTORIES` in its include directories.

* Introduce a "shiny" target `folly_deps` for managing folly's dependencies and interface specification.
  * `folly_deps` is an [INTERFACE library target](https://cmake.org/cmake/help/v3.0/command/add_library.html).
  * It encapsulates the interface dependencies (compile definitions, include directories, link libraries, etc.) for other targets.
  * The usage of the new target is clean and simple:
    `target_link_libraries(<target_name> (PUBLIC|PRIVATE) folly_deps)`
    (except for OBJECT library targets, like `folly_base` - included in the change).

Possible modifications
 ---
The name `folly_deps` could be replaced with a better one.
The target can be extended to include the PUBLIC compile options set on individual targets.
Reviews and suggestions welcome.
Closes https://github.com/facebook/folly/pull/818

Reviewed By: simpkins

Differential Revision: D7642870

Pulled By: Orvid

fbshipit-source-id: c1c5fdae67f5a677c82f05757217af6b6de9db02

Summary:
Turns out we needed this method to be virtual to mock it out in tests because it makes
a bunch of syscalls.

Reviewed By: yangchi

Differential Revision: D7665938

fbshipit-source-id: 1ae5768ade2c927929f5cb1f9e1ad62dad1ba237

Reviewed By: aary

Differential Revision: D7680645

fbshipit-source-id: 6a3742c215a6924ec5c1c5b8bc1d2bff315355e7

Summary:
Add `try_lock` methods to `folly::Synchronized` and add the corresponding
extensions to `LockTraits`.  These return `LockedPtr`s that are valid and
convert to true when the lock operation was successful, null otherwise

override-unit-failure

Reviewed By: yfeldblum, ot

Differential Revision: D7651765

fbshipit-source-id: eb85987a2e4476cd916747dfc2ae69d124690ee6

Summary: TDigest is designed to process a stream of data in batches. DigestBuilder is a fast, thread safe approach for buffering those writes and building a digest.

Reviewed By: davidtgoldblatt

Differential Revision: D7582745

fbshipit-source-id: 528ad9b21685746887b3a602d433662221fb875a

Summary:
Use new refcount hazptr feature.

This prevents many roundtrips through release()->retire()->~Node()->release()->retire() etc, and instead can call delete immediately through most of the chain

See D6142066

Reviewed By: yfeldblum

Differential Revision: D6290004

fbshipit-source-id: d8cfb2aa41260918a7f201765febc31d558742bb

Summary: Revert "Use unbounded queue in NotificationQueue"

Reviewed By: magedm

Differential Revision: D7669679

fbshipit-source-id: 269139fc8238896640fc60ed36c83e728ed489b4

Summary: This diff adds reads for sum, mean, and count on TDigest. The results are calculated at merge time, to make reads O(1).

Reviewed By: anakryiko

Differential Revision: D7639133

fbshipit-source-id: bb8f203ec0ed3197f090d2ce9223a2e9d1bca752

Summary:
Unset the error message callbacks when err
message so that we dont deliver errors when
not needed

Reviewed By: yfeldblum

Differential Revision: D7661052

fbshipit-source-id: 5a2330b2cd11f844649d56343307e2c75b626bdc

Summary: blame D7477268.  Some callsites use UnboundedBlockingQueue with non-copyable CPUTasks, must also have std::move here.

Reviewed By: yfeldblum

Differential Revision: D7655710

fbshipit-source-id: cf8dba1df0c1703ffea1c0c0445c7d14deaf1d61

Summary: Add missing markdown notation

Reviewed By: shixiao

Differential Revision: D7655769

fbshipit-source-id: a0db34846e48afd845b8878de84764d30330b096