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.
