Nibbles

One mechanism in three or four stages, each one reachable only through the one before. Lives on logicalart.us.

Everything here, in one chronology, is on the studio index. The smaller pieces are bits, and the whole machines are bytes.

1937 Nibble Subject: logic, also numbers, hardware.
The Adder
Every bit adds correctly on its own. The carry is what makes it slow.
/nibbles/adder/
1946-1947 Nibble Subject: logic, also hardware.
Trigger
Why the trace stands still.
/nibbles/trigger/
1949 Nibble Subject: encoding, also numbers.
Sampling
The same samples fit two different waves, and nothing in them says which one you had.
/nibbles/sampling/
1949 Nibble Subject: numbers, also logic.
The Middle Square
An early way of making random numbers by arithmetic, and it dies: every seed there is falls into one of eight short cycles.
/nibbles/middle-square/
1950s-1970s Nibble Subject: hardware, also numbers.
Score Reel
An electromechanical table cannot add, it can only count at the speed of a motor.
/nibbles/score-reel/
1950 Nibble Subject: errors.
Hamming
Put the checks at the powers of two and the failures spell the address.
/nibbles/hamming/
1952 Nibble Subject: compression.
Huffman
The two rarest symbols marry, and the tree that falls out is provably the best code of its kind.
/nibbles/huffman/
1953 Nibble Subject: hardware.
Core Memory
Half a current does not flip the core. Reading the bit is what destroys it.
/nibbles/core-memory/
1953 Nibble Subject: storage, also encoding.
Hash Table
Finding the key stays cheap until too many keys want the same drawer.
/nibbles/hash-table/
1954 Nibble Subject: hardware, also concurrency.
The Interrupt
What happens in between two instructions.
/nibbles/interrupt/
1956 Nibble Subject: logic, also numbers, hardware.
Carry-Lookahead Adder
Stop waiting for the carry to ripple and work out where every carry is born.
/nibbles/carry-lookahead/
1958 Nibble Subject: hardware, also storage.
DMA
The processor never copied these bytes and they arrived in memory anyway.
/nibbles/dma/
1959 Nibble Subject: numbers, also hardware.
CORDIC
A sine, from nothing but shifts and adds.
/nibbles/cordic/
1960 Nibble Subject: logic, also storage.
The Call Stack
Recursion spends memory that appears in no line of the source. You can work out the exact depth it dies at.
/nibbles/call-stack/
1960 Nibble Subject: storage, also logic.
Garbage
Memory becomes garbage when nobody can reach it, not when somebody says it is finished.
/nibbles/garbage/
1960 Nibble Subject: errors, also storage.
Reed-Solomon
Erase the bytes you can see are gone and the equations hand them back.
/nibbles/reed-solomon/
1961 Nibble Subject: errors.
CRC
Divide the message by a polynomial and the remainder is what you send.
/nibbles/crc/
1961 Nibble Subject: hardware.
The Pipeline
The next instruction starts before this one finishes, until it needs something that does not exist yet.
/nibbles/pipeline/
1961 Nibble Subject: concurrency, also hardware.
Round Robin
Every program believes it owns the processor because none of them gets to keep it.
/nibbles/round-robin/
1962 Nibble Subject: hardware, also storage.
Page Fault
The address exists even when the memory does not.
/nibbles/page-fault/
1962 Nibble Subject: hardware, also storage.
The TLB
If every address must be translated, where does the translation table live?
/nibbles/tlb/
1962 Nibble Subject: hardware, also security.
The System Call
One digit of the function code decides whether the hardware obeys the instruction or files it.
/nibbles/system-call/
1962 Nibble Subject: hardware, also concurrency.
Context Switch
Your program is stopped between two instructions, its registers are copied somewhere, another program runs for a while, and then everything is put back so precisely that it cannot tell.
/nibbles/context-switch/
1964 Nibble Subject: numbers, also logic.
The Shuffle
The obvious way to shuffle a list is biased above two cards, and you can prove it by counting rather than by measuring.
/nibbles/seeded-shuffle/
1964 Nibble Subject: networks, also hardware.
Packet Switching
Each station is destroyed at random, and the network is measured by how much of it still holds together.
/nibbles/packet-switching/
1964-1967 Nibble Subject: hardware.
Out of Order
The processor reorders your instructions, runs them in an order you never wrote, and is required to produce the answer you would have got anyway.
/nibbles/out-of-order/
1965-1990s Nibble Subject: hardware.
CPU Cache
Reading memory twice is not the same operation twice.
/nibbles/cpu-cache/
1965 Nibble Subject: numbers.
FFT
Reusing a sum instead of recomputing it takes n-squared work down to n log n.
/nibbles/fft/
1965 Nibble Subject: concurrency.
Deadlock
Each program is waiting for the other to release the thing it cannot release.
/nibbles/deadlock/
1965 Nibble Subject: concurrency.
Race
Two increments. One of them goes missing.
/nibbles/race/
1965 Nibble Subject: concurrency.
The Semaphore
The count is the permission, and no process has to know which other one is waiting.
/nibbles/semaphore/
1965 Nibble Subject: storage, also logic.
Fragmentation
There is enough free memory for the request and the request still fails.
/nibbles/fragmentation/
1966 Nibble Subject: hardware, also numbers.
SIMD
One instruction, many lanes, and the speedup stops being the number of lanes the moment the data disagrees.
/nibbles/simd/
1968 Nibble Subject: numbers.
Fifteen Planes
It passes every easy test. Then everything lands on fifteen planes.
/nibbles/fifteen-planes/
1968 Nibble Subject: hardware, also storage.
DRAM Refresh
The bit disappears unless the machine keeps reading it and writing it back.
/nibbles/dram-refresh/
1968 Nibble Subject: encoding, also logic.
Regular Expressions
The search holds every state at once, which is why it never has to go back and can never be made to take forever.
/nibbles/regex/
1969 Nibble Subject: hardware, also storage.
Page Replacement
Giving a program more memory can make it fault more, and the obvious algorithm is where it happens.
/nibbles/page-replacement/
1970 Nibble Subject: storage.
B-tree
A billion rows in four reads. Node width is the whole reason.
/nibbles/b-tree/
1970 Nibble Subject: storage, also numbers.
Bloom Filter
No means no. Yes means maybe.
/nibbles/bloom-filter/
1971 Nibble Subject: storage.
The Inode
The filename is not the file.
/nibbles/inode/
1972 Nibble Subject: hardware, also storage.
Copy-on-Write
Two processes share the same memory until one of them writes.
/nibbles/copy-on-write/
1973 Nibble Subject: graphics, also hardware.
Double Buffer
Why the picture tears.
/nibbles/double-buffer/
1973 Nibble Subject: hardware, also logic.
Metastability
Catch a flip-flop at the wrong instant and it cannot promise when it decides.
/nibbles/metastability/
1973 Nibble Subject: security, also encoding.
Avalanche
Change one bit and half the answer changes.
/nibbles/avalanche/
1973-1976 Nibble Subject: networks, also concurrency.
Backoff
Two machines transmit on the same wire. Both back off for a random interval.
/nibbles/backoff/
1974 Nibble Subject: encoding, also errors.
Checkout
The label tells the scanner which way up it went across the glass.
/nibbles/checkout/
1974-1981 Nibble Subject: networks, also errors.
Sequence Numbers
The stream arrives in order and nothing underneath it is in order.
/nibbles/sequence-numbers/
1974 Nibble Subject: concurrency.
Compare and Swap
Change it only if the value is still the one you last read.
/nibbles/compare-and-swap/
1974 Nibble Subject: graphics, also hardware.
Z-Buffer
Draw the triangles in any order and every pixel still keeps the nearest one.
/nibbles/z-buffer/
1975 Nibble Subject: numbers.
Goodhart planned
It ranked them correctly for years, and then a cheaper way to raise it arrived.
1976 Nibble Subject: security, also numbers.
Diffie-Hellman
The secret is not among the things that crossed the wire, and everything that did is on the screen.
/nibbles/diffie-hellman/
1976 Nibble Subject: graphics, also encoding.
Dithering
The error you cannot remove, pushed into the pixels next door.
/nibbles/dithering/
1976 Nibble Subject: compression.
Arithmetic Coding
The whole message becomes one number in an interval that keeps shrinking.
/nibbles/arithmetic-coding/
1977-1981 Nibble Subject: hardware, also numbers.
Zero Address
Assembly for a processor that was usually not there.
/nibbles/zero-address/
1977-2018 Nibble Subject: compression, also encoding, graphics.
Fringes
Colour and resolution are the same currency.
/nibbles/fringes/
1977 Nibble Subject: compression.
LZ77
A repeat becomes a pointer into bytes you have already seen.
/nibbles/lz77/
1978 Nibble Subject: storage, also networks.
Two-Phase Commit
Everyone promises before anyone acts, and a coordinator lost at the wrong moment blocks them all.
/nibbles/two-phase-commit/
1978 Nibble Subject: security.
Signature
How can everyone verify something only one person could have produced?
/nibbles/signature/
1978 Nibble Subject: networks, also concurrency.
Logical Clock
The clocks disagree and the machines still agree on an order that never puts an effect before its cause.
/nibbles/logical-clock/
1978 Nibble Subject: storage, also concurrency.
MVCC
The reader never waits, because it is reading a version nobody is writing.
/nibbles/mvcc/
1979 Nibble Subject: encoding, also compression.
Z-Characters
Five bits is not enough for English. Zork shifted.
/nibbles/z-characters/
1979 Nibble Subject: encoding.
Line Discipline planned
The end of a file is not a character you can type. It is a read that comes back empty.
1979 Nibble Subject: encoding, also logic.
Shell Expansion planned
The line you typed is rewritten before it runs, and the order decides which files it touches.
1979 Nibble Subject: security, also errors.
Merkle Proof
Proof that a leaf is in the tree, without being shown the tree.
/nibbles/merkle-proof/
1979 Nibble Subject: concurrency, also hardware.
Memory Ordering
Both processors wrote first, and both can still read zero.
/nibbles/memory-ordering/
1981-1990s Nibble Subject: hardware.
Branch Prediction
The processor runs an instruction before knowing whether it should exist.
/nibbles/branch-prediction/
1981-1992 Nibble Subject: storage, also concurrency.
Write-Ahead Log
The database says done before half the database has been written.
/nibbles/write-ahead-log/
1982 Nibble Subject: errors, also encoding.
Interleave
Scratch the disc and watch a burst thin out across many codewords.
/nibbles/interleave/
1983 Nibble Subject: networks.
DNS
No server knows every answer, and each one either answers or says who to ask next.
/nibbles/dns/
1984-1990s Nibble Subject: hardware, also concurrency.
False Sharing
Two threads, two variables, nothing shared. In one cache line they still fight.
/nibbles/false-sharing/
1984 Nibble Subject: hardware, also concurrency.
Cache Coherence
The fourth state is free.
/nibbles/cache-coherence/
1984-1987 Nibble Subject: compression, also encoding.
LZW
The dictionary is never sent. Both ends build it from the data.
/nibbles/lzw/
1984 Nibble Subject: graphics, also encoding.
Premultiplied Alpha
Average straight colour and the cut-out's edge picks up whatever the transparent pixels hide.
/nibbles/premultiplied-alpha/
1985 Nibble Subject: numbers.
Floating Point
The answer is already wrong before the addition rounds it.
/nibbles/floating-point/
1985 Nibble Subject: numbers, also logic.
Quantum Interference
Measured once it is fifty-fifty, and the same step twice gives one answer every time.
/nibbles/quantum-interference/
1985 Nibble Subject: networks.
Spanning Tree
One spare cable and the network drowns; cut the right links and it is safe.
/nibbles/spanning-tree/
1987-1990s Nibble Subject: storage, also hardware.
Erase Block
The drive cannot overwrite the page you asked it to overwrite.
/nibbles/erase-block/
1988 Nibble Subject: networks, also concurrency.
Slow Start
Nobody tells TCP how fast it may send. It finds out by hurting the network.
/nibbles/slow-start/
1988 Nibble Subject: networks, also concurrency.
Vector Clock
Each machine counts everyone's messages, so it can tell concurrent from caused.
/nibbles/vector-clock/
1988 Nibble Subject: storage, also errors.
RAID Parity
A whole disk is gone and XOR still knows every byte that was on it.
/nibbles/raid-parity/
1991 Nibble Subject: numbers, also errors.
Catastrophic Cancellation
The subtraction is exact and loses nothing, which is what makes it ruinous.
/nibbles/cancellation/
1992-2008 Nibble Subject: security, also concurrency.
Longest Chain
History goes to the chain with the most accumulated work, not the one that actually cost the most.
/nibbles/longest-chain/
1992 Nibble Subject: compression, also graphics.
JPEG
Throw away numbers, not pixels.
/nibbles/jpeg/
1992 Nibble Subject: encoding.
UTF-8
Starting to read in the middle costs a bit in every byte.
/nibbles/utf-8/
1993 Nibble Subject: compression.
Masking
Put a loud tone beside a quiet one, then throw the quiet one away.
/nibbles/masking/
1993-1995 Nibble Subject: networks.
Longest Prefix
Three routes match the address, and the longest one wins.
/nibbles/longest-prefix/
1996 Nibble Subject: storage.
LSM-Tree
Never change a file, write another, then keep rewriting them all.
/nibbles/lsm-tree/
1996-1997 Nibble Subject: compression, also graphics.
PNG Filters
The compression happens after something else has made the bytes boring.
/nibbles/png-filters/
1996-1999 Nibble Subject: graphics, also numbers.
Gamma
The numbers are not brightness, which is why the average of two of them is the wrong colour.
/nibbles/gamma/
1997 Nibble Subject: networks, also storage.
Consistent Hashing
Add one more server and almost every key stays where it was.
/nibbles/consistent-hashing/
1998 Nibble Subject: numbers.
PageRank
Importance defined by importance, and the circle closes if you iterate.
/nibbles/pagerank/
2001 Nibble Subject: security, also encoding.
AES
Sixteen bytes go in, and every byte that comes out depends on every byte that went in.
/nibbles/aes/
2002-2015 Nibble Subject: errors.
Merge Collapse
The sort behind python, java, android and v8, and the invariant it did not keep.
/nibbles/merge-collapse/
2002 Nibble Subject: concurrency.
Futex planned
A lock that never asks the kernel for anything until two threads want it at once.
2005 Nibble Subject: storage, also security.
Merkle DAG
A commit holds hashes pointing at hashes, and never holds your repository.
/nibbles/merkle-dag/
2007 Nibble Subject: numbers.
Count Distinct
Wrong on purpose, by an amount it knows before it starts.
/nibbles/count-distinct/
2014 Nibble Subject: concurrency, also networks.
Majority
A write counts once most machines have it, and no later majority can miss it.
/nibbles/majority/
2014 Nibble Subject: concurrency, also networks.
Consensus planned
One of them is elected to speak, and the decision survives losing it.
2014 Nibble Subject: security, also hardware.
Rowhammer
Reading one address changes a different address you never wrote.
/nibbles/rowhammer/
2018 Nibble Subject: security, also hardware.
Spectre
The instruction never happened, and the cache remembers that it did.
/nibbles/spectre/
2018 Nibble Subject: security, also networks.
TLS Handshake
Everybody hears the conversation that agrees the key nobody else has.
/nibbles/tls-handshake/

Goodhart planned

Line Discipline planned

Shell Expansion planned

Futex planned

Consensus planned