Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Kaligosi, Kanela
Sanders, Peter

dblp
dblp

Not MPG Author(s):

Sanders, Peter

Editor(s):

Azar, Yossi
Erlebach, Thomas

dblp
dblp

Not MPII Editor(s):

Azar, Yossi
Erlebach, Thomas

BibTeX cite key*:

Kaligosi2006a

Title, Booktitle

Title*:

How Branch Mispredictions Affect Quicksort

Booktitle*:

Algorithms - ESA 2006, 14th Annual European Symposium

Event, URLs

URL of the conference:

http://algo06.inf.ethz.ch/esa

URL for downloading the paper:

http://www.springerlink.com/content/t072587734005lvh/fulltext.pdf

Event Address*:

Zürich, Switzerland

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

11 September 2006

Event End Date:

13 September 2006

Publisher

Name*:

Springer

URL:

http://www.springer.com/west/home/computer/lncs?SGWID=4-164-0-0-0&SHORTCUT=www.springer.com/lncs/

Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

4168

Number:


Month:


Pages:

780-791

Year*:

2006

VG Wort Pages:


ISBN/ISSN:

3-540-38875-3

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:


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.

URL for the Abstract:

http://dx.doi.org/10.1007/11841036_69



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Kaligosi2006a,
AUTHOR = {Kaligosi, Kanela and Sanders, Peter},
EDITOR = {Azar, Yossi and Erlebach, Thomas},
TITLE = {How Branch Mispredictions Affect Quicksort},
BOOKTITLE = {Algorithms - ESA 2006, 14th Annual European Symposium},
PUBLISHER = {Springer},
YEAR = {2006},
VOLUME = {4168},
PAGES = {780--791},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Z{\"u}rich, Switzerland},
ISBN = {3-540-38875-3},
}


Entry last modified by Christine Kiesel, 03/12/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Kanela Kaligosi
Created
03/06/2007 03:35:13 PM
Revision
1.
0.


Editor
Christine Kiesel
Kanela Kaligosi


Edit Date
12.03.2007 14:22:53
03/06/2007 03:35:13 PM


Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section