C++ string implementation

Question

I use all over my code std::string objects, most of them stack allocated. I replaced default new/delete operators to check the average memory allocation size and I was surprised to see that most allocations come from std::string and, this is very important, they are between 12 and 32 bytes! To optimize this(large number of small strings allocated from the free storage) I came with a simple solution:

• implement custom string class
• add predefined buffer in it with fixed size, for example 64 bytes(I can adjust this size after profiling)
• use predefined buffer when the length of the string is less than 64 bytes or allocate new buffer from the free storage for larger strings.

With this implementation I will add 64 bytes memory overhead to all my strings with length > 64 add also (64-lenth) overhead to strings shorter than 64 bytes, but I will prevent all the allocations for small strings.

Did you tried such approach? Is it resonable to add this memory overhead, most of the time on the stack to save allocation time/memory fragmentation?

Is this approach better than custom str::string allocators?

Answer 1

Did you tried such approach?

No, but I did write my own allocator. It is an alternative I prefer.

Is it resonable to add this memory overhead, most of the time on the stack to save allocation time/memory fragmentation?

The definition of what is "reasonable" varies with your situation. Do you need to prevent memory fragmentation? Do you need to minimize number of allocations? Maximize speed at the cost of extra memory per string?

Do you simply want to optimize the std:: implementation as an exercise?

Do you have a target platform with performance (or memory) limitations?

Each of these questions will alter the answer (on whether the memory overhead is reasonable).

Is this approach better than custom str::string allocators?

Depends on your situation.

Answer 2

Is it reasonable? It depends. Unless you have found yourself actually running out of memory by using std::string or identified a real (as opposed to perceived) performance problem with continued allocation and deallocation, you're wasting your time doing this.

Don't get me wrong, you can (and I have) made great gains over standard allocators by using extra information unavailable to them. But, unless there's a real problem to be fixed, you're better off using the standard method and devoting your time elsewhere.

Answer 3

I think it's been done before, along the lines you mentioned, in folly: "fbstring is a drop-in replacement for std::string. The main benefit of fbstring is significantly increased performance on virtually all important primitives."

https://github.com/facebook/folly/blob/master/folly/docs/FBString.md

This should be pretty well optimized:

Storage strategies

Small strings (<= 23 chars) are stored in-situ without memory allocation.

Medium strings (24 - 255 chars) are stored in malloc-allocated memory and copied eagerly.

Large strings (> 255 chars) are stored in malloc-allocated memory and copied lazily.