4 ms·

Small string optimisation proof-of-concept

33 points by nly 12y ago

aetherspawn 12y ago
Looks like this from 2009: http://tulrich.com/rants-2009.html#d2009-01-03T00:00:00Z http://tulrich.com/rants-2009.html#d2009-01-03T00:00:00Z
- nly 12y 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 12y 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.h#L273 https://github.com/facebook/folly/blob/master/folly/FBString...
jhallenworld 12y 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..).
- bodyfour 12y 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
  - jhallenworld 12y 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; }
    - bodyfour 12y ago
      Just a few days ago there was a lot of discussion here about std::string performance: https://news.ycombinator.com/item?id=8704318 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)
Dewie 12y 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").

33 points by nly 12y ago

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

nly 12y 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 12y 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.h#L273 https://github.com/facebook/folly/blob/master/folly/FBString...

jhallenworld 12y 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..).

bodyfour 12y 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
- jhallenworld 12y 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; }
  - bodyfour 12y ago
    Just a few days ago there was a lot of discussion here about std::string performance: https://news.ycombinator.com/item?id=8704318 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)

Dewie 12y 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").