Uploaded image for project: 'Qpid Dispatch'
  1. Qpid Dispatch
  2. DISPATCH-1372

alloc_pool intrusive linked list can be replaced by a linked stack

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Implemented
    • Affects Version/s: 1.8.0
    • Fix Version/s: 1.9.0
    • Component/s: Routing Engine
    • Labels:
      None

      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.

       

        Attachments

        1. image-2019-06-21-11-09-02-228.png
          64 kB
          Francesco Nigro
        2. image-2019-06-21-11-08-17-015.png
          63 kB
          Francesco Nigro
        3. stack_list_misses.svg
          1.76 MB
          Francesco Nigro
        4. linked_list_misses.svg
          1.72 MB
          Francesco Nigro
        5. DOOM-3-BFG-Technical-Note.pdf
          204 kB
          Francesco Nigro

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                nigro.fra@gmail.com Francesco Nigro
              • Votes:
                0 Vote for this issue
                Watchers:
                3 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: