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…

Paxos Commit with Constraints

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 algorithm as an alternative to 2PC for achieving Transaction Commit. It's a very natural application of the Paxos…

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…

BW-Tree

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/) is a B-Tree variant proposed by…

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,…

Fix visual artifact on Linux running AMD 3400G

I did a mini-itx build with AMD 3400G. It works great except occasionaly visual artifacts which affected Firefox the most when watching videos. The problem is solved by disabling IOMMU. I verfied that setting kernel parameter iommu=pt also works. https://en.wikipedia.org/wiki/Input%E2%80%93output_memory_…

Compile `folly` from source on Arch Linux

You first need to install all the dependencies as documented on the folly github page, fmt googletest, boost gflag glog These are pretty straightforward, as you can build them just fine by following the github page for each project respectively. However I ran into some issues when building folly from…

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…