Cache friendly string

Question

Suppose you have a vector or list from the following:

struct Data{
   std::string key;
   //...
};

When you do some processing, when you compare the key, it always does pointer indirection when a key is checked. (I know, except in the case of SSO, but let's ignore that.)

With my SmallString class, you can do the following:

struct Data{
   SmallString8 hkey;
   std::string key;
   //...
};

Then you can compare the first 8 characters with hkey, then if the comparison return 0, you need to compare with the key itself, in order to be sure the value is really equal.

Here is example from real application at https://github.com/nmmmnu/HM4/

Using the class my the application speed-up is almost 50%!!!

class OPair{
// ...
public:
    int cmp(const StringRef &key) const noexcept{
        int const r = hkey.compare(key);

        if (r || key.size() <= hkey.capacity())
            return r;

        return pp->cmp(key);
    }

private:
    SmallString8                hkey;
    std::unique_ptr<const Pair> pp;
};

Here is SmallString itself:

template <size_t BYTES>
class SmallString{
    static_assert(BYTES >= 1 && BYTES <= 64, "BYTES must be between 1 and 64");

private:
    constexpr static size_t SIZE = BYTES;

public:
    // CONSTRUCTORS

    SmallString() noexcept{
        clear_();
    }

    SmallString(const char *data) noexcept{
        if (data)
            strncpy(data_, data, SIZE);
        else
            clear_();
    }

    SmallString(const char *data, size_t const size) noexcept{
        if (data)
            copyNotNull_(data, size);
        else
            clear_();
    }

//  SmallString(const StringRef &sr) noexcept{
//      copyNotNull_(sr.data(), sr.size());
//  }

private:
    void copyNotNull_(const char *data, size_t const size) noexcept{
        if (size >= SIZE){
            memcpy(data_, data, SIZE);
        }else{
            memcpy(data_, data, size);
            memset(data_ + size, 0, SIZE - size);
        }
    }

    void clear_() noexcept{
        memset(data_, 0, SIZE);
    }

public:
    // INFO

    constexpr static size_t capacity() noexcept{
        return SIZE;
    }

    // DATA MEMBERS AND CASTS

    constexpr const char *data() const noexcept{
        return data_;
    }

    constexpr const char *c_str() const noexcept{
        return data();
    }

    size_t size() const noexcept{
        return strnlen(data_, SIZE);
    }

    size_t length() const noexcept{
        return size();
    }

    constexpr bool empty() const noexcept{
        return data_[0] == 0;
    }

    // ITERATORS

    constexpr const char &operator [] (size_t const index) const noexcept{
        assert(index < SIZE);
        return data_[index];
    }

    constexpr const char *begin() const noexcept{
        return data_;
    }

    const char *end() const noexcept{
        return data_ + size();
    }

    // COMPARES

//  int compare(const StringRef &sr) const noexcept{
//      return compare(sr.data(), sr.size());
//  }

    int compare(const char *data, size_t const size) const noexcept{
        assert(data);
        return compare_(data, min__(size));
    }

    int compare(const char *data) const noexcept{
        assert(data);
        return compare_(data, SIZE);
    }

    // EQUALS

//  bool equals(const StringRef &sr) const noexcept{
//      return equals(sr.data(), sr.size());
//  }

    bool equals(const char *data, size_t size) const noexcept{
        assert(data);
        return equals_(data, min__(size));
    }

    bool equals(const char *data) const noexcept{
        assert(data);
        return equals_(data, SIZE);
    }

    // OPERATORS NOT INCLUDED

private:
    // COMPARES / EQUALS HELPERS

    int compare_(const char *data, size_t const size) const noexcept{
        // if data_ is less SIZE, it is null terminated
        return strncmp(data_, data, size);
    }

    bool equals_(const char *data, size_t const size) const noexcept{
        // if data_ is less SIZE, it is null terminated
        return strncmp(data_, data, size) == 0;
    }

private:
    // HELPERS

    constexpr static size_t min__(size_t const size) noexcept{
        return size < SIZE ? size : SIZE;
    }

private:
    char data_[SIZE];
};

// ==================================

template <size_t BYTES>
inline std::ostream& operator << (std::ostream& os, const SmallString<BYTES> &sr){
    // cast because of clang
    //return os.write(sr.data(), static_cast<std::streamsize>( sr.size() ));
    // almost the same, but std::setw() works
    return __ostream_insert(os, sr.data(), static_cast<std::streamsize>( sr.size() ));
}

// ==================================

using SmallString8  = SmallString<8>;
using SmallString16 = SmallString<16>;

I understand I have several constexpr methods, without constexpr c-tor, but this is preparing for the future.

hoffmale · Accepted Answer · 2017-10-30 06:22:32Z

Implementation

SmallString::c_str() does not return a C style string in some cases (e.g. if size() == BYTES), because the final '\0' char is missing.

There is a lot of code duplication in the compare(...) and equals(...) methods that could be eliminated by defaulting parameters (e.g. compare(const char *data, size_t const size = SIZE)). Those six member functions (four public and 2 private) could be reduced to these two:

int compare(const char *data, const size_t size = SIZE) const noexcept {
    assert(data);
    return strncmp(data_, data, min__(size));
}

bool equals(const char *data, const size_t size = SIZE) const noexcept {
    assert(data);
    return compare(data, size) == 0;
}

A lot of the assert calls might be dangerous: They only verify the preconditions in debug builds, but not in release builds. This might be fine in cases where both debug builds and release builds process exactly the same data set, but most of the time, they don't.

Design

I'm missing a constructor from a std::string and comparison functions/operators for other SmallStrings. I expect those would be handy.
There's no simple way to change the contents of a SmallString (other than assigning a new instance with the new values).
The length restriction to 64 characters seems kind of arbitrary. It probably wouldn't fit your original use case to have a "SmallString" of 1000+ characters, but the implementation is effectively an InPlaceString - which could be larger than 64 bytes for other use cases (think binary formats, e.g. for files or network messages).

where is code duplication? equals is written in this way, because for equals, the compiler uses something else than strcmp() . e.g. instead of three way comparison, it do two way comparison. — Nick
– Nick, Commented Oct 30, 2017 at 6:07
@Nick: See my edit, I added a excerpt showing how the code duplication can be reduced/removed. — hoffmale
– hoffmale, Commented Oct 30, 2017 at 6:24
I see what you mean. but i still prefer to have strncmp() != 0 looks more "clear" to me. once again - when compiller sees strncmp() != 0 it does call another non standard function. I know optimizer will still call it, but is not very visible — Nick
– Nick, Commented Oct 30, 2017 at 13:10

Stack Exchange Network

Cache friendly string

1 Answer 1

Implementation

Design

You must log in to answer this question.

Hot Network Questions

Cache friendly string

1 Answer 1

Implementation

Design

You must log in to answer this question.

Related

Hot Network Questions