Software - Articles

ArrayDeque Performance Results

Herman van Hövell tot Westerflier replaced the Stack used in the iterative code with an ArrayDeque, introduced in Java 6. As many people, including Herman, have pointed out, Stack is a synchronized data structure and, as such, will incur an unnecessary performance penalty. Herman's results are posted below. The main result is that the fast iterative version comes within roughly 130% of the hardcore version, representing a significant tightening compared to the Stack.

Table 1: ArrayDeque Performance Results
Solution Time (ns) Heap (bytes)
Elegant Recursion 9,904,119 1,107,961
Fast Recursion 3,848,919 0
Elegant Iterative 15,827,117 1,107,848
Fast Iterative 6,389,560 26,772
Hardcore Iterative 5,000,875 26,792