Small string optimisation proof-of-concept

https://github.com/elliotgoodrich/SSO-23/blob/master/README.md

by nly • 12 years ago

33 8 12 years ago

Looks like this from 2009: http://tulrich.com/rants-2009.html#d2009-01-03T00:00:00Z

nly• 12 years ago

Not quite, that implementation adds an extra flag field, so isn't space efficient (it's 4 words instead of 3, which is suboptimal for long strings)

ot• 12 years ago

FBString in folly also stores at most 23 characters in-place, and it's a widely used implementation (at least within Facebook :) )

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

jhallenworld2• 12 years ago

I'm surprised that malloc doesn't round the 24 byte object up to 32 bytes (no matter what sizeof(std::basic_string) says..).

bodyfour2• 12 years ago

Remember that std::string can be on the stack or a member of a larger structure.

These comparisons seem to all be against versions of std::string that keep size/capacity inside the std::string, not ones (like the default GCC one) that keep those members adjacent to the character data itself

jhallenworld2• 12 years ago

Well that's a whole other topic: does your string library support copy on write or not? If you have mostly short strings and SSO you are better off without copy on write.

My string class has copy on write, including splicing- so it uses the most space.. I'm sure it's not really worth it (It also supports string semi-predicates: you can safely return NULL as a string and test for it- I sure wish they had this in the standard library).

  struct Stringraw
    {
    int ref;              // Reference count
    int len;              // String length  
    // String data starts here
    };

  class String
    {
    Stringraw *raw;       // Pointer to possibly shared malloc block holding string
    char *s;              // Start of string in raw
    int len;              // Length of string
  . . .

  // Sub-string
  inline String substr(int start,int size) const
    {
    String x;
    x.s=s+start;
    x.len=size;
    x.raw=raw;
    ++raw->ref;
    return x;
    }

Dewie• 12 years ago

Does there exist a similar optimization for arbitrary size integers? Like using the pointer that is supposed to point to something like an array of ints, instead store the int itself (with a bit of bit twiddling to make room for a flag that says that "this is an integer; don't use me as a pointer").

Small string optimisation proof-of-concept

Related Stories