News for hackers. Stuff that matters.
Re:How to implement strings by rwmj on Saturday November 03, 2018 @05:25PM (#18372556)
Another idea is the OCaml string representation which is a sort of cross between C and Pascal. I wrote about it in [1]. It allows O(1) length, can store \0 in the string, while being backwards compatible with existing C-string-consuming functions.

It's applicable to C because most realistic implementations of malloc(3) store the size of the malloc'd area to the nearest word[2] and so the Pascal size part does not need to be stored explicitly. (Note this would require minor changes to the C runtime to allow malloc to make explicit the currently implicit size).

[1] https://rwmj.wordpress.com/2009/08/05/ocaml-internals-part-2...

[2] https://rwmj.wordpress.com/2016/01/08/half-baked-ideas-c-str...

Re:How to implement strings by ric129 on Sunday November 04, 2018 @07:47AM (#18375603)
>It's applicable to C because most realistic implementations of malloc(3) store the size of the malloc'd area to the nearest word[2]

This is not so true anymore, and I'd be very careful with that sort of tricks. While the default memory allocator on most distributions (ptmalloc2) still probably works like that, there are other memory allocators in use like jemalloc/tcmalloc, which store metadata for a group of blocks (e.g all equal-sized blocks in a page) rather than for every single block.

Like Asooka wrote, you can malloc_usable_size(), if available. But have in mind that malloc_usable_size() returns the size of the block that malloc has given you, which can be _larger_ than the size you requested, as many memory allocators round block sizes up.

I actually wrote a memory allocator that works that way: https://github.com/ricleite/lrmalloc

Re:How to implement strings by Asooka on Saturday November 03, 2018 @06:02PM (#18372741)
You can get the size of a malloc'd block with malloc_usable_size. Can't say if it's actually O(1) though.
Re:How to implement strings by jws on Saturday November 03, 2018 @07:38PM (#18373109)
You had my hopes up for a minute there, until I checked portability…

malloc_usable_size() is a GNU extension, so usable on Linux. MacOS has malloc_size().

One web page [1] says the GNU one is about 10 cpu cycles and the MacOS one is about 50 cpu cycles, so not the end of the world, but maybe a little long for string length checking.

I didn’t check any BSDs and I have to wonder what the effect of changing allocators in Linux has. Certainly they could have a performance impact and possible a ‘does not implement’ problem.

[1] https://lemire.me/blog/2017/09/15/how-fast-are-malloc_size-a...