Lean programs, branch mispredictions, and sorting

Amr Ahmed Abd Elmoneim Elmasry; Jyrki Katajainen

doi:10.1007/978-3-642-30347-0_14

Lean programs, branch mispredictions, and sorting

Amr Ahmed Abd Elmoneim Elmasry, Jyrki Katajainen

Department of Computer Science

6 Citations (Scopus)

Abstract

According to a folk theorem, every program can be transformed into a program that produces the same output and only has one loop. We generalize this to a form where the resulting program has one loop and no other branches than the one associated with the loop control. For this branch, branch prediction is easy even for a static branch predictor. If the original program is of length κ, measured in the number of assembly-language instructions, and runs in t(n) time for an input of size n, the transformed program is of length O(κ) and runs in O(κt(n)) time. Normally sorting programs are short, but still κ may be too large for practical purposes. Therefore, we provide more efficient hand-tailored heapsort and mergesort programs. Our programs retain most features of the original programs-e.g. they perform the same number of element comparisons-and they induce O(1) branch mispredictions. On computers where branch mispredictions were expensive, some of our programs were, for integer data and small instances, faster than the counterparts in the GNU implementation of the C++ standard library.

Original language	English
Title of host publication	Fun with Algorithms : 6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012. Proceedings
Editors	Evangelos Kranakis, Danny Krizanc, Flaminia Luccio
Number of pages	12
Publisher	Springer
Publication date	2012
Pages	119-130
ISBN (Print)	978-3-642-30346-3
ISBN (Electronic)	978-3-642-30347-0
DOIs	https://doi.org/10.1007/978-3-642-30347-0_14
Publication status	Published - 2012
Event	The Sixth International conference on Fun with Algorithms - Venice, Italy Duration: 4 Jun 2012 → 6 Jun 2012 Conference number: 6

Conference

Conference	The Sixth International conference on Fun with Algorithms
Number	6
Country/Territory	Italy
City	Venice
Period	04/06/2012 → 06/06/2012

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

Access to Document

10.1007/978-3-642-30347-0_14

Cite this

Lean programs, branch mispredictions, and sorting. / Elmasry, Amr Ahmed Abd Elmoneim; Katajainen, Jyrki.

Fun with Algorithms: 6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012. Proceedings. ed. / Evangelos Kranakis; Danny Krizanc; Flaminia Luccio. Springer, 2012. p. 119-130 (Lecture notes in computer science, Vol. 7288).

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

Elmasry, AAAE & Katajainen, J 2012, Lean programs, branch mispredictions, and sorting. in E Kranakis, D Krizanc & F Luccio (eds), Fun with Algorithms: 6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012. Proceedings. Springer, Lecture notes in computer science, vol. 7288, pp. 119-130, The Sixth International conference on Fun with Algorithms, Venice, Italy, 04/06/2012. https://doi.org/10.1007/978-3-642-30347-0_14

@inproceedings{3639171c305c425e992b9d7d1968099c,

title = "Lean programs, branch mispredictions, and sorting",

abstract = "According to a folk theorem, every program can be transformed into a program that produces the same output and only has one loop. We generalize this to a form where the resulting program has one loop and no other branches than the one associated with the loop control. For this branch, branch prediction is easy even for a static branch predictor. If the original program is of length κ, measured in the number of assembly-language instructions, and runs in t(n) time for an input of size n, the transformed program is of length O(κ) and runs in O(κt(n)) time. Normally sorting programs are short, but still κ may be too large for practical purposes. Therefore, we provide more efficient hand-tailored heapsort and mergesort programs. Our programs retain most features of the original programs-e.g. they perform the same number of element comparisons-and they induce O(1) branch mispredictions. On computers where branch mispredictions were expensive, some of our programs were, for integer data and small instances, faster than the counterparts in the GNU implementation of the C++ standard library.",

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

year = "2012",

doi = "10.1007/978-3-642-30347-0_14",

language = "English",

isbn = "978-3-642-30346-3",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "119--130",

editor = "Evangelos Kranakis and Danny Krizanc and Flaminia Luccio",

booktitle = "Fun with Algorithms",

note = "The Sixth International conference on Fun with Algorithms ; Conference date: 04-06-2012 Through 06-06-2012",

}

TY - GEN

T1 - Lean programs, branch mispredictions, and sorting

AU - Elmasry, Amr Ahmed Abd Elmoneim

AU - Katajainen, Jyrki

N1 - Conference code: 6

PY - 2012

Y1 - 2012

N2 - According to a folk theorem, every program can be transformed into a program that produces the same output and only has one loop. We generalize this to a form where the resulting program has one loop and no other branches than the one associated with the loop control. For this branch, branch prediction is easy even for a static branch predictor. If the original program is of length κ, measured in the number of assembly-language instructions, and runs in t(n) time for an input of size n, the transformed program is of length O(κ) and runs in O(κt(n)) time. Normally sorting programs are short, but still κ may be too large for practical purposes. Therefore, we provide more efficient hand-tailored heapsort and mergesort programs. Our programs retain most features of the original programs-e.g. they perform the same number of element comparisons-and they induce O(1) branch mispredictions. On computers where branch mispredictions were expensive, some of our programs were, for integer data and small instances, faster than the counterparts in the GNU implementation of the C++ standard library.

AB - According to a folk theorem, every program can be transformed into a program that produces the same output and only has one loop. We generalize this to a form where the resulting program has one loop and no other branches than the one associated with the loop control. For this branch, branch prediction is easy even for a static branch predictor. If the original program is of length κ, measured in the number of assembly-language instructions, and runs in t(n) time for an input of size n, the transformed program is of length O(κ) and runs in O(κt(n)) time. Normally sorting programs are short, but still κ may be too large for practical purposes. Therefore, we provide more efficient hand-tailored heapsort and mergesort programs. Our programs retain most features of the original programs-e.g. they perform the same number of element comparisons-and they induce O(1) branch mispredictions. On computers where branch mispredictions were expensive, some of our programs were, for integer data and small instances, faster than the counterparts in the GNU implementation of the C++ standard library.

U2 - 10.1007/978-3-642-30347-0_14

DO - 10.1007/978-3-642-30347-0_14

M3 - Article in proceedings

SN - 978-3-642-30346-3

T3 - Lecture notes in computer science

SP - 119

EP - 130

BT - Fun with Algorithms

A2 - Kranakis, Evangelos

A2 - Krizanc, Danny

A2 - Luccio, Flaminia

PB - Springer

T2 - The Sixth International conference on Fun with Algorithms

Y2 - 4 June 2012 through 6 June 2012

ER -

Lean programs, branch mispredictions, and sorting

Abstract

Conference

Access to Document

Fingerprint

Cite this