ACM Journal of Experimental Algorithmics · 2007 · 43 citations · 20 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureData StructuresParallel ComputingCachingCaching StrategiesData Locality OptimizationMemory HierarchyMemory Hierarchy OptimizationString AlgorithmsCache OptimizationInternal SortingMemory Access LatencyMemory Access LocalityMemory LocalityQuicksortSortingTrie Data Structures
Burstsort is a cache-oriented sorting technique that uses a dynamic trie to efficiently divide large sets of string keys into related subsets small enough to sort in cache. In our original burstsort, string keys sharing a common prefix were managed via a bucket of pointers represented as a list or array; this approach was found to be up to twice as fast as the previous best string sorts, mostly because of a sharp reduction in out-of-cache references. In this paper, we introduce C-burstsort, which copies the unexamined tail of each key to the bucket and discards the original key to improve data locality. On both Intel and PowerPC architectures, and on a wide range of string types, we show that sorting is typically twice as fast as our original burstsort and four to five times faster than multikey quicksort and previous radixsorts. A variant that copies both suffixes and record pointers to buckets, CP-burstsort, uses more memory, but provides stable sorting. In current computers, where performance is limited by memory access latencies, these new algorithms can dramatically reduce the time needed for internal sorting of large numbers of strings.
20
Computer architecture: a quantitative approach
Martin Shute · Microelectronics Journal · 1993 · 3.4K citations
C. A. R. Hoare · The Computer Journal · 1962 · 755 citations · Full text
C. A. R. Hoare · Communications of the ACM · 1961 · 539 citations
Fast algorithms for sorting and searching strings
Jon Bentley, Robert Sedgewick · 1997 · 399 citations