Re: [RFC PATCH v2] Introduce Hierarchical Per-CPU Counters

[Matthew Wilcox]

On Tue, Apr 08, 2025 at 09:37:18AM -0700, Christoph Lameter (Ampere) wrote:
> > The hierarchical per-CPU counters propagate a sum approximation through
> > a binary tree. When reaching the batch size, the carry is propagated
> > through a binary tree which consists of log2(nr_cpu_ids) levels. The
> > batch size for each level is twice the batch size of the prior level.
> 
> A binary tree? Could we do this N-way? Otherwise the tree will be 8 levels
> on a 512 cpu machine. Given the inflation of the number of cpus this
> scheme better work up to 8K cpus.

I find that a fan-out somewhere between 8 and 16 works well in practice.
log16(512) gives a 3 level tree as does a log8 tree.  log16(8192) is a 4
level tree whereas log8(8192) is a 5 level tree.  Not a big difference
either way.

Somebody was trying to persuade me that a new tree type that maintained
additional information at each level of the tree to make some operations
log(log(N)) would be a better idea than a B-tree that is log(N).  I
countered that a wider tree made the argument unsound at any size tree
up to 100k.  And we don't tend to have _that_ many objects in a
data structure inside the kernel.

ceil(log14(100,000)) = 5
ceil(log2(log2(100,000))) = 5

at a million, there's actually a gap, 6 vs 5.  But constant factors
become a much larger factor than scalability arguments at that point.