Implement D3DXMatrixStack_Push

[Stefan Dösinger]

Am Mittwoch, 9. April 2008 10:54:37 schrieb David Adam:
> On 08/04/2008, David Adam <david.adam.cnrs at gmail.com
>
> <http://www.winehq.org/mailman/listinfo/wine-patches>> wrote:
> >* +    This->current = This->current +1;
>
> *>* +    HeapReAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, This->matrix,
> (This->current +1) * sizeof(D3DXMATRIX) );
> *>* +    if ( This->matrix == NULL ) return E_OUTOFMEMORY;
> *
>
> > Aside from being a bit suboptimal (doing a realloc on every push),
> > this probably doesn't do what you want. Consider what happens to the
> > size of the array when you do something like push/pop/push/pop/...etc.
> >
> > It would be better to keep track of the current stack size, and then
> > grow it by a factor (eg. 2 or 1.5) if a push would overflow the
> > current stack.
> > You could also consider shrinking the array again if a
> > pop would make it use less than a certain percentage of the current
> > size (eg. a third).
>
> This would increase the size of the stack exponentially. Would it be
> better to do this:
> Take a stack_size_reference (for instance 32 items)
> When This->current =32, then increase the size of the stack of
> stack_size_reference (that is 64 items now)
> Then when This->current is =64, again increase the size of the stack
> of stack_size_reference (that is 98 items now), and so on....
>
> This would increase the size of the stack linearly instead of
> exponentially.
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.

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, ...