Tarik Al Hadethi Download CV

A 41% error rate I cannot price

A maintainer asked me a narrow question about a kernel picker. I measured twenty-nine real shapes and found it chooses badly on twelve of them. That number sounds decisive. It is not, and the interesting part of this is why.

Some background, briefly. My OCR runs on tract, a pure-Rust neural network runtime. For matrix multiplication it does not have one implementation, it has a set of hand-written kernels tuned for different tile shapes, and something has to choose between them for each operation. Choose badly and you leave throughput on the floor for no reason at all.

I had measured tract running about 6.7 times slower than onnxruntime on detection, which is a big enough gap to want a cause. Two candidate causes: the picker is choosing the wrong kernel, or the kernels themselves are bound by how data gets packed into them. Those have completely different fixes.

The good part was that the question came with a condition attached

A maintainer set the fork before seeing any data:

If the picker is wrong at that rate on the big tiles, it starts to matter. If not, we are back to packing.

That is a genuinely useful way to ask for a measurement, because it decides in advance what each outcome means. Nobody gets to look at the numbers afterwards and pick the reading they like.

The answer went against the interesting outcome

The two large tiles he was worried about are picked correctly, at 1.03x and 1.04x off the best available kernel. So by his own framing, the answer is packing, not the kernels, and the exciting hypothesis was dead on arrival.

That is the whole result, and I could have stopped there. But the full sweep had turned up something real on the way past.

Twelve of twenty-nine, with a shape to it

Across twenty-nine F32 shapes, twelve are mis-picked. Not randomly:

  • One kernel, fma_24x4, wins on nine of the twelve and is chosen for one. Another, fma_8x8, is chosen for five and wins one.
  • It concentrates at narrow N. 53% mis-picked at N ≤ 64 (nine of seventeen) against 25% above it (three of twelve).
  • The worst single case is 2.00x, and it is almost funny once you see it. The shape is 8,64,102400. With m = 8, the 8x8 kernel is an exact fit. The picker takes 24x4, which wastes sixteen of its twenty-four rows. That kernel was seventh in the list.
  • The misses invert each other. It takes 24x4 where 8x8 wins, and takes 8x8 where 16x6 wins. So it is not a simple bias toward wide tiles or narrow ones, which would have been an easy fix and an easy story.

One clean negative result worth recording: the avx_* variants track three to eight percent below their FMA twins everywhere and never win a single shape. Nothing to do there.

What I cannot tell you

Here is the part I think matters more than the finding.

I do not know what any of that is worth in wall clock, and I said so in the reply. Per-node timings exist for four convolutions from an earlier profile, and these twenty-nine shapes cannot be weighted by them. So there is no way to say where the 115 ms of matmul time actually lands among them.

A 41% error rate on cold shapes and a 41% error rate on hot shapes are completely different findings. One is a footnote and one is a real optimisation, and the rate alone cannot tell them apart.

There was a number available to borrow, which is exactly why this needs saying. An earlier five-shape run had priced two mis-picks at 6.7 and 6.8 ms of a 318.7 ms network, about 2%. It would be very easy, and completely wrong, to carry that forward and write "41% of shapes, worth 2%". Those are two different measurements of two different sets. The honest sentence is that the second one is unmeasured, and the next step is to pull the per-node times and weight it properly.

The run that would have measured nothing

The first attempt at this would have started while a release build was saturating every core on the machine.

Numbers taken then describe the load, not the kernels. Worse than useless: contention could easily flip which kernel appears faster, and which kernel is faster is the entire question. So the benchmark was chained to wait for the build to finish, settle for thirty seconds, and assert the CPU was actually idle, which it was, at 21%.

A smaller one, for anybody running long benchmarks: piping the output through sed to strip colour codes made it buffer, so the file sat at zero lines for the entire sixty-five minute run and I had no idea whether it was alive. Strip the colours afterwards, not in the pipe.

The general shape

“Wrong on 41% of shapes” is a good headline and I am not going to use it as one, because a rate counts occurrences and an impact weights them, and nothing I have measured connects the two.

A rate is not an impact. Until you know where the time actually goes, a percentage of cases is a description of your sample, not of the system.

The finding is real and the picker should be fixed. I just cannot yet tell anyone how much they would get for fixing it, and pretending otherwise would have made a better post and a worse contribution.

Measured on an i7-12700K, AVX2 and FMA, no AVX-512, single-threaded, against onnxruntime 1.29.0.  ·  More writing