Add memory access pattern overview to the DESIGN document

1 files changed, 35 insertions, 3 deletions

diff --git a/DESIGN b/DESIGN
index f089a3d..480aa9b 100644
--- a/DESIGN
+++ b/DESIGN
@@ -108,6 +108,32 @@ single-family torrent pays for the absent family's vector header. On jemalloc
 the bins differ, so the per-shape figures do too, but the empty-torrent and
 single-allocation gains hold on both.
 
+Reading those structs for one announce is a walk down cold memory. With the
+hash in hand, the steady-state path to an existing torrent reads, in order:
+
+    step            reads                                  load
+    lock            one bucket mutex                       cold
+    bucket header   that bucket's torrent vector           cold
+    torrent search  a hash per probe, log2 of the bucket   cold
+    peerlist        the torrent's peerlist                 cold
+    peer search     a peer per probe, log2 of the swarm    cold
+    reply counts    the peerlist's sizes and seeder count  hot
+
+Each cold line is a separate allocation, and on a large table each is a miss.
+The hot line rode in on the peerlist step before it. The torrent search
+dominates, one miss per probe into a bucket of hundreds of thousands, with the
+peerlist pointer chase and the peer search behind it. Aging the torrent adds
+nothing in steady state: one touched this minute has a zero span and the
+cleaner returns at once. The reply counts are hot because the two family
+sizes and the seeder count share the peerlist's line. A split swarm is the
+exception, since summing its size walks the bucket headers, but those are the
+largest torrents, where handing out peers already walks the swarm.
+
+A request waits on two system calls around this, a receive and a send, each
+on the order of a handful of misses. Memory latency and kernel time are
+co-dominant. Neither hides behind the other, and no term in the table is one
+a cache would hold still.
+
 A refused announce is answered over UDP with a well formed announce for an
 empty swarm rather than with the error action. BEP 15 binds a client to the
 interval it is handed and says nothing about what a client should do with an
@@ -140,7 +166,7 @@ Build hardening the shipped binary
 ----------------------------------
 
 The production and debug binaries carry -fstack-protector-strong, -fPIE and
-_FORTIFY_SOURCE=2 on every platform; the GNU-style linkers also get -pie and
+_FORTIFY_SOURCE=2 on every platform. The GNU-style linkers also get -pie and
 full RELRO (-z relro,-z now). Measured cost on
 the announce hot path is 300 to 305 nanoseconds, under two per cent, and the
 individual flags sit inside the run-to-run noise: add_peer has few stack
@@ -152,7 +178,7 @@ The link flags -pie and RELRO are gated on the operating system: Apple's
 linker rejects -z, and flags a bare -pie in the combined compile-and-link as
 unused, while macOS links executables PIE by default, so leaving both off
 there costs no hardening. The branch runs in the shell through a != assignment,
-the one form both bmake and GNU make 4 accept; $(shell) is GNU only and GNU
+the one form both bmake and GNU make 4 accept. $(shell) is GNU only and GNU
 make 3.81, which stock macOS ships, has neither. On that old make the != line
 is inert and leaves the flags empty, which is the right answer for macOS
 anyway, so every platform resolves correctly without a make conditional.
@@ -225,13 +251,19 @@ A directory for object files. bmake has no pattern rules and the Makefile
 builds under FreeBSD's make today. Building each binary in one invocation
 clears the objects out of the tree without giving that up.
 
+A cached peer count on the torrent or the peerlist. The count is a vector's
+own size, a field in a line the peer insert has already loaded, so a cache
+would hold a second copy of a number already in reach and have to be kept in
+step with the vector it copies. Only a split swarm pays, to sum its buckets,
+and there the sum is lost against walking the swarm to answer at all.
+
 
 
 Platform differences that cost us code
 --------------------------------------
 
 SO_REUSEPORT means three different things. Linux spreads datagrams over the
-group; FreeBSD permits the bind and needs SO_REUSEPORT_LB to spread. Darwin
+group. FreeBSD permits the bind and needs SO_REUSEPORT_LB to spread. Darwin
 hands every datagram to whichever socket bound last, so a group there starves
 all but one reader.