std::basic_string
is the C++ string class (template) and is intended for general purpose
usage. Some use cases, however, cannot be implemented with std::basic_string
, because it has
some drawbacks:
std::basic_string
allocates memory on the heap, which makesstd::basic_string
an "improper" replacement for "plain old C" character arrays.std::basic_string
allocates and reallocates data as required, transparently growing (or potentially shrinking) the reserved memory area.
First of all: they're not bad. They are actually great, because std::basic_string
can grow
almost unlimited, so you can store strings at all lengths and don't have to worry that they are
longer than any arbitrary limit.
But there is a small caveat: Allocating memory on the heap is a performance penalty compared to
"allocating" memory on the stack. For most use cases, this penalty is worth it. Current
implementations of std::basic_string
try to avoid heap allocations for short strings
(Short/Small String Optimizations, SSO), but this is usually limited to lengths < 30 characters.
Using the stack instead of the heap however limits the string to a fixed maximum length, because
data on the stack cannot be resized on demand. But if you either know a maximum length or can
"live" with one in order to get that last bit of performance, a stack-based string class is
an interesting alternative. This is were spsl::ArrayString<N>
starts to look nicer...
A real-life example that motivated me to write the precursor of spsl::ArrayString<N>
are
SQL database access layers: If you have columns in your SQL database with a maximum length,
you can use the same limit in your code. For example, if your "lastname" colum in the "persons"
table is defined as VARCHAR(50)
, you know a maximum string length and can take advantage
of this fact to skip heap allocations. That's why there is spsl::ArrayString<N>
.
This also isn't a bad thing per-se. It's actually a great feature for most usage patterns:
Let's say you need N bytes of data from the heap. You allocate it from the OS and fill it with
your data. Next thing you know is that you need more space because you need to append more
data. You simply call std::basic_string::append
and you're done.
In this case, two things can happen (assuming you're not ouf of memory):
If you still have enough unused capacity left, the new data is appended and "almost nothing"
happens. This often is the case because std::basic_string
implementations usually
allocate more memory than initially requested to avoid reallocations.
But if the remaining space is to small, a new memory area is allocated, all your data
is copied. The string objects releases the old memory are and will use the new one from now on.
The old memory can now be used by other processes. Again - very useful.
But there is one caveat: The memory areas that are released aren't cleaned up. For at least 99% of all use cases, that's not a problem. But if you stored sensitive data in this memory region, e.g. the password for your cloud provider, this data is still there. And now, other processes can see it, because if they allocate memory on the heap, they might get the region with your old data - because you don't need it anymore for your string.
The only solution is to manually "clean up" or "wipe" the memory you used before deallocating it.
That's what spsl::PasswordString[W]
does (and more...).
After reading the arguments above, you might argue: "But this is what std::allocator
was
designed for, right? Just write an allocator that uses an array on the stack / wipes memory
before deallocating it and use this with std::basic_string
. You don't need to implement
another string class template!"
My answer to this is sad and short: I tried, but I failed. But what kept me going was: It's not my fault :-)
The reason why both use cases cannot be implemented with recent std::basic_string
implementations are the already mentioned Short String Optimizations:
These optimizations work by cleverly using some of the stack space, that is already required
to store a std::basic_string
object, and put short strings there.
The actual implementation doesn't really matter in this case - simply imagine that someone
found a "clever hack" to mix meta-information and data. The great thing about this: no heap
allocation, more speed.
But there are 2 problems, why this defeats any std::allocator
implementations:
- We cannot simply write an allocator that wipes memory before deallocating it, because there
might not be any allocation at all. With SSO, a short password may directly be stored on the
stack - outside of the reach of an allocator. In order to wipe this memory as well,
std::basic_string
needs to be modified, which is not an option. - The
max_size()
limitation of the allocator isn't directly respected instd::basic_string
implementations. This means that the maximum capacity that an allocator implementation can provide is either ignored or further reduced, making an allocator implementation based on a fixed-size array impossible.
To provide more background for the second point, we need to take a look at the different STL implementations (at leat the relevant parts):
GCC 4.9
_Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT))
[...]
/// Returns the size() of the largest possible %string.
size_type
max_size() const _GLIBCXX_NOEXCEPT
{ return _Rep::_S_max_size; }
The allocator's max_size()
is ignored, thus calling max_size()
on a string wouldn't return
the actual size limit. An API that provides incorrect values is not an option for production code.
GCC 5.4
/// Returns the size() of the largest possible %string.
size_type
max_size() const _GLIBCXX_NOEXCEPT
{ return (_Alloc_traits::max_size(_M_get_allocator()) - 1) / 2; }
Here, the allocator's limit is respected, but it's cut in half (TODO: why?).
Thus, if the allocator would have space for N characters, only (N-1)/2 would be used.
To solve this, the allocator must either over-allocate memory - waisting half of it's space -
or "lie" about it's max_size()
. Both aren't an option for production code.
libc++ (LLVM)
template <class _CharT, class _Traits, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
typename basic_string<_CharT, _Traits, _Allocator>::size_type
basic_string<_CharT, _Traits, _Allocator>::max_size() const _NOEXCEPT
{
size_type __m = __alloc_traits::max_size(__alloc());
#if _LIBCPP_BIG_ENDIAN
return (__m <= ~__long_mask ? __m : __m/2) - __alignment;
#else
return __m - __alignment;
#endif
}
In this implementation, alignment is taken into account. This also reduces the allocator's maximum capacity and would also require either over-allocation or an "dishonest" API. Also, for big endian machines, the limit may also be cut in half to reserve the highest bit in the capacity for SSO.
Unfortunatly, this forces a re-implementation of the std::basic_string
template in order
to cover the use cases described above.