stefan at codeweavers.com
Wed Apr 9 13:37:07 CDT 2008
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
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, ...
More information about the wine-devel