queue

Overview ¶

Command queue runs a rewriter per goroutine over a queue of documents, checks that no worker sees another's work, and says how much of the time went on building rewriters rather than on rewriting.

$ queue -workers 4 -items 400 -selectors 50 -size 1024
400 items of 1050 bytes, 4 workers, 50 selectors each
  cross-talk       none: every output equals the same document rewritten alone
  wall clock       11.9ms for the queue, 29.8µs per item across 4 workers
  build and close  6.3ms for the queue, 15.8µs per item (53%)
  allocations      495 per item, of which building and closing 415 (84%)
  work done        12620 elements rewritten across the queue
  advice           most of the time is construction: fewer selectors, or larger items, or both
  clock tick       41ns, fastest of 3 passes each

Two shares, because they answer different questions and one of them needs a clock: see "Why two queues and not two stopwatches" and "The figure that does not need a clock".

A lolhtml.Writer cannot be reused: Close ends it, and there is no reset. So a queue pays the cost of building one per item, and that cost is a function of the selector list rather than of the document - about 8 allocations and three quarters of a microsecond per registered selector, whether the document is empty or sixteen kilobytes.

Measured on an M3 Pro, one rewriter built and closed per document:

document      1 selector   10 selectors   50 selectors
nothing          1.7µs         8.2µs         38.4µs
30 bytes         2.3µs         8.6µs         38.4µs
1 KB            10.4µs        17.8µs         52.2µs
16 KB          141.4µs       153.4µs        252.9µs

Read down a column and the construction is a constant; read across a row and it is the whole story for small documents. With fifty selectors, a queue of documents under about sixteen kilobytes spends more time building rewriters than rewriting, and there is nothing to amortise it against: the parsed selectors belong to the Writer and cannot be shared with the next one.

How many workers ¶

Fewer than you would think, and the number is a property of the machine rather than of the library, so -scan measures it instead of guessing:

$ queue -scan -items 400 -selectors 50 -size 1024
workers   wall clock   items/sec   speedup
      1       36.2ms       11049      1.00x
      2       21.1ms       18957      1.72x
      4       12.1ms       33057      2.99x
      8       19.2ms       20833      1.88x
     12       20.7ms       19323      1.75x

Peak at four on a twelve-thread M3 Pro, and worse above it. A rewrite of a small document with a large rule set is mostly allocation - 406 allocations before a byte is written, with fifty selectors - and allocation-heavy work contends. The large-document case saturates instead of declining: 3.4x at four workers and the same at twelve. Either way the useful number is not the core count.

Why two queues and not two stopwatches ¶

The first version of this program timed each item's build and each item's total with time.Since and reported the mean. That does not work, for two independent reasons, and both of them were found by CI rather than here.

The first is that the thing being timed is a few microseconds long and the scheduler is not. One item that loses its core for a millisecond outweighs the other fifty-nine put together, and where the pause lands decides the answer: in the build, and the build looks like the whole cost; in the rewrite, and it looks free. Sixty 128-byte documents, one selector, on an M3 Pro with forty spinning processes for company - the same build, sixty times:

run   median build   95th   slowest   slowest over median
  1        1.708µs   21.5µs   41.5µs                  24x
  2        1.458µs    4.0µs   11.9µs                   8x
  3        4.125µs   28.4µs   92.1µs                  22x
  4        4.041µs   17.4µs   28.2µs                   7x
  5        1.875µs    9.4µs   29.8µs                  16x

A mean over those samples is mostly the slowest one. Over twenty runs the mean build share ranged from 0.16 to 0.45 while the median of the same samples held between 0.16 and 0.18. A CI run reported 0.64 for one selector against 0.60 for fifty, which is the ordering backwards.

The second reason is that a median does not save it. On the Windows runner every per-item figure came out as exactly zero: the clock's tick is coarser than an item, so sixty readings of a hundred microseconds each read zero, and the median of sixty zeros is zero. The mean had been hiding that - a sum of mostly-zero readings with the occasional tick in it is not zero, so it looked like a measurement. The program reports the tick it measured, because the number is a property of the platform and not of the library.

So there is no per-item stopwatch here at all. The queue is run twice: once doing the work, and once building a rewriter per item and closing it without writing the document, which is the cost that cannot be amortised. Both are whole-queue intervals of milliseconds, thousands of ticks even on a coarse clock, and the build share is the ratio of the two. Each is run three times and the fastest kept, because preemption only ever adds time.

Checked against the method it replaced, one worker on a quiet machine, and with the per-item stopwatch counting Close as part of the overhead so that both methods measure the same thing:

documents          selectors   two queues   per-item medians
400 x 1050 bytes          50        0.458              0.461
400 x 150 bytes           50        0.839              0.852
400 x 150 bytes            1        0.253              0.272
200 x 32 KB               50        0.027              0.028

The agreement is the point: the per-item method could get the right answer, it just could not be relied on to, and on a coarse clock it could not get one at all.

Two things the timed ratio does not say. It is a figure for the worker count it ran at - the overhead pass is pure allocation, which contends more than the mixed workload, so four workers put the same rule set at 0.51 where one worker puts it at 0.46 - and it is a ratio of totals, so it says nothing about the spread across items.

And two passes are not always separable. They are separate runs, so whichever goes second pays for the first one's rubbish, and the work pass allocates far more: on the project's arm64 runner the overhead pass came out *longer* than the work pass and the share was 1.33. The passes alternate which goes first and each starts from a collected heap now, which is the fix for the bias, and a share that still comes out at or above 1 is reported as two passes that could not be separated rather than printed. Outcome.Resolvable is the test, and the counted share below has none of this in it.

The figure that does not need a clock ¶

The report carries a second share, counted rather than timed: the mallocs an item cannot avoid, over the mallocs it makes in total. That number has no clock in it and no scheduler either. Eight runs of this program's own test against forty spinning processes:

                        allocation share   time share
200 x 128 B, 50 sel                0.963   0.831 to 0.909
200 x 128 B, 1 sel                 0.636   0.242 to 0.377
20 x 32 KB, 50 sel                 0.158   0.005 to 0.034

The allocation shares did not move at all across the eight runs. The time share for a 32 KB document moved sevenfold.

It is not the time share and does not pretend to be: allocation misses the per-byte parsing, which is most of a large document's time and almost none of its allocation, so it reads high wherever parsing dominates. What it does is rank - over six combinations of document size and rule set, measured, the two shares put them in exactly the same order:

document    selectors   allocation share   time share
150 bytes          50              0.963        0.825
1050 bytes         50              0.828        0.431
150 bytes           1              0.605        0.229
1050 bytes          1              0.243        0.042
32 KB              50              0.158        0.025
32 KB               1              0.012        0.002

So the tests assert on the counted share, which holds on every platform and at any load, and on the timed share only where the clock can resolve the intervals - and say which one they skipped rather than passing quietly. A reader wanting to know what their own queue costs should read the timed figure; a reader comparing two rule sets should read the counted one.

What a queue does not have to worry about ¶

Cross-talk, as long as the options are built per item. Each worker's handlers close over their own state, so nothing is shared: this program checks every output against the same document rewritten on its own, and a mismatch is a failure rather than a warning. What is not safe is building one lolhtml.Option at startup and handing it to every worker, because then the closure's state is shared - see the package documentation on reusing an Option.