English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  How Branch Mispredictions Affect Quicksort

Kaligosi, K., & Sanders, P. (2006). How Branch Mispredictions Affect Quicksort. In Algorithms - ESA 2006, 14th Annual European Symposium (pp. 780-791). Berlin, Germany: Springer.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Kaligosi, Kanela1, Author           
Sanders, Peter1, Author           
Azar, Yossi, Editor
Erlebach, Thomas, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2007-03-122006
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 314360
Other: Local-ID: C1256428004B93B8-9F331DF0CA804105C1257296005020FB-Kaligosi2006a
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Zürich, Switzerland
Start-/End Date: 2006-09-11

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms - ESA 2006, 14th Annual European Symposium
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 780 - 791 Identifier: ISBN: 3-540-38875-3

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 4168 Sequence Number: - Start / End Page: - Identifier: -