The Influence of Caches on the Performance of Sorting Export

@inproceedings{citeulike:573222, abstract = {We investigate the effect that caches have on the performance of sorting algorithms both experimentally and analytically. To address the performance problems that high cache miss penalties introduce we restructure heapsort, mergesort and quicksort in order to improve their cache locality. For all three algorithms the improvement in cache performance leads to a reduction in total execution time. We also investigate the performance of radix sort. Despite the extremely low instruction count...}, author = {Lamarca and Ladner}, booktitle = {SODA: {ACM}-{SIAM} Symposium on Discrete Algorithms (A Conference on Theoretical and Experimental Analysis of Discrete Algorithms)}, citeulike-article-id = {573222}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.1153}, keywords = {algorithm, sorting}, posted-at = {2006-04-02 13:58:02}, priority = {3}, title = {The Influence of Caches on the Performance of Sorting}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.1153}, year = {1997} }

TY - CONF ID - citeulike:573222 L3 - citeulike-article-id:573222 N2 - We investigate the effect that caches have on the performance of sorting algorithms both experimentally and analytically. To address the performance problems that high cache miss penalties introduce we restructure heapsort, mergesort and quicksort in order to improve their cache locality. For all three algorithms the improvement in cache performance leads to a reduction in total execution time. We also investigate the performance of radix sort. Despite the extremely low instruction count... TI - The Influence of Caches on the Performance of Sorting T2 - SODA: {ACM}-{SIAM} Symposium on Discrete Algorithms (A Conference on Theoretical and Experimental Analysis of Discrete Algorithms) KW - algorithm KW - sorting AU - Lamarca AU - Ladner PY - 1997/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.1153 ER -