Summary: [Folly] Smaller implementations for `findFirstSet`, `findLastSet`.

Reviewed By: nbronson

Differential Revision: D8471816

fbshipit-source-id: 699af98d404e6dd76df02e344d09c850abc1c32f

Summary: [Folly] Split BitIterator test and bench, improving the benchmark in some small ways, and fixing missing `std::iterator_traits` applications along the way.

Reviewed By: nbronson

Differential Revision: D8509129

fbshipit-source-id: 0fad0ce4d1c5abf76e33e04e98db36912e9cb651

Summary:
Before this diff the vector storage policy for F14 allocated the
chunk array and the value_type array via separate calls to the allocator.
After this diff they are performed via a single allocation using a byte
allocator rebound from the original value allocator.  This will halve
the number of calls to malloc and free from a majority of F14FastMap-s
and F14FastSet-s (and from all F14VectorMap and F14VectorSet).
The optimization is likely to be most important for small sets and maps.

In a microbenchmark that just creates and destroys 1-element
F14VectorMap-s, this diff was a 20% CPU win.

This diff is not pure win.  The unified allocation of
`(64+10*sizeof(value_type))*N` causes more internal fragmentation in
jemalloc for most value_type sizes than separate allocations of `64*N`
and `10*sizeof(value_type)*N`.  48-byte value_type is probably the most
affected in practice; this diff will increase the memory footprint
of vector-policy tables with 48-byte keys by 13% once internal memory
fragmentation is taken into account.

Taking into account the default jemalloc allocation classes,

    sizeof(value_type)  |  footprint change
    --------------------|--------------------
                   24   |   1.03797
                   32   |   1.
                   40   |   1.07462
                   48   |   1.1273
                   56   |   1.0185
                   64   |   1.06558
                   72   |   1.02742
                   80   |   1.02672
                   88   |   1.
                   96   |   1.
                  104   |   1.05961
                  112   |   1.05849
                  120   |   0.965071
                  128   |   1.10305
                  136   |   0.942188
                  144   |   0.942984
                  152   |   1.05624
                  160   |   1.05549
                  168   |   0.927757
                  176   |   1.0238
                  184   |   1.02353
                  192   |   1.02327
                  200   |   1.08255
                  208   |   1.08173
                  216   |   1.08093
                  224   |   1.08015
                  232   |   0.981946
                  240   |   0.982102
                  248   |   0.982255
                  256   |   1.12316

Reviewed By: yfeldblum

Differential Revision: D8485933

fbshipit-source-id: 1a7df390e11e71e1f56f23527aebec4806eb03d1

Summary:
Restrict F14 availability (and use the fallback version) on 32-bit platforms
until we audit the code, removing assumptions such as `size_t` is 64-bit and
finding a mixer that does not require `__int128`.

Reviewed By: nbronson

Differential Revision: D8525351

fbshipit-source-id: 54fce48fe94235c8525074216426cf254db26b4e

Summary: Fix broken build due to "missing braces around initializer" error

Reviewed By: nbronson

Differential Revision: D8541080

fbshipit-source-id: f73f973c575b6d3dad999a454d1306f7608122c7

Summary:
If RTTI is disabled for the compilation unit, simply skip recording the type of
F14Policy in computeStats.

This diff also contains a few fixes for when folly is built without RTTI.

Reviewed By: nbronson

Differential Revision: D8523618

fbshipit-source-id: dfbfa93ec462c0ff72c06b9f65d61b081e361f41

Summary:
The headerfile was removed from the source tree, but is still
referenced, causing autotools based builds to fail.
Closes https://github.com/facebook/folly/pull/874

Reviewed By: nbronson

Differential Revision: D8531520

Pulled By: calebmarchent

fbshipit-source-id: 33844e57f4551a66dd13ab9ec03a441c7779c41e

Summary: Adds header to the test headers exported by folly

Reviewed By: yfeldblum

Differential Revision: D8524926

fbshipit-source-id: 06983789c3ee9e403211fb5335365663878c2590

Summary: Extend AsyncUDPServerSocket to support dynamically pausing/resuming reading from the underlying socket. This functionality already exists for AsyncServerSocket but not for UDP server sockets.

Reviewed By: djwatson

Differential Revision: D8358256

fbshipit-source-id: 7d5cf14b656ef9280747515b23cd0ae2899ec38b

Summary:
Sometimes get_executor gets called from threads where there is no asyncio evenloop.
In those cases return NULL.

The caller is responsible for this situation.

Reviewed By: yfeldblum

Differential Revision: D8492709

fbshipit-source-id: 325689ecd4541b9ba097cfe1cb4d6d61ad81cb43

Summary:
Using the alignment bits to store the index for a packed
iterator is one of the steps toward better support of 32-bit platforms
(and pointer authentication in future platforms, such as ARMv8.3-A).
Previously this was complicated by a desire to make construction of
a packed ItemIter as cheap as possible.  The ItemPtr has a variable
number of bits available due to alignment, which may not be sufficient
to encode the index.  This diff observes that we can piggyback on the
chunk alignment to efficiently deduce the remaining bits of the index.
If sizeof(Item) gives us only 2 bits of alignment, for example, then we
can deduce 2 bits of the index from the Item*.

Differential Revision: D8452991

fbshipit-source-id: 40dfd9957da3733090bb947646c553620cc7d33d

Summary: Cleanup checks if the current thread has retired objects during bulk reclaim. It does so by flushing the thread local set of retired objects and checking if domain's list of retired objects.

Reviewed By: djwatson

Differential Revision: D8503159

fbshipit-source-id: 59ddd29d8ae1429b62b5bc9511b84e4c9e7128f2

Summary: Add shutdown indicator to domain to be checked in retire to avoid accessing thread local private list of objects at shutdown time when the thread local structure may be already destroyed.

Reviewed By: djwatson

Differential Revision: D8501530

fbshipit-source-id: 16adef34f2fd265f35851c792bd9e62a2f19b81a

Summary: As title

Reviewed By: yfeldblum

Differential Revision: D8517773

fbshipit-source-id: 971178184e446c9de476cf43f65e04f49f05e0ad

Summary: facepaw

Reviewed By: yfeldblum

Differential Revision: D8465375

fbshipit-source-id: 9cbd00286963366e8e987b7fe865ec5d334e65b3

Reviewed By: shixiao

Differential Revision: D8516223

fbshipit-source-id: 0e259ce65183d779f066869091cdea837b7bd237

Summary:
Sometimes unit tests compare the JSON output of a
component. We want a simple way to compare them semantically and also
to ignore numerical errors for double values.

Reviewed By: yfeldblum

Differential Revision: D8505209

fbshipit-source-id: 04da89889f08a595e8296716f71b9a22156e3506

Summary: [Folly] Let `window` work with functions returning `SemiFuture`.

Reviewed By: LeeHowes

Differential Revision: D8505836

fbshipit-source-id: 51c14b131760528eb6c367298cb23c4deec30ab3

Summary: [Folly] Let `makeSemiFutureWith` accept functions returning `Future`, joining what would otherwise be the resulting `SemiFuture<Future<...>>` into `SemiFuture<...>`.

Reviewed By: LeeHowes

Differential Revision: D8505834

fbshipit-source-id: 10b626fae00b5002877295b59716066f089cb6a8

Summary:
rehash's max_size check was previously relying on the optimizer
to inline and then remove a loop whose value could be determined at
compile time.  It failed to do this even in some trivial cases, wasting
about 10 nanoseconds per rehash.  This code moves the max_size check lower
(more than 6 entries) and removes the loop entirely.

Reviewed By: ot

Differential Revision: D8499582

fbshipit-source-id: 8f5c288d3922b094da81ee9261254c729e8cb1b9

Summary: exception_wrapper requires the actual exception object to be passed in for any std::exception.

Reviewed By: memorybank

Differential Revision: D8501214

fbshipit-source-id: 034a4c7df9979711dcb3740ca5c4313944f29cb6

Summary:
The `glog/logging.h` header is a bit expensive here considering its size, and how frequently `Range.h` is used.

Replace the `DCHECK_${comparison}` macro usage with macros defined in this file.

Reviewed By: yfeldblum

Differential Revision: D8473303

fbshipit-source-id: cc2a7e9eabab2c1f83a377de5191f708f1c9f317

Summary: Adjust the growth factor based on the StaticMetaBase::head_::elementsCapacity

Reviewed By: yfeldblum

Differential Revision: D8409650

fbshipit-source-id: 189b839e19a1d3f2f1ac8e4b35a2f11a4d319ad7

Summary:
- Use the hazard pointer library under folly/synchronization.
  - NodeT derived from hazptr_obj_base_linked.
  - Bucket heads are hazptr_root-s with dtor that automatically unlinks nodes
  - Provides support for uncertain removal of NodeT-s both from NodeT and Buckets
  - As intended, hazptr_cleanup reclaims all unprotected removed objects even if they have not been determined to be retirable at the start of cleanup.

Fixes the following:
- The pattern of calling h.get_protected(node->next_), when hazptr_holder h is protecting node is unsafe because try_protect (inside get_protected) may fail and we end protecting neither node nor next. This diff uses a different hazptr_holder to protect the next node. A correct pattern is to call h2.get_protected(node->next_) then h.swap(h2); h2.reset();
- The pattern of calling h2.reset(node) then h1.reset() to continue protecting a node already protected by h1 is unsafe because h2's protection may be too late after node was retired. A correct pattern is h2.swap(h1).

Reviewed By: djwatson

Differential Revision: D7708325

fbshipit-source-id: 617dcfe19410071888abafa32f0e1ada9d123983

Summary: [Folly] `bool_constant` (C++17 backport) and `index_constant`.

Reviewed By: aary

Differential Revision: D8440131

fbshipit-source-id: 2bc4fae1e2d1f404d4060c209ee325beebe2a415

Summary:
A comment to `FutureAlreadyContinued` to explain to readers in what circumstance it is thrown.

(Note: this ignores all push blocking failures!)

Reviewed By: yfeldblum

Differential Revision: D8460097

fbshipit-source-id: 49657e030efe72c026c1c3eea3612952746bb0e1

Summary: Add `explicit` to `MoveCtorOnly::MoveCtorOnly(int)` in FutureTest.cpp

Reviewed By: yfeldblum

Differential Revision: D8439496

fbshipit-source-id: 51217f186aa9b79d342a7be7f460d0a9c3f070c1

Summary:
When passing elements of a set or map through a bulk API that understands
arrays, it is a useful optimization to be able to iterator or visit
contiguous ranges rather than individual elements.  This diff adds
visitContiguousRanges to F14 maps and sets, which repeatedly passes a
contiguous range to the visitor.  The range is identified with a begin
and end value_type const*.  Each value_type of the table will be included
in exactly one of the passed ranges, and the number of ranges will be
minimized whenever possible.

Reviewed By: yfeldblum

Differential Revision: D8332897

fbshipit-source-id: a7cd5d670b14faeeef97497cccd4cb0a3b07dd50

Summary:
vshrn_n_u16 can be used to efficiently get a bit of information
from every byte in a 16-byte vector into an 8-byte vector, which is better
than the previous NEON sequence used during tag matching.  The resulting
code is faster and smaller on aarch64.  x86_64 code is refactored but
should compile to the same assembly.

Reviewed By: shixiao

Differential Revision: D8420917

fbshipit-source-id: 21a9f920f55ffc479b20fee6882a5987b626c89a

Summary: Add rvalue-qualified overloads of Future::get() and get(dur) which invalidate their this-object.

Reviewed By: yfeldblum

Differential Revision: D8242442

fbshipit-source-id: 4dea8a41878d59f6088504df2b8b3e686d581c89

Summary:
Codemod non-pointer expressions:
   - expr.get() ==> std::move(expr).get()
   - expr.get(dur) ==> std::move(expr).get(dur)
when expr is not already an xvalue.

Reviewed By: yfeldblum

Differential Revision: D8430137

fbshipit-source-id: 20da463f9cceb5cb1e71a7226f3b11d1e8007011

Summary: When hazptr_priv dtor pushes objects to the domain and that happens to trigger (either due to timed cleanup or reaching the bulk reclaim threshold) bulk reclamation that retires objects. These newly retired objects should be pushed to the domain and not into the hazptr_priv.

Reviewed By: djwatson

Differential Revision: D8410795

fbshipit-source-id: c7af01cc41a1d82896bd3700fa072f698c0aa77b

Summary: Currently the implementation just relies on futures::sleep. Ideally it should be able to use Executor's timer if available.

Reviewed By: yfeldblum

Differential Revision: D8404592

fbshipit-source-id: e952a0cc3d99bc528ea14ff5c68835d63a71e685

Summary:
[Folly] Optimize Futures Core state-dependent fields, controlling when they are constructed and destructed.

* Reduces layout size by removing the `Optional` wrapper for the result.
* Reduces code size by removing checks and destructions in assignment operators which are not in constructors for `Optional`, `Try`, `Function`, and `shared_ptr`.

Reviewed By: andriigrynenko

Differential Revision: D8346365

fbshipit-source-id: 83ac164dc36934065f2fcfb112440869d023b674

Reviewed By: aary

Differential Revision: D8393345

fbshipit-source-id: 5fc9bbfb3fa1dc63077cd406f4335c2a7967a53d

Summary:
This diff extends heterogeneous key handling (when the hasher and
key equality functor are transparent) to mutating operations.  If a key
of type K was previously eligible for heterogeneous find and key_type can
be constructed from the key, then that construction can be deferred until
after it is verified that the key is not previously in the table when
using any of the operations that may insert a new element.  If the key was
already present then this avoids the construction of key_type entirely.
Heterogeneous erase is also added in the obvious fashion.

Construction of key_type from K can be accomplished without key_type's
cooperation by the use of an explicit conversion operator, such as the
explicit operator std::string recently added to StringPiece.  That means
that a F14 map or set with std::string key and transparent StringPiece
hash and equality can now use StringPiece natively as a key.

Destructuring is applied whenever possible, so the heterogeneous key
type K may be found as the first element of a pair (for map insert or
emplace) or even inside the first tuple when using map emplace with
std::piecewise_construct.

This diff adds heterogeneous key support to

    Map::insert
    Map::insert_or_assign
    Map::emplace
    Map::try_emplace
    Map::operator[]
    Set::insert
    Set::emplace

Reviewed By: yfeldblum

Differential Revision: D8301887

fbshipit-source-id: 1a45e13739c550f094afe09123839a3c9cd892ff

Summary:
[Folly] In Futures Core, destroy context when destroying callback since they basically go together.

Also removes expectations in an Eden FS test case which affirm the old behavior, along with a TODO to remove the expectations once the affirmed behavior is fixed.

Reviewed By: marshallcline

Differential Revision: D8347040

fbshipit-source-id: ed9fec932ad1e0aa1e40675cf70081d19bbe4325

Summary:
[Folly] Use a simpler atomic state in Futures `Core` v.s. `FSM` which abstracts an atomic state plus a spin-lock.

The `FSM` abstraction can be useful in more complex cases, but is not needed in the current case. All that is needed is a single barrier state, which is `Done` - setting callback and result happen before state transitions to `Done`, while invoking callback with result happens after state transitions to `Done`.

Reviewed By: marshallcline

Differential Revision: D8083703

fbshipit-source-id: 42d96b41cbdac5e7c42f3f8a661d5db3113655db

Summary:
[Folly] Use `terminate_with` in Futures `Core` invalid transitions.

Both `Promise` and `Future` check state validity before calling the `Core` transition methods and throws in invalid state. So `Core` no longer needs to throw and may terminate instead.

Reviewed By: marshallcline

Differential Revision: D8346113

fbshipit-source-id: 9ff158673149096789b29544453262797b06d441

Summary: [Folly] `folly::terminate_with`, to terminate as if by forwarding to `folly::throw_exception` but in a `noexcept` context.

Reviewed By: marshallcline

Differential Revision: D8345962

fbshipit-source-id: bc5cf5d3a3e1f085dd2989c940a6ea753a520cbf