## File: README.md Folly: Facebook Open-source Library =================================== # What is `folly`? Folly (an acronym loosely after Facebook Open Source Library) is a library of C++20 components designed with practicality and efficiency in mind. **Folly contains a variety of core library components used extensively at Facebook**. In particular, it's often a dependency of Facebook's other open source C++ efforts and place where those projects can share code. It complements (as opposed to competing against) offerings such as Boost and of course `std`. In fact, we embark on defining our own component only when something we need is either not available, or does not meet the needed performance profile. We endeavor to remove things from folly if or when `std` or Boost obsoletes them. Performance concerns permeate much of Folly, sometimes leading to designs that are more idiosyncratic than they would otherwise be (see e.g. `PackedSyncPtr.h`, `SmallLocks.h`). Good performance at large scale is a unifying theme in all of Folly. ## Check it out in the intro video [](https://www.youtube.com/watch?v=Wr_IfOICYSs) # Logical Design Folly is a collection of relatively independent components, some as simple as a few symbols. There is no restriction on internal dependencies, meaning that a given folly module may use any other folly components. All symbols are defined in the top-level namespace `folly`, except of course macros. Macro names are ALL_UPPERCASE and should be prefixed with `FOLLY_`. Namespace `folly` defines other internal namespaces such as `internal` or `detail`. User code should not depend on symbols in those namespaces. # Physical Design At the top level Folly uses the classic "stuttering" scheme `folly/folly` used by Boost and others. The first directory serves as an installation root of the library (with possible versioning a la `folly-1.0/`), and the second is to distinguish the library when including files, e.g. `#include `. The directory structure is flat (mimicking the namespace structure), i.e. we don't have an elaborate directory hierarchy (it is possible this will change in future versions). The subdirectory `experimental` contains files that are used inside folly and possibly at Facebook but not considered stable enough for client use. Your code should not use files in `folly/experimental` lest it may break when you update Folly. The `folly/folly/test` subdirectory includes the unittests for all components, usually named `ComponentXyzTest.cpp` for each `ComponentXyz.*`. The `folly/folly/docs` directory contains documentation. # What's in it? Because of folly's fairly flat structure, the best way to see what's in it is to look at the headers in [top level `folly/` directory](https://github.com/facebook/folly/tree/main/folly). You can also check the [`docs` folder](folly/docs) for documentation, starting with the [overview](folly/docs/Overview.md). Folly is published on GitHub at https://github.com/facebook/folly. # Build Notes Because folly does not provide any ABI compatibility guarantees from commit to commit, we generally recommend building folly as a static library. folly supports gcc (5.1+), clang, or MSVC. It should run on Linux (x86-32, x86-64, and ARM), iOS, macOS, and Windows (x86-64). The CMake build is only tested on some of these platforms; at a minimum, we aim to support macOS and Linux (on the latest Ubuntu LTS release or newer.) ## `getdeps.py` This script is used by many of Meta's OSS tools. It will download and build all of the necessary dependencies first, and will then invoke cmake etc to build folly. This will help ensure that you build with relevant versions of all of the dependent libraries, taking into account what versions are installed locally on your system. It's written in python so you'll need python3.6 or later on your PATH. It works on Linux, macOS and Windows. The settings for folly's cmake build are held in its getdeps manifest `build/fbcode_builder/manifests/folly`, which you can edit locally if desired. ### Dependencies If on Linux or MacOS (with homebrew installed) you can install system dependencies to save building them: # Clone the repo git clone https://github.com/facebook/folly # Install dependencies cd folly sudo ./build/fbcode_builder/getdeps.py install-system-deps --recursive If you'd like to see the packages before installing them: ./build/fbcode_builder/getdeps.py install-system-deps --dry-run --recursive On other platforms or if on Linux and without system dependencies `getdeps.py` will mostly download and build them for you during the build step. Some of the dependencies `getdeps.py` uses and installs are: * a version of boost compiled with C++14 support. * googletest is required to build and run folly's tests. ### Build This script will download and build all of the necessary dependencies first, and will then invoke cmake etc to build folly. This will help ensure that you build with relevant versions of all of the dependent libraries, taking into account what versions are installed locally on your system. `getdeps.py` currently requires python 3.6+ to be on your path. `getdeps.py` will invoke cmake etc. # Clone the repo git clone https://github.com/facebook/folly cd folly # Build, using system dependencies if available python3 ./build/fbcode_builder/getdeps.py --allow-system-packages build It puts output in its scratch area: * `installed/folly/lib/libfolly.a`: Library You can also specify a `--scratch-path` argument to control the location of the scratch directory used for the build. You can find the default scratch install location from logs or with `python3 ./build/fbcode_builder/getdeps.py show-inst-dir`. There are also `--install-dir` and `--install-prefix` arguments to provide some more fine-grained control of the installation directories. However, given that folly provides no compatibility guarantees between commits we generally recommend building and installing the libraries to a temporary location, and then pointing your project's build at this temporary location, rather than installing folly in the traditional system installation directories. e.g., if you are building with CMake you can use the `CMAKE_PREFIX_PATH` variable to allow CMake to find folly in this temporary installation directory when building your project. If you want to invoke `cmake` again to iterate, there is a helpful `run_cmake.py` script output in the scratch build directory. You can find the scratch build directory from logs or with `python3 ./build/fbcode_builder/getdeps.py show-build-dir`. ### Run tests By default `getdeps.py` will build the tests for folly. To run them: cd folly python3 ./build/fbcode_builder/getdeps.py --allow-system-packages test ### `build.sh`/`build.bat` wrapper `build.sh` can be used on Linux and MacOS, on Windows use the `build.bat` script instead. Its a wrapper around `getdeps.py`. ## Build with cmake directly If you don't want to let getdeps invoke cmake for you then by default, building the tests is disabled as part of the CMake `all` target. To build the tests, specify `-DBUILD_TESTS=ON` to CMake at configure time. NB if you want to invoke `cmake` again to iterate on a `getdeps.py` build, there is a helpful `run_cmake.py` script output in the scratch-path build directory. You can find the scratch build directory from logs or with `python3 ./build/fbcode_builder/getdeps.py show-build-dir`. Running tests with ctests also works if you cd to the build dir, e.g. `(cd $(python3 ./build/fbcode_builder/getdeps.py show-build-dir) && ctest)` ### Finding dependencies in non-default locations If you have boost, gtest, or other dependencies installed in a non-default location, you can use the `CMAKE_INCLUDE_PATH` and `CMAKE_LIBRARY_PATH` variables to make CMAKE look also look for header files and libraries in non-standard locations. For example, to also search the directories `/alt/include/path1` and `/alt/include/path2` for header files and the directories `/alt/lib/path1` and `/alt/lib/path2` for libraries, you can invoke `cmake` as follows: ``` cmake \ -DCMAKE_INCLUDE_PATH=/alt/include/path1:/alt/include/path2 \ -DCMAKE_LIBRARY_PATH=/alt/lib/path1:/alt/lib/path2 ... ``` ## Ubuntu LTS, CentOS Stream, Fedora Use the `getdeps.py` approach above. We test in CI on Ubuntu LTS, and occasionally on other distros. If you find the set of system packages is not quite right for your chosen distro, you can specify distro version specific overrides in the dependency manifests (e.g. https://github.com/facebook/folly/blob/main/build/fbcode_builder/manifests/boost ). You could probably make it work on most recent Ubuntu/Debian or Fedora/Redhat derived distributions. At time of writing (Dec 2021) there is a build break on GCC 11.x based systems in lang_badge_test. If you don't need badge functionality you can work around by commenting it out from CMakeLists.txt (unfortunately fbthrift does need it) ## Windows (Vcpkg) Note that many tests are disabled for folly Windows builds, you can see them in the log from the cmake configure step, or by looking for WINDOWS_DISABLED in `CMakeLists.txt` That said, `getdeps.py` builds work on Windows and are tested in CI. If you prefer, you can try Vcpkg. folly is available in [Vcpkg](https://github.com/Microsoft/vcpkg#vcpkg) and releases may be built via `vcpkg install folly:x64-windows`. You may also use `vcpkg install folly:x64-windows --head` to build against `main`. ## macOS `getdeps.py` builds work on macOS and are tested in CI, however if you prefer, you can try one of the macOS package managers ### Homebrew folly is available as a Formula and releases may be built via `brew install folly`. You may also use `folly/build/bootstrap-osx-homebrew.sh` to build against `main`: ``` ./folly/build/bootstrap-osx-homebrew.sh ``` This will create a build directory `_build` in the top-level. ### MacPorts Install the required packages from MacPorts: ``` sudo port install \ boost \ cmake \ gflags \ git \ google-glog \ libevent \ libtool \ lz4 \ lzma \ openssl \ snappy \ xz \ zlib ``` Download and install folly with the parameters listed below: ``` git clone https://github.com/facebook/folly.git cd folly mkdir _build cd _build cmake .. make sudo make install ``` --- ## File: folly/coro/safe/docs/Captures.md ## Simple guide to `bind::capture()`, `capture` and friends If you are just reading some code with `bind::capture()` arguments -- think of these as zero-cost (compile-time) smart pointers, each owned by the `async_closure` taking the arg. For example, `n` below is a `capture`. It is an **owned capture**, a wrapper around `int` whose lifetime is tightly bound to the closure. ```cpp namespace bind = folly::bind; // Can add to `.cpp` files and project namespaces assert(15 == co_await async_closure( // NB: Can omit the outer `args` -- its sole arg is `bind::ext::like_args` bind::args{bind::capture(5)}, [](auto n) -> closure_task { co_await async_closure( bind::args{n}, [](auto nRef) -> closure_task { *nRef += 10; co_return; }); co_return *n; })); ``` On the other hand, `nRef` is `capture`. It is a **capture reference** that was implicitly made from `n`. Per `LifetimeSafetyDesign.md`, there are various compile-time checks that make it harder to construct invalid capture references. ### When & how to use `bind::capture()` 1. If type `T` requires async RAII (`co_cleanup`), you will need `bind::capture_in_place()`. For a working example, see `BackgroundTask.h` or `SafeAsyncScope.h`. 1. Suppose you passed a `co_cleanup` type `T` into an async closure (example: `safeAsyncScope<>()`). Then, the closure will internally own `co_cleanup_capture`, and the closure's coroutine will get a capture reference `c`. Now imagine your closure wants to pass a **reference** to a variable `v` into the cleanup object, something like `c.someMethod(v)`. Any correctly implemented `co_cleanup` type should require that its inputs are valid beyond the point where its cleanup is awaited. For example, cleanup runs after your closure's coroutine exits, so any references to your coro's stack are unsafe. The `capture` type system causes such safety bugs not to compile. See `LifetimeSafetyBenefits.md` for more. `capture`s are our mechanism for making lifetime-safe references. In order to make `c.someMethod(v)` work, you will need to make `v` itself a capture, by having your closure take `auto v`, and make it either: - `bind::capture()` for an owned capture, **OR** - `parentA` to make a capture reference from a parent's capture. ### Accessing `capture`s If your function takes a capture, here is all you need to know: - All `capture` class templates act like pointers. Use `->` and `*` to access your `T`. - Don't worry about the difference between the `capture` templates -- either pass by `auto`, or use the type from the compiler error. - Never move the capture wrapper, always move the `T` inside it. In other words -- good: `*std::move(cap)`, bad: `std::move(*cap)`. - Captures should be transparent to value-category modifiers. That is: * `const capture` acts like & converts to `capture`. * `capture&` converts to `capture`. * `capture&&` converts to `capture`. - If you pass `capture c` into an `async_closure`, it is always passed by-reference. That is, the child closure automatically gets `capture`, or `capture` from `std::move(c)`. - `capture` behaves much like `T`, besides the above caveats (must dereference; pass-by-reference in async closures): * For value type `V`, `capture` represents ownership. The capture wrapper belongs to whatever constructed it, and **should not be moved** -- but, if `V` is movable, you can of course move the inner type: ```cpp V dst = *std::move(srcCap); ``` * `capture` is copyable & movable. * `capture` is move-only, can *explicitly* convert to `capture` *Caveat*: To reduce use-after-move errors, dereferencing requires rvalues. That is, `*rcap` won't work -- you must `*std::move(rcap)`. - *Power users:* It is a limitation of C++ that `operator->` loses value category by returning a pointer. In special cases where this is critical for a good UX, it is technically possible to address that returning a pointer to a specially crafted rvalue proxy for `rval_ptr` queries. In regular metaprogramming, you should use `(*cap).member` for deref. ### `safe_alias` warning: the "composition hole" & lambda captures It bears repeating the "composition hole" warning from `SafeAlias.h`. - If a type stores any kind of reference (like `capture`) or pointer, or anything else that's not a straight-up value type, then it **must** correctly specialize `safe_alias_of`. - When your child closure gets a lambda (or another object) from a parent, it is **particularly risky** to pass `capture`s into its `operator()` (or other member function). If the parent stored any reference in that object, (as easy as `[&](...) { ... }`, then the child can incorrectly plumb through its own short-lived references into the parent's scope. ### Syntax sugar: `capture_indirect>` To access `capture capSharedN`, you need to dereference twice: ```cpp **capSharedN += 10; ``` Writing `bind::capture_indirect()` gives you `capture_indirect`, which needs just one dereference, and can still access the `shared_ptr` via `get_underlying_unsafe()` -- but see its docblock for **RISKS**. **Watch out:** Be sure to null-check `capture_indirect` via its `operator bool`. This is important, since, the underlying type is typically nullable! ### Escape hatch: Capture-by-reference Use via `bind::capture_const_ref{}`, `bind::capture{bind::const_ref{}}`, `bind::capture_mut_ref{}`, etc in your closure's `bind::args{}` list. This mechanism solves problems similar to `AfterCleanup.h`, but after-cleanup is strictly safer, so you should prefer it when applicable. Capture-by-ref is a way of turning a reference from a parent scope into a `capture` or `` inside a child `async_now_closure`. While the `now_task` restriction aids lifetime safety, the user must still be careful to avoid giving the child the ability to store short-lived child refs in the parent's scope. To fix a concrete instance of this problem, the `BindAsyncClosure.h` implementation blocks the capture-by-ref mechanism from passing `co_cleanup` refs & `captures`. #### Design notes for capture-by-reference This section discusses potential relaxations of the capture-by-ref safety rules, which would make it more broadly applicable. However, the relaxations would come with both new footguns, and new complexity, so I'm currently thinking of them as "rejected designs" rather than future work. **Note 1:** It would be within the spirit of regular RAII to defer awaiting the closure to a later point in the current scope. That is, the `safe_task` taking these `capture_ref()` args would be marked down to `<= lexical_scope_ref` safety. This could be a new safety level with: ```cpp after_cleanup_ref >= lexical_scope_ref >= shared_cleanup ``` The valid lifetime for this body-only `safe_task` is clearly shorter than `after_cleanup_ref` -- it's invalid whenever the captured refs are destroyed, which (under typical RAII) is a bit longer than the lexical lifetime of the task. In the `lexical_scope_ref` scenario, the user can, of course, invalidate the reference before awaiting the task, but it takes a bit of effort, and might be covered if the [P1179R1 lifetime safety profile](https://wg21.link/P1179R1) is standardized. For example: ```cpp std::optional> t; { int i = 5; t = async_closure([](auto i) -> closure_task { std::cout << *i << std::endl; co_return; }, capture_ref(i)); ++i; } // BAD: The reference to `i` is now invalid! co_await std::move(*t); ``` **Note 2:** The way that `async_closure(... bind::capture_const_ref(...) ...)` behaves, it seems like we could just universally allow creating `lexical_scope_capture` from `T&` -- even outside `async_closure` invocations. `Captures.h` would need to support auto-upgrade of `lexical_scope_capture` to `capture` or `after_cleanup_capture`, depending on `shared_cleanup` status. This "universal" implementation would be more complex, but without `async_closure()`'s capture-upgrade semantics, there's not a lot of value in obtaining a `lexical_scope_capture` -- for example, you can't use it to schedule work on a nested `safe_async_scope`. ### Debugging lifetime safety compile errors If you're working with captures, and get a compile error about `safe_task`, `safe_alias_of`, or similar, there is a good chance that you triggered a lifetime safety check. Read `LifetimeSafetyDebugging.md` for what to do next -- it also covers the lifetime safety design of `Captures.h`. ### Implementation gaps - While `Captures.h` mentions `restricted_co_cleanup_capture`, the implementation is not finished. See `FutureWork.md` for more details. - `FutureLinters.md` describes several linters that help achieve maximum lifetime safety when using captures. --- --- --- ## Notes for advanced users ### Why does `capture` even exist? `async_closure` is a lexical scope with guaranteed async RAII. When implementing such a thing, you end up needing to store two kinds of values that live strictly longer than the coroutine function scope itself. Specifically: - Values with `co_cleanup` (details in `CoCleanupAsyncRAII.md`). The archetypal type is `safe_async_scope`, which is immovable to allow an efficient implementation -- so the storage mechanism also needs to support in-place construction. - Values that outlive the cleanup, so they can be safely referenced by the `co_cleanup` types. - Both kinds of values are passed by-reference into the inner coro. And, since `async_closure` tasks often need to be movable (e.g. to run on scopes), the value storage **must provide stable pointers**. - In addition to the above two special types of data, we want to be able to pass regular arguments into async closures, without ambiguity. At its core, `capture` addresses those "must have" needs. However, it also provides some important "bonus" features: - As discussed in "your own `co_cleanup` type" below, types supporting `co_cleanup` should not be usable outside of a "managed" context that always awaits cleanup. Without captures, passing a "passkey" type into the in-place constructor for `co_cleanup` type could address this need (with some static assertions). However, with captures, `capture_proxy` gives us a cleaner solution. - `capture`s also help us enforce `safe_alias` lifetime safety heuristics using the type system. Doing something equivalent with static analysis on "plain" arguments would be prohibitive, e.g. because it would require chasing references across compilation units. In contrast, `capture` types automatically embed a lifetime safety contract. ### `shared_cleanup` closures downgrade `capture` safety to `after_cleanup_` *tl;dr* If you see `after_cleanup_SOME_capture`, know that it quacks just like `SOME_capture`, but with a lower `safe_alias` level. If this behavior is blocking you, you may benefit from finishing `restricted_co_cleanup_capture`. #### Problem solved When a child closure takes a reference to a parent's async scope, it can easily give a short-lived reference to a longer-lived task on that scope: ```cpp co_await async_closure( safeAsyncScope(), [](auto scope) -> closure_task { co_await async_closure( bind::args{scope, bind::capture(5)}, [](auto outerScope, auto n1) -> closure_task { outerScope->with(co_await co_current_executor).schedule( [](capture n2) -> co_cleanup_safe_task { assert(*n2 == 5); // Invalid memory access! co_return; }(n1)); }); }); ``` Note that the lifetime of `n1` aka `n2` is shorter than that of `scope`. That is, by the time `*n2` happens, the closure owning `n1` may have been destroyed. Fortunately, this code doesn't compile thanks to the `after_cleanup_` downgrade described below: ``` no known conversion from 'after_cleanup_capture' to 'capture' ``` Changing the inner lambda to `after_cleanup_capture` still won't compile: ``` Bad safe_task: check for unsafe aliasing in arguments or return type ``` Relaxing the inner task to `safe_task` also won't let the bug through, since `schedule()` won't take a less-safe task. ``` constraints not satisfied ... schedule( ... is_void_safe_task< safe_task, safe_alias::co_cleanup_safe_ref>' evaluated to false ``` To understand the solution, let's reformulate this bug more abstractly: - Any closure taking `co_cleanup_capture` is vulnerable to the problem, **unless** the API of `T` specifically ensures that it only takes inputs of safety `maybe_value`. In this section, we focus on `co_cleanup` types that must be able to take references, like `safe_async_scope`. NB: Types with value-only APIs should expose `capture_restricted_proxy()`. - Actually, closures sometimes reference `co_cleanup` types in ways besides `co_cleanup_capture` -- for example, `capture>`. For this reason, we define a brand-new level `safe_alias::shared_cleanup`, which must be used for any type that may give a child closure access to the parent's longer-lived lexical scope. **Note:** The name `shared_cleanup` aims to evoke that a child taking such an argument must take the parent's perspective on safety measurements. - By definition, APIs of `co_cleanup` types must guard against inputs less safe than `co_cleanup_safe_ref`, so the problem can only occur if a child is able to obtain a plain `capture<>` (or equivalently `capture_heap<>` / `capture_indirect<>). - Plain `capture<>`s come about in two ways: * Getting a `capture<>` reference from a parent. This scenario is fine -- **if** the parent could safely hold the `capture<>` together with the `co_cleanup_capture` that creates the risk, then it's no less safe for the child to handle that `capture` ref. * Making an owned `capture`. By default, owned captures are plain, but in the above example, `after_cleanup_capture<>` makes an appearance. That is, in fact, the fix! **Anytime a closure takes a `shared_cleanup` input, it loses the ability to instantiate plain captures.** Its owned captures get the `after_cleanup_` prefix (the "downgrade"), and it can no longer "upgrade" `after_cleanup_capture` references that it gets from a parent -- more on both below. Now that you saw the problem, and the solution, let's review the formalism. #### Upgrade/downgrade rules The reference downgrade rules rely on the fact that `co_cleanup_capture` APIs (per "your own `co_cleanup` type" below) are required to check that the lifetime safety of each input is `>= co_cleanup_safe_ref`. An `async_closure` is considered `shared_cleanup` if any of its external (non-owned) arguments have `shared_cleanup` safety. Such closures deviate from normal `capture`-passing rules in two ways: - **Own `capture`s are downgraded:** In the example, you will note that `n1` is of type `after_cleanup_capture`. Whereas, in the absence of `outerScope`, the type would be `capture`. - **Parent `capture`s are not upgraded:** Suppose the example scheduled a closure: `.schedule(async_closure(bind::args{n1}, ...))`. Then, **inside that closure** `n1` would be visible as `capture` because it can't be exfiltrated to `outerScope`. That's the upgrade behavior[†]. But, when passing `bind::args{outerScope, n1}`, the `shared_cleanup` argument blocks the upgrade, and the closure would still see `after_cleanup_capture`. > [†] Note that when a closure upgrades its refs, e.g. from > `after_cleanup_capture` to `capture`, the safety of the closure's task is > **not** affected. That is, reference upgrades are an internal matter. #### **Why is the downgraded name `after_cleanup_`?** In short, because such `capture`s can safely be used in `co_return move_after_cleanup()` and similar constructs. We need a new `after_cleanup_ref` level because: - `after_cleanup_capture` is safer than a `shared_cleanup` ref, which is *not* allowed in `move_after_cleanup` et al. - `after_cleanup_ref` is less safe than `co_cleanup_safe_ref`, since we don't want the downgraded references to be scheduled on scopes. ### Avoid safety downgrades via `restricted_co_cleanup_capture` **NB:** This feature isn't fully implemented yet (see "Implementation gaps" in this doc, and `FutureWork.md`), but what remains is quite simple, just search the code for "restricted". In some scenarios -- e.g. passing around a fire-and-forget logger -- it is important to avoid the safety downgrade. For example, a closure taking a `co_cleanup_capture` would be unable to pass any of its own captures to a `co_cleanup_capture` that it owns. To avoid downgrades, pass `restricted_co_cleanup_capture` to the child closure. This `capture` uses ADL customization point `capture_restricted_proxy()` to dereference, returning a proxy object that **only** accepts inputs with `maybe_value` safety. Obviously, such a proxy cannot accidentally pass short-lived refs from a child closure to a parent `co_cleanup_capture`, and thus it needs no downgrades. **IMPORTANT:** The implementation must pick between one of: - "once restricted, always restricted" - "restricted->unrestricted also downgrades `capture`s from parents" What we cannot do is "let a closure take a formerly `restricted` ref as unrestricted **and** take non-downgraded refs from parents." If both were possible at once, then the following lifetime safety violation could occur: - depth 0: creates a `co_cleanup_capture x0` - depth 1: takes restricted `x1` and owns `capture y1` - depth 2: unrestricts `x1` as `x2`, takes ref to `y1` as `y2` The problem is that short-lived `y2` can now be passed to `x0`. Either solution above eliminates the safety gap. ### The no-cleanup closure optimization & `_heap` captures Although `async_closure` was built to support async RAII, it should also see usage *just* because of `LifetimeSafetyBenefits.md`. Closures are implemented in such a way that users don't have to choose between safety and performance. Specifically, an async closure that takes no `co_cleanup` captures should perform exactly the same as the bare inner coroutine. This zero-cost behavior is called the "no-cleanup closure optimization". When implementing async RAII, it is hard (or perhaps impossible) to avoid allocating a second coro frame, the one that awaits cleanup. But, when `async_closure` sees that it owns no `co_cleanup_capture`s, it will: - Omit the outer coro frame (which would now be no-op) - Move in its own captures into the inner coro. - For owned captures that are `bind::in_place`, automatically use the `capture_heap` variation. From most perspectives, a no-cleanup closure quacks just like its outer-coro-awaits-inner-coro cousin. However, its own capture args' signatures will differ: - `capture` is passed instead of `capture`. - `bind::in_place` captures use the `capture_heap` template. By design, reference and value, plain and `_heap` captures have identical interfaces, letting `async_closure` freely pick the storage for those typical inner coros that take all captures by `auto`. In the unlikely event of a no-cleanup closure taking lots of `bind::in_place` captures, you can try `async_closure::force_outer_coro` to coalesce allocations. ### Integrating your own `co_cleanup` type This section assumes you're familiar with `CoCleanupAsyncRAII.md`. A properly implemented `co_cleanup` type `T` should: - Construct `T` in a state that does not yet require cleanup. - Be immovable, e.g. derive from `private folly::NonCopyableNonMovable`. This prevents lifetime issues, since all our safety checks assume that the `T` is cleaned up by its original owner. - Restrict public APIs that affect `T`'s need for cleanup to **only** be accessible by dereferencing `co_cleanup_capture`. This guarantees that if cleanup is needed, it will be called. When `capture` types evaluate `operator*` and `operator->`, they look for an ADL customization point. Declare it like so: ```cpp template T> friend auto capture_proxy(capture_proxy_tag, T&); ``` This should return a proxy type implementing your public API appropriate for both `Kind`, and the `const`-qualification of `T` -- `forward_like` may be useful when accessing members of `T`. The proxy type should be `NonCopyableNonMovable` with a constructor restricted to your class. - For public APIs, require `lenient_safe_alias_of_v` of at least `co_cleanup_safe_ref` for any input that may be stored until cleanup time. - If `restricted_co_cleanup_capture` support is desired, ADL-customize `capture_restricted_proxy()` as above, and enforce that all API inputs have `lenient_safe_alias_of_v` of `maybe_value`. ### How many templates are in this type zoo? Can't you type-erase? Look at `is_any_capture`. There are 8 as of this writing. Only the 3 `after_cleanup_` ones are specific to lifetime-safety tracking. We deliberately chose distinct templates instead of template parameters, since this should result in more readable compiler errors. Type-erasure isn't a very practical idea for simplifying the type signatures. There are two reasons: - `folly/coro/safe` should be zero-cost so teams can adopt it confidently. - We shouldn't type-erase the lifetime safety level, and at present 4 different ones need to be distinguished. Shrinking the capture type zoo from 8 to 4 doesn't seem worth the runtime & complexity cost of type erasure. ### Why do `capture`s quack like pointers? Morally, they are either values or references, and the "pointer-like" UX hurts ergonomics. Let's consider the "no wrapper" alternative. It would be possible for `bind::capture()` args to `async_closure` to just pass a reference to the underlying type into the inner coro. This comes with many downsides: - Bug farm: The inner coro has to remember to write `auto&` / `ActualType&` -- **except** when you have the no-cleanup closure optimization. Pass-by-value for non-cleanup captures **will** compile, making a copy, but the runtime behavior is wrong. This is fragile enough that I wold abandon the no-cleanup optimization in this scenario. - Clarity: The inner coro signature doesn't distinguish between captures and plain arguments, even though they have important lifetime differences (only capture refs can be passed into async scope tasks, e.g.). - Raw reference: no lifetime safety checks are possible. - To prevent `co_cleanup` types from being used in unmanaged contexts, we'd have to use the "passkey constructor" pattern, which is less flexible than the `capture_proxy` design. While [C++20 lacks a good story for generic reference-like wrapper types](https://medium.com/@snowp/transparent-phantom-types-in-c-de6ac5bed1d1), per above, the uglier dereferenceable wrapper style provides benefits that far outweigh the syntactic boilerplate. --- ## File: folly/coro/README.md # Coro ## Introduction [folly::coro](https://github.com/facebook/folly/tree/main/folly/coro) is a developer-friendly asynchronous C++ framework built on [C++20 coroutines](https://en.cppreference.com/w/cpp/language/coroutines.html). ### Basic example ```c++ folly::coro::Task task42() { co_return 42; } folly::coro::Task taskSlow43() { co_await folly::futures::sleep(std::chrono::seconds{1}); co_return co_await task42() + 1; } int main() { ... CHECK_EQ(43, folly::coro::blockingWait(co_withExecutor( folly::getGlobalCPUExecutor(), taskSlow43()))); ... } ``` The same logic implemented with `folly::SemiFuture`: ```c++ folly::SemiFuture task42() { return folly::makeSemiFuture().deferValue([](auto) { return 42; }); } folly::SemiFuture taskSlow43() { return folly::futures::sleep(std::chrono::seconds{1}) .semi() .deferValue([](auto) { return task42(); }) .deferValue([](auto value) { return value + 1; }); } int main() { ... CHECK_EQ( 43, taskSlow43().via(folly::getCPUExecutor().get()).get()); ... } ``` ### Features * Better performance than `folly::Future` * Full-compatibility with `folly::Future` and `folly::SemiFuture` * Asynchronous synchronization primitives (e.g. `coro::Baton`, `coro::Mutex`, `coro::SharedMutex`) * Compatible with other libraries based on C++20 coroutines ## Overview ### Writing a coroutine Any function that returns a `folly::coro::Task` and has at least one use of `co_await` or `co_return` is a coroutine. Use `co_return` instead of `return` in a coroutine. ```c++ folly::coro::Task task42() { co_return 42; } folly::coro::Task task43() { auto value = co_await task42(); co_return value + 1; } ``` ### Starting a coroutine Calling a `folly::coro::Task`-coroutine function captures the arguments, but doesn't start executing the coroutine immediately. Instead the coroutine is lazily started when you `co_await` the task. Alternatively, you can start executing a coroutine from a normal function by attaching a `folly::Executor` via `co_withExecutor()` and either calling `start()` or using `folly::coro::blockingWait()`. ```c++ folly::coro::Task checkArg(int arg42) { CHECK_EQ(42, arg42); co_return; } void runCoroutine1() { int arg42 = 42; // Coroutine arguments are captured here, not when we start the coroutine. auto task = checkArg(arg42); arg42 = 43; folly::coro::blockingWait(co_withExecutor( folly::getCPUExecutor(), std::move(task))); } void runCoroutine2() { folly::SemiFuture f = co_withExecutor( folly::getCPUExecutor(), checkArg(42)).start(); } ``` ### Executor stickiness Every `folly::coro::Task` will always be running on the `Executor` on which it was launched, even if it `co_await`ed something that completed on a different `Executor`. You can extract the Executor which the `folly::coro::Task` is running on by using `folly::coro::co_current_executor`. ```c++ folly::coro::Task task42Slow() { // This doesn't suspend the coroutine, just extracts the Executor*. folly::Executor* startExecutor = co_await folly::coro::co_current_executor; co_await folly::futures::sleep(std::chrono::seconds{1}); folly::Executor* resumeExecutor = co_await folly::coro::co_current_executor; CHECK_EQ(startExecutor, resumeExecutor); } ``` By default, when a `folly::coro::Task` is awaited within the context of another `Task` it inherits the executor from the awaiting coroutine. If you want to run a child coroutine on a different executor then you can call `co_withExecutor()` to explicitly specify an alternative executor. ```c++ folly::coro::Task foo() { co_await folly::futures::sleep(std::chrono::seconds{1}); std::cout << "Current executor is " << (co_await folly::coro::co_current_executor) << std::endl; } folly::coro::Task bar(folly::CPUThreadPoolExecutor* otherExecutor) { // Executes foo() on whatever execution context bar() was launched on. co_await foo(); // Launches foo() on 'otherExecutor' and when it's done resumes this // coroutine on whatever executor bar() was launched on. co_await co_withExecutor(otherExecutor, foo()); } ``` ### Awaitables You can `co_await` anything that follows the C++ [awaitable protocol](https://en.cppreference.com/w/cpp/language/coroutines.html#co_await). It can be `folly::coro::Task`, `folly::Future`, `folly::SemiFuture` etc. Keep in mind that an `Awaitable` may result in an exception, so you'll have to use try-catch blocks to handle errors. ```c++ folly::coro::Task throwCoro() { throw std::logic_error("Expected"); co_return; } folly::coro::Task coro() { auto future42 = folly::makeSemiFuture(42); EXPECT_EQ(42, co_await std::move(future42)); try { co_await throwCoro(); LOG(FATAL) << "Unreachable"; } catch (const std::logic_error&) { } catch (...) { LOG(FATAL) << "Unreachable"; } } ``` ### Concurrently awaiting multiple Tasks When you invoke a coroutine that returns a `folly::coro::Task`, the coroutine doesn't begin execution immediately. It only starts when you apply `co_await` to the returned task. Applying `co_await` also suspends the coroutine that is awaiting, until the awaited operation is complete. This means that you cannot perform two operations concurrently by simply calling the two coroutines and later awaiting them both. **SLOWER: The following will execute the two operations sequentially** ```c++ folly::coro::Task task1(); folly::coro::Task task2(); folly::coro::Task example() { auto t1 = task1(); auto t2 = task2(); int result1 = co_await std::move(t1); int result2 = co_await std::move(t2); co_return result1 + result2; } ``` If, instead, you want to perform these operations concurrently and wait until both of the operations complete you can use `folly::coro::collectAll()`. **FASTER: The following _may_ execute the two operations concurrently** ```c++ folly::coro::Task task1(); folly::coro::Task task2(); folly::coro::Task example() { auto [result1, result2] = co_await folly::coro::collectAll(task1(), task2()); co_return result1 + result2; } ``` Note that in the above example, when the `co_await` expression is evaluated it first launches the `task1()` coroutine and it will execute in the current thread until it reaches its first suspend-point, at which point it will then launch `task2()`. Once both sub-tasks are complete then the `example()` coroutine is resumed with a tuple of the individual results. Note that if both `task1()` and `task2()` complete synchronously then they will still be executed sequentially. ### Handling partial failure When executing multiple sub-tasks concurrently it's possible that some of those tasks will fail with an exception and some will succeed. If you use the `folly::coro::collectAll()` function to concurrently wait for multiple tasks to complete then any partial results are discarded if any of the tasks complete with an exception. If multiple sub-tasks complete with an exception then one of the exceptions is rethrown as the result and the others are discarded. If you need to be able determine which sub-operation failed or if you need to be able to retrieve partial results then you can use `folly::coro::collectAllTry()` instead. Instead of producing a tuple of the results it produces a tuple of `folly::Try` values, one for each input task. ```c++ folly::coro::Task task1(); folly::coro::Task task2(); folly::coro::Task example() { auto [try1, try2] = co_await folly::coro::collectAllTry(task1(), task2()); int result = 0; if (try1.hasValue()) { result += try1.value(); } else { LOG(ERROR) << "Error in task1(): " << try1.exception().what(); } if (try2.hasValue()) { result += try2.value(); } else { LOG(ERROR) << "Error in task2(): " << try2.exception().what(); } co_return result; } ``` ### folly::SemiFuture Any `folly::coro::Task` can be converted to a `folly::SemiFuture` by calling `.semi()`. Use this for interoperability with APIs that require `folly::Future` or `folly::SemiFuture`; otherwise, prefer coroutine-native primitives. ```c++ folly::coro::Task task1(); folly::coro::Task task2(); folly::coro::Task sumTask() { auto f1 = task1().semi(); auto f2 = task2().semi(); folly::Try r1, r2; std::tie(r1, r2) = co_await folly::collectAllSemiFuture(std::move(f1), std::move(f2)); co_return *r1 + *r2; } ``` ### Lambdas A lambda can be a coroutine, but its return type must be specified explicitly because the compiler cannot deduce it from the body. IMPORTANT: You need to be very careful about the lifetimes of temporary lambda objects. Invoking a lambda coroutine returns a `folly::coro::Task` that captures a reference to the lambda and so if the returned Task is not immediately `co_await`ed then the task will be left with a dangling reference when the temporary lambda goes out of scope. Use the `folly::coro::co_invoke()` helper when immediately invoking a lambda coroutine to keep the lambda alive as long as the `Task`. **BAD:** The following code has undefined behavior. ```c++ folly::coro::Task coro_send(const Request&); folly::SemiFuture semifuture_send(const Request& request) { auto task = [request]() -> folly::coro::Task { auto reply = co_await coro_send(request); if (reply.isError()) { LOG(reply.error().message()); } co_return reply; }(); // <-- Whoops, lambda is destroyed at semicolon. return std::move(task).semi(); } ``` **GOOD:** Use `co_invoke` to invoke the lambda to prevent the lambda from being destroyed. ```c++ folly::SemiFuture semifuture_send(const Request& request) { auto task = folly::coro::co_invoke([request]() -> folly::coro::Task { auto reply = co_await coro_send(request); if (reply.isError()) { LOG(reply.error().message()); } co_return reply; }); return std::move(task).semi(); } ``` ### Writing loops with coroutines #### Sequential retry loop ```c++ folly::coro::Task pingServer(); folly::coro::Task pingServerWithRetry(int retryCount) { for (int retry = 0; retry <= retryCount; ++retry) { try { co_await pingServer(); co_return; } catch (...) { LOG(WARNING) << "Ping attempt " << retry << " failed"; if (retry == retryCount) throw; } // Wait before trying again. co_await folly::futures::sleep(10ms); } } ``` #### Concurrently execute many operations Operations with side-effects: ```c++ folly::coro::Task doWork(int i); folly::coro::Task example(int count) { std::vector> tasks; for (int i = 0; i < count; ++i) { tasks.push_back(doWork(i)); } co_await folly::coro::collectAllRange(std::move(tasks)); } ``` Operations that return values: ```c++ folly::coro::Task getString(int i); folly::coro::Task example(int count) { std::vector> tasks; for (int i = 0; i < count; ++i) { tasks.push_back(getString(i)); } // Concurrently wait for all of these tasks. std::vector strings = co_await folly::coro::collectAllRange(std::move(tasks)); // ... use 'strings' } ``` --- ## File: folly/debugging/exception_tracer/README.md Exception tracer library This library allows you to inspect the exception stack at runtime. The library can be used in three ways: 1. Link in the exception_tracer_base library. You get access to the functions in ExceptionTracer.h, but no stack traces. This has no runtime overhead, and is compliant with the C++ ABI. 2. Link in the (full) exception_tracer library. You get access to the functions in ExceptionTracer.h, the std::terminate and std::unexpected handlers are installed by default, and you get full stack traces with all exceptions. This has some runtime overhead (the stack trace must be captured and stored whenever an exception is thrown) added to throw and catch, but no runtime overhead otherwise. This is less portable (depends on internal details of GNU's libstdc++). 3. LD_PRELOAD libexceptiontracer.so. This is equivalent to #2 above, but requires no link-time changes. On the other hand, you need to ensure that libexceptiontracer.so is compiled with the same compiler and flags as your binary, and the usual caveats about LD_PRELOAD apply (it propagates to child processes, etc). --- ## File: folly/detail/base64_detail/README.md *This file contains explanation of how SIMD implementation of Base64 functions* Our solution is based on 0x80 blog: [encoding](http://0x80.pl/notesen/2016-01-12-sse-base64-encoding.html), [decoding](http://0x80.pl/notesen/2016-01-17-sse-base64-decoding.html). This is a different version of the same explanation + we have some differences. *NOTE: We are using 1 digit for two bits when writing data* # Understanding Base64 encoding. *If you find it easier, [Wikipedia](https://en.wikipedia.org/wiki/Base64).* The goal of base64 is to encode arbitrary byte data as text that can be passed around. It works as follows: * we select a 64 character alphabet. * we insert two 0 bits after each 6 bits. 2^6 is 64. * because we now only need to encode 64 values, our alphabet is sufficient. # Encoding So, we have 2 steps needed to do the conversion: 1. get indexes 0-64, 2. lookup the corresponding char. There is also a little bit of tail handling, see the appropriate section. If one letter represents two bits, it looks smth like this (remember - our machines are little endian): ``` `cddd`bbcc`aaab => 0ddd`0ccc`0bbb`0aaa ``` After this we just have to convert the bytes into the selected alphabet. This means we have two steps to the algorithm: encodeToIndexes and lookupByIndex. ## encodeToIndexes *NOTE: assume 16 byte registers.* We will only be converting 12 bytes to output 16 bytes. The last 4 loaded bytes are ignored. 1. We need to shuffle bytes in a way that each dword contains all the bits to construct output for that dword. Specifically: ``` PONM,LKJI,HGFE,DCBA => KLJK,GIGH,EFDE,BCAB ``` > STEP BY STEP: > * We had bytes in memory ABCD. > * Loaded on a LE machine they become DCBA. > * The first output dword will only fit ABC, D goes into the second dword. > * We will also reshuffle CBA as BCAB because this will make further operations simpler. After this we will mutate each dword (letter+digit indicate 2 bits): ``` shuffled b2b3c1c2'c3d1d2d3'a1a2a3b1'b2b3c1c2 expected 00d1d2d3'00c1c2c3'00b1b2b3'00a1a2a3 ``` At the moment of writing this we only have an SSE4.2 version. We can do it fairly straightforwardly with shifts and blends. However the 0x80 blogs suggests that using a tricky multiplication scheme is superior, and that's what we do. For neon there are by element shift instructions which would help. On avx2 there are `srlv` family of instructions that can come in handy as well. The 0x80 blog also talks about a BMI implementation (pdep/pext instructions). They had issues on AMD but apparently not on the AMDs in Meta's fleet, so in the future we can consider it as a possibility as well. ## lookupByIndex The idea is to use table lookup/shuffle instructions (`pshuvb` on sse4.2). They allow you to shuffle a register by index (`0..16`). We have values `0..64`. However, we can utilize that the output values are not random. The are split into a few contiguous groups. We don't have to lookup the complete encoding, we just need to lookup the offset to add. | Index | Maps to | Add to encode | | ----- | --------| ------------- | | 0-25 | 'A'-'Z' | 'A' - 0 | | 26-51 | 'a'-'z' | 'a' - 26 | | 52-61 | '0'-'9' | '0' - 52 | | 62 | '+' | '+' - 62 | | 63 | '/' | '/' - 63 | *NOTE: the URL version of Base64 encoding uses -_ instead of +/*. Since we have 16 values to map to, we are not going to bother with consolidating 52-61 to a single base and instead will them up individually. This is our final lookup table: ``` 0: 'A' - 0 1: 'a' - 26 2: '0' - 52, 3: '1' - 53 ... 11: '9' - 61 12: '+' - 62 13: '/' - 63 14: - 15: - ``` We even have two extra indexes `14` and `15` that are unused. ## Tail handling What if we have less than register size to load? What if we have less than 3 elements to encode? Base64 for incomplete 3 bytes works as if there were extra 0s at the end, except the garbage elements are replaced with either a padding character or just removed. Example: |input bytes (be) | Basic | Url | |-----------------|--------|------| | (1) | AQ== | AQ | | (1, 0) | AQA= | AQA | | (1, 0, 0) | AQAA | AQAA | After measuring different options, using scalar loop peeling proved to be the fastest. # Decoding Overall the decoding process is similar to inverse of the encoding: 1. from chars get numbers `0..63` 2. pack them into bytes. However, unlike encoding, not all the sequences of bytes are valid. We have to decide which ones to accept and how to handle errors. *NOTE: error detection is fairly expensive, if in the future there is a need for a decode that can sometimes swallow invalid values, it can be done faster*. Decisions: `base64Decode` requires `=` padding and accepts only [`+`, `/`] as 62/63 character. If there are extra bits on the end, those are not allowed: iZ== is not a valid input because no input sequence will produce it. `base64URLDecode`: allows everything encoded with plain base64 and base64URL. It will successfully decode some combinations that are not either. The extra bits on the end are currently allowed: iZ== will decode successfully (this decision is not motivated by anything). *NOTE:* details on `baseURLDecode` rules: * Padding bytes follow regular base64: if they are present they are allowed to be only in positions that regular base64 allows them to be in: 4th or 3rd and 4th in the 4 byte chunk. "aa==", "aaa=" - OK, "aa=", "==" - not OK. This decision follows the previous most common implementation of base64 in the codebase. * Both ['+', '/'] and ['-', '_'] are allowed in any combinations. "+-" is legal for example. *NOTE: this follows the previous design and not necessarily how other places define base64URLDecode. The difference comes to decoding invalid sequence of padding characters. Example: "ba=" we consider invalid while some other implementations might just strip '='. We suspect it won't be an issue*. This behaviour matches what the previous implementation did. We only have a SIMD version of this algorithm for `base64Decode` because the URL decode has very little use (so far at least). The SIMD algorithm has 2 steps: - `decodeCharToIndex`: convert to numbers from `0..63` - `packIndexesToBytes`: packs `0..63` into the originally encoded bytes. If we encounter an error, we are not going to stop processing data. We are just going to mark it and then check at the end. ## decodeCharToIndex Conversions we want | Char | Char's Hex code | Res | Res Hex | |-----------|-----------------|---------|-------------| | '+' | 0x2B | 62 | 0x3E | | '/' | 0x2F | 63 | 0x3F | | '0' - '9' | 0x30 - 0x39 | 52 - 61 | 0x34 - 0x3D | | 'A' - 'Z' | 0x41 - 0x5A | 0 - 25 | 0x00 - 0x19 | | 'a' - 'z' | 0x61 - 0x7A | 26 - 51 | 0x1A - 0x33 | ### Idea We have unique higher 4 bits (nibble) per consecutive group, except for '+' and '/'. We can find a unique offset with pshuvb by it. ### Deal with '+' and '/' nibbles We need to move '+' and '/' into their own nibbles. It's important that all previously invalid chars stay invalid. The best way I see to do it is to subtract 0x0f from everything less than or equal to +. The reason to use 0x0f is that it's a constant we will need anyways ot get 4 higher nibbles. However on intel there is no unsigned comparison, so all the negative values will be considered as <= '+'. To deal with it, we can use a signed comparison but subtract with saturation. * <= '+' gives -1 where '+' * and 0x0f * subs Everything bigger than '+' will stay the same. Everything smaller than '+' is invalid and will become even smaller. It will saturate to -127 which is still invalid, so we are OK. *NOTE: I was also thinking if this is possible to do with just one subtraction and no mask. Unfortunately we also need to keep a separate nibble for '0' and '/' and '0' == '/' + 1, so that subtraction will guarantee put '/' and '0' on the same higher nibble.* *NOTE: If we drop the requirement on invalid elements, again - this is much easier*. New conversion table: | Char | New Hex code | Res | Res Hex | |-----------|---------------|---------|-------------| | '+' | 0x1C | 62 | 0x3E | | '/' | 0x2F | 63 | 0x3F | | '0' - '9' | 0x30 - 0x39 | 52 - 61 | 0x34 - 0x3D | | 'A' - 'Z' | 0x41 - 0x5A | 0 - 25 | 0x00 - 0x19 | | 'a' - 'z' | 0x61 - 0x7A | 26 - 51 | 0x1A - 0x33 | ### Detect invalid values. The idea is that we have valid higher nibbles in range from `1..7`. We can convert higher nibbles into a bitmask `0000'0010 ... 1000'0000` (`1 << nibble`) Due to a lack of proper shift instruction on x86, we will use a table lookup (`pshuvb`). All other higher nibbles can become 0, indicating invalid input. Now for all possible lower nibbles we have a set of valid higher nibbles. | Lower Nibble | Valid higher nibble | | ------------ | ------------------- | | 0 | 3, 5, 7 | | 1 - 9 | 3, 4, 5, 6, 7 | | A | 4, 5, 6, 7 | | B | 4, 6 | | C | 1, 4, 6 | | D, E | 4, 6 | | F | 2, 4, 6 | So: by higher nibble lookup a bit that indicates that higher nibble by lower nibble lookup a set of valid bits and This will give us a non-zero when it's OK. And 0 when it's not. Between iterations we can accumulate error with unsigned min. 0 - is the smallest value - so we will get 0 if there was one. ### Offset to correct values. Similar idea to encode - we just lookup the proper offset and add it. We'll need to lookup by higher nibble. | Char | New Hex code | Res | Offset (- means minus) | |-----------|---------------|---------|------------------------| | '+' | 0x1C | 62 | 62 - 0x1C | | '/' | 0x2F | 63 | 63 - '/' | | '0' - '9' | 0x30 - 0x39 | 52 - 61 | 52 - '0' | | 'A' - 'O' | 0x41 - 0x4F | 0 - 14 | 0 - 'A' | | 'P' - 'Z' | 0x50 - 0x5A | 15 - 25 | 0 - 'A' | | 'a' - 'o' | 0x61 - 0x6F | 26 - 40 | 26 - 'a' | | 'p' - 'z' | 0x70 - 0x7A | 26 - 51 | 26 - 'a' | ## packIndexesToBytes *NOTE: assume 16 byte registers.* From a register of 16 bytes we need to get 12 bytes. I think the only way to do it is to convert each 4 bytes to appropriate 3 bytes and then put them all together. After we doing conversion 4 to 3 we'll remove the leftover byte with one shuffle. Goal (*One letter - 2 bits*): - Input: `0ddd'0ccc'0bbb'0aaa` - Needed bytes: `'cddd'bbcc'aaab` We can obviously shift and or to get the desired result (and maybe on ARM we should) but again, shifting story for x86 is poor. The 0x80 blog suggests the following trick. ### Multiply add (MADD) solution On SSE there are `madd` instructions for adjacent bytes (`_mm_maddubs_epi16`) and words (`_mm_madd_epi16`). Multiply is a strictly more powerful operation than shift, so this will work. *NOTE: all of our numbers are positive so the sign of the operations doesn't matter* Here is the scalar equivalent of the code we'll do. (*I omit indicating leading 0s and ignore casts*). ``` std::uint16_t aaabbb = aaa << 6 + bbb; std::uint16_t cccddd = ccc << 6 + ddd; std::uint32_t aaabbbcccddd = aaabbb << 12 + cccddd; ``` Multiplication equivalent of `<< 6` is `* 0x40` and of `<< 12` is `* 0x1000`. Now that we have `0000'aaab'bbcc'cddd`. The correct order `cddd'bccc'aaab` which we can mix into the final shuffle. ## looping We can convert only in registers. There is a question: when can we write the whole register to the output? For example, for 16 bytes of input (no padding) we only have 12 bytes of output space. A simple way to answer if we have enough space is to compute how much output space we'll need overall. However, this operation is somewhat expensive and is likely already done for the allocation. So computing output size ideally should be avoided. We can prove that as long as the `Register` is bigger than 16 bytes, `1.5 Register` of input space is enough to guarantee at least one register of the output space. Proof. Out of `1.5 Register`, `1 Register` converts to `0.75 Register` in the output. So we are left with proving that `0.5 Register` will produce at least `0.25 Register` of the output. If there is no padding - `0.5` converts to `3/8`, which is `> 0.25`. If there is padding, the last dword of input might produce just `1` output byte. So, we need to prove that: `convertedSize(RegisterSize / 2 - 4) >= RegisterSize / 4 - 1` For `16` bytes it works `convertedSize(4) == 3`. For `Register > 16` bytes, we can split: ``` convertedSize(RegisterSize / 4) + convertedSize(RegisterSize / 4 - 4) >= RegisterSize / 8 + RegisterSize / 8 - 1 ``` Since `convertedSize(RegisterSize / 4) > RegisterSize / 8` we just reduced the problem to 16 bytes. Proven. ## Decoding SWAR SWAR stands for SIMD Within A Register i.e. using bit tricks to process multiple bytes in a bigger integer register. Previous version of Base64Decode was using some bit tricks and, as a result, was beating our performance for tails. On top of that, if the platform lacks the necessary SIMD capabilities, SWAR is beneficial, so we decided to implement it. How does it work? The simple version of the decoding algorithm matches from the input char to the index: let's say char `a` is matched to the number `26`. So we would first match chars to the corresponding indexes and then blend those indexes together. Let's say (one letter still 2 bits): ``` 0AAA'0BBB'0CCC'0DDD // input chars 0aaa'0bbb'0ccc'0ddd // corresponding bytes cddd'bbcc'aaab'____ // after a bunch of bit manipulations // (last byte is w/e) ``` However, what if we incorporated both position and character in the lookup table? ``` char: 0AAA corresponds to index: 0aaa [0][0AAA] = 0000'0000'aaa0'0000 [1][0AAA] = 0000'aa00'000a'0000 [2][0AAA] = a000'00aa'0000'0000 [4][0AAA] = 0aaa'0000'0000'0000 ``` This way we can just `or` results for all input chars. Since we have one byte, which is always `0000`, we can use that byte for marking errors. So for a busted input we can just store `0xffffffff`. We will `or` everything we output - and then check for `0xffffffff` in the end. This is the formula for each position (d - decoded index for char): ``` d << 2; // 0: 0000'0000'0000'aaa0 d >> 4 | (d << 12 & 0xff00); // 1: 0000'0000'bb00'000b (d << 6 & 0xff00) | (d << 22 & 0xff0000); // 2: 0000'c000'00cc'0000 d << 16; // 3: 0000'0ddd'0000'0000 ``` This is a memory/speed trade off. For a simple table lookup decoding we store 256 bytes. For this decoding we store 256 * 4 * 4 = 4kb. On big enough data this is a win of about a third over naive code. As far as SIMD clean up code is concerned, this is more questionable but for now we decided to go with it given that it shows an improvement in microbenchmarks. --- ## File: folly/docs/AtomicHashMap.md `folly/AtomicHashmap.h` ---------------------- `folly/AtomicHashmap.h` introduces a synchronized UnorderedAssociativeContainer implementation designed for extreme performance in heavily multithreaded environments (about 2-5x faster than tbb::concurrent_hash_map) and good memory usage properties. Find and iteration are wait-free, insert has key-level lock granularity, there is minimal memory overhead, and permanent 32-bit ids can be used to reference each element. ### Limitations *** Although it can provide extreme performance, AtomicHashmap has some unique limitations as well. * The space for erased elements cannot be reclaimed (they are tombstoned forever) so it's generally not a good idea to use this if you're erasing things a lot. * Only supports 32 or 64 bit keys - this is because they must be atomically compare-and-swap'ed. * Growth beyond initialization reduces performance - if you don't know the approximate number of elements you'll be inserting into the map, you probably shouldn't use this class. * Must manage synchronization externally in order to modify values in the map after insertion. Lock pools are a common way to do this, or you may consider using `folly::PackedSyncPtr` as your `ValueT`. * Must define special reserved key values for empty, erased, and locked elements. For a complete list of limitations and departures from the UnorderedAssociativeContainer concept, see `folly/AtomicHashMap.h` ### Unique Features *** * `value_type` references remain valid as long as the map itself. Note this is not true for most other probing hash maps which will move elements when rehashing, which is necessary for them to grow. AtomicHashMap grows by chaining additional slabs, so elements never need to be moved. * Unique 32-bit ids can be used to reference elements in the map via `iterator::getIndex()`. This can be helpful to save memory in the rest of the application by replacing 64-bit pointers or keys. * Iterators are never invalidated. This means you can iterate through the map while simultaneously inserting and erasing. This is particularly useful for non-blocking map serialization. ### Usage *** Usage is similar to most maps, although note the conspicuous lack of operator[] which encourages non thread-safe access patterns. Below is a synchronized key counter implementation that allows the counter values to be incremented in parallel with serializing all the values to a string. ```Cpp class Counters { private: AtomicHashMap ahm; public: explicit Counters(size_t numCounters) : ahm(numCounters) {} void increment(int64_t obj_id) { auto ret = ahm.insert(make_pair(obj_id, 1)); if (!ret.second) { // obj_id already exists, increment NoBarrier_AtomicIncrement(&ret.first->second, 1); } } int64_t getValue(int64_t obj_id) { auto ret = ahm.find(obj_id); return ret != ahm.end() ? ret->second : 0; } // Serialize the counters without blocking increments string toString() { string ret = "{\n"; ret.reserve(ahm.size() * 32); for (const auto& e : ahm) { ret += folly::to( " [", e.first, ":", NoBarrier_Load(&e.second), "]\n"); } ret += "}\n"; return ret; } }; ``` ### Implementation *** AtomicHashMap is a composition of AtomicHashArray submaps, which implement the meat of the functionality. Only one AHA is created on initialization, and additional submaps are appended if the first one gets full. If the AHM grows, there will be multiple submaps that must be probed in series to find a given key. The more growth, the more submaps will be chained, and the slower it will get. If the initial size estimate is good, only one submap will ever be created and performance will be optimal. AtomicHashArray is a fixed-size probing hash map (also referred to as an open addressed hash map) where hash collisions are resolved by checking subsequent elements. This means that they can be allocated in slabs as arrays of value_type elements, have excellent cache performance, and have no memory overhead from storing pointers. The algorithm is simple - when inserting, the key is hash-mod'ed to an offset, and that element-key is atomically compare-and-swap'ed with the locked key value. If successful, the value is written and the element-key is unlocked by setting it to the input key value. If the compare fails, the next element is tried until success or the map is full. Finds are even simpler. The key is hash-mod'ed to an offset, and the element-key is examined. If it is the same as the input key, the reference is returned, if it's the empty key, failure is returned, otherwise the next key is tried. This can be done wait-free without any atomic instructions because the elements are always in a valid state. Erase is done by finding the key, then compare-and-swap'ing the element-key with the reserved erased key value. If the swap succeeds, return success, otherwise return failure (the element was erased by a competing thread). If the key does not exist, return failure. --- ## File: folly/docs/Benchmark.md `folly/Benchmark.h` ----------------- `folly/Benchmark.h` provides a simple framework for writing and executing benchmarks. Currently the framework targets only single-threaded testing (though you can internally use fork-join parallelism and measure total run time). Also read `docs/BenchmarkAdaptive.md`, which describes`--bm_mode=adaptive`, an easier & quicker way to get reliable timings for your `BENCHMARK`s. ### Overview *** Using `folly/Benchmark.h` is very simple. Here's an example: ``` Cpp #include #include using namespace std; using namespace folly; BENCHMARK(insertFrontVector) { // Let's insert 100 elements at the front of a vector vector v; for (unsigned int i = 0; i < 100; ++i) { v.insert(v.begin(), i); } } BENCHMARK(insertBackVector) { // Let's insert 100 elements at the back of a vector vector v; for (unsigned int i = 0; i < 100; ++i) { v.insert(v.end(), i); } } int main() { runBenchmarks(); } ``` Compiling and running this code produces to the standard output: ``` =============================================================================== test.cpp relative ns/iter iters/s =============================================================================== insertFrontVector 3.84K 260.38K insertBackVector 1.61K 622.75K =============================================================================== ``` Let's worry about the empty column "relative" later. The table contains, for each benchmark, the time spent per call and the converse number of calls per second. Numbers are represented in metric notation (K for thousands, M for millions etc). As expected, in this example the second function is much faster (fewer ns/iter and more iters/s). The macro `BENCHMARK` introduces a function and also adds it to an internal array containing all benchmarks in the system. The defined function takes no arguments and returns `void`. The framework calls the function many times to collect statistics about it. Sometimes the function itself would want to do that iteration---for example how about inserting `n` elements instead of 100 elements? To do the iteration internally, use `BENCHMARK` with two parameters. The second parameter is the number of iterations and is passed by the framework down to the function. The type of the count is implicitly `unsigned`. Consider a slightly reworked example: ``` Cpp #include #include #include using namespace std; using namespace folly; BENCHMARK(insertFrontVector, n) { vector v; for (unsigned int i = 0; i < n; ++i) { v.insert(v.begin(), i); } } BENCHMARK(insertBackVector, n) { vector v; for (unsigned int i = 0; i < n; ++i) { v.insert(v.end(), i); } } int main() { runBenchmarks(); } ``` The produced numbers are substantially different: ``` =============================================================================== Benchmark relative ns/iter iters/s =============================================================================== insertFrontVector 39.92 25.05M insertBackVector 3.46 288.89M =============================================================================== ``` Now the numbers indicate the speed of one single insertion because the framework assumed the user-defined function used internal iteration (which it does). So inserting at the back of a vector is more than 10 times faster than inserting at the front! Speaking of comparisons... ### Baselines *** Choosing one or more good baselines is a crucial activity in any measurement. Without a baseline there is little information to derive from the sheer numbers. If, for example, you do experimentation with algorithms, a good baseline is often an established approach (e.g. the built-in `std::sort` for sorting). Essentially all experimental numbers should be compared against some baseline. To support baseline-driven measurements, `folly/Benchmark.h` defines `BENCHMARK_RELATIVE`, which works much like `BENCHMARK`, except it considers the most recent lexically-occurring `BENCHMARK` a baseline, and fills the "relative" column. Say, for example, we want to use front insertion for a vector as a baseline and see how back insertion compares with it: ``` Cpp #include #include #include using namespace std; using namespace folly; BENCHMARK(insertFrontVector, n) { vector v; for (unsigned int i = 0; i < n; ++i) { v.insert(v.begin(), i); } } BENCHMARK_RELATIVE(insertBackVector, n) { vector v; for (unsigned int i = 0; i < n; ++i) { v.insert(v.end(), i); } } int main() { runBenchmarks(); } ``` This program prints something like: ``` =============================================================================== Benchmark relative ns/iter iters/s =============================================================================== insertFrontVector 42.65 23.45M insertBackVector 1208.24% 3.53 283.30M =============================================================================== ``` showing the 1208.24% relative speed advantage of inserting at the back compared to front. The scale is chosen in such a way that 100% means identical speed, numbers smaller than 100% indicate the benchmark is slower than the baseline, and numbers greater than 100% indicate the benchmark is faster. For example, if you see 42% that means the speed of the benchmark is 0.42 of the baseline speed. If you see 123%, it means the benchmark is 23% or 1.23 times faster. To close the current benchmark group and start another, simply use `BENCHMARK` again. ### Ars Gratia Artis *** If you want to draw a horizontal line of dashes (e.g. at the end of a group or for whatever reason), use `BENCHMARK_DRAW_LINE()`. The line fulfills a purely aesthetic role; it doesn't interact with measurements in any way. ``` Cpp BENCHMARK(foo) { Foo foo; foo.doSomething(); } BENCHMARK_DRAW_LINE(); BENCHMARK(bar) { Bar bar; bar.doSomething(); } ``` If you want to print arbitrary text (e.g. a comment or for whatever reason), use `BENCHMARK_DRAW_TEXT("your text here")`. The output will be the literal value so escape codes like `\n` or `\t` will not work. To add multiple lines of output use multiple `BENCHMARK_DRAW_TEXT` calls. ``` Cpp BENCHMARK(foo) { Foo foo; foo.doSomething(); } BENCHMARK_DRAW_TEXT("Note: bar is expected to be 2x more expensive."); BENCHMARK(bar) { Bar bar; bar.doSomething(); } ``` ### Suspending a benchmark *** Sometimes benchmarking code must do some preparation work that is physically inside the benchmark function, but should not take part to its time budget. To temporarily suspend the benchmark, use the pseudo-statement `BENCHMARK_SUSPEND` as follows: ``` Cpp BENCHMARK(insertBackVector, n) { vector v; BENCHMARK_SUSPEND { v.reserve(n); } for (unsigned int i = 0; i < n; ++i) { v.insert(v.end(), i); } } ``` The preallocation effected with `v.reserve(n)` will not count toward the total run time of the benchmark. Only the main thread should call `BENCHMARK_SUSPEND` (and of course it should not call it while other threads are doing actual work). This is because the timer is application-global. If the scope introduced by `BENCHMARK_SUSPEND` is not desired, you may want to "manually" use the `BenchmarkSuspender` type. Constructing such an object suspends time measurement, and destroying it resumes the measurement. If you want to resume time measurement before the destructor, call `dismiss` against the `BenchmarkSuspender` object. The previous example could have been written like this: ``` Cpp BENCHMARK(insertBackVector, n) { BenchmarkSuspender braces; vector v; v.reserve(n); braces.dismiss(); for (unsigned int i = 0; i < n; ++i) { v.insert(v.end(), i); } } ``` ### `doNotOptimizeAway` *** Finally, the small utility function `doNotOptimizeAway` prevents compiler optimizations that may interfere with benchmarking . Call doNotOptimizeAway(var) against variables that you use for benchmarking but otherwise are useless. The compiler tends to do a good job at eliminating unused variables, and this function fools it into thinking a variable is in fact needed. Example: ``` Cpp BENCHMARK(fpOps, n) { double d = 1; FOR_EACH_RANGE (i, 1, n) { d += i; d -= i; d *= i; d /= i; } doNotOptimizeAway(d); } ``` ### A look under the hood *** `folly/Benchmark.h` has a simple, systematic approach to collecting timings. First, it organizes measurements in several large epochs, and takes the minimum over all epochs. Taking the minimum gives the closest result to the real runtime. Benchmark timings are not a regular random variable that fluctuates around an average. Instead, the real time we're looking for is one to which there's a variety of additive noise (i.e. there is no noise that could actually shorten the benchmark time below its real value). In theory, taking an infinite amount of samples and keeping the minimum is the actual time that needs measuring. That's why the accuracy of benchmarking increases with the number of epochs. Clearly, in real functioning there will also be noise and a variety of effects caused by the running context. But the noise during the benchmark (straight setup, simple looping) is a poor model for the noise in the real application. So taking the minimum across several epochs is the most informative result. Inside each epoch, the function measured is iterated an increasing number of times until the total runtime is large enough to make noise negligible. At that point the time is collected, and the time per iteration is computed. As mentioned, the minimum time per iteration over all epochs is the final result. The timer function used is `clock_gettime` with the `CLOCK_REALTIME` clock id. Note that you must use a recent Linux kernel (2.6.38 or newer), otherwise the resolution of `CLOCK_REALTIME` is inadequate. --- ## File: folly/docs/Conv.md `folly/Conv.h` ------------- `folly/Conv.h` is a one-stop-shop for converting values across types. Its main features are simplicity of the API (only the names `to` and `toAppend` must be memorized), speed (folly is significantly faster, sometimes by an order of magnitude, than comparable APIs), and correctness. ### Synopsis *** All examples below are assume to have included `folly/Conv.h` and issued `using namespace folly;` You will need: ``` Cpp // To format as text and append to a string, use toAppend. fbstring str; toAppend(2.5, &str); CHECK_EQ(str, "2.5"); // Multiple arguments are okay, too. Just put the pointer to string at the end. toAppend(" is ", 2, " point ", 5, &str); CHECK_EQ(str, "2.5 is 2 point 5"); // You don't need to use fbstring (although it's much faster for conversions and in general). std::string stdStr; toAppend("Pi is about ", 22.0 / 7, &stdStr); // In general, just use to(sourceValue). It returns its result by value. stdStr = to("Variadic ", "arguments also accepted."); // to is 2.5x faster than to for typical workloads. str = to("Variadic ", "arguments also accepted."); ``` ### Integral-to-integral conversion *** Using `to(value)` to convert one integral type to another will behave as follows: * If the target type can accommodate all possible values of the source value, the value is implicitly converted. No further action is taken. Example: ``` Cpp short x; unsigned short y; ... auto a = to(x); // zero overhead conversion auto b = to(y); // zero overhead conversion ``` * Otherwise, `to` inserts bounds checks and throws `std::range_error` if the target type cannot accommodate the source value. Example: ``` Cpp short x; unsigned short y; long z; ... x = 123; auto a = to(x); // fine x = -1; a = to(x); // THROWS z = 2000000000; auto b = to(z); // fine z += 1000000000; b = to(z); // THROWS auto b = to(z); // fine ``` ### Anything-to-string conversion *** As mentioned, there are two primitives for converting anything to string: `to` and `toAppend`. They support the same set of source types, literally by definition (`to` is implemented in terms of `toAppend` for all types). The call `toAppend(value, &str)` formats and appends `value` to `str` whereas `to(value)` formats `value` as a `StringType` and returns the result by value. Currently, the supported `StringType`s are `std::string` and `fbstring` Both `toAppend` and `to` with a string type as a target support variadic arguments. Each argument is converted in turn. For `toAppend` the last argument in a variadic list must be the address of a supported string type (no need to specify the string type as a template argument). #### Integral-to-string conversion Nothing special here - integrals are converted to strings in decimal format, with a '-' prefix for negative values. Example: ``` Cpp auto a = to(123); assert(a == "123"); a = to(-456); assert(a == "-456"); ``` The conversion implementation is aggressively optimized. It converts two digits at a time assisted by fixed-size tables. Converting a `long` to an `fbstring` is 3.6x faster than using `boost::lexical_cast` and 2.5x faster than using `sprintf` even though the latter is used in conjunction with a stack-allocated constant-size buffer. Note that converting integral types to `fbstring` has a particular advantage compared to converting to `std::string` No integral type (<= 64 bits) has more than 20 decimal digits including sign. Since `fbstring` employs the small string optimization for up to 23 characters, converting an integral to `fbstring` is guaranteed to not allocate memory, resulting in significant speed and memory locality gains. Benchmarks reveal a 2x gain on a typical workload. #### `char` to string conversion Although `char` is technically an integral type, most of the time you want the string representation of `'a'` to be `"a"`, not `96` That's why `folly/Conv.h` handles `char` as a special case that does the expected thing. Note that `signed char` and `unsigned char` are still considered integral types. #### Floating point to string conversion `folly/Conv.h` uses [V8's double conversion](http://code.google.com/p/double-conversion/) routines. They are accurate and fast; on typical workloads, `to(doubleValue)` is 1.9x faster than `sprintf` and 5.5x faster than `boost::lexical_cast` (It is also 1.3x faster than `to(doubleValue)` #### `const char*` to string conversion For completeness, `folly/Conv.h` supports `const char*` including i.e. string literals. The "conversion" consists, of course, of the string itself. Example: ``` Cpp auto s = to("Hello, world"); assert(s == "Hello, world"); ``` #### Anything from string conversion (i.e. parsing) *** `folly/Conv.h` includes three kinds of parsing routines: * `to(const char* begin, const char* end)` rigidly converts the range [begin, end) to `Type` These routines have drastic restrictions (e.g. allow no leading or trailing whitespace) and are intended as an efficient back-end for more tolerant routines. * `to(stringy)` converts `stringy` to `Type` Value `stringy` may be of type `const char*`, `StringPiece`, `std::string`, or `fbstring` (Technically, the requirement is that `stringy` implicitly converts to a `StringPiece` * `to(&stringPiece)` parses with progress information: given `stringPiece` of type `StringPiece` it parses as much as possible from it as type `Type` and alters `stringPiece` to remove the munched characters. This is easiest clarified by an example: ``` Cpp fbstring s = " 1234 angels on a pin"; StringPiece pc(s); auto x = to(&pc); assert(x == 1234); assert(pc == " angels on a pin"; ``` Note how the routine ate the leading space but not the trailing one. #### Parsing integral types Parsing integral types is unremarkable - decimal format is expected, optional `'+'` or `'-'` sign for signed types, but no optional `'+'` is allowed for unsigned types. The one remarkable element is speed - parsing typical `long` values is 6x faster than `sscanf`. `folly/Conv.h` uses aggressive loop unrolling and table-assisted SIMD-style code arrangement that avoids integral division (slow) and data dependencies across operations (ILP-unfriendly). Example: ``` Cpp fbstring str = " 12345 "; assert(to(str) == 12345); str = " 12345six seven eight"; StringPiece pc(str); assert(to(&pc) == 12345); assert(str == "six seven eight"); ``` #### Parsing floating-point types `folly/Conv.h` uses, again, [V8's double-conversion](http://code.google.com/p/double-conversion/) routines as back-end. The speed is 3x faster than `sscanf` and 1.7x faster than in-home routines such as `parse` But the more important detail is accuracy - even if you do code a routine that works faster than `to` chances are it is incorrect and will fail in a variety of corner cases. Using `to` is strongly recommended. Note that if the string "NaN" (with any capitalization) is passed to `to` then `NaN` is returned, which can be tested for as follows: ``` Cpp fbstring str = "nan"; // "NaN", "NAN", etc. double d = to(str); if (std::isnan(d)) { // string was a valid representation of the double value NaN } ``` Note that passing "-NaN" (with any capitalization) to `to` also returns `NaN`. Note that if the strings "inf" or "infinity" (with any capitalization) are passed to `to` then `infinity` is returned, which can be tested for as follows: ``` Cpp fbstring str = "inf"; // "Inf", "INF", "infinity", "Infinity", etc. double d = to(str); if (std::isinf(d)) { // string was a valid representation of one of the double values +Infinity // or -Infinity } ``` Note that passing "-inf" or "-infinity" (with any capitalization) to `to` returns `-infinity` rather than `+infinity`. The sign of the `infinity` can be tested for as follows: ``` Cpp fbstring str = "-inf"; // or "inf", "-Infinity", "+Infinity", etc. double d = to(str); if (d == std::numeric_limits::infinity()) { // string was a valid representation of the double value +Infinity } else if (d == -std::numeric_limits::infinity()) { // string was a valid representation of the double value -Infinity } ``` Note that if an unparseable string is passed to `to` then an exception is thrown, rather than `NaN` being returned. This can be tested for as follows: ``` Cpp fbstring str = "not-a-double"; // Or "1.1.1", "", "$500.00", etc. double d; try { d = to(str); } catch (const std::range_error &) { // string could not be parsed } ``` Note that the empty string (`""`) is an unparseable value, and will cause `to` to throw an exception. #### Non-throwing interfaces `tryTo` is the non-throwing variant of `to`. It returns an `Expected`. You can think of `Expected` as like an `Optional`, but if the conversion failed, `Expected` stores an error code instead of a `T`. `tryTo` has similar performance as `to` when the conversion is successful. On the error path, you can expect `tryTo` to be roughly three orders of magnitude faster than the throwing `to` and to completely avoid any lock contention arising from stack unwinding. Here is how to use non-throwing conversions: ``` Cpp auto t1 = tryTo(str); if (t1.hasValue()) { use(t1.value()); } ``` `Expected` has a composability feature to make the above pattern simpler. ``` Cpp tryTo(str).then([](int i) { use(i); }); ``` --- ## File: folly/docs/Dynamic.md `folly/dynamic.h` ----------------- `folly/dynamic.h` provides a runtime dynamically typed value for C++, similar to the way languages with runtime type systems work (e.g. Python). It can hold types from a predetermined set of types (ints, bools, arrays of other dynamics, etc), similar to something like `std::variant`, but the syntax is intended to be a little more like using the native type directly. ### Overview *** Here are some code samples to get started (assumes a `using folly::dynamic;` was used): ``` Cpp dynamic twelve = 12; // creates a dynamic that holds an integer dynamic str = "string"; // yep, this one is an fbstring // A few other types. dynamic nul = nullptr; dynamic boolean = false; // Arrays can be initialized with dynamic::array. dynamic array = dynamic::array("array ", "of ", 4, " elements"); assert(array.size() == 4); dynamic emptyArray = dynamic::array; assert(emptyArray.empty()); // Maps from dynamics to dynamics are called objects. The // dynamic::object constant is how you make an empty map from dynamics // to dynamics. dynamic map = dynamic::object; map["something"] = 12; map["another_something"] = map["something"] * 2; // Dynamic objects may be initialized this way dynamic map2 = dynamic::object("something", 12)("another_something", 24); ``` ### Runtime Type Checking and Conversions *** Any operation on a dynamic requires checking at runtime that the type is compatible with the operation. If it isn't, you'll get a `folly::TypeError`. Other exceptions can also be thrown if you try to do something impossible (e.g. if you put a very large 64-bit integer in and try to read it out as a double). More examples should hopefully clarify this: ``` Cpp dynamic dint = 42; dynamic str = "foo"; dynamic anotherStr = str + "something"; // fine dynamic thisThrows = str + dint; // TypeError is raised ``` Explicit type conversions can be requested for some of the basic types: ``` Cpp dynamic dint = 12345678; dynamic doub = dint.asDouble(); // doub will hold 12345678.0 dynamic str = dint.asString(); // str == "12345678" dynamic hugeInt = std::numeric_limits::max(); dynamic hugeDoub = hugeInt.asDouble(); // throws a folly/Conv.h error, // since it can't fit in a double ``` For more complicated conversions, see [DynamicConverter](DynamicConverter.md). ### Comparison Operators and Hashing #### Equality Operators Equality operators (`==`, `!=`) are supported for all types. For dynamics of the same type, the underlying equality operator shall apply. For comparisons between different numeric types (double and int64), numeric equality will apply - thus `2.0 == 2`. Values of any other different types will be deemed to not be equal. #### Ordering operators Ordering operators (`<`, `<=`, `>`, `>=`) are supported for all types, except `dynamic::object` which will throw if it is involved in an ordering operator. For dynamics of the same type, the underlying ordering operator shall apply. For comparisons between different numeric types (double and int64), numeric ordering will apply - thus `1.5 < 2`. Ordering of values between other different types will maintain total ordering properties and be consistent within a given binary run, and thus safe for use in e.g. `std::set`. The actual ordering is undefined and could change across versions, thus a dependency should not be taken outside of the total ordering property within a given binary. #### Hashing Hashing is supported by all types, and the hashes of two values will match if they are equal per `dynamic::operator==`. As a result, numerical types have the same numerical hashing regardless of int64 vs double - so e.g. `std::hash()(2)` will give the same value as `std::hash()(2.0)`. ### Iteration and Lookup *** You can iterate over dynamic arrays as you would over any C++ sequence container. ``` Cpp dynamic array = dynamic::array(2, 3, "foo"); for (auto& val : array) { doSomethingWith(val); } ``` You can iterate over dynamic maps by calling `items()`, `keys()`, `values()`, which behave similarly to the homonymous methods of Python dictionaries. ``` Cpp dynamic obj = dynamic::object(2, 3)("hello", "world")("x", 4); for (auto& pair : obj.items()) { // Key is pair.first, value is pair.second processKey(pair.first); processValue(pair.second); } for (auto& key : obj.keys()) { processKey(key); } for (auto& value : obj.values()) { processValue(value); } ``` You can find an element by key in a dynamic map using the `find()` method, which returns an iterator compatible with `items()`: ``` Cpp dynamic obj = dynamic::object(2, 3)("hello", "world")("x", 4); auto pos = obj.find("hello"); // pos->first is "hello" // pos->second is "world" auto pos = obj.find("no_such_key"); // pos == obj.items().end() ``` ### Erasure You can erase elements from dynamic arrays by calling member `dynamic::erase`, which works like and has overloads like `std::vector::erase`, and from dynamic objects by calling member `dynamic::erase`, which works like and has overloads like `std::unordered_map::erase`. You can also find and erase elements from dynamic arrays by calling free function `erase`, and from dynamic arrays or objects by calling free function `erase_if`, which work and have overloads like `erase(std::vector)`, `erase_if(std::vector)`, and `erase_if(std::unordered_map)`. https://en.cppreference.com/w/cpp/container/vector/erase2 https://en.cppreference.com/w/cpp/container/unordered_map/erase_if.html ### Use for JSON *** The original motivation for implementing this type was to try to make dealing with json documents in C++ almost as easy as it is in languages with dynamic type systems (php or javascript, etc). The reader can judge whether we're anywhere near that goal, but here's what it looks like: ``` Cpp // Parsing JSON strings and using them. std::string jsonDocument = R"({"key":12,"key2":[false, null, true, "yay"]})"; dynamic parsed = folly::parseJson(jsonDocument); assert(parsed["key"] == 12); assert(parsed["key2"][0] == false); assert(parsed["key2"][1] == nullptr); // Building the same document programmatically. dynamic sonOfAJ = dynamic::object ("key", 12) ("key2", dynamic::array(false, nullptr, true, "yay")); // Printing. (See also folly::toPrettyJson) auto str = folly::toJson(sonOfAJ); assert(jsonDocument.compare(str) == 0); ``` ### Performance *** Dynamic typing is more expensive than static typing, even when you do it in C++. ;) However, some effort has been made to keep `folly::dynamic` and the json (de)serialization at least reasonably performant for common cases. The heap is only used for arrays and objects, and move construction is fully supported. String formatting internally also uses the highly performant `folly::to<>` (see `folly/Conv.h`). A trade off to keep in mind though, is that `sizeof(folly::dynamic)` is 64 bytes. You probably don't want to use it if you need to allocate large numbers of them (prefer static types, etc). ### Some Design Rationale *** **Q. Why doesn't a dynamic string support begin(), end(), and operator[]?** The value_type of a dynamic iterator is `dynamic`, and `operator[]` (or the `at()` function) has to return a reference to a dynamic. If we wanted this to work for strings, this would mean we'd have to support dynamics with a character type, and moreover that the internal representation of strings would be such that we can hand out references to dynamic as accessors on individual characters. There are a lot of potential efficiency drawbacks with this, and it seems like a feature that is not needed too often in practice. **Q. Isn't this just a poor imitation of the C# language feature?** Pretty much. --- ## File: folly/docs/DynamicConverter.md `folly/DynamicConverter.h` -------------------------- When dynamic objects contain data of a known type, it is sometimes useful to have its well-typed representation. A broad set of type-conversions are contained in `DynamicConverter.h`, and facilitate the transformation of dynamic objects into their well-typed format. ### Usage *** Simply pass a dynamic into a templated convertTo: ```cpp dynamic d = { { 1, 2, 3 }, { 4, 5 } }; // a vector of vector of int auto vvi = convertTo>(d); ``` ### Supported Types *** convertTo naturally supports conversions to 1. arithmetic types (such as int64_t, unsigned short, bool, and double) 2. fbstring, std::string 3. containers and map-containers NOTE: convertTo will assume that Type is a container if * it has a Type::value_type, and * it has a Type::iterator, and * it has a constructor that accepts two InputIterators Additionally, convertTo will assume that Type is a map if * it has a Type::key_type, and * it has a Type::mapped_type, and * value_type is a pair of const key_type and mapped_type If Type meets the container criteria, then it will be constructed by calling its InputIterator constructor. ### Customization *** If you want to use convertTo to convert dynamics into your own custom class, then all you have to do is provide a template specialization of DynamicConverter with the static method convert. Make sure you put it in namespace folly. Example: ``` Cpp struct Token { int kind_; fbstring lexeme_; explicit Token(int kind, const fbstring& lexeme) : kind_(kind), lexeme_(lexeme) {} }; namespace folly { template <> struct DynamicConverter { static Token convert(const dynamic& d) { int k = convertTo(d["KIND"]); fbstring lex = convertTo(d["LEXEME"]); return Token(k, lex); } }; } ```