Re: Segments

On 17/01/2025 03:10, MitchAlsup1 wrote:

On Fri, 17 Jan 2025 1:04:03 +0000, Keith Thompson wrote:
 

mitchalsup@aol.com (MitchAlsup1) writes:

On Thu, 16 Jan 2025 23:18:22 +0000, Keith Thompson wrote:

Terje Mathisen <terje.mathisen@tmsw.no> writes:
[...]

I do know that several people have created fast string libraries,
where any string that is short enough ends up entirely inside the dope
vector, so no heap allocation.

>
Some implementations of C++ std::string do this.  For example, the GNU
implementation appears to store up to 16 characters (including the
trailing null character) in the std::string object.

>
Why use an 8-byte pointer to store a string 16 or fewer bytes long ? !!

>
I don't understand.  What pointer are you referring to?

 The pointer which would have had to point elsewhere had the string
not been contained within.
 

There are a couple of ways you can do "small string optimisation".  One would be to have a structure something like this :
struct String1 {
size_t capacity;
char * data;
char small_string[16];
}
Then "data" would point to "small_string" for a capacity of 16, and if that's not enough, use malloc to allocate more space.
An alternative would be to have something like this (I'm being /really/ sloppy with alignments, rules for unions, and so on - this is illustrative only, not real code!) :
struct String2 {
bool is_small;
union {
char small_string[31];
struct {
size_t capacity;
char * data;
}
}
}
This second version lets you put more characters in the local small_string area, reusing space that would otherwise be used for the pointer and capacity.  But it has more runtime overhead when using the string :
void print1(String1 s) {
printf(s.data);
}
void print2(String2 s) {
if (s.is_small) {
printf(s.small_string);
} else {
printf(s.data);
}
}
There are, of course, many other ways to make string types (such as supporting copy-on-write), but I suspect that Mitch is thinking of style String2 while Keith is thinking of style String1.

In the implementation I'm referring to, std::string happens to be 32
bytes in size.  If the string has a length of 15 or less, the string
data is stored directly in the std::string object (in the last 16 bytes
as it happens).  If the string is longer than that it's stored
elsewhere, and that 16 bytes is presumably use to manage the
heap-allocated data.