[PATCH] stack: introduce pile

[Morten Brørup]

> From: Bruce Richardson [mailto:bruce.richardson at intel.com]
> Sent: Wednesday, 12 August 2026 18.16
> 
> 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?

We could consider replacing the lock-free stack implementation by the pile implementation, but the pile is not strictly LIFO, so it seems risky.

For a mempool holding mbufs, there's probably no harm in the difference.
But for a mempool holding some other object type, it could be harmful. I don't know.
IMO, not worth the risk.

Good idea, though!
I'm usually in favor of cleaning up. Just not this one. :-)