SeqLock

Sequential lock is a common technique used to protect data that's frequently read and rarely updated. Writers are required to take exclusive lock to mutate the data. Reads are effectively lock free and optimistic. The data protected by a SeqLock usually needs to be trivially_copy_constructible. // reader std::atomoc&…

`folly::Indestructible`

folly::Indestructible<T> is a class template that makes a static variable well, indestructible. Notice that it's meant for static variables in the Meyers Singleton pattern. If it's for heap allocated memory, it would just be called memory leak instead of "indestructible". It boils down to making a…

C++ Map Lookup Memoization

Memoization is an old technique. It's basically caching outputs for giving inputs (usually in a map). But a map lookup itself is not free. How can we memoize map lookups? I learned from my coworker this nifty trick recently. Let's say we have a map (e.g. std::unordered_map&…

C++ Type Erasure

You have heard about Type Erasure of C++. You probably know std::function is a classic usage of the pattern. But what is Type Erasure in C++? It's effectively trying to achieve Duck Typing, which is common in languages like Python. # Notice that there's no relationship between Bar1 or Bar2…

atomic_thread_fence

Just like you can have a std::atomic synchronizes two threads with each other with release-acquire semantic, you can also have Fence-Fence, Atomic-Fence, Fence-Atomic synchronizations. C++ reference has very detailed documentation about when there exists a valid synchronizes-with relationship, https://en.cppreference.com/w/cpp/atomic/atomic_thread_fence. Rust's…

How C++ `typeid` operator works

C++ language include an operator called typeid (https://en.cppreference.com/w/cpp/language/typeid). Queries information of a type. Used where the dynamic type of a polymorphic object must be known and for static type identification. It gives you information about the type of an object, as long as…

GNU Visibility Attribute

When going through the folly code base, sometimes, you see definitions like class FOLLY_EXPORT OptionalEmptyException : public std::runtime_error { ... FOLLY_EXPORT is defined as #define FOLLY_EXPORT __attribute__((__visibility__("default"))) It sets the visibility attribute of symbol OptionalEmptyException to "default". What does it do exactly,…

std::atomic from bottom up

std::atomic combines read-modify-write atomic instructions, memory barriers in hardware and memory order concept in C++ altogether. It's commonly used for lock-free programming, which often looks like, if (futex.compare_exchange_strong(expected, 1, memory_order_acquire)) { // lock acquired } Multiple Caches Data race doesn't exist until we had computers with…

Linear scalable read-write lock

The basic concept of a read-write lock is simple. It allows multiple readers to access the resource simultaneously, but at most one thread can have exclusive ownership of the lock (a.k.a write lock). It's supposed to be an optimization, comparing to simple mutex (e.g. std::mutex). As…

Global Data Locality – Why and How

Why In folly, Facebook's open source c++ library, you often see code like the following: #define FOLLY_SETTING_DEFINE(_project, _name, _Type, _def, _desc) \ /* Fastpath optimization, see notes in FOLLY_SETTINGS_DEFINE_LOCAL_FUNC__. \ Aggregate all off these together in a single section for better TLB \ and cache locality. */ \ __attribute_…