qpid-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (DISPATCH-1372) alloc_pool intrusive linked list can be replaced by a linked stack
Date Tue, 02 Jul 2019 06:53:00 GMT

    [ https://issues.apache.org/jira/browse/DISPATCH-1372?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16876726#comment-16876726

ASF GitHub Bot commented on DISPATCH-1372:

franz1981 commented on issue #525: DISPATCH-1372 alloc_pool intrusive linked list can be replaced
by a linked stack
URL: https://github.com/apache/qpid-dispatch/pull/525#issuecomment-507545028
   @kgiusti I've just squashed the commit with the batch move between stacks ie `unordered_move_stack`.

   The benchmarks shows that it delivers a small (but measurable) speedup over the original
version, so IMO it worths to be used. 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:

> 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

To unsubscribe, e-mail: dev-unsubscribe@qpid.apache.org
For additional commands, e-mail: dev-help@qpid.apache.org

View raw message