9 ms·
The biggest advantage of zero-terminated to me is simplicity, next would be efficiency for really small strings - although this is a fringe concern. Strings wit
by jstimpfle 4y ago
The biggest advantage of zero-terminated to me is simplicity, next would be efficiency for really small strings - although this is a fringe concern. Strings with explicit length should at least have a 32-bit length field (maybe 64) IMO - for example, it's common to read files (and store them in contiguous memory) that are larger than 64K.
- jbverschoor 4y agoWell you could easily use the first 4 bits to indicate how many bytes the length is + 1. 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. This gets you a 7-byte = 56bit number, minimal overhead for smaller strings. 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)
- jstimpfle 4y agoThese considerations can make sense when thinking about storage formats (probably you want to compress the string too), but they are not convenient for in-memory representation where you want to get the location of the first character with a simple member access.
- jbverschoor 4y agoIt starts at the start of the frame + the first nibble + 1
- deleted 4y ago[deleted]
- abcd_f 4y agoThe length can be packed, e.g. like utf-8 does it or something similar. The caveat is the cost of unpacking on access, but the memory overhead will be minimal.
- lifthrasiir 4y agoMost memory allocators have an internal fragmentation which removes most efficiency gained by zero-termination. In fact it's worse, because zero-termination means that deallocation can't take a size parameter and it can often cause a performance hit for many modern allocators due to cache misses [1]. [1] https://isocpp.org/files/papers/n3778.html https://isocpp.org/files/papers/n3778.html
- jstimpfle 4y agozero-terminated says nothing about allocation, so there's that.
- lifthrasiir 4y agoYou were talking about [space] efficiency for small strings, which is inherently related to the memory allocation scheme.
- jstimpfle 4y agoWhat? You can allocate zero-terminated strings in .rodata by typing "a string literal" in source code, for example. It's fair to say that there's no fragmentation or whatever and you don't have to think about deallocation either. 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.
- deleted 4y ago[deleted]
- thom 4y agoSDS supports 64-bit lengths. It also dynamically changes the size of its size/flags field to accommodate growth. The minimum overhead is an extra char (same as null termination).