[DISPATCH-1372] alloc_pool intrusive linked list can be replaced by a linked stack

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Implemented
• Affects Version/s: 1.8.0
• Fix Version/s: 1.9.0
• Component/s: Routing Engine
• Assignee: Unassigned
• Reporter: Francesco Nigro
• Created: 21/Jun/19 08:57
• Updated: 19/Sep/19 21:04
• Resolved: 17/Jul/19 16:07

Description

alloc_pool is currently using a intrusive linked list approach to reduce the need of external data structures to hold data, saving expensive 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.

 

Issue Links

• links to: GitHub Pull Request #525