Implement D3DXMatrixStack_Push

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

In the opposite, for MatrixStack_Pop, assume that the size of the
stack is 98 and This->current is 64.
Then one could shrink the size of the stack from 98 to
98-size_stack_reference that is 64.
> You should also assign the result of HeapReAlloc() to This->matrix
> again.

*I thought that

HeapReAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, This->matrix, ..........);**
*
do exactly what you say

Although it's quite possible for HeapReAlloc to just grow the
> current block without changing its location, there's no guarantee it
> will. The NULL check is useless this way.

Thanks for your very useful feedback.

David

[H. Verbeet]

On 09/04/2008, David Adam  wrote:
> 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.

Growing exponentially is intended. If HeapReAlloc can't simply grow
the current block, it has to copy the contents over to a new memory
location. If the stack becomes larger, the relative time it costs to
do the copy becomes more and more expensive compared to the actual
push. Growing by a factor instead of by a constant size keeps the
amortized running time for a series of pushes constant independent of
the the array size. (Not that I expect a matrix stack to become large
enough for this to matter a whole lot, but that's the reasoning.)
> > You should also assign the result of HeapReAlloc() to This->matrix
> > again.
>
> I thought that
>
> HeapReAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, This->matrix, ..........);
>
> do exactly what you say

It can't do that. HeapReAlloc takes a pointer to a memory location, so
it can change the memory at that location, but it can't change the
pointer itself.

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

[H. Verbeet]

On 09/04/2008, Stefan Dösinger  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
factor.

[Stefan Dösinger]

Am Mittwoch, 9. April 2008 22:41:25 schrieb H. Verbeet:
> On 09/04/2008, Stefan Dösinger  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.

Good point