swMATH ID: 30175
Software Authors: Wild, Sebastian; Nebel, Markus; Reitzig, Raphael; Laube, Ulrich
Description: Engineering Java 7’s dual pivot quicksort using MaLiJAn. Recent results on Java 7’s dual pivot quicksort have revealed its highly asymmetric nature. These insights suggest that asymmetric pivot choices are preferable to symmetric ones for this quicksort variant. From a theoretical point of view, this should allow us to improve on the current implementation in Oracle’s Java 7 runtime library. In this paper, we use our new tool MaLiJAn to confirm this asymptotically for combinatorial cost measures such as the total number of executed instructions. 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.
Homepage: http://wwwagak.cs.uni-kl.de/home/forschung/malijan.html
Related Software: Find; Quicksort
Cited in: 3 Publications

Cited in 1 Serial

3 Algorithmica

Citations by Year