Francesco Nigro created DISPATCH-1372:
-----------------------------------------
Summary: alloc_pool intrusive linked list can be replaced by a
linked stack
Key: DISPATCH-1372
URL: https://issues.apache.org/jira/browse/DISPATCH-1372
Project: Qpid Dispatch
Issue Type: Improvement
Components: Routing Engine
Affects Versions: 1.8.0
Reporter: Francesco Nigro
Attachments: DOOM-3-BFG-Technical-Note.pdf, linked_list_misses.svg,
stack_list_misses.svg
alloc_pool is currently using a intrusive linked list approach to reduce the
need of external data structure and pointer chasing, but on modern
architectures the data dependency between a current node and next/prev prevent
the CPU prefetcher to stream nodes speculatively.
There are different approaches that could benefit of prefetcing, but need to
decouple the data stored from its container eg a linked stack.
A linked stack is composed by doubly-linked chunks (allocated lazily) that make
possible for the CPU to prefetch next/prev pointers given that those are
already contained in the current chunk (if any).
Although it seems counter-intuitive (given that introduce 1 more hop to reach
the data), such data-structure is much more cache-friendly on modern
architectures: I will attach some cache misses analysis to show it.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
