Memory-efficient C++ strings (interning, ropes, copy-on-write, etc)

Question

My application is having memory problems, including copying lots of strings about, using the same strings as keys in lots of hashtables, etc. I'm looking for a base class for my strings that makes this very efficient.

I'm hoping for:

String interning (multiple strings of the same value use the same memory),
copy-on-write (I think this comes for free in nearly all std::string implementations),
something with ropes would be a bonus (for O(1)-ish concatenation).

My platform is g++ on Linux (but that is unlikely to matter).

Do you know of such a library?

score 9 · Answer 1 · edited Oct 11 '11 at 20:55

9

copy-on-write (I think this comes for free in nearly all std::string implementations)

I don't believe this is the case any longer. Copy-on-write causes problems when you modify the strings through iterators: in particular, this either causes unwanted results (i.e. no copy, and both strings get modified) or an unnecessary overhead (since the iterators cannot be implemented purely in terms of pointers: they need to perform additional checks when being dereferenced).

Additionally, all modern C++ compilers perform NRVO and eliminate the need for copying return value strings in most cases. Since this has been one of the most common cases for copy-on-write semantics, it has been removed due to the aforementioned downsides.

edited Oct 11 '11 at 20:55

Ross Rogers

23,523
27
108
164

answered Jul 12 '09 at 13:36

Konrad Rudolph

530,221
131
937
1,214

4

Not to mention multithreading issues... – Nicolas Simonet Jul 12 '09 at 14:46
2

Also, some strings have a small string optimization, using not the heap but an embedded small buffer for storing the data. Surprisingly, though, GCC's default string class (libstdc++) does copy-on-write. – Johannes Schaub - litb Jul 12 '09 at 17:13
1

C++ 11 prohibits COW string classes – Ghita Jun 07 '13 at 12:13
1

@Ghita This answer by far predates C++11. – Konrad Rudolph Jun 07 '13 at 12:20
@KonradRudolph Yes I know. Just wanted to mention for completeness. It's stack overflow here :-) – Ghita Jun 18 '13 at 20:09

score 7 · Accepted Answer · answered Jul 12 '09 at 13:32

7

If most of your strings are immutable, the Boost Flyweight library might suit your needs.

It will do the string interning, but I don't believe it does copy-on-write.

answered Jul 12 '09 at 13:32

Ferruccio

98,941
38
226
299

If I use it to wrap a std::string, it looks like it wouldn't harm the copy-on-write. – Paul Biggar Jul 12 '09 at 13:37

score 5 · Answer 3 · answered Jul 13 '09 at 09:14

5

Andrei Alexandrescu's 'Policy Based basic_string implementation' may help.

answered Jul 13 '09 at 09:14

graham.reeds

16,230
17
74
137

This doesn't help that much, but it is none-the-less awesome. – Paul Biggar Jul 13 '09 at 12:17
It's been a while since I read it, but it sprung to mind when I saw your post. – graham.reeds Jul 13 '09 at 14:31

score 2 · Answer 4 · answered Jul 13 '09 at 09:03

2

Take a look at The Better String Library from legendary Paul Hsieh

answered Jul 13 '09 at 09:03

Indy9000

8,651
2
32
37

That looks quite nice but it sorely lacks iterators. – Konrad Rudolph Jul 13 '09 at 09:24
2

I wouldn't trust any library write who states that "Bstrlib is, by design, impervious to memory size overflow attacks. The reason is it is resiliant to length overflows is that bstring lengths are bounded above by INT_MAX, instead of ~(size_t)0.". Yet another amateur who thinks he's found a silver bullet, that's how it appears. – MSalters Jul 13 '09 at 10:51
It doesn't seem to offer anything I'm looking for... – Paul Biggar Jul 13 '09 at 12:01
2

@MSalters I think you are confusing buffer overflows with memory size overflows here. Still, there are silver bullets in the buffer overflow department and they are called runtime checking of array bounds. – jpc Apr 30 '11 at 01:34

Memory-efficient C++ strings (interning, ropes, copy-on-write, etc)

4 Answers4

Linked