2.2 FastArrayStack: An Optimized ArrayStack

Much of the work done by an ArrayStack involves shifting (by $\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ and $\ensuremath{\mathrm{remove}(\ensuremath{\mathit{i}})}$) and copying (by $\ensuremath{\mathrm{resize}()}$) of data. In a naive implementation, this would be done using ${\color{black} \textbf{for}}$ loops. It turns out that many programming environments have specific functions that are very efficient at copying and moving blocks of data. In the C programming language, there are the $\ensuremath{\mathrm{memcpy}(\ensuremath{\mathit{d}},\ensuremath{\mathit{s}},\ensuremath{\mathit{n}})}$ and $\ensuremath{\mathrm{memmove}(\ensuremath{\mathit{d}},\ensuremath{\mathit{s}},\ensuremath{\mathit{n}})}$ functions. In the C++ language there is the $\ensuremath{\mathrm{stdcopy}(\ensuremath{\mathit{a_0}},\ensuremath{\mathit{a_1}},\ensuremath{\mathit{b}})}$ algorithm. In Java there is the $\ensuremath{\mathrm{System}.\mathrm{arraycopy}(\ensuremath{\mathit{s}},\ensure... ...t{i}},\ensuremath{\mathit{d}},\ensuremath{\mathit{j}},\ensuremath{\mathit{n}})}$ method.

These functions are usually highly optimized and may even use special machine instructions that can do this copying much faster than we could by using a ${\color{black} \textbf{for}}$ loop. Although using these functions does not asymptotically decrease the running times, it can still be a worthwhile optimization.

In our C++ and Java implementations, the use of fast array copying functions resulted in speedups of a factor between 2 and 3, depending on the types of operations performed. Your mileage may vary.