Physical · your machine is the apparatus

The Shape of the Silicon Under Your Finger

A web page is not allowed to ask what processor it is running on. It is allowed to time things. That turns out to be enough: from a loop of dependent loads and a clock that was deliberately blunted to stop exactly this, your browser can draw the shape of the caches physically present in the chip under your hand, and put numbers on them. This page does that, in front of you, on your machine. Then it does the harder half, which is telling you how far off those numbers are, and which part of the gap is your machine rather than your error.

1Your machine, in about ten seconds

Here is the whole method. Take an array. Fill it with a single closed cycle of pointers, one landing site every 64 bytes, in a random order. Then follow it: each load's address is the value the previous load returned, so the processor cannot run two of them at once and cannot guess where you are going. Every load costs whatever it costs to reach the memory it lands in.

Now grow the array. While the whole cycle fits in the fastest cache, every load is cheap. When the cycle stops fitting, the cost steps up to whatever the next level costs, and stays there until that level fills too. What you get is a staircase, and the positions of the steps are the sizes of the caches. The absolute nanoseconds are weather. The steps are the measurement.

The rule that turns that curve into knees was fixed before any machine was measured with it, and it is short. A plateau is a run of at least four consecutive sizes, spanning at least a doubling of the working set, over which the time never rises by more than a quarter. Two plateaus are two levels of the hierarchy only if the slower one is at least 1.35 times the faster. The knee between two levels is where the curve crosses the geometric mean of the two plateau floors, interpolated between the two sizes that bracket it.

2Now ask the machine what it thinks it is

This page cannot see the answer. There is no browser API that reports cache sizes, which is the entire reason the measurement is interesting, and also the reason the comparison has to be done by hand. Run one command in a terminal on this machine and paste the numbers in. The page will not go looking, and it has nothing to look with.

Whatever you typed, do not expect the first row to come in under it. It may well come in over. What is reliable is not the sign of the first gap but the ordering of all of them: on every capture this page ships, the knee sits closest to the published size at the first level and falls further behind it at each level down.

That is not a bug, and section 4 is about why. First, the thing that ought to have made this impossible.

3The clock you are allowed to have

In 2015 Oren, Kemerlis, Sethumadhavan and Keromytis showed that a page of JavaScript could spy on the machine it was loaded into, using nothing but a fine-grained clock and the cache. Browsers responded by taking the fine-grained clock away. Schwarz, Maurice, Gruss and Mangard, writing two years later, put the situation exactly:

We demonstrate the inefficacy of this mitigation by finding and evaluating a wide range of new sources of timing information. Schwarz, Maurice, Gruss and Mangard, Fantastic Timers and Where to Find Them, Financial Cryptography and Data Security 2017, LNCS volume 10322, pages 247 to 267. Graz University of Technology.

They are quoted for that sentence and for nothing else, and the difference matters. Their two methods are not this page's method: they build a busy-wait counter calibrated between two edges of the clock and interpolate the time in the gap, and they pad a fast function until it crosses one fewer edge. Neither is averaging, and the word does not appear in their paper. Their techniques are also far stronger than this one, reaching two nanoseconds with a shared buffer and a counting thread. So the amortising argument in the next section is this page's own, resting on their result that the clamp did not close the door, not on any claim of theirs about averaging.

This page is a much gentler thing than what they built, but it lives on the same fact, and the fact is worth holding directly. Press the button and watch your own clock. It does not move smoothly. It moves in steps, and the steps have a size.

MDN states the two cases plainly: Resolution in isolated contexts: 5 microseconds and Resolution in non-isolated contexts: 100 microseconds. Firefox goes further and adds jitter on top of the rounding, which is a harder thing to see through than rounding alone.

And none of it stops this page. A clock too blunt to time one load is not too blunt to time a million of them. Put a million dependent loads inside one pair of clock readings and the quantum divides by a million: a 1 millisecond clock, amortised over ten million loads, resolves a tenth of a nanosecond per access. What a coarse clock costs you is not accuracy. It is iterations.

There is a real limit here, and the instrument found it before you did. On the committed browser capture, asking for a 5 microsecond clamp produced a 95 microsecond clock, because Chromium's performance.now() only moves every 100 microseconds and you cannot round a number to finer than it already is. That row is marked unusable and reported as a refusal rather than as a number. The two clocks the browser could actually have are both fine.

4Why the deep numbers come in low

The knee is not the cache, and it is not a lower bound on the cache either. This page's knee is the point half way up the shoulder, so it sits above the largest working set the level still served, and it can land on either side of the published size. On four of the six captures here the first knee comes in above it. The rule that was retired, the top of the plateau, is a genuine lower bound and is still computed and shipped beside this one, so you can see the difference for yourself in the table further down.

What survives, on every capture, is not the sign of the gap but its ordering, and the ordering is a property of the machine rather than of the estimator. Your cache is not yours. The first level is private to one core, so it holds almost only your array and there is very little to lose; the loop's own code and stack want a few kilobytes of it, and the width of the shoulder more than covers them. The last level is shared with every other core and every other process on the machine, so by the time your array is the size of it, most of it belongs to somebody else. In between, the second level is partly yours.

Here is that stated as a prediction and then tested. If the deep levels come in low because they are shared, then deliberately giving the shared cache a competitor should move the deep knee much further than the shallow one. Three threads were set streaming through memory beside the sweep, on the same machine, and the sweep was run again. The prediction as it was written said the first level would be left alone, and it was not: read the two falls below and notice that the private one is a sixth, not nothing.

The second reason the estimator could have been fooling itself is that it was chosen by looking at one machine. So the honest test is a machine it had never seen.

Every capture this page ships, side by side, replayed through the same reduction that just measured you:

Two of those rows are the same machine measured through two different clocks. One is the same machine again with a competitor running. Three are a machine in a data centre somewhere, whose last-level cache is far larger than this page's sweep reaches, which is why its third knee is missing rather than wrong. The last column is the retired rule, the top of the plateau, computed on the same points: it never exceeds the published size on any capture here, and the shipped rule in the fourth column always exceeds it. That is the whole difference between a lower bound and an estimate.

5How far apart is far?

A cache does not fetch bytes, it fetches lines. So there should be a distance d below which two loads are nearly one load, and above which they are two, and the distance where that changes should be the line size. Saavedra and Smith set this out in 1995, in a section called B.3. Cache Line Size:

The value of s when the transition between regimes 2.a and 2.b gives the cache line size. Rafael H. Saavedra and Alan Jay Smith, Measuring Cache and TLB Performance and Their Effect on Benchmark Runtimes, IEEE Transactions on Computers, vol. 44, no. 10, October 1995, pages 1223 to 1235. University of Southern California and University of California, Berkeley.

The probe here is a variation. Each step of the chase is a pair: land somewhere random, then read a second word exactly d bytes away, then jump somewhere random again. The first address is placed at a random offset inside its line, uniformly, so the answer cannot depend on where the runtime happened to put the array. That matters more than it sounds: without it, this probe read the line size as 48 bytes, which is not a number any cache has ever had.

The probe is run in three places, and one of them is designed to fail. Inside the first cache, nothing is being fetched from anywhere, so there is no granule to find and an accepted answer would mean the fit is inventing one. Between the first and second knees, and past the last knee, there is a real fetch to find.

There is a trap in this probe that it fell into, and the trap is now a rule. While d is inside the granule, each pair touches one line; once it is outside, each pair touches two. So the footprint doubles across exactly the transition being measured. Put the probe where that doubling steps over the edge of a cache and it will report the edge instead of the granule, with a beautiful fit. On the build machine, one placement did precisely that and returned a confident 64 bytes, which happens to be the right answer for the wrong reason. The rule now is that both footprints, the small one and the doubled one, must sit clear of both shoulders of the same level, and if no such placement exists the probe refuses.

Placed legally, on the build machine, the probe returns 128 bytes. That machine's own kernel says its coherency line is 64. Both are true, and the reason is written down:

Spatial Prefetcher: This prefetcher strives to complete every cache line fetched to the L2 cache with the pair line that completes it to a 128-byte aligned chunk. Intel 64 and IA-32 Architectures Optimization Reference Manual, order number 248966-026, April 2012, section 2.1.5.4 Data Prefetching. That section sits under the heading INTEL MICROARCHITECTURE CODE NAME SANDY BRIDGE, and the sentence appears exactly once in the whole 800-page manual, so the part measured below is two generations past the part the sentence was written about. The measurement is what carries the claim here. The manual is why the measurement is not a surprise.

So the probe is not measuring the coherency line and this page does not claim it is. It measures the distance over which the machine rewards adjacency, and on an Intel part that is a pair of lines, because the machine fetches them in pairs. Your number is what your machine does. The kernel's number is what your machine promises. They are answers to different questions.

On the three captures from the shared machine in the data centre, this probe refused every placement, three runs out of three. A busy virtual machine does not hold still enough. That is printed as a refusal, not smoothed into a number.

6Six curves that are not yours, and thirteen that are not real

Pick any committed capture and it is replayed here, now, in your browser, through the identical code that measured your machine a minute ago. Nothing about the reduction changes between your curve and theirs. That is the point of putting them here: if the reduction only worked on the author's laptop, this is where it would show.

And then the curves that were never measured at all. A reduction that returns a confident number from noise is not an instrument, it is a random number generator with a citation. These were built by hand with known answers, six of them built to have no answer, and they are run here every time this page loads.

Two of those rows are worth stopping on, because each of them caught this page returning a confident number out of a curve that had no answer in it.

The first is granuleRamp, and it is the reason the fit now has a ceiling. The adjacency model is a ramp that climbs until d reaches the granule and is flat afterwards, and the evidence that a granule is there is the flat part. When the winning granule is the largest distance swept there is no flat part in the data at all, and the model collapses into a straight line, which fits any unbroken climb perfectly. A curve rising a twentieth of a nanosecond per byte and never turning over was accepted at 256 bytes with all of the variance explained and a hundred per cent margin over the runner-up. The rule now is that a granule needs at least two swept distances above it, which makes 256 unreachable on this ruler. That changed no reading on any real capture, because every accepted fit here is 128, which has four distances above it. It is also why the synthetic 256-byte ramp in the table above is refused rather than answered: a real 256-byte granule and a curve that never turns over are the same numbers on this grid, and the honest output is to decline both. Read a refusal there as "past the end of the ruler", never as "small".

The second is smoothClimb, and it is still fooling the page. A featureless curve that rises about a quarter per octave and contains no cache edge anywhere gets named a hierarchy. The cause is arithmetic: four sizes span an octave, so a curve rising at very nearly the twenty-five per cent plateau tolerance chops itself into plateaus that are not there. The window is narrow, roughly 1.19 to 1.28 times per octave, and outside it the instrument refuses; a real memory curve steps rather than creeping and does not sit in that window. But the instrument cannot see through it, so the curve stays in the table with its wrong answer printed in red, rather than being left out.

The row that matters most is still the one that shows the adjacency fit returning 32, 64 and 128 bytes on curves built with those breakpoints. On the real captures the agreement is thinner than it looks and the page will not dress it up: one physical processor produced an accepted fit, in both of its legal placements, in both of the clocks it was measured through, and every time it said 128. The other physical processor refused all nine of its placements. So the evidence for 128 is one machine answering four times, not two machines agreeing, and without the synthetic rows showing the fit is capable of saying 32 and 64, and of refusing rather than reaching for the top of its own list, it would not be evidence at all.

7What this page will not tell you

A page that always produces a figure is a page that will eventually produce a wrong one. Every place this instrument declined to answer during your visit is listed here, with the reason. An empty list means you have not asked it anything yet.

The standing ones, which no reader can talk it out of: it will not name a cache level from fewer than two plateaus; it will not report a sweep whose points mostly failed the block-length rule; it will not trust a sweep taken while the tab was in the background, because a background tab is throttled; it will not place the adjacency probe across a cache edge; it will not accept an adjacency fit whose ramp is under 18 per cent of its plateau, or which explains under 80 per cent of the variance, or which beats its runner-up by under 6 per cent, or which has fewer than two swept distances above it, which is what stops it reading an unbroken climb as a 256-byte granule; and it will not tell you your cache sizes, because it cannot see them, and neither can anything else running in this tab.

And one it cannot refuse, named here because it is the sharpest thing known against this instrument. A curve that rises smoothly at close to a quarter per octave, with no cache edge anywhere in it, is read as a hierarchy rather than declined. That curve is in the table in section 6 with its wrong answer printed. Nothing on this page detects it; what protects the readings above is only that real memory steps instead of creeping.

What the check panel checks

Everything above is recomputed below, in your browser, from the shipped module and the committed captures. Lines marked OFFLINE are results your browser cannot redo. The rest it just did.