7 ms·

The Cost of a Closure in C: The Rest

66 points by ingve 10mo ago

andsoitis 10mo ago
> Cost of a Closure in C C does not have closures. You could simulate closures, but it is neither robust not automatic compared to languages tha truly support them.
- aragilar 10mo ago
  C does not currently have closures, the post it looking at their performance properties with an eye for what form closures should be added to the standard.
- skavi 10mo ago
  I think maybe this post would make more sense if you were familiar to its antecedent [0] which compares existing closure extensions to C. IIRC the comparison was in the context of considering designs for standardization. [0]: https://thephd.dev/the-cost-of-a-closure-in-c-c2y https://thephd.dev/the-cost-of-a-closure-in-c-c2y
- pjmlp 10mo ago
  Completely missed the point of the article, this is about ongoing C2y efforts at WG14.
- flohofwoe 10mo ago
  The post is about a potential new feature of C. The author is working on the C committee and has contributed new C features in the past.
userbinator 10mo ago
Those graph axes units are... perplexing, to say the least. So, we need to swap to the logarithmic graphs to get a better picture I wish more people would know about decibels.
- throw_await 10mo ago
  Logarithmic axes are inifinitely better than decibels, because dB are just to overloaded semantically
- Someone 10mo ago
  >> So, we need to swap to the logarithmic graphs to get a better picture > I wish more people would know about decibels. Huh? Is there any difference? https://en.wikipedia.org/wiki/Decibel https://en.wikipedia.org/wiki/Decibel: “The decibel […] expresses the ratio of two values of a power or root-power quantity on a logarithmic scale”
Panzerschrek 10mo ago
Why struggling using qsort? std::sort from C++ is much better in terms of usability and performance.
- pjmlp 10mo ago
  Because some people will never move beyond C, no matter what.
  - tliltocatl 10mo ago
    People will never move beyond C (among other reasons) because C allows precise control over memory allocation. Closures and precise control over memory allocation doesn't play very well together.
    - spacechild1 10mo ago
      > Closures and precise control over memory allocation doesn't play very well together. How so? In C++ a lambda is just a regular type that does not allocate any memory by itself. You have in fact precise control over how/where a lambda is allocated.
      - flohofwoe 10mo ago
        True, but once a capture needs to survive the parent function scope you'll need to store it somewhere, either via a std::function object which has opaque rules on whether a heap allocation happens or via your own std::function implementation where you define the heap allocation rules but then will have to face discussions about why you're rewriting the stdlib ;) Any C implementation of capturing lambdas has the same problem of course, that's why the whole idea doesn't really fit into the C language IMHO.
        fuhsnn 10mo ago
        I did a version with explicit capture objects for fun: https://github.com/fuhsnn/c-extensions#extended-capture https://github.com/fuhsnn/c-extensions#extended-capture Basically, with each capturing lambda, a context type _Ctxof(fn) is created that users can then declare on stack or on heap themselves.
djaouen 10mo ago
Lisp solves the performance hit of closures with macros. However, given what macros look like in C, I hope it never amounts to that!
- skavi 10mo ago
  There’s no necessary performance hit for closures. The performance cost here is caused by these closures needing to conform to a function pointer looking interface in order to be generally useful in C.
  - djaouen 10mo ago
    Iirc, in Lisp, closures are heap-allocated, unless they are created at compile-time with macros. Therefore, there is the added overhead of malloc and free calls with each closure created. Am I wrong here?
    - BoingBoomTschak 10mo ago
      Yes, in that normal closures being stack or heap allocated is an implementation detail; at least in CL. SBCL can stack allocate some closures if DYNAMIC-EXTENT is used: https://www.sbcl.org/manual/#Stack-allocation-1 https://www.sbcl.org/manual/#Stack-allocation-1
      - deleted 10mo ago
        [deleted]
      - pfdietz 10mo ago
        Or I believe if it can determine the closure has dynamic extent, for example if it's passed to a standard function for which it knows the closure will not escape.
        BoingBoomTschak 10mo ago
        Indeed, it's newish (from this summer https://github.com/sbcl/sbcl/releases/tag/sbcl-2.5.6 https://github.com/sbcl/sbcl/releases/tag/sbcl-2.5.6) and mainly thanks to C. Zhang's work. https://github.com/sbcl/sbcl/commit/021414445224e692ebb9c48c0505b0c1ffc10669 https://github.com/sbcl/sbcl/commit/021414445224e692ebb9c48c... https://github.com/sbcl/sbcl/commit/2c56c5901df1a5ea98ae19e966ec9315be3ebfb9 https://github.com/sbcl/sbcl/commit/2c56c5901df1a5ea98ae19e9...
uecker 10mo ago
Since it mentions my paper again: "It also brings into question whether a “lean” approach that grabs the “environment pointer” or the “stack frame” pointer directly, as in n3654 is a good idea to start with." which is annoying since the approach promoted in n3654 is not even tested here. At least he continues with "But, it’s premature to condemn n3654 because it’s unknown if the problem is the fact that the use of accessing variables through what is effectively __builtin_stack_address and a trampoline is why performance sucks so bad, or if it’s the way the trampoline screws with the stack". So why insinuating it when you have no idea? It is well known that the trampoline approach is costly, and it seems particular bad on arm. But n3654 does not promote trampolines and instead wide function pointers which is similar to std::function_ref, but without wasting the static chain register and avoiding the need to create a thunk when converting a regular function pointer. I am also not entirely sure whether "manorboy" is a good benchmark, but for estimating the function call overhead it should be ok. For the access to variables part, other considerations are far more important IMHO. So I am not sure I would put too much weight on the accessing "k" part of the post. n3654 contains a criticism of the lambda approach from a language-design perspective. The issue is that it seems not to be a good fit for C. Copying values is always cheap, but this obviously works in toy examples but not necessarily for interesting data structures. In C++ you could then capture a pointer as a value, but then you haven't avoided an indirection either. In general, this is fine in C++ as smart pointer than deal with the memory management, but in C having a captured value in a lambda you can not have explicit access to anymore does not make too much sense. The "unfortunately, is that unlike C++ there are no templates in C" is also interesting. I fled from C++ back to C exactly because of templates. In a performance context, the fallacy is that you can always create super-optimized code using compile-time techniques that absolutely shines in microbenchmarks (such as this one) but cause a lot of bloat on larger scale (and long compilations times). If you want this, I think you should stick to C++.
- dfawcus 10mo ago
  Well his "Normal Functions" (benchmarks/closures/source/normal_functions.cpp in his repo) looks quite similar to what I had with my GNU nested functions using a stand in "wide pointer", and hence no generated trampoline. (https://news.ycombinator.com/item?id=46243298 https://news.ycombinator.com/item?id=46243298) Which rather suggests to me that such a scheme, but generated by the compiler, should have a similar performance to said "Normal Functions" and hence similar to his preferred lambda form. Since his benchmark environment is so unwieldy, I may have a go at extracting those two code sets to a standalone environment, and measure them so see...
greatgib 10mo ago
This article is so badly written, it makes it hard to understand something that should be easy to understand...

66 points by ingve 10mo ago

> Cost of a Closure in C C does not have closures. You could simulate closures, but it is neither robust not automatic compared to languages tha truly support them.

aragilar 10mo ago
C does not currently have closures, the post it looking at their performance properties with an eye for what form closures should be added to the standard.
skavi 10mo ago
I think maybe this post would make more sense if you were familiar to its antecedent [0] which compares existing closure extensions to C. IIRC the comparison was in the context of considering designs for standardization. [0]: https://thephd.dev/the-cost-of-a-closure-in-c-c2y https://thephd.dev/the-cost-of-a-closure-in-c-c2y
pjmlp 10mo ago
Completely missed the point of the article, this is about ongoing C2y efforts at WG14.
flohofwoe 10mo ago
The post is about a potential new feature of C. The author is working on the C committee and has contributed new C features in the past.

userbinator 10mo ago

Those graph axes units are... perplexing, to say the least. So, we need to swap to the logarithmic graphs to get a better picture I wish more people would know about decibels.

throw_await 10mo ago
Logarithmic axes are inifinitely better than decibels, because dB are just to overloaded semantically
Someone 10mo ago
>> So, we need to swap to the logarithmic graphs to get a better picture > I wish more people would know about decibels. Huh? Is there any difference? https://en.wikipedia.org/wiki/Decibel https://en.wikipedia.org/wiki/Decibel: “The decibel […] expresses the ratio of two values of a power or root-power quantity on a logarithmic scale”

Panzerschrek 10mo ago

Why struggling using qsort? std::sort from C++ is much better in terms of usability and performance.

pjmlp 10mo ago
Because some people will never move beyond C, no matter what.
- tliltocatl 10mo ago
  People will never move beyond C (among other reasons) because C allows precise control over memory allocation. Closures and precise control over memory allocation doesn't play very well together.
  - spacechild1 10mo ago
    > Closures and precise control over memory allocation doesn't play very well together. How so? In C++ a lambda is just a regular type that does not allocate any memory by itself. You have in fact precise control over how/where a lambda is allocated.
    - flohofwoe 10mo ago
      True, but once a capture needs to survive the parent function scope you'll need to store it somewhere, either via a std::function object which has opaque rules on whether a heap allocation happens or via your own std::function implementation where you define the heap allocation rules but then will have to face discussions about why you're rewriting the stdlib ;) Any C implementation of capturing lambdas has the same problem of course, that's why the whole idea doesn't really fit into the C language IMHO.
      - fuhsnn 10mo ago
        I did a version with explicit capture objects for fun: https://github.com/fuhsnn/c-extensions#extended-capture https://github.com/fuhsnn/c-extensions#extended-capture Basically, with each capturing lambda, a context type _Ctxof(fn) is created that users can then declare on stack or on heap themselves.

djaouen 10mo ago

Lisp solves the performance hit of closures with macros. However, given what macros look like in C, I hope it never amounts to that!

skavi 10mo ago
There’s no necessary performance hit for closures. The performance cost here is caused by these closures needing to conform to a function pointer looking interface in order to be generally useful in C.
- djaouen 10mo ago
  Iirc, in Lisp, closures are heap-allocated, unless they are created at compile-time with macros. Therefore, there is the added overhead of malloc and free calls with each closure created. Am I wrong here?
  - BoingBoomTschak 10mo ago
    Yes, in that normal closures being stack or heap allocated is an implementation detail; at least in CL. SBCL can stack allocate some closures if DYNAMIC-EXTENT is used: https://www.sbcl.org/manual/#Stack-allocation-1 https://www.sbcl.org/manual/#Stack-allocation-1
    - deleted 10mo ago
      [deleted]
    - pfdietz 10mo ago
      Or I believe if it can determine the closure has dynamic extent, for example if it's passed to a standard function for which it knows the closure will not escape.
      - BoingBoomTschak 10mo ago
        Indeed, it's newish (from this summer https://github.com/sbcl/sbcl/releases/tag/sbcl-2.5.6 https://github.com/sbcl/sbcl/releases/tag/sbcl-2.5.6) and mainly thanks to C. Zhang's work. https://github.com/sbcl/sbcl/commit/021414445224e692ebb9c48c0505b0c1ffc10669 https://github.com/sbcl/sbcl/commit/021414445224e692ebb9c48c... https://github.com/sbcl/sbcl/commit/2c56c5901df1a5ea98ae19e966ec9315be3ebfb9 https://github.com/sbcl/sbcl/commit/2c56c5901df1a5ea98ae19e9...

uecker 10mo ago

Since it mentions my paper again: "It also brings into question whether a “lean” approach that grabs the “environment pointer” or the “stack frame” pointer directly, as in n3654 is a good idea to start with." which is annoying since the approach promoted in n3654 is not even tested here. At least he continues with "But, it’s premature to condemn n3654 because it’s unknown if the problem is the fact that the use of accessing variables through what is effectively __builtin_stack_address and a trampoline is why performance sucks so bad, or if it’s the way the trampoline screws with the stack". So why insinuating it when you have no idea? It is well known that the trampoline approach is costly, and it seems particular bad on arm. But n3654 does not promote trampolines and instead wide function pointers which is similar to std::function_ref, but without wasting the static chain register and avoiding the need to create a thunk when converting a regular function pointer. I am also not entirely sure whether "manorboy" is a good benchmark, but for estimating the function call overhead it should be ok. For the access to variables part, other considerations are far more important IMHO. So I am not sure I would put too much weight on the accessing "k" part of the post. n3654 contains a criticism of the lambda approach from a language-design perspective. The issue is that it seems not to be a good fit for C. Copying values is always cheap, but this obviously works in toy examples but not necessarily for interesting data structures. In C++ you could then capture a pointer as a value, but then you haven't avoided an indirection either. In general, this is fine in C++ as smart pointer than deal with the memory management, but in C having a captured value in a lambda you can not have explicit access to anymore does not make too much sense. The "unfortunately, is that unlike C++ there are no templates in C" is also interesting. I fled from C++ back to C exactly because of templates. In a performance context, the fallacy is that you can always create super-optimized code using compile-time techniques that absolutely shines in microbenchmarks (such as this one) but cause a lot of bloat on larger scale (and long compilations times). If you want this, I think you should stick to C++.

dfawcus 10mo ago
Well his "Normal Functions" (benchmarks/closures/source/normal_functions.cpp in his repo) looks quite similar to what I had with my GNU nested functions using a stand in "wide pointer", and hence no generated trampoline. (https://news.ycombinator.com/item?id=46243298 https://news.ycombinator.com/item?id=46243298) Which rather suggests to me that such a scheme, but generated by the compiler, should have a similar performance to said "Normal Functions" and hence similar to his preferred lambda form. Since his benchmark environment is so unwieldy, I may have a go at extracting those two code sets to a standalone environment, and measure them so see...

greatgib 10mo ago

This article is so badly written, it makes it hard to understand something that should be easy to understand...