| ID:
314360.0,
MPI für Informatik / Algorithms and Complexity Group |
| How Branch Mispredictions Affect Quicksort |
| Authors: | Kaligosi, Kanela; Sanders, Peter |
| Editors: | Azar, Yossi; Erlebach, Thomas |
| Language: | English |
| Publisher: | Springer |
| Place of Publication: | Berlin, Germany |
| Date of Publication (YYYY-MM-DD): | 2006 |
| Title of Proceedings: | Algorithms - ESA 2006, 14th Annual European Symposium |
| Start Page: | 780 |
| End Page: | 791 |
| Title of Series: | Lecture Notes in Computer Science |
| Place of Conference/Meeting: | Zürich, Switzerland |
(Start) Date of Conference/Meeting
(YYYY-MM-DD): | 2006-09-11 |
| Audience: | Experts Only |
| Intended Educational Use: | No |
| Abstract / Description: | We explain the counterintuitive observation that finding “good” pivots (close
to the median of the array to be partitioned) may not improve performance of
quicksort. Indeed, an intentionally skewed pivot improves performance. The
reason is that while the instruction count decreases with the quality of the
pivot, the likelihood that the direction of a branch is mispredicted also goes
up. We analyze the effect of simple branch prediction schemes and measure the
effects on real hardware. |
| Last Change of the Resource (YYYY-MM-DD): | 2007-03-12 |
| External Publication Status: | published |
| Document Type: | Conference-Paper |
| Communicated by: | Kurt Mehlhorn |
| Affiliations: | MPI für Informatik/Algorithms and Complexity Group
|
| Identifiers: | LOCALID:C1256428004B93B8-9F331DF0CA804105C1257296005020FB-...
ISBN:3-540-38875-3 |
|
Advanced
