Branch mispredictions don’t affect mergesort

Amr Ahmed Abd Elmoneim Elmasry; Jyrki Katajainen; Max Stenmark

doi:10.1007/978-3-642-30850-5_15

Branch mispredictions don’t affect mergesort

Amr Ahmed Abd Elmoneim Elmasry, Jyrki Katajainen, Max Stenmark

Department of Computer Science

9 Citations (Scopus)

Abstract

In quicksort, due to branch mispredictions, a skewed pivot-selection strategy can lead to a better performance than the exact-median pivot-selection strategy, even if the exact median is given for free. In this paper we investigate the effect of branch mispredictions on the behaviour of mergesort. By decoupling element comparisons from branches, we can avoid most negative effects caused by branch mispredictions. When sorting a sequence of n elements, our fastest version of mergesort performs n log ₂ n + O(n) element comparisons and induces at most O(n) branch mispredictions. We also describe an in-situ version of mergesort that provides the same bounds, but uses only O(log ₂ n) words of extra memory. In our test computers, when sorting integer data, mergesort was the fastest sorting method, then came quicksort, and in-situ mergesort was the slowest of the three. We did a similar kind of decoupling for quicksort, but the transformation made it slower.

Original language	English
Title of host publication	Experimental Algorithms : 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedings
Editors	Ralf Klasing
Number of pages	12
Publisher	Springer
Publication date	2012
Pages	160-171
ISBN (Print)	978-3-642-30849-9
ISBN (Electronic)	978-3-642-30850-5
DOIs	https://doi.org/10.1007/978-3-642-30850-5_15
Publication status	Published - 2012
Event	11th International Symposium on Experimental Algorithms - Bordeaux, France Duration: 7 Jun 2012 → 9 Jun 2012 Conference number: 11

Conference

Conference	11th International Symposium on Experimental Algorithms
Number	11
Country/Territory	France
City	Bordeaux
Period	07/06/2012 → 09/06/2012

Series	Lecture notes in computer science
Volume	7276
ISSN	0302-9743

Access to Document

10.1007/978-3-642-30850-5_15

Cite this

Branch mispredictions don’t affect mergesort. / Elmasry, Amr Ahmed Abd Elmoneim; Katajainen, Jyrki; Stenmark, Max.

Experimental Algorithms: 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedings. ed. / Ralf Klasing. Springer, 2012. p. 160-171 (Lecture notes in computer science, Vol. 7276).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Elmasry, AAAE, Katajainen, J & Stenmark, M 2012, Branch mispredictions don’t affect mergesort. in R Klasing (ed.), Experimental Algorithms: 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedings. Springer, Lecture notes in computer science, vol. 7276, pp. 160-171, 11th International Symposium on Experimental Algorithms, Bordeaux, France, 07/06/2012. https://doi.org/10.1007/978-3-642-30850-5_15

@inproceedings{bd9a6b305f724f3993e98e3fe8388795,

title = "Branch mispredictions don{\textquoteright}t affect mergesort",

abstract = "In quicksort, due to branch mispredictions, a skewed pivot-selection strategy can lead to a better performance than the exact-median pivot-selection strategy, even if the exact median is given for free. In this paper we investigate the effect of branch mispredictions on the behaviour of mergesort. By decoupling element comparisons from branches, we can avoid most negative effects caused by branch mispredictions. When sorting a sequence of n elements, our fastest version of mergesort performs n log 2 n + O(n) element comparisons and induces at most O(n) branch mispredictions. We also describe an in-situ version of mergesort that provides the same bounds, but uses only O(log 2 n) words of extra memory. In our test computers, when sorting integer data, mergesort was the fastest sorting method, then came quicksort, and in-situ mergesort was the slowest of the three. We did a similar kind of decoupling for quicksort, but the transformation made it slower.",

author = "Elmasry, {Amr Ahmed Abd Elmoneim} and Jyrki Katajainen and Max Stenmark",

year = "2012",

doi = "10.1007/978-3-642-30850-5_15",

language = "English",

isbn = "978-3-642-30849-9",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "160--171",

editor = "Ralf Klasing",

booktitle = "Experimental Algorithms",

note = "11th International Symposium on Experimental Algorithms ; Conference date: 07-06-2012 Through 09-06-2012",

}

TY - GEN

T1 - Branch mispredictions don’t affect mergesort

AU - Elmasry, Amr Ahmed Abd Elmoneim

AU - Katajainen, Jyrki

AU - Stenmark, Max

N1 - Conference code: 11

PY - 2012

Y1 - 2012

N2 - In quicksort, due to branch mispredictions, a skewed pivot-selection strategy can lead to a better performance than the exact-median pivot-selection strategy, even if the exact median is given for free. In this paper we investigate the effect of branch mispredictions on the behaviour of mergesort. By decoupling element comparisons from branches, we can avoid most negative effects caused by branch mispredictions. When sorting a sequence of n elements, our fastest version of mergesort performs n log 2 n + O(n) element comparisons and induces at most O(n) branch mispredictions. We also describe an in-situ version of mergesort that provides the same bounds, but uses only O(log 2 n) words of extra memory. In our test computers, when sorting integer data, mergesort was the fastest sorting method, then came quicksort, and in-situ mergesort was the slowest of the three. We did a similar kind of decoupling for quicksort, but the transformation made it slower.

AB - In quicksort, due to branch mispredictions, a skewed pivot-selection strategy can lead to a better performance than the exact-median pivot-selection strategy, even if the exact median is given for free. In this paper we investigate the effect of branch mispredictions on the behaviour of mergesort. By decoupling element comparisons from branches, we can avoid most negative effects caused by branch mispredictions. When sorting a sequence of n elements, our fastest version of mergesort performs n log 2 n + O(n) element comparisons and induces at most O(n) branch mispredictions. We also describe an in-situ version of mergesort that provides the same bounds, but uses only O(log 2 n) words of extra memory. In our test computers, when sorting integer data, mergesort was the fastest sorting method, then came quicksort, and in-situ mergesort was the slowest of the three. We did a similar kind of decoupling for quicksort, but the transformation made it slower.

U2 - 10.1007/978-3-642-30850-5_15

DO - 10.1007/978-3-642-30850-5_15

M3 - Article in proceedings

SN - 978-3-642-30849-9

T3 - Lecture notes in computer science

SP - 160

EP - 171

BT - Experimental Algorithms

A2 - Klasing, Ralf

PB - Springer

T2 - 11th International Symposium on Experimental Algorithms

Y2 - 7 June 2012 through 9 June 2012

ER -

Branch mispredictions don’t affect mergesort

Abstract

Conference

Access to Document

Fingerprint

Cite this