You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@qpid.apache.org by "Francesco Nigro (JIRA)" <ji...@apache.org> on 2019/06/21 09:14:00 UTC
[jira] [Commented] (DISPATCH-1372) alloc_pool intrusive linked list
can be replaced by a linked stack
[ https://issues.apache.org/jira/browse/DISPATCH-1372?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16869312#comment-16869312 ]
Francesco Nigro commented on DISPATCH-1372:
-------------------------------------------
Below the flamegraph of a 1 pair + router cache-misses events.
On master with the original allocator:
!image-2019-06-21-11-08-17-015.png!
On masterbut with a linked stack allocator:
!image-2019-06-21-11-09-02-228.png!
In violet there are the calls to qd_alloc.
To explain the improvement, the relative samples for qd_buffer in _qd_buffer_list_clone are:
master linked list: 277 samples
master linked stack: 54 samples
The overall cache misses on the router_core_thread instead are:
master linked list: 1817 samples
master linked stack: 1488 samples
The improvement has yet to be verified under load with more clients, but seems promising.
> 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
> Priority: Major
> Attachments: DOOM-3-BFG-Technical-Note.pdf, image-2019-06-21-11-08-17-015.png, image-2019-06-21-11-09-02-228.png, 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 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.
>
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@qpid.apache.org
For additional commands, e-mail: dev-help@qpid.apache.org