`folly::Indestructible`

By Lu Pan in c++ on

folly::Indestructible [https://github.com/facebook/folly/blob/master/folly/Indestructible.h] 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…

C++ Map Lookup Memoization

By Lu Pan in c++ on

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 and `std::function`

By Lu Pan in c++ on

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

By Lu Pan in c++ on

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 [https://preshing.com/20130823/the-synchronizes-with-relation/] relationship, https://en.cppreference.com/w/cpp/…

Paxos Commit with Constraints

By Lu Pan in paxos on

Correction: The following description of Paxos Commit is inaccurate. The algorithm is still correct but it's not the same Paxos Commit proposed in the paper. 4/25/2021. Lamport proposed Paxos Commit [https://lamport.azurewebsites.net/video/consensus-on-transaction-commit.pdf] algorithm as an alternative to 2PC for achieving Transaction Commit. It's…

How C++ `typeid` operator works

By Lu Pan in c++ on

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…

BW-Tree

By Lu Pan in btree on

Traditional B-Tree has a few noticeable downsides e.g. heavy disk IO (for in-place update), and low space utilization (as B-Tree leaves a lot of space on the table to avoid frequent splits and merges). BW-Tree [https://www.microsoft.com/en-us/research/publication/the-bw-tree-a-b-tree-for-new-hardware/] ( https://www.microsoft.com/en-us/research/…

GNU Visibility Attribute

By Lu Pan in c++ on

When going through the folly [https://github.com/facebook/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…