7 ms·

I think in order to really reap the benefits of this you'll want to actually reorganize the in-memory layout of the trees in order to make sure all elements nee

by flgr 9y ago

I think in order to really reap the benefits of this you'll want to actually reorganize the in-memory layout of the trees in order to make sure all elements needed for the comparison end up in the same cache line. I haven't been following this closely, but the last time I checked scatter-gather loads were really really slow. Chapter 3.3 from page 27 (PDF page 43) on of this be interesting: https://www.researchgate.net/profile/Florian_Gross/publication/275971053_Index_Search_Algorithms_for_Databases_and_Modern_CPUs/links/554cffca0cf29f836c9cd539.pdf https://www.researchgate.net/profile/Florian_Gross/publicati... Also contains a survey of some other related data structures and algorithms.

0xfaded 9y ago
Thank you, scatter-gather was the google term I was looking for, though I couldn't immediately find any architectures that implement a vector scatter-gather. Are you aware of any?
- wbl 9y ago
  The Cray absolutely did. How else do you do sparse matrix multiply?
- pandaman 9y ago
  Not sure what could be a scalar scatter/gather, but NV and AMD GPUs do the vector one (you can read write n values from n offsets with a single instruction).
cperciva 9y ago
As the saying goes, "memory is the new disk". Data structures like B-trees which were designed to improve the performance of data accesses from disk are now useful for improving the performance of algorithms in memory.
- delhanty 9y ago
  Does anybody have any data on whether external sorting [1] is the way to go these days for CPU based sorts? That is, use quicksort for chunks up to the size of the L1/L2/L3 cache (depending on benchmarking) and then mergesort the chunks. [1] https://en.wikipedia.org/wiki/External_sorting https://en.wikipedia.org/wiki/External_sorting
  - cperciva 9y ago
    I don't have any data readily available, but it's generally understood that you want a cache-aware sort, yes. Usually I see people opt for samplesort rather than sorting chunks and merging, though.
    - delhanty 9y ago
      Thanks for your opinion. I did not know about samplesort - found it on Wikipedia.
  - adrianN 9y ago
    You can have a look at the best sorting algorithms (for various definitions of "best") here http://sortbenchmark.org/ http://sortbenchmark.org/
    - cperciva 9y ago
      That's for big sorts. The question here is about sorting with a single CPU.
      - adrianN 9y ago
        Look at the Joule category.

by flgr 9y ago

0xfaded 9y ago

Thank you, scatter-gather was the google term I was looking for, though I couldn't immediately find any architectures that implement a vector scatter-gather. Are you aware of any?

wbl 9y ago
The Cray absolutely did. How else do you do sparse matrix multiply?
pandaman 9y ago
Not sure what could be a scalar scatter/gather, but NV and AMD GPUs do the vector one (you can read write n values from n offsets with a single instruction).

cperciva 9y ago

As the saying goes, "memory is the new disk". Data structures like B-trees which were designed to improve the performance of data accesses from disk are now useful for improving the performance of algorithms in memory.

delhanty 9y ago
Does anybody have any data on whether external sorting [1] is the way to go these days for CPU based sorts? That is, use quicksort for chunks up to the size of the L1/L2/L3 cache (depending on benchmarking) and then mergesort the chunks. [1] https://en.wikipedia.org/wiki/External_sorting https://en.wikipedia.org/wiki/External_sorting
- cperciva 9y ago
  I don't have any data readily available, but it's generally understood that you want a cache-aware sort, yes. Usually I see people opt for samplesort rather than sorting chunks and merging, though.
  - delhanty 9y ago
    Thanks for your opinion. I did not know about samplesort - found it on Wikipedia.
- adrianN 9y ago
  You can have a look at the best sorting algorithms (for various definitions of "best") here http://sortbenchmark.org/ http://sortbenchmark.org/
  - cperciva 9y ago
    That's for big sorts. The question here is about sorting with a single CPU.
    - adrianN 9y ago
      Look at the Joule category.