(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science
   

COMPUTER SCIENCE COLLOQUIUM

Java 7’s Dual Pivot Quicksort --- Analysis and Engineering

Markus Nebel
Department of Computer Science
University of Kaiserslautern, Germany

Department of Mathematics and Computer Science
University of Southern Denmark

Tuesday, 05 March, 2013 at 14:15
IMADA's Seminar Room

ABSTRACT

Recently, a new Quicksort variant due to Yaroslavskiy was chosen as standard sorting method for Oracle’s Java 7 runtime library. The decision for the change was based on empirical studies showing that on average, the new algorithm is faster than the formerly used classic Quicksort. Surprisingly, the improvement was achieved by using a dual pivot approach, an idea that was considered not promising by several theoretical studies in the past. In this talk, we identify the reason for this unexpected success. Moreover, we present the first precise average case analysis of the new algorithm showing e.g. that a random permutation of length n is sorted using 1.9n ln n - 2.46n + O(ln n) key comparisons and 0.6n ln n + 0.08n + O(ln n) swaps.

Our analysis reveals a highly asymmetric nature of the algorithm. This suggest that asymmetric pivot choices are preferable to symmetric ones. From a theoretical point of view, this should allow us to improve on the current implementation in Oracle’s Java 7 runtime library. We present results derived by means of our tool MaLiJAn to confirm this for asymptotic combinatorial cost measures such as the total number of executed instructions (Java bytecodes). However, the observed running times show converse behavior. With the support of data provided by MaLiJAn we are able to identify the profiling capabilities of Oracle’s just-in-time compiler to be responsible for this unexpected outcome.

Host:


SDU HOME | IMADA HOME | Previous Page
Daniel Merkle