Jump to content
  • Advertisement
Sign in to follow this  
ClementLuminy

Memory Allocator for string class

This topic is 4157 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello everybody . I'm actually trying to find a way reduce the amount of call to new/delete in my simple string class. Actually, every time a string is constucted it allocate memory space in order to store the char array, which in final drive to a lot of small memory allocation... I wonder if anybody of you know a kind of memory allocator, that can help me to make less memory allocation ( pre allocating a string buffer ... ?? ..., using a small object memory allocator ... ??? ...) If you have any idea... Thanks !

Share this post


Link to post
Share on other sites
Advertisement
The first problem is about calling new and delete every time i need to use a string ...

I would like to use something faster ...

And the second reason, is about memory fragmentation with all that small allocation ...

I'm making a 3d engine, and i use this class pretty intensivly ...

You think it's not a problem at all to use this class without efficient memory management ??


Share this post


Link to post
Share on other sites
What language? The new/delete part seems to suggest C++, but if you really use C++ then you should just use std::string unless you have a good reason not to (you can't write anything faster).

There are plenty of things you can do. For small strings you could have a regular character array and when a string's length exceed some fixed number you start using dynamic memory allocation (done by several std::string implementations).

You might also allocate large chunks at a time. For example you might have a string with 200 elements and you don't have room for any more. Then you add a character to the end, but instead of freeing the 200 character elements and allocating 201 character elements you could simply allocate 400 characters to avoid many small allocations. Then when you exceed 400 characters you could allocate 800 characters. A flexible string class would allow the user to specify an optional policy both for when to allocate more memory and how much more memory.

If you delete a string of 100 characters then you might choose to throw it on a list. Then the next time you create a string less than 101 characters you just take that object and use it. Of course when multiple elements are on the list you should choose the smallest one with a larger size than is required.

Copy-on-write might also reduce some memory allocations, but in practice it can often be too slow. Especially with multithreading.

For some applications using ropes for strings might even boost your performance.

Quote:
using a small object memory allocator

How would that help? I guess your string objects are likely to differ in size and you want the content to be laid out in a sequential fashion.

Share this post


Link to post
Share on other sites
Quote:
Original post by ClementLuminy
You think it's not a problem at all to use this class without efficient memory management ??


Fragmentation is always a problem and unless you intend to defragment your memory (might actually be possible while paused or on a loading screen) then you're going to run into trouble when someone plays your game for a long time.

Share this post


Link to post
Share on other sites
Quote:
Original post by CTar
Quote:
using a small object memory allocator

How would that help? I guess your string objects are likely to differ in size and you want the content to be laid out in a sequential fashion.


I have had some success using small object allocators for strings. I have a few allocators for different sizes, 32, 128, 512 and 2048 bytes, and allocate from the smallest pool possible or new them if they are larger than the biggest pool.

However, as CTar is getting at, is this *really* a problem? Have you profiled and found string alloation to be taking up an unreasonable amount of your time?

You talk about fragmentation, but on Windows at least you can usually rely on virtual memory to deal with it for you. In the cases where you can't, design a system that solved your specific problem (ie, why are you burning through so many temporary string allocations?).

Alan

Share this post


Link to post
Share on other sites
in fact i'm developping this engine as a hobby, so i do not have any other platform than windows to test my system ( i know ... it sound funny :) )

BUT, i want to develop my system has if was able to run it on consoles ...
Which simply mean that i try to take in account every problem that can occur on those platforms .... ( i.e fragmentation )

And also for those reasons ( and also mainly for learning purpose ), i do not use any kind of stl stuff including their string class ....

Can you just tell me a little more about your small object memory allocators ??
Do you have a link to a page that explain how does it works ???
Is it efficient ???
And an other thing :
By using this allocator, does the problem of fragmentation just move from system memory to custom allocator memory ???

Thanks a lot...

And again, it's for performances AND for learning purposes that i'm doing that ...


:)

Thanks !

Share this post


Link to post
Share on other sites
Quote:
Original post by ClementLuminy
And also for those reasons ( and also mainly for learning purpose ), i do not use any kind of stl stuff including their string class ....

That seems like a bad idea. You aren't likely to encounter significant fragmentation if you use the standard library well.

Doing something for learning purpose is a bad idea in a big project. If you want to learn how to create data structures do it in a seperate project because if you do it as a part of a bigger project you will not learn as much and the project as a whole will suffer from this.

Quote:
Can you just tell me a little more about your small object memory allocators ??
Do you have a link to a page that explain how does it works ???
Is it efficient ???

He explained it in his post. For a 42 character string you'd just take a 128 byte block and use because it's the smallest available which can contain 42 characters. When you stop using strings you just let go of the block and let someone take it.

This can result in a little internal fragmentation because you might have some blocks, but not the kind you'd like to use, but there are ways to get around that (the buddy memory allocation algorithm is a well-known efficient one, but still suffers from some internal fragmentation).

Share this post


Link to post
Share on other sites
Quote:

BUT, i want to develop my system has if was able to run it on consoles ...
Which simply mean that i try to take in account every problem that can occur on those platforms .... ( i.e fragmentation )

This is an excellent way to waste your time. Until you've deployed the system on a target platform, you don't know what the systems problems will be on that target platform. You should not try to optimize for a situation you have not encountered yet; this is premature optimization. Furthermore, as others have suggested, it might be micro-optimization as well -- if a profiler told me I was allocating a lot of strings, I'd spend my time trying to reduce the need to allocate strings, not trying to make the allocations themselves faster. The fastest code is code that never runs.

Quote:

And also for those reasons ( and also mainly for learning purpose ), i do not use any kind of stl stuff including their string class .... And again, it's for performances AND for learning purposes that i'm doing that ...

Those two are at odds. If you want to write a string class to learn, fine (it's not among the best ways to learn, because you won't really know if you've made stupid design or implementation choices, but I digress). However, what you write to learn should not be intended for production code. It is highly unlikely that you will be capable of outperforming the SC++L string class, in general, at this moment in time. std::basic_string<char,T> where T is a custom allocator will probably alleviate the worst of the memory pressure.

Your responses suggest that you're not particularly well-informed regarding the SC++L's performance or methods to increase or tweak its performance, nor do you seem to be particularly familiar with some of the relevant optimization methods. This suggests that writing the class for educational purposes is a halfway decent plan, but thinking that you're writing it for "performance reasons" and to support theoretical console deployment is folly.

Quote:

Can you just tell me a little more about your small object memory allocators ??
Do you have a link to a page that explain how does it works ???

The book "Modern C++ Design" has some prose on small object allocators. Google turns up some relevant results as well.

Share this post


Link to post
Share on other sites
Quote:
By using this allocator, does the problem of fragmentation just move from system memory to custom allocator memory ???


Yes.

It'll be even worse, since your allocator will not be scalable or thread-safe, unless you go to incredible lengths to ensure that. And at that point, you'll be back at square one.

The first solution to allocations is to avoid them. May sound stupid, but rather than trying to solve a non-existant problem, reduce the number of allocations first.

Pass strings by reference. Allocate them once. When concatenating, use pre-allocated buffers.

And this should eliminate the bulk of your problem. This way you also pinpoint where allocations are necessary. There are very few places where you really need to allocate strings - concatenation is not one of them, neither is passing them around.

As always - the fastest operation and best allocation is the one not performed.

And until you start profiling and testing your console on actual console, unless you have heaps of experience with such systems, you *cannot* determine what the problems will be.

Will fragmentation be a problem? Possibly. But will your game really run for that long, or will it purge entire state every 5 minutes, releasing all of the allocated memory?

The only benefits from custom memory allocation come from optimizing for usage patterns, not some abstract general cases. And even then that only happens when, and only when, you have determined that your application will have problems with that, after you have eliminated all the redundant allocations.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!