flat assembler
Message board for the users of flat assembler.

Index > Main > Memory resizing strategy.

Author
Thread Post new topic Reply to topic
JohnFound



Joined: 16 Jun 2003
Posts: 3500
Location: Bulgaria
JohnFound
Well, the problem is following: If we have memory buffer, that have to be dynamically resized, on every resize we have to decide what the new size should be. As long as, the dynamic memory allocations are slow, the usual approach is to allocate more memory than needed and use it for future enlargements, until it ends and then to allocate again.
But what is the most proper strategy to determine the reserve that have to be allocated? Different languages and libraries uses different strategies, but I never read some argumentation why this strategy was chose.
AFAIK, C libraries uses Size*2, that is too aggressive IMO. Delphi uses more gentle Size*1.5 again without explanation. Of course Size+constant is also possible again with a lot of intermediate variants.

What do you think? Is it possible to determine one optimal strategy, possibly based on the size of the elements added to the buffer; some statistics of the addition history; user prediction for the final size; moon phases Wink and so on...

Regards
Post 01 Dec 2010, 09:32
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
Whenever allocation becomes the problem (both speed and size wise), the developer should write custom memory management suited for particular task. Otherwise, I think plain *1.5 is just okay. There is no way better for every single possible case, and there is no need to think about solutions to nonexistent problems
Post 01 Dec 2010, 13:11
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
JohnFound



Joined: 16 Jun 2003
Posts: 3500
Location: Bulgaria
JohnFound
Custom memory management will not solve the problem, because the problem is not related to any particular memory manager.
What about the "plain *1.5" - I, as a former Delphi programmer can only agree with this approach. But many C and C++ guys will claim "plain *2" is better and faster... Very Happy (also it is possible to use plain *1.25, *1.125... that are, at least, as easy to compute and will make very little "overallocation").
Post 01 Dec 2010, 13:31
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
I meant that when this causes real problems to particular application, then the application shouldn't use generic memory manager. So I don't see any reason to spend too many thoughts on this.
Post 01 Dec 2010, 14:43
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
push dword[count] ;count of bytes
call malloc ;find first available memory chunk
pop dword[fptr] ;far pointer to memory chunk

it appear that the problem is malloc only.
Post 01 Dec 2010, 15:58
View user's profile Send private message Visit poster's website Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
Don't have any links on hand, but I recall being told that the *2 factor had been chosen after a fair amount of research and testing - that for generic purposes it was the best compromise between not wasting too much memory and not wasting too much [s]memory[/s] time on more reallocations.

You'll have to keep in mind that wasted memory is only part of the problem - consider memory fragmentation. It might actually be a much better strategy to overshoot memory allocation by a fair amount if you can reduce the amount of fragmented small-to-the-point-of-being-unusable free holes in your heap.

I kinda agree with vid anyway - if memory allocation becomes a legitimate concern in your application, move to custom allocators. Custom resize strategies, pooled allocation, you name it.

Also, if you need a lot of resizing, consider not using a linear layout data structure. The C++ deque container, for instance, would typically allocate in "linked chunks":
Quote:
Both vectors and deques provide thus a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors are very similar to a plain array that grows by reallocating all of its elements in a unique block when its capacity is exhausted, the elements of a deques can be divided in several chunks of storage, with the class keeping all this information and providing a uniform access to the elements. Therefore, deques are a little more complex internally, but this generally allows them to grow more efficiently than the vectors with their capacity managed automatically, specially in large sequences, because massive reallocations are avoided.


Last edited by f0dder on 02 Dec 2010, 09:34; edited 1 time in total
Post 02 Dec 2010, 08:14
View user's profile Send private message Visit poster's website Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
edfed wrote:
push dword[count] ;count of bytes
call malloc ;find first available memory chunk
pop dword[fptr] ;far pointer to memory chunk

it appear that the problem is malloc only.
Ummm... return value is in eax, and it's a near pointer, not far. What you're popping off the stack is the [count] you passed in as argument to malloc.

_________________
Image - carpe noctem
Post 02 Dec 2010, 08:17
View user's profile Send private message Visit poster's website Reply with quote
JohnFound



Joined: 16 Jun 2003
Posts: 3500
Location: Bulgaria
JohnFound
Quote:
Don't have any links on hand, but I recall being told that the *2 factor had been chosen after a fair amount of research and testing - that for generic purposes it was the best compromise between not wasting too much memory and not wasting too much memory.


Well, it would be interesting to read some arguments about this opinion and some texts what was tested and how.

Actually I know that for a specific tasks, custom memory manager is the best.
I am talking here especially for "general purpose" memory allocation strategies.
Post 02 Dec 2010, 09:02
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
sinsi



Joined: 10 Aug 2007
Posts: 692
Location: Adelaide
sinsi
f0dder wrote:
best compromise between not wasting too much memory and not wasting too much memory.

So it was arbitrary then Laughing
Post 02 Dec 2010, 09:30
View user's profile Send private message Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
JohnFound wrote:
Well, it would be interesting to read some arguments about this opinion and some texts what was tested and how.
Indeed - especially to be able to validate that the strategy hasn't been invalidated by changes in program design and usage patterns.

sinsi wrote:
f0dder wrote:
best compromise between not wasting too much memory and not wasting too much memory.

So it was arbitrary then Laughing
Oops, fixed Smile

_________________
Image - carpe noctem
Post 02 Dec 2010, 09:35
View user's profile Send private message Visit poster's website Reply with quote
JohnFound



Joined: 16 Jun 2003
Posts: 3500
Location: Bulgaria
JohnFound
BTW, the initial size of the memory block is important too in the approach size*multiplier. The main problems with smaller multipliers is that the function grows too slow on small sizes. Actually, the approach where the multiplier is big at the begin, and then becomes smaller can improve memory usage without affecting speed too much...
But the problem in this variant is that we don't know when to make the multiplier smaller. Because we don't know the final size of the memory. But on the other hand, if we knew the final size, we could allocate it at once. Very Happy
What if we compute some statistics on the allocation procedure and then optimize the resize strategy using this statistics.
Post 02 Dec 2010, 10:36
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
JohnFound wrote:
What if we compute some statistics on the allocation procedure and then optimize the resize strategy using this statistics.
I probably wouldn't add that kind of code to a production memory allocator - but it makes a lot of sense doing it during development for your heavy allocations, and using that information to tune your allocator parameters.

_________________
Image - carpe noctem
Post 02 Dec 2010, 10:46
View user's profile Send private message Visit poster's website Reply with quote
bogdanontanu



Joined: 07 Jan 2004
Posts: 403
Location: Sol. Earth. Europe. Romania. Bucuresti
bogdanontanu
I usually use something like: new_size = old_size + empiric_constant; in my C/C++ programs.

And then empiric_constant = N*sizeof(ONE_ITEM); where N is calculated from my experience and tests with the algorithm at hand.

Form my experience I have found that new_size = old_size*2; is to much for real life production code.
Post 02 Dec 2010, 15:50
View user's profile Send private message Visit poster's website Reply with quote
Kain



Joined: 26 Oct 2003
Posts: 108
Kain
if i don't know what to expect, i use (size needed * 2 )+padding
where padding is long enough to provide overflow space for moving instructions.
Post 03 Dec 2010, 22:58
View user's profile Send private message Reply with quote
drobole



Joined: 03 Nov 2010
Posts: 67
Location: Norway
drobole
How about leaving it to the client to decide the block size?
Post 04 Dec 2010, 01:23
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.