Implement D3DXMatrixStack_Push

H. Verbeet hverbeet at
Wed Apr 9 15:41:25 CDT 2008

On 09/04/2008, Stefan Dösinger <stefan at> wrote:
> You usually grow the memory by a factor of the old size because this reduces
>  the number of needed grows. So growing the stack is an O(log(n)) instead of
>  O(n), which is a huge difference.
No, the amortized time per push is O(1). The realloc becomes more
expensive as the array gets larger.

>  The drawback is that you have potentially more wasted memory. I don't know
>  what the theory says to that though. The amount of wasted memory is always
>  smaller than the amount of used memory at least if you double the size and
>  smaller if you grow it by 1/2 of the existing size, ...
On average the percentage of wasted memory is (factor - 1) / 2. You
make a trade of between memory usage and run time when picking the

More information about the wine-devel mailing list