3
\$\begingroup\$

I've been designing the memory management module for my game engine, including things like custom allocators and when it came to allocating memory for strings I kinda got stuck. What I mean by strings in this context is things like UI text, Items description, dialogues etc, so basically strings themselves are immutable, but they can stop being useful and just get freed.

With the string (and basically any object type with such allocation patterns) allocator I'd like to mostly get rid of the malloc/free invocations and so I'm wondering what kind of allocator is suitable for this jobs. Another thing that worries me is fragmentation, because string have variable length by nature

How do game engines handle strings like this in the first place?

EDIT

Firstly I'd like to address some of the questions that came up.

The strings themselves would be loaded from an asset file.

By 'stop being useful' I mean a situation where player interacts with some kind of item that has a description associated with it and we'd like to show the description on screen.

To do that, the text would get loaded, displayed and freed some time after the player closes the description window (the delay is here because there the player could reopen the window again in a brief second for whatever reason).

Such allocations would occur very often, because we don't need all the resources at all times, just a specific subset of them and my idea was to create an allocator for that purpose. It would malloc a large enough block of memory and store the strings (or any resource of such allocation pattern) in it, marking the free spots as the string get freed.

That's when 'what about fragmentation' came up in my mind, because some strings might actually be stored a bit longer than others, leading to fragmentation inside the allocator.

But after reading some of the comments I figured that what I actually need is separate allocators for long-living strings/resources, such as UI elements, and for short-lived elements, like the dialogues and descriptions What I also realized thanks to @Moo-Juice is that I could introduce something like resource-groups, that would hold the group of resources needed at that time, for example when entering some location, we'd load all the things that are contained within that location. Thanks for the insight!

One thing remains a puzzle for me tho. I've looked around Doom 3 source code, where I found a class called idStrPool which uses new/delete to allocate/deallocate strings. Can anybody comment on that? After reading some books and articles I was convinced, that such a thing is pure evil in a game engine, yet here it its. A use case I see for this is like handling input from the player, i.e. when the player types something and we want to capture it. Can anyone comment on that?

Edit 2

Ok, I see that guys from idSoftware have overrided the operators in Heap.h

\$\endgroup\$
  • 2
    \$\begingroup\$ Those player-facing strings would generally all be read from a localization file, no? ie. You'd load your localisation file for the current language into memory as one chunk (or one chunk for the current mode/state if you break it into multiple parts), then it becomes like a block of read-only data you can refer to for each of your strings. When you're done with a chapter / switching languages, you can free the whole file and pull in the next one. When would you allocate and free an individual string of the kind you described above? \$\endgroup\$ – DMGregory Jan 31 at 12:55
  • \$\begingroup\$ @DMGregory that was my original approach - to allocate a large enough block at the beggining, put strings into it, made them available by some kind of a hash-table and just free the whole things when it's not needed anymore. But then I realized that I might have string that would be needed only for a brief amount of time, for example: a player picks up a weapon that has a descriptions associated with it so it's show to him. but once he read the description and closes the window containing it, we need longer need the description in memory, hence it gets freed \$\endgroup\$ – wookie Jan 31 at 13:57
  • \$\begingroup\$ Do you construct this item description string on the fly, or open a file to pull out just the one string you need to display? \$\endgroup\$ – DMGregory Jan 31 at 14:05
  • \$\begingroup\$ I'd have I file containing such things, but not per item basis \$\endgroup\$ – wookie Jan 31 at 14:10
  • \$\begingroup\$ I could also mmap such files as I think of it now 🤔 \$\endgroup\$ – wookie Jan 31 at 14:10
2
\$\begingroup\$

To address your initial concern, unless you are targeting older generation consoles or embedded devices, you probably don't need to worry about fragmentation.

With that said, one way you can address the problem is to have a dedicated memory pool for strings which are then interned.

With string interning in C, you create a hash table where the keys are ids of the hashes of the strings. Whenever you want to use a string you get it from the string intern pool. If the hash of that string isn't in the pool yet, you add it. If it is, you can just return it. This makes it so that you don't pay the cost for duplicated strings.

If your use case contains lots of unique temporary strings, then interning might not be the best solution. And if you have concerns about hashing performance, look up compile time string hashing.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Pombal gives a very good answer, but I'd just like to add a note to it.

Like your textures, sounds, and other game-related data, strings are also a resource. Lots of game engines allow you to load and unload resources in groups... that is, you can have a global group (this stuff is alive for the duration of a play session), and then more specific groups for portions of a game (e.g. specific levels).

Strings are no different, and using the hash-table that Pombal mentions, is a fast way of looking up the string resource you want, and by using the resource allocation methods mentioned above, you are not allocating the strings for your whole game at the start, nor are you doing it on demand - rather you are doing it at the beginning of a level, or some other game-defined event.

I prefer the resource-group method, as it is done at a stage when the player is not actually actively participating (think... global being the game start, and at the beginning of a level or whatever resource group or partition you feel necessary). And believe me, you can load thousands of string resources in a heart beat using this method, and nobody will notice - and they're available.

Think ahead! :)

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.