Small string optimisation proof-of-concept | Hacker News Reader

Small string optimisation proof-of-concept

github.com

33 pointsnly8 comments

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...

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

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)

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

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

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;
    }

Just a few days ago there was a lot of discussion here about std::string performance: https://news.ycombinator.com/item?id=8704318

I think refcounted strings are falling out of favor. In a multithreaded environment you need to use atomic ops to maintain the reference count which gets expensive. (folly's fbstring class does use them for large strings though)

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").

Reply on news.ycombinator.com