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.

  1. 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/
  2. 1946-1947 Nibble Subject: logic, also hardware.

    Trigger

    Why the trace stands still.

    /nibbles/trigger/
  3. 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/
  4. 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/
  5. 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/
  6. 1950 Nibble Subject: errors.

    Hamming

    Put the checks at the powers of two and the failures spell the address.

    /nibbles/hamming/
  7. 1952 Nibble Subject: compression.

    Huffman

    The two rarest symbols marry, and the tree that falls out is provably the best.

    /nibbles/huffman/
  8. 1953 Nibble Subject: hardware.

    Core Memory

    Half a current does nothing. Reading the bit is what destroys it.

    /nibbles/core-memory/
  9. 1953 Nibble Subject: storage, also encoding.

    Hash Table

    Finding the key is constant time until two keys want the same drawer.

    /nibbles/hash-table/
  10. 1954 Nibble Subject: hardware, also concurrency.

    The Interrupt

    What happens in between two instructions.

    /nibbles/interrupt/
  11. 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/
  12. 1958 Nibble Subject: hardware, also storage.

    DMA

    The processor never copied these bytes and they arrived in memory anyway.

    /nibbles/dma/
  13. 1959 Nibble Subject: numbers, also hardware.

    CORDIC

    A sine, from nothing but shifts and adds.

    /nibbles/cordic/
  14. 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/
  15. 1960 Nibble Subject: storage, also logic.

    Garbage

    Memory becomes garbage when nobody can reach it, not when somebody says it is finished.

    /nibbles/garbage/
  16. 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/
  17. 1961 Nibble Subject: errors.

    CRC

    Divide the message by a polynomial and the remainder is what you send.

    /nibbles/crc/
  18. 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/
  19. 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/
  20. 1962 Nibble Subject: hardware, also storage.

    Page Fault

    The address exists even when the memory does not.

    /nibbles/page-fault/
  21. 1962 Nibble Subject: hardware, also storage.

    The TLB

    If every address must be translated, where does the translation table live?

    /nibbles/tlb/
  22. 1962 Nibble Subject: hardware, also security.

    The System Call planned

    The same instruction runs in one mode and traps in the other, and the trap is the only door.

  23. 1962 Nibble Subject: hardware, also concurrency.

    Context Switch

    Your program is stopped mid-instruction, 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/
  24. 1964 Nibble Subject: numbers, also logic.

    The Shuffle

    The obvious way to shuffle a list cannot be fair, and you can prove it by counting rather than by measuring.

    /nibbles/seeded-shuffle/
  25. 1964 Nibble Subject: networks, also hardware.

    Packet Switching

    The message is cut into pieces that find their own way, so the network can route around what is gone.

    /nibbles/packet-switching/
  26. 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. Most of the time it manages.

    /nibbles/out-of-order/
  27. 1965-1990s Nibble Subject: hardware.

    CPU Cache

    Reading memory twice is not the same operation twice.

    /nibbles/cpu-cache/
  28. 1965 Nibble Subject: numbers.

    FFT

    Reusing a sum instead of recomputing it takes n-squared work down to n log n.

    /nibbles/fft/
  29. 1965 Nibble Subject: concurrency.

    Deadlock

    Each program is waiting for the other to release the thing it cannot release.

    /nibbles/deadlock/
  30. 1965 Nibble Subject: concurrency.

    Race

    Two increments. One of them goes missing.

    /nibbles/race/
  31. 1965 Nibble Subject: concurrency.

    The Semaphore planned

    The count is the permission, and no process has to know which other one is waiting.

  32. 1965 Nibble Subject: storage, also logic.

    Fragmentation

    There is enough free memory for the request and the request still fails.

    /nibbles/fragmentation/
  33. 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/
  34. 1968 Nibble Subject: numbers.

    Fifteen Planes

    It passes every easy test. Then everything lands on fifteen planes.

    /nibbles/fifteen-planes/
  35. 1968 Nibble Subject: hardware, also storage.

    DRAM Refresh

    The bit disappears unless the machine keeps reading it and writing it back.

    /nibbles/dram-refresh/
  36. 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/
  37. 1969 Nibble Subject: hardware, also storage.

    Page Replacement planned

    Giving a program more memory can make it fault more, and the obvious algorithm is where it happens.

  38. 1970 Nibble Subject: storage.

    B-tree

    A billion rows in four reads. Node width is the whole reason.

    /nibbles/b-tree/
  39. 1970 Nibble Subject: storage, also numbers.

    Bloom Filter

    No means no. Yes means maybe.

    /nibbles/bloom-filter/
  40. 1971 Nibble Subject: storage.

    The Inode

    The filename is not the file.

    /nibbles/inode/
  41. 1972 Nibble Subject: hardware, also storage.

    Copy-on-Write

    Two processes share the same memory until one of them writes.

    /nibbles/copy-on-write/
  42. 1973 Nibble Subject: graphics, also hardware.

    Double Buffer

    Why the picture tears.

    /nibbles/double-buffer/
  43. 1973 Nibble Subject: hardware, also logic.

    Metastability

    Catch a flip-flop at the wrong instant and it cannot promise when it decides.

    /nibbles/metastability/
  44. 1973 Nibble Subject: security, also encoding.

    Avalanche

    Change one bit and half the answer changes.

    /nibbles/avalanche/
  45. 1973-1976 Nibble Subject: networks, also concurrency.

    Backoff

    Two machines transmit on the same wire. Both back off for a random interval.

    /nibbles/backoff/
  46. 1974 Nibble Subject: encoding, also errors.

    Checkout

    The label tells the scanner which way up it went across the glass.

    /nibbles/checkout/
  47. 1974-1981 Nibble Subject: networks, also errors.

    Sequence Numbers

    The stream arrives in order and nothing underneath it is in order.

    /nibbles/sequence-numbers/
  48. 1974 Nibble Subject: concurrency.

    Compare and Swap

    Change it only if nobody changed it since you looked.

    /nibbles/compare-and-swap/
  49. 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/
  50. 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/
  51. 1976 Nibble Subject: graphics, also encoding.

    Dithering

    The error you cannot remove, pushed into the pixels next door.

    /nibbles/dithering/
  52. 1976 Nibble Subject: compression.

    Arithmetic Coding

    The whole message becomes one number in an interval that keeps shrinking.

    /nibbles/arithmetic-coding/
  53. 1977-1981 Nibble Subject: hardware, also numbers.

    Zero Address

    Assembly for a processor that was usually not there.

    /nibbles/zero-address/
  54. 1977-2018 Nibble Subject: compression, also encoding, graphics.

    Fringes

    Colour and resolution are the same currency.

    /nibbles/fringes/
  55. 1977 Nibble Subject: compression.

    LZ77

    The next bytes are a pointer into bytes you have already seen.

    /nibbles/lz77/
  56. 1978 Nibble Subject: storage, also networks.

    Two-Phase Commit

    Everyone promises before anyone acts, and one silent machine blocks them all.

    /nibbles/two-phase-commit/
  57. 1978 Nibble Subject: security.

    Signature

    How can everyone verify something only one person could have produced?

    /nibbles/signature/
  58. 1978 Nibble Subject: networks, also concurrency.

    Logical Clock

    The clocks disagree and the machines still agree which event happened first.

    /nibbles/logical-clock/
  59. 1978 Nibble Subject: storage, also concurrency.

    MVCC

    The reader never waits, because it is reading a version nobody is writing.

    /nibbles/mvcc/
  60. 1979 Nibble Subject: encoding, also compression.

    Z-Characters

    Five bits is not enough for English. Zork shifted.

    /nibbles/z-characters/
  61. 1979 Nibble Subject: security, also errors.

    Merkle Proof

    Proof that a leaf is in the tree, without being shown the tree.

    /nibbles/merkle-proof/
  62. 1979 Nibble Subject: concurrency, also hardware.

    Memory Ordering

    Both processors wrote first, and both can still read zero.

    /nibbles/memory-ordering/
  63. 1981-1990s Nibble Subject: hardware.

    Branch Prediction

    The processor runs an instruction before knowing whether it should exist.

    /nibbles/branch-prediction/
  64. 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/
  65. 1982 Nibble Subject: errors, also encoding.

    Interleave

    Scratch the disc and watch a burst come apart into single symbols.

    /nibbles/interleave/
  66. 1983 Nibble Subject: networks.

    DNS

    Nobody knows the answer, and everybody knows who to ask next.

    /nibbles/dns/
  67. 1984-1990s Nibble Subject: hardware, also concurrency.

    False Sharing

    Two threads, two variables, nothing shared. They still fight.

    /nibbles/false-sharing/
  68. 1984 Nibble Subject: hardware, also concurrency.

    Cache Coherence

    The fourth state is free.

    /nibbles/cache-coherence/
  69. 1984-1987 Nibble Subject: compression, also encoding.

    LZW

    The dictionary is never sent. Both ends build it from the data.

    /nibbles/lzw/
  70. 1984 Nibble Subject: graphics, also encoding.

    Premultiplied Alpha

    The edge of the cut-out is wrong unless you multiply before you blend.

    /nibbles/premultiplied-alpha/
  71. 1985 Nibble Subject: numbers.

    Floating Point

    The answer is already wrong before the addition rounds it.

    /nibbles/floating-point/
  72. 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/
  73. 1985 Nibble Subject: networks.

    Spanning Tree

    One spare cable and the network drowns; cut the right links and it is safe.

    /nibbles/spanning-tree/
  74. 1987-1990s Nibble Subject: storage, also hardware.

    Erase Block

    The drive cannot overwrite the page you asked it to overwrite.

    /nibbles/erase-block/
  75. 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/
  76. 1988 Nibble Subject: networks, also concurrency.

    Vector Clock

    Each machine counts everyone's messages, so it can tell concurrent from caused.

    /nibbles/vector-clock/
  77. 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/
  78. 1991 Nibble Subject: numbers, also errors.

    Catastrophic Cancellation planned

    Subtracting two close numbers throws away the digits you still needed.

  79. 1992-2008 Nibble Subject: security, also concurrency.

    Longest Chain

    History is whatever was most expensive to produce.

    /nibbles/longest-chain/
  80. 1992 Nibble Subject: compression, also graphics.

    JPEG

    Throw away numbers, not pixels.

    /nibbles/jpeg/
  81. 1992 Nibble Subject: encoding.

    UTF-8

    Starting to read in the middle costs a bit in every byte.

    /nibbles/utf-8/
  82. 1993 Nibble Subject: compression.

    Masking

    Put a loud tone beside a quiet one, then throw the quiet one away.

    /nibbles/masking/
  83. 1993-1995 Nibble Subject: networks.

    Longest Prefix

    Three routes match the address, and the longest one wins.

    /nibbles/longest-prefix/
  84. 1996 Nibble Subject: storage.

    LSM-Tree

    Never change a file, write another, then keep rewriting them all.

    /nibbles/lsm-tree/
  85. 1996-1997 Nibble Subject: compression, also graphics.

    PNG Filters

    The compression happens after something else has made the bytes boring.

    /nibbles/png-filters/
  86. 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/
  87. 1997 Nibble Subject: networks, also storage.

    Consistent Hashing

    Add one more server and almost every key stays where it was.

    /nibbles/consistent-hashing/
  88. 1998 Nibble Subject: numbers.

    PageRank

    Importance defined by importance, and the circle closes if you iterate.

    /nibbles/pagerank/
  89. 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/
  90. 2002-2015 Nibble Subject: errors.

    Merge Collapse

    The sort in every standard library, and the invariant it did not keep.

    /nibbles/merge-collapse/
  91. 2005 Nibble Subject: storage, also security.

    Merkle DAG

    A commit holds hashes pointing at hashes, and never holds your repository.

    /nibbles/merkle-dag/
  92. 2007 Nibble Subject: numbers.

    Count Distinct

    Wrong on purpose, by an amount it knows before it starts.

    /nibbles/count-distinct/
  93. 2014 Nibble Subject: concurrency, also networks.

    Majority

    A write counts once most machines have it, and no later majority can miss it.

    /nibbles/majority/
  94. 2014 Nibble Subject: concurrency, also networks.

    Consensus planned

    One of them is elected to speak, and the decision survives losing it.

  95. 2014 Nibble Subject: security, also hardware.

    Rowhammer

    Reading one address changes a different address you never wrote.

    /nibbles/rowhammer/
  96. 2018 Nibble Subject: security, also hardware.

    Spectre

    The instruction never happened, and the cache remembers that it did.

    /nibbles/spectre/
  97. 2018 Nibble Subject: security, also networks.

    TLS Handshake

    Everybody hears the conversation that agrees the key nobody else has.

    /nibbles/tls-handshake/