Hacker News Reader

Comment by vertex-four | Hacker News Reader

Note that this pattern[0] is essentially "copy-on-write", which can be encapsulated safely as such in a reasonably simple type (in a language with generics) and used elsewhere. I use a similar mechanism pervasively in some low-level web server code to use references into the query string, body and JSON objects directly when possible, and allocated strings when not.

[0] https://github.com/curl/curl/commit/5f1163517e1597339d

View on HN

But why not use alloca instead of always allocating 10 elements on the stack you might not need?

Edit: I would also be tempted to remove the ufds_on_stack variable and just check if the ufds pointer points to the stack or not.

Because always allocating them on the stack costs zero cycles in the typical case, while alloca costs more than zero cycles in the typical case. And assuming that "struct pollfd" isn't big, and the function isn't very recursive, there's no practical downside to wasting a little stack space for the life of the function.

(Of course, he could get rid of "bool ufds_malloc" and just see if his pointer is NULL before calling free(); or not even bother checking, since free(NULL) is defined to be a no-op.)

`alloca` is a simple addition to the stack pointer, so a single instruction, presuming it isn't folded into the normal bump of the stack pointer to allocate the fixed size local variables. There isn't really much cost to doing a dynamic stack allocation rather than a fixed one. Variable length arrays (VLAs) allow the same thing but can be slightly more portable.

Normal C caveats do apply here though: alloca is POSIX, not C (but is widely implemented outside of POSIX systems). VLAs are an optional standard feature. Neither is required to actually use the stack for storage.

Not sure if there are any platforms supported by curl which would prevent it's use of VLAs or alloca.

tl;dr - alloca costs, history, and why it is problematic

Alloca is somewhat more expensive on x86/x64 than a single instruction.

[0] shows the code generation for four functions that generate and sum an iota array. I used -O1 to make the differences more apparent.

iota_sum_alloca and iota_sum_vla generate similar code. They both require a frame pointer (RBP) and code to preserve the 16 byte alignment of the stack frame.

iota_sum_const_alloca and iota_sum_array generate identical code. Clang recognizes that alloca is invoked with a constant argument.

History of Alloca

Alloca was originally written for unix V7 [1]. Doug Gwyn wrote a public domain implementation [2] in the early 80s for porting existing programs. The FSF used Gwyn's alloca implementation in GDB, Emacs, and other programs. This helped to spread the idea.

Problems of Alloca

[3] is a comp.compilers thread that discusses some of the issues with alloca. Linus does not want either VLAs or alloca in the Linux kernel [4].

References:

[0] https://godbolt.org/g/1JyXhQ

[1] http://yarchive.net/comp/alloca.html

[2] https://github.com/darchons/android-gdb/blob/android-gdb_7_5...

[3] http://compilers.iecc.com/comparch/article/91-12-079

[4] https://groups.google.com/forum/#!msg/fa.linux.kernel/ROgkTB...

Edited for minor formatting changes.

https://godbolt.org/g/XKAZOb fixes the bugs in the sample code in the parent post.

If you compile with -O2 then iota_sum_const_alloca and iota_sum_array are both evaluated at compile time.

Also, because curl is c89-portable, and alloca might fail on the portability standpoint.

Statically allocating stack memory is essentially free in environments with enough memory - you just subtract a little more from your stack pointer. Alloca is not standard C - it might not even be available in some compilers that curl compiles on.

> Alloca is not standard C

A similar option is a variable-length array, which is standard C. It does share the problem of not being available in some compilers, however.

That said, there are other problems with alloca/VLAs. For small enough sizes, like you said it's faster and simpler to statically allocate. For large enough sizes, you risk overflowing the stack, which might be more constrained than you'd expect (especially when using threads). There might be a sweet spot where it's better, but it's not worth the portability cost and the potential headaches.

Note that variable-length arrays ended up being a particularly troublesome feature, and were therefore made optional in C11. It's still "standard," but a compliant compiler is allowed not to support them, so it might as well not be.

Reply on news.ycombinator.com