13 ms·
Comparing the Cost of Different Multiple-return Techniques in C
- Tloewald 13y agoWell, I guess the final point is almost worth it -- code for clarity.
- mitchty 13y agoWould've liked to see the exact code to better gauge what clarity involves specifically.
- silentbicycle 13y agoI'm planning on posting a repo with the benchmarks soon.
- mitchty 13y agoCool beans. I saw this this morning and was excited. I've been dealing with rewrites of a few internal utilities in C (was going to use go, but the runtime has issues) and was going to start testing how struct passing with errors in a struct for example would look in C. I'll keep an eye out thanks!
- silentbicycle 13y agoDue to an inconveniently timed cold, it may still be another day or two. Soon.
- silentbicycle 13y agoThe code is up: https://github.com/atomicobject/multiple_return_in_c_benchmarks https://github.com/atomicobject/multiple_return_in_c_benchma...
- justincormack 13y agoThe other method is to change the calling convention and use a different ABI. NetBSD syscalls have multiple return values in registers, although it is little used (pipe returns two args, plus functions that return 64 bits on 32 bit platforms. If you were inventing a new ABI this could be nice. Multiple return values are very idiomatic...
- mikeash 13y agoFrom the ABI perspective, struct returns are multiple return values. ARM64 allows structs to be returned in registers if the struct members are suitable for it.
- justincormack 13y agoI didnt know that. Apparently amd64 lets you return two 64 bit values in registers too, but no more.
- mprovost 13y agoTwo is still an incredibly handy feature. I would guess that the most common case for returning multiple values is data and size, like all the functions that return a string and the length of the string.
- justincormack 13y agoYes. Or the value. error style as used by node.js. forcing errors unto the domain gets messy.
- j_baker 13y agoI'm curious: why are lower numbered benchmarks on the openbsd machine so much slower than higher-numbered benchmarks? Clearly, the machine is older and less powerful than the others, but I wouldn't expect that to alter the timing in this way. Is this a result of the machine, the OS, or the version of the OS?
- silentbicycle 13y agoI'm not sure, and digging into it would likely be a separate post. It's probably due to OpenBSD having very different cache strategies from OSX or Linux. It seemed to consistently do badly on the first run or two, then catch up on on the rest. It's often recommended to throw away the first run in a set of benchmarks, due to the added overhead of disk IO, but I wanted to retain that because something interesting is going on there. The graphs also show more overhead for returning a struct with additional padding. OpenBSD's memory allocator favors security rather than speed, and the extra size may have costs for buffer overruns felt elsewhere. I like testing C code on OpenBSD -- it's almost as good as valgrind for detecting memory bugs, but with significantly less overhead, since the memory checking is integrated into the OS.
- evmar 13y agoHere's a post where I walk through the assembly generated by some different approaches. http://neugierig.org/software/blog/2011/12/return-by-value.html http://neugierig.org/software/blog/2011/12/return-by-value.h... One possibility is that OpenBSD uses the alternative ABI for returning structs mentioned in that post.
- silentbicycle 13y agoThe code for the benchmarks is up, if you want to investigate: https://github.com/atomicobject/multiple_return_in_c_benchmarks https://github.com/atomicobject/multiple_return_in_c_benchma...
- hepek 13y agoReminded me of a very good book called "21st Century C" http://shop.oreilly.com/product/0636920025108.do http://shop.oreilly.com/product/0636920025108.do
- eropple 13y agoSorry, but I seriously have to disagree: 21st Century C is one of the worst tech books I've had the misfortune to read. It's written by a butthurt C devotee whose interest is as much in sneering at other languages as it is in teaching something. It argues brace styles and text editors. It's loaded with inaccuracies. It can't be bothered to mention when it's using a header file to introduce a function. Typos abound. It seriously, without the slightest trace of humor, includes a chapter called "Becoming a Better Typist." It's just...crap. I stopped buying O'Reilly books after I couldn't get a refund for this mess. This article is by clueful professionals. That book is everything except that.
- mitchty 13y agoAre you reading the same book as me, there is NO (FULL STOP) chapter named becoming a better typist. There is a note with that title at page 100 (ebook not sure on book), its also 4 short paragraphs long. Is the entire book great? No, to be honest it touched too little on the C side for me, and yeah the punk analogies was a bit annoying at times, but it did get me to look critically at how I wrote c. Much like this blog I'm writing for clarity first and not optimization. What would you recommend for a c programming book instead of this book?
- eropple 13y agoSorry, yeah, it was a section, not a chapter. My bad. Its existence is still stupid and is a good anecdote regarding the book's lack of focus. I haven't yet found a decent C book. I've found many good C++ books and have backported the lessons I've learned there into C, however.
- mitchty 13y ago
- acqq 13y agoI don't see the description of the most obvious (to this old C programmer) approach: if your function "returns multiple values" it probably should be rewritten to operate on a struct. Once you recognize that, you'd probably discover that you'll be able to use the same struct in more other functions, and that you'd need just to pass a single pointer to that stuct around, significantly reducing the overhead of a lot of parameter passing.
- dmlorenzetti 13y agoOne of the methods tested was mutate-struct -- Dereference a struct pointer and mutate both its fields.
- acqq 13y agoThanks. I haven't seen the description under "Three Common Techniques." And I also claim that the benchmarking isn't giving the method the due justice as the benefits of it can be visible only in the context where you really do operate with more functions on the same structures. Moreover, I think it's better to simply know how the C is translated to the assembly then to measure one very limited example. Specifically, some optimizations avoid calling functions at all. But the measurements of such examples don't properly reflect the behavior in bigger programs, where it can be bigger performance benefit to have smaller code than a fast microbenchmark.
- klipt 13y ago> Once you recognize that, you'd probably discover that you'll be able to use the same struct in more other functions And now you've reinvented (the basic premise of) OOP!
- acqq 13y agoI don't see that in "Fundamental features and concepts" of OOP. http://en.wikipedia.org/wiki/Object-oriented_programming#Fundamental_features_and_concepts http://en.wikipedia.org/wiki/Object-oriented_programming#Fun... Let's stay on topic, talking about C. We'll avoid philosophy and hype and will keep talking about the work being done in C.
- MichaelGG 13y agoWhen compiling at full optimization and link-time code gen optimization, will the compiler and linker "get smart" about passing structs around? I'm inexperienced here, but it always seemed odd that a struct with two words can't just be shoved into registers (calling or returning). Is there a reason the x86/64 ABIs don't specify such a way? Also, it seems that the 128-bit and larger registers aren't used as often to pass values. For something like a GUID, wouldn't they be a perfect fit? Or does the processor optimize stack handling so that it's almost as cheap as registers?
- vinkelhake 13y agoWith full optimizations and LTO, the compiler may very well decide to inline a function. When a function is inlined, nothing is really "passed". That said, structs can absolutely be passed by registers. I whipped up a quick example that shows a simple 2-word struct being passed in two registers on x86-64: http://goo.gl/2Yxooe http://goo.gl/2Yxooe On x86-64, the SSE registers are used to pass floating point parameters.
- pcwalton 13y agoIn LLVM, internalized functions (which get created in LTO mode) are converted to fastcall. So yes, the ABI becomes smarter in that case. The platform ABIs mostly are the way they are for backwards compatibility at this point. They aren't particularly efficient and have weird corner cases (e.g. complex numbers are treated differently than the equivalent struct, IIRC). On x86-64 the situation is a little better, but still not ideal.
- pmjordan 13y agoThe x86-64 ABI does specify for multi-word structs to be returned in registers. If I remember correctly, it's up to 4 registers - rax, rdx and 2 others which I'll need to look up. This only happens if the struct fields on their own would be returned in this way, so an array of 16 chars would not typically be returned in 2 8-byte registers. To use SSE or AVX registers for anything other than float or double scalars, you'll need to use the special vector types. I think x86 lets you return in eax and edx, but only if you're returning a single 64-bit value, not a struct with 2 32-bits. Not 100% on all of this.
- IsTom 13y agoWas the data allocated on stack or heap when using pointers? I would assume the later as it's not stated explicitely and perhaps there is something to win here for short-lived values.
- theoh 13y agoWhy not just write everything in Continuation Passing Style? (joke)
- silentbicycle 13y agoThat's why I mentioned compiling SML to C, actually. :) It's worth evaluating costs for what generated C looks like when something else (SML, Chicken Scheme, etc.) is compiling its constructs to C, just as much as it is for what people will typically write.
- andrewla 13y agoAs with all benchmarks, without standard deviations, or, preferably, the complete test data, it is meaningless to attempt to infer anything from this data.
- silentbicycle 13y agoYeah, I'm planning on posting the benchmark source, but between Christmas, a rather nasty ice storm, and a bad cold, I'm a bit behind. It will be up in a few days.
- wyager 13y agoHow feasible is it to change the C standard to allow for implicit struct unpacking? So if I have `point foo(void)`, I can do `x, y, z = foo()`. It seems like it would work well with the many ABIs that return small structs in registers.
- deleted 13y ago[deleted]
- Peaker 13y agoIIRC the ARM ABI for C actually uses an implicit output parameter for a returned struct - so it's identical to passing the output parameters manually.