7
\$\begingroup\$

On one of the projects I'm working on, we have many objects that store (small) strings, loaded from database. I know std::string's have small string optimization (SSO), but the overhead, in my opinion, is too big; most strings are < 16 characters, and on my platform sizeof(std::string) is 32, wasting 50% of memory. Also less data == less work.

This is not meant as a replacement for std::string, but to be used in places where one can guarantee the size of string won't exceed capacity. Basic functionality is provided to allow interoperability (to some degree) with std::string.

How it works:

It stores remaining capacity (a very clever trick by Andrei Alexandrescu, nicely explained here). When creating/appending larger strings than the capacity, data is truncated instead of throwing an exception, for performance reasons.

#pragma once

#include <string>
#include <iosfwd>       // ostream operator <<
#include <cstring>      // memcpy


template <std::size_t Size, class T = char>
class ShortString {
public:
    using size_type = std::size_t;
    using value_type = T;


    constexpr ShortString() noexcept
        : _buffer{}
    {
        set_size(0u);
    }


    template <size_type N>
    constexpr ShortString(const T(&str)[N]) noexcept
        : _buffer{}
    {
        auto size = N >= Size ? Size - 1 : N - 1;
        std::memcpy(_buffer, str, size);
        set_size(size);
    }


    template <class Traits, class Allocator>
    ShortString(const std::basic_string<T, Traits, Allocator>& str) noexcept
        : _buffer{}
    {
        auto size = str.size() >= Size ? Size : str.size();
        std::memcpy(_buffer, str.c_str(), size);
        set_size(size);
    }


    template <size_type N>
    constexpr ShortString(const ShortString<N>& rhs) noexcept
        : _buffer{}
    {
        auto size = N >= Size ? Size : N;
        std::memcpy(_buffer, rhs.c_str(), size);
        set_size(size);
    }


    template <size_type N>
    constexpr ShortString& operator = (const T(&str)[N]) noexcept {
        auto size = N >= Size ? Size - 1 : N - 1;
        std::memcpy(_buffer, str, size);
        set_size(size);
        return *this;
    }


    template <class Traits, class Allocator>
    ShortString& operator = (const std::basic_string<T, Traits, Allocator>& str) noexcept {
        auto size = str.size() >= Size ? Size : str.size();
        std::memcpy(_buffer, str.c_str(), size);
        set_size(size);
        return *this;
    }


    template <size_type N>
    constexpr ShortString& operator = (const ShortString<N>& rhs) noexcept {
        if ((void*)this != (void*)&rhs) {
            auto size = N >= Size ? Size : N;
            std::memcpy(_buffer, rhs.c_str(), size);
            set_size(size);
        }
        return *this;
    }


    template <size_type N>
    ShortString(ShortString<N>&& rhs) {
        auto size = N >= Size ? Size: N;
        std::memcpy(_buffer, rhs.c_str(), size);
        set_size(size);
    }


    template <size_type N>
    ShortString& operator = (ShortString<N>&& rhs) {
        if ((void*)this != (void*)&rhs) {
            auto size = N >= Size ? Size : N;
            std::memcpy(_buffer, rhs.c_str(), size);
            set_size(size);
        }
        return *this;
    }


    inline void append(value_type value) noexcept {
        if (size() < capacity()) {
            _buffer[size()] = value;
            set_size(size() + 1);
        }
    }


    inline const value_type* c_str() const noexcept { return _buffer; }


    inline std::string to_string() const { return {reinterpret_cast<const char*>(_buffer), size()}; }


    constexpr size_type size() const noexcept { return capacity() - _buffer[capacity()]; }
    constexpr size_type capacity() const noexcept { return Size - 1; }


    template <size_type N>
    constexpr bool compare(const ShortString<N>& rhs) const noexcept {
        return compare(_buffer, rhs.c_str());
    }


    inline const value_type* begin() const { return _buffer; }
    inline const value_type* end() const { return _buffer + size(); }


    template <std::size_t SizeB>
    ShortString<Size, T>& operator += (const ShortString<SizeB, T>& rhs) noexcept {
        for (const auto c : rhs) {
            append(c);
        }
        return *this;
    }


    template <std::size_t N>
    ShortString<Size, T>& operator += (const T(&str)[N]) noexcept {
        for (const value_type* p = str; *p; ++p) {
            append(*p);
        }
        return *this;
    }


    template <class Traits, class Allocator>
    ShortString<Size, T>& operator += (const std::basic_string<T, Traits, Allocator>& rhs) noexcept {
        for (const auto c : rhs) {
            append(c);
        }
        return *this;
    }


private:
    inline void set_size(size_type size) noexcept { _buffer[capacity()] = Size - 1 - size; }


    constexpr bool compare(const value_type* lhs, const value_type* rhs) const noexcept {
        return (*lhs && *rhs) ? (*lhs == *rhs && compare(lhs + 1, rhs + 1)) : (!*lhs && !*rhs);
    }


    value_type _buffer[Size];
};


template <std::size_t SizeA, std::size_t SizeB, class T>
ShortString<SizeA, T> operator + (ShortString<SizeA, T> a, const ShortString<SizeB, T>& b) noexcept {
    a += b;
    return a;
}


template <std::size_t Size, class CharT, class Traits, class Allocator>
ShortString<Size, CharT> operator + (ShortString<Size, CharT> ss, const std::basic_string<CharT, Traits, Allocator>& str) noexcept {
    ss += str;
    return ss;
}


template <std::size_t Size, class T, std::size_t N>
ShortString<Size, T> operator + (ShortString<Size, T> ss, const T(&str)[N]) noexcept {
    ss += str;
    return ss;
}


template <std::size_t Size, class T, std::size_t N>
ShortString<Size, T> operator + (const T(&str)[N], ShortString<Size, T> ss) noexcept {
    ss += str;
    return ss;
}


template <std::size_t SizeA, std::size_t SizeB, class T>
constexpr bool operator == (const ShortString<SizeA, T>& a, const ShortString<SizeB, T>& b) noexcept {
    return a.compare(b);
}


template <std::size_t Size, class CharT, class Traits, class Allocator>
bool operator == (const ShortString<Size, CharT>& lhs, const std::basic_string<CharT, Traits, Allocator>& rhs) noexcept {
    return std::strncmp(lhs.c_str(), rhs.c_str(), Size) == 0;
}


template <class CharT, class Traits, class Allocator, std::size_t Size>
bool operator == (const std::basic_string<CharT, Traits, Allocator>& lhs, const ShortString<Size, CharT>& rhs) noexcept {
    return rhs == lhs;
}


template <std::size_t Size, class T>
std::ostream& operator << (std::ostream& os, const ShortString<Size, T>& s) {
    return os << s.c_str();
}
\$\endgroup\$
7
  • \$\begingroup\$ Just to be sure, sizeof returns bytes, so the minimal size is 32/8=4 chars. Why is this such a big overhead, or was your reasoning, that std::string has capacity for at least 32 characters? \$\endgroup\$
    – miscco
    Dec 6 '16 at 11:34
  • 1
    \$\begingroup\$ sizeof indeed returns bytes not bits, so there's no division by 8. std::string has 24 (3 * 8 (data, size, capacity)) usable bytes; short string optimization, with a theoretical maximum of 23 characters, writes to those instead of allocating space on the heap. The overhead is waste of space (23 chars vs 31 with ShortString for same size), but only if you know you're dealing with short strings. \$\endgroup\$
    – nullw0rm
    Dec 9 '16 at 15:26
  • \$\begingroup\$ Additionaly, note that 23 bytes is a theoretical maximum. In practice, you are virtually guaranteed to get fewer usable bytes. \$\endgroup\$ Jan 20 '20 at 4:39
  • \$\begingroup\$ Actually, interesting note: you're both kinda correct. The minimum is 3 bytes, as it's possible to implement std::string such that the capacity and current size are in the same heap allocation as the rest of the bytes, leaving only the data pointer in the std::string itself. (which also can be done in such a way that it is bitwise identical to a char*, so it "does the right thing" when passed to printf. Though that's UB and you shoudn't do that) \$\endgroup\$ Jan 20 '20 at 4:41
  • \$\begingroup\$ While I understand the desire to make everything better, will this optimization actually make a difference in the end? Are there cases where this optimized string makes the difference between fitting in memory and not? Or making a significant performance difference in something that matters that can't be done by using a better algorithm? I'm asking because even if you hold a million strings in memory, you're still only saving at most 32 MB of RAM which is nothing today... You're also not showing any actual benchmarks to indicate that it's actually faster than std::string. \$\endgroup\$
    – Emily L.
    Jan 20 '20 at 20:11
5
\$\begingroup\$

I feel like the implementation of the class would be simpler if backed by a std::array<value_type , Size> instead of value_type _buffer[Size];, because then you could use the standard algorithms (aka iterators) easier, and get bounds checking in debug builds (at least in MSVC).

Initializing the buffer via : _buffer{} is unnecessarily slowing you down for no reason in most of the constructors, since you proceed to fill in the buffer regardless.

compare should be named operator==, so it's clear which comparison it's doing. I'd assumed it was operator< at first. It's also only ever passed buffer objects, so there's no reason to be strict about comparing nulls. It's also recursive, which is slow. Just use std::equal.

operator+ should be written out rather than calling append in a loop. Right now it's doing a capacity check for every character and updating the length for every character. Very inefficient. Just use std::copy.

You have operator== but no operator!= which is weird. And operator<< but no operator>>, also weird.

You're missing a very significant amount of the std::basic_string interface. Prefer to match the existing design patterns.

Also I strongly disagree with the exception throwing vs truncation. Definitely throw exceptions. At least assert. There's no performance penalty for exceptions here on most compilers, except when it's hit.

\$\endgroup\$
3
\$\begingroup\$

I would recommend marking explicit the conversions that could truncate values (e.g. construction from another short string, with N > Size).

Almost every function assumes that the string ends at the first NUL character, rather than continuing to the actual length of the string, making it much less useful than std::string.

I don't like the imposition on the user to account for the final size byte - if I create a ShortString<3>, I would expect to be able to store 3 characters. The code seems thoroughly confused about whether sizes include an extra NUL or not (see the extract below).

I would expect to see a constraint to prevent instantiating the class with a Size greater than can be held in the final T value. Consider accessing _buffer[capacity] as an unsigned type rather than taking on T's signedness.


Here, we assume that a ShortString<N> always holds exactly N characters (even though its limit is N-1; so we end up setting the size to -1 if N >= Size):

template <size_type N>
ShortString(ShortString<N>&& rhs)
{
    auto size = N >= Size ? Size: N;
    std::memcpy(_buffer, rhs.c_str(), size);
    set_size(size);
}

I think you meant something like

    auto length = std::max(N-1, rhs.size());
    std::memcpy(_buffer, rhs_buffer, length+1);
    set_size(length);
\$\endgroup\$
3
\$\begingroup\$

(Too long for a comment, not really a code review)

I've seen the Facebook presentation about their custom fbstring class used as a motivation for people writing their own string classes. However people seem to conveniently miss the part that even at Facebook where arguably they do a lot more string processing than the average Joe Programmer, the performance gain over using non SSO optimised std::string in GCC < 5.0 is only 1% of their total CPU time.

The video also clearly states that they have no benchmarks (at time of filming) about if their fbstring class is any better than then new SSO std::string in GCC >= 5.0, and that it is a non trivial engineering effort to maintain the string class. And their use case is also pathological for the new standard string as their most commonly stored string is a 20 byte UUID which fits in the SSO of fbstring but not in std::string of GCC >= 5.0, at least for compilers they talk about in the presentation. I don't know about clang or the latest and greatest from GCC.

I want to emphasise the above, it's a non trivial engineering effort for a large, multinational, tech company with large amounts of engineering resources to maintain having their custom string class. And the gains over standard string in modern compilers is unclear from the presentation.

Yes, I know CPU cache utilisation and memory layout benefit from a smaller data structure. Yes this is true, but the impact to your overall runtime may still be low if you don't actually miss the accesses in the cache. If your access pattern is bad and you make the cache prefetcher sad and the majority time of your program is spent working these strings in a random fashion, then you can gain some performance by having more of your strings in the cache, but you can likely gain a larger improvement by fixing your access patterns instead.

You are also making interoperability with other libraries that typically use std::string harder and you will incur string copy penalties when converting between them in addition to the extra code complexity. And you will miss out on improvements to the standard string with new versions of the standard library.

What I'm trying to say is, unless you have clear benchmark data that indicates that writing your own micro optimised string class actually has a measurable and appreciable macro level performance impact on your application that is worth the engineering effort in developing and long term maintaining the use of this string class, your efforts would probably be better spent fixing bugs, adding features or optimising some other part of the application where the ROI will be higher.

The original post as written does not have any benchmarks (macro or micro) or other raw data to support the claim that this class makes a significant impact to the total program runtime/performance, but rather seems to argue that "FB did it so I should do it as well" and "it's smaller, so it's gotta be faster!". Remember that Facebook only got 1% improvement, which is basically indistinguishable from measurement noise except when your data set is massive, and 1% of a hundred million of dollars is still a million dollar less in utility cost in Facebook's case (or whatever their DCs cost to run). Does a 1% gain make sense in your application?

At the end of the day, I'm a sign, not a cop, and I'm not here to tell you what to do or how to code. I'm a just a friendly neighbourhood engineer, pointing out that it might be worth reconsidering if this is the best way to spend your effort; and stop to think about if you're building yourself a future headache and if it'll be worth it.

\$\endgroup\$
3
  • \$\begingroup\$ Note that the fbstring is a replacement for generic std string globally, wheras this code is merely for optimizations in certain cases. So the "only 1% improvement" metric doesn't really apply. \$\endgroup\$ Jan 27 '20 at 2:20
  • \$\begingroup\$ It would be hard to produce clear benchmark data without first making a micro optimized string class to measure with. \$\endgroup\$ Jan 27 '20 at 2:22
  • 1
    \$\begingroup\$ The "only 1%" makes sense when you're using that FB presentation to argue why you're creating your own string class without providing your own measurements. Yes, write class, write benchmark, measure, analyse, ask for review, make decision. Asking for a review with hard data in hand, "this is this much better, here is the benchmark code you can use to test any changes" is going to give you a much more valuable review with qualitative data to base your decision on rather than making a decision before you have the data and possibly pessimising your code. \$\endgroup\$
    – Emily L.
    Jan 27 '20 at 21:27

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.