Category Archives: Bitwise Stuff

Latency Numbers Every Programmer Should Know

This is coming from GitHub: L1 cache reference                            0.5 ns Branch mispredict                             5   ns L2 cache reference                            7   ns             14x L1 cache Mutex lock/unlock                            25   ns Main memory reference                       100   ns             20x L2 cache, 200x L1 cache Compress 1K bytes with Zippy              3,000   ns Send 1K bytes over 1 Gbps network        10,000   ns    0.01 ms SSD random read                         150,000   ns Read […]

Implementing Huffman Coding in C

Huffman Coding (link to Wikipedia) is a compression algorithm used for loss-less data compression. Here’s the basic idea: each ASCII character is usually represented with 8 bits, but if we had a text filed composed of only the lowercase a-z letters we could represent each character with only 5 bits (i.e., 2^5 = 32, which […]