[PATCH] stack: introduce pile

[Bruce Richardson]

On Wed, Aug 12, 2026 at 06:01:31PM +0200, Morten Brørup wrote:
> > From: Bruce Richardson [mailto:bruce.richardson at intel.com]
> > Sent: Wednesday, 12 August 2026 16.34
> > 
> > On Wed, Aug 12, 2026 at 01:47:56PM +0000, Morten Brørup wrote:
> > > Added a new high-performance lock-free "pile", using the Stack API.
> > > The pile behaves roughly like a stack, but is not strictly LIFO.
> > >
> > > The pile is optimized for pushing/popping bulks of objects, which
> > > it does significantly faster than the lock-free stack.
> > >
> > > Pushing/popping a number of objects not divisible by the compile time
> > > configurable bulk size is handled gracefully, but not as fast as
> > > complete bulks.
> > >
> > > Performance examples, stack_pile_perf_autotest vs. stack_lf_autotest:
> > >
> > > On a single core, pushing/popping 1 or 8 objects is similar speed.
> > > On a single core, pushing/popping 32 objects is 2x faster.
> > > On a single core, pushing/popping 512 objects is 10x faster.
> > >
> > > On four cores, pushing/popping 1, 8 or 32 objects is slightly faster.
> > > On four cores, pushing/popping 512 objects is 4x faster.
> > >
> > How does it differ, or what are the benefits vs the standard stack.
> 
> The standard stack is generally faster on single core.
> Only pushing/popping 512 objects is slightly faster than the standard stack, but maybe the standard stack could be microoptimized to fix that.
> 
> On four cores, it is slightly faster than the standard stack with multiple objects:
> 
> stack_perf_autotest
> Average cycles per object push/pop (bulk size: 1): 3806.65
> Average cycles per object push/pop (bulk size: 8): 554.77
> Average cycles per object push/pop (bulk size: 32): 144.70
> Average cycles per object push/pop (bulk size: 512): 13.52
> 
> stack_pile_perf_autotest
> Average cycles per object push/pop (bulk size: 1): 4012.39
> Average cycles per object push/pop (bulk size: 8): 459.82
> Average cycles per object push/pop (bulk size: 32): 122.40
> Average cycles per object push/pop (bulk size: 512): 9.60
> 
> 
> > The
> > LF
> > stack I'd view as a strange edge case, since even with the standard
> > MP/MC
> > ring mempool driver you still have atomics on the fast-path and you
> > will
> > still get stalls if a thread gets context switched out in the middle of
> > a
> > mempool operation.
> 
> Yes, the no-stall guarantee is a key benefit of the lock-free stack and the pile.
> 

Ok, that is good. Next question, rather than adding a whole new mempool
driver implementation, can we use this to replace one of the existing stack
implementations? Do we need to have so many mempool stack drivers
generally?

/Bruce