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

    • Improvement
    • Status: Closed
    • Major
    • Resolution: Implemented
    • 1.8.0
    • 1.9.0
    • Routing Engine
    • 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. DOOM-3-BFG-Technical-Note.pdf
          204 kB
          Francesco Nigro
        2. linked_list_misses.svg
          1.72 MB
          Francesco Nigro
        3. stack_list_misses.svg
          1.76 MB
          Francesco Nigro
        4. image-2019-06-21-11-08-17-015.png
          63 kB
          Francesco Nigro
        5. image-2019-06-21-11-09-02-228.png
          64 kB
          Francesco Nigro

        Issue Links

          Activity

            People

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

              Dates

                Created:
                Updated:
                Resolved: