Hacker News Reader

Comment by charcircuit | Hacker News Reader

No mention of just having the caller do allocation?

That isn’t efficient in cases where the caller cannot know the size to allocate up front. For example:

To use sprintf, you’d have to guess at the buffer size to pass in, or suffer a buffer overflow.

snprintf is a bit better in that you can recover from passing a buffer that’s too small, but still either requires you to be generous in sizing the buffer, or accept that you often call snprintf twice, doing double work.

The way around that is to pass a pointer to an allocation routine, but that’s a simple form of the allocator interface that this article favors.

>That isn’t efficient in cases where the caller cannot know the size to allocate up front

This can typically be avoided though. With your sprintf example you could have one function that does the first half that calculates the size and then a second function that does the second half that actually copies into the destination buffer. Alternatively if you want to use realloc you could have a function like snprintf which allows resuming from where it ran out of space.

This strategy, while is worth mentioning as another separate post, can only be applied to simple interfaces. A whole API can be much larger and can't avoid allocations inside. There are some cases where the whole API was carefully designed to avoid such allocations, but it is difficult and not always suitable for users.

For the first idea: Yes, but both of those would have to interpret the format string and determine the character lengths of the arguments which is duplicated work. I'd imagine its a large portion of the work. I'm not convinced its any more efficient than snprintf.

The second idea is neat though... it could return an extra argument which is a pointer to the first part of the format string that wasn't printed

A more realistic version of the former is that the call is opportunistically given a buffer and returns an error with the required buffer size if the buffer is too small. If the buffer is big enough you only need a single call, otherwise you need two calls with a redundant processing, which is better then the original version---this even works when the caller can't preallocate a buffer. This approach is pretty common in the Windows API.

----

ADDED: I thought charcircuit was talking about always calling two functions in a row, missing the original comment that charcircuit was replying to. My bad, so I'd like to update this comment as follows...

I think the former approach would indeed work if the first call is always given a pointer to the space that can be used to record what has been done so far. Like, `snprintf(ptr, n, &recover, "format", ...)`, and `recover` can be relatively small, like 16 bytes. I would record original `ptr` and `format` arguments to be safe, and largest offsets to `ptr` and `format` that are known to be written and synchronized to each other. Of course this is just a workaround for C's inability to construct and return a sum type.

? This is exactly how snprintf works, which is what we're discussing.

Oh wait, I missed the original comment. I see what did you actually mean there.

>which is duplicated work

The caller can allocate memory to be shared between the 2 function calls to avoid needing duplicate work

How do you know how much memory you need to allocate when you need to do the work in the first place to determine it? Maybe if snprintf was resumable by supplying a larger buffer while it was doing its work, but this seems like a lot of complexity.

In this case the state takes a constant amount of space so it is just a matter of allocating a single struct.

With the approach of having the caller allocate you have carefully design the API to make it possible.

What if the function does more than a single allocation? Imagine a library like libxml2 that can parse a whole XML document into a DOM tree. In many cases you it would be nice to just pass an arena allocator and throw away the whole DOM in one go. Unfortunately libxml2's allocator customization kinda sucks and it's not easy to do.

You can still do something like the original article describes.

Sure, that's what I was getting at. Being able to pass stateful allocators as function arguments is very flexible.

This is about the case when the caller can’t know how much memory to allocate but is able to provide an estimate for most cases. Either it becomes possible to avoid repeated allocation and make deallocation faster, or another classic dynamic allocator can be asked for additional memory for outlier cases.

If the lifetime of the allocation works out this can end up with a nice pattern of "try to use a cheap stack buffer, and fall back to a more expensive heap allocation when that fails"

If you click the link in the first sentence it brings you to an article about that.

"Just"

Reply on news.ycombinator.com