That is how strings use to be stored before C made the choice of using null-terminator. Pascal stored the string size before the string data. The advantage of relying on a terminator symbol is that the string size can be any length where as storing the size at the start forces the string to not exceed certain size.
That, plus you'd be a fool to store a huge string in this way in any case.
Not necessarily. A 64-bit system could give processes an address space that’s significantly larger than half the full 64-bit address space and have an allocator that allows you to allocate a block of more than SIZE_MAX bytes (malloc takes a size_t, but you can use calloc)
The calloc() [1] function mentioned above takes two values of type size_t, and allocates their product bytes.
I'm on mobile without (!) the C99 draft spec but at least the man page gives no such restriction.
However, the standard says (https://en.cppreference.com/w/c/types/size_t):
“size_t can store the maximum size of a theoretically possible object of any type (including array).”
and (https://en.cppreference.com/w/c/language/pointer):
“Pointer is a type of an object that refers to a function or an object of another type, possibly adding qualifiers. Pointer may also refer to nothing, which is indicated by the special null pointer value.”
⇒ pointers must either be null or point to an object, and objects aren’t larger than SIZE_MAX, so I think having a pointer pointing to a block larger than SIZE_MAX violates the standard.
it's simply not possible, by definition.
calloc returns NULL when it's not possible to satisfy the request.
On a quick test on my 64-bit system, a C program doing `printf("%zu\n", SIZE_MAX);` outputs 18446744073709551615, which looks like (2^64)-1 to me.
Or is there a thing in the standard that says this isn't always the case?
> The type ssize_t shall be capable of storing values at least in the range [-1, {SSIZE_MAX}].
[1] https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sy...
Note that neither is ptrdiff_t guaranteed to be that signed version, or to hold any possible value in the domain of size_t or (strictly speaking) any possible object size. Both GCC and Clang assume the latter, though, and can miscompile[3] code that relies on (e.g.) malloc() succeeding for sizes > 2^31 on a 32-bit system.
[1] https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sy...
[2] https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/li...
[3] https://trust-in-soft.com/blog/2016/05/20/objects-larger-tha...
In the same way that since we identify unicode code points with a 16-bit value, it's impossible to include U+1D460 in a string?
In the same way that since Matroska files encode the length of their segments, there's a hard upper limit on the length of a segment?
Of course none of those things is actually true. Storing the string size has no implications for how long the string can be. It requires an amount of space, to store the string size, that is logarithmic in the length of the string, and completely insignificant.
Not a single 16-bit value. Some codepoints are two 16-bit values.
What do you gain in handling short strings from an inability to handle long ones?
Flexible width encoding is more complicated compared to simple member access to get at the first character. And how do you handle construction of a string whose size you don't know yet? You might have to move the string away to make space for a bigger string length field. I don't like it.
I don't think this is true either. It's almost true. But what happens if the string length is 0?
If you make the assumption that you can access the first character of a zero-length string by just grabbing whatever is in memory after the string header, you're going to make the exact mistake the length field is there to stop you from making, a memory access violation. You have to process the length field in order to do any access at all; many strings don't have a first character.
> And how do you handle construction of a string whose size you don't know yet? You might have to move the string away to make space for a bigger string length field.
That's true; you'll either need to be willing to store the character data and the length metadata in separate locations, or you'll need to be willing to occasionally move the data around.
1. Read the first chunk of the string length.
2. Is it more than 0?
1. Read the first chunk of the string length.
2. Did we get the whole thing?
3. Is the length more than 0?
---
Also, it occurs to me that this whole discussion is talking about how to serialize or deserialize a string, when the original discussion is over how the string should be represented in memory.
c0 (0b0000) -> length is 0xc = 12
1341 (0b0001) -> length is 0x134 = 69,940
239a42 (0b0010) -> length is 0x239a42 = 145,828
deadbeaf239a47 (0b0111) -> length is 0xdeadbeaf239a4 = 3917404957718948.
Maybe reserve 0x1111 for future use.
Maybe the other endian makes more sense here, and maybe 0 should mean zero-length.
It's probably not very performant compared to other solutions, but you can just shift 4 bits, and you're done
I'm curious how many strings are allocated at a particular point in time (across everything, kernel, os, apps, etc)
Other popular approaches to allocate strings dynamically would generally group strings of similar lifetime or by size, amortizing possible overheads over many strings.
If your favorite memory allocator requires a size field to support efficient deallocation, then by all means put that in the allocation record. But this is totally orthogonal to the format of a simple string representation.
In fact, in standard Pascal, string handling is extremely rudimentary; there was no way to express "this variable / parameter / pointer refers to a string with a length not known at compile-time".
https://www.iso.org/standard/18237.html
Additionally, Modula-2 was already available in 1978, sorting out all the issues of original Pascal, with all the features needed for a safe systems programming language in the late 70's.
Do you seriously expect in two years left of 70's for Modula-2 to be available everywhere?
But we digress. The topic at hand was "How does Pascal store strings?" I stand by the pedantic statement that ISO Standard Pascal does not require string lengths to be stored with the string (nor anywhere else); there's no way for the programmer to obtain the length of a string at compile-time, never mind run-time, without resorting to some sort of compiler-specific language extension (most (all?) of which did indeed put the string length in front). Conversely, the Extended Pascal standard pretty much requires strings to instead be implemented as "fat pointers," consisting of a length and a pointer to the actual characters. I say this because substring operations return references to pieces of the original string, thus you can't stuff a length in front of the actual characters of the substring, as this would over-write characters in the original string.
Another way to do it is to use:
typedef struct{ size_t allocated; size_t used; char buffer[]; }String;
This lets the header and the string be the same allocation. Thats a huge saving. Its also useful to store the allocation and use size separatly so that you can reuse / modify buffers. The used field lets you use memcpy without looking for string termination.
You can make it even more complex by adding flags if the string is on the stack or on the heap. That way you can do things like:
String buffer = MACRO_TO_CREATE_STRING_BUFFER_ON_STACK(256), *b; b = &buffer;
b = do_processing_with_buffer(&b); // allocates on heap a larger buffer if needed
string_free(b); // frees buffer if its on heap.
The best way to be efficient is often to make assumptions about the data. Most strings don't need any dynamic allocation after having been "built". So it makes a ton of sense to make a string builder API that returns a final string when it's finished. In this way, you save at least the "allocated" member.
The advantage of the simpler method is that it's a representation that works for any string (or substring) that is contiguous in memory, and is completely decoupled from allocation concerns. E.g. I can easily
#define STRING(string_literal) \
((String) { string_literal "", sizeof string_literal - 1 })
String my_string = STRING("Foo bar");
In practice, I find string handling so easy that I rarely even define this struct String. I just pass around strings to functions as two arguments - pointer + size. It feels so light and data flows so easily between APIs, I love it.
A big downside is that you you can't easily take ownership of an existing buffer and treat it as this string type.
string s;
char some_buf[];
string_take(&s, some_buf, some_capacity);
Also you would of course never dynamically allocate string structs, just the data member if needed.
This library takes string slices without having to allocate or copy memory; it seems to be for use cases involving breaking down strings in complex ways, where good ergonomics and efficiency of obtaining a null-terminated C string are secondary.
This has drawbacks:
1. you can't convert an existing buffer to an sds buffer
2. you can't slice into a buffer, because the metadata is part of the string's buffer (even if it's before the pointer)
Counterpoint #1: You can't pass SDS strings to functions that accept `char **` (which is a common way to return a string of unknown length, and often can act as an in-out parameter as well).
Counterpoint #2: You rarely access individual "characters" (whatever this means). It is a conscious decision to whether you should iterate over bytes or Unicode scalar values or code points or grapheme clusters, and for this reason it is better to make the decision explicit even though it's C `char` in the surface level.
I have no evidence for nor against advantage #3 though.
Malloc does this.
One obvious advantage of such scheme of course is that you can pass them as-is to C APIs
It is still single allocation, so the allocation is just as fast.
The pointer is in the same cache line as the string bytes in all strings except for slices (and any other fancy indirect string types). Even though the code fetches indirectly via that pointer, the CPU will be able to fetch the initial string byte efficiently as soon as it has the pointer.
The length-prefix string has a major problem - it cannot be sliced to produce another length-prefix string. It has to be copied. Instead, using a phat pointer (size_t length, char* ptr) works very, very well. We've been using it in D for 20 years.
I've proposed it for C, too:
int x[10];
Sould mean "put 10 ints in memory, and make x the pointer to it.". The thing that messes this up is sizeof. sizeof(x) doesnt give the size of the pointer like it should, it gives you the size of the array. If that was fixed (obviusly it can without breaking everything) then things would be much better and consistent.
But "arrays" definitely are pointers. I put "arrays" in quote because C has nothing I would personally call an array. It’s just contiguous memory allocation. It’s to the point that 10[a] and a[10] are desugared to the same thing.
Come again? Of course it can. It can't be done in place, mind you, but that's a pretty bad way to do any string slicing, regardless of implementation, in a manual memory management environment. Do most programmers expect their slices to result in undefined behavior if they release the larger string they were made from? I doubt it.
Oh come on.. I'm pretty sure Walter meant taking a view kind of slice. Obviously one can always copy part of a string, but that's not what slice implies I think.
> It can't be done in place, mind you, but that's a pretty bad way to do any string slicing, regardless of implementation, in a manual memory management environment.
It's not bad. It's the best, most efficient way. O(1)-ish.
> Do most programmers expect their slices to result in undefined behavior if they release the larger string they were made from? I doubt it.
That's what copy-on-write is for : release of the parent is blocked until no views are left on it.
I made a C String lib using CoW. It works well:
1. don't have to make a copy
2. don't have to scan to find the length
3. don't have to load the string into the cache to find its length
As a bonus, they're memory safe.
I guess the SDS authors might ship a linter to spot all the times you mistakenly use free() instead of sdsfree()? That could make the cleverness more tolerable?
It's pretty weird to see it anywhere other than malloc though especially masquerading as a basic type. It's incompatible with other common patterns like returning via (char *) and you can't identify which deallocator you're supposed to give the result to from the type alone.
https://github.com/antirez/sds
The trick is the size is hidden before the adress of the buffer.("Learn this one simple trick that will change your life for ever").
From the Readme:
```
Advantage #1: you can pass SDS strings to functions designed for C functions without accessing a struct member or calling a function
Advantage #2: accessing individual chars is straightforward.
Advantage #3: single allocation has better cache locality. Usually when you access a string created by a string library using a structure, you have two different allocations for the structure representing the string, and the actual buffer holding the string. Over the time the buffer is reallocated, and it is likely that it ends in a totally different part of memory compared to the structure itself. Since modern programs performances are often dominated by cache misses, SDS may perform better in many workloads.
```