Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn

Wild, Sebastian ORCID: 0000-0002-6061-9177, Nebel, Markus, Reitzig, Raphael and Laube, Ulrich
(2013) Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn. .

[img] Text
wild-nebel-reitzig-laube-2013.pdf - Author Accepted Manuscript

Download (4MB) | Preview


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.

Item Type: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 21 Oct 2019 14:17
Last Modified: 19 Jan 2023 00:21
DOI: 10.1137/1.9781611972931.5
Related URLs: