Hacker News Reader

Comment by billziss | Hacker News Reader

While I often implement strings along the lines you suggest I disagree that this feature belongs in the standard library. For one thing how big (sizeof) should the length prefix be? 16-bits? 32-bits? 64-bits?

The beauty of the C string is that it is minimal and straightforward: if you have a pointer to it, you know where it ends. And it works with pretty much any OS out there.

(My personal variant of dynamic strings are refcounted, length prefixed and nul-terminated with the pointer pointing to the traditional C string.)

View on HN

> For one thing how big (sizeof) should the length prefix be? 16-bits? 32-bits? 64-bits?

size_t, or uintptr_t [1]. Maybe uint32_t, although given pointer alignment, smaller-than-pointer for size doesn't help all that much.

> The beauty of the C string is that it is minimal and straightforward: if you have a pointer to it, you know where it ends.

And if you screw up adding a null byte, client code will happily keep running through the rest of memory to find it. And if your string has embedded nulls, you're SOL anyways.

> And it works with pretty much any OS out there.

And for safety reasons, the OS generally has to assume a maximum length anyways, otherwise, you tend to have security vulnerabilities.

[1] size_t is not necessarily the same size as uintptr_t. An architecture with a 64-bit base pointer shared across several 32-bit indexes is an interesting idea that could use some more programming exploration.

Using size_t as the common solution seems like the way to go.

    struct string { char *data; size_t size; size_t alloc_size; };
    struct string_view { char *data; size_t size; };

And we have the same design that C++ uses.

I do not think I have ever seen a string that needs more than 64K, but then again I do not read whole files in memory in C. (I do in Python.) So this would be wasteful in many cases.

My personal variant uses 32-bits for length and 32-bits for refcount, which aligns well on most platforms, including 64-bit ones.

Something like:

    struct string_header
    {
        int32_t refcnt;
        int32_t length;
        // character content starts here
    };

Given a char pointer to get to the header you must do:

    ((struct string_header *)p)[-1]

How would you use the refcount?

I use the refcount to avoid copying the string when passing it around. I just refcount it instead.

To clarify this is part of a larger library that includes other memory management machinery, such as autorelease pools, etc.

There is no 'I' in standard libraries :)

C++ implementations sometimes optimize for storing short strings inside the string structure itself. One approach looks something like this on 64-bit machines:

    struct string {
        union {
            struct {
                char *ptr;
                size_t capacity;
            };
            char str[16];
        } data;
        size_t length;
    };

It looks complex, but it’s actually a really nice design because it requires no separate allocation for strings less than 16 bytes long, which is a common case, and the strings are relatively compact. And, it stores a capacity parameter which allows you to know when it’s safe to grow the string without allocating, making it possible to implement efficient repeated concatenation.

Why not go full Pascal strings, and go for 8 bit?

The good thing about 64 bit lengths is you never need to worry about overflowing the string. The bad thing is no one know what to do, or codes for the possibility of the string overflowing. 8 bits 'should' avoid people making that assumption.

The was my thought earlier this morning.

Something anything is better than the total shit design we've been living with.

> For one thing how big (sizeof) should the length prefix be? 16-bits? 32-bits? 64-bits?

Exactly like what is returned by strlen... ?

Is your string library open sourced? Could you provide a link?

Reply on news.ycombinator.com