1
$\begingroup$

Disclaimer: I'm not a compiler expert, but some of my best friends are! :)

I do a lot of embedded systems programming where stack (and other memory) is limited. Most of my code is written in gcc, so I thought nested functions could be useful for reducing stack usage. Here's an example of what I had in mind:

(Though the algorithm isn't important for this question, assume that list_traverse takes a pointer to a list head and a function. The contains_aux() function gets called with each element in turn.)

bool list_contains(list_t *head, list_t *item) {
  bool found = false;
  void contains_aux(list_t *list) {
    if (list == item) {
      found = true;
    }
  }
  list_traverse(head, contains_aux);
  return found;
}

I assumed that the nested contains_aux() function would be able to directly reference its lexically closed variables (found and item). But I was wrong.

Instead, looking at the generated code, I see that it installs some sort of trampoline function on the stack and calls that before getting to the contains_aux() function.

I know that contains_aux() can't share the same stack frame as list_contains() because there's an intervening function on the stack (list_traverse()), but -- geez -- it seems like the compiler could pass the frame pointer from list_contains() so contains_aux() could access its locals.

Is there a reason it doesn't work this way? Is there a way I could torture the compiler into doing that? Or should I just resign myself using un-nested functions and passing a "context" object to contains_aux()?

$\endgroup$
  • $\begingroup$ Given that gcc is a Compiler Collection: is the code presented above in any particular programming language? $\endgroup$ – greybeard Jun 4 at 7:41
  • $\begingroup$ @graybeard How about arm gcc 8.3.1? $\endgroup$ – fearless_fool Jun 4 at 16:33
2
$\begingroup$

I don't see any obvious reason why the compiler could not inline the call to list_traverse, assuming that it is a simple and that its definition is available in the translation unit. But apparently it doesn't. (Actually, I do see an obvious reason: "It would be a lot of work, and the benefit might not be great." Not saying that that statement is necessarily valid, but a reason can be just a suspicion.)

Without inlining, though, it's very difficult to see how the trampoline could be avoided. The frame containing the variables has to be passed through list_traverse so that it can be handed off to contains_aux. But presumably list_traverse is used elsewhere, and those other calls might not even involve a nested function, in which case there would be no stack frame to be passed through. There's nothing in list_traverse's prototype which specifies that it might be called with a nested function, so if it has external linkage, it needs to be usable with the standard calling convention, which has no room for hidden parameters. And if it is called with a nested function, there is no guarantee that the nested function it is called with was nested in the same way. (For example, there might be more than one stack frame which needs to accompany the closure, if the bound variables come from different places in the call stack.)

So aside from inlining, the only safe solution is to manufacture something which can be called like an ordinary function, thereby conforming with the type of list_traverse's first argument.

As evidence that inlining is possible, I offer the following C++ program, in which the same compiler happily inlines the lambda:

struct list_t {
    int value;
    list_t* next;
};

template<typename F>
void list_traverse(list_t* head, F check) {
    while (head && check(head))
        head = head->next;
}

bool list_contains(list_t *head, list_t* item) {
    bool found = false;
    list_traverse(head, [&](list_t *list)->auto {
        return list == item ? (found = true, false) : true;
        });
    return found;
}

(Alternatively, with a strangely bloated result: https://gcc.godbolt.org/z/s9XqW7).

I do understand that inlining might not be exactly what you're looking for, though.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Heh. This brings me one step closer to using C++ for embedded systems. (I'm always concerned about hidden overhead, though...) $\endgroup$ – fearless_fool Jun 3 at 12:51
  • $\begingroup$ I remember a report from Apple, who didn’t like the feature (for reasons I cant remember), examined a huge codebase, and found eight uses of this feature that could all be easily removed. So they got rid of the feature in their compiler version. $\endgroup$ – gnasher729 Jun 3 at 19:32
  • $\begingroup$ @gnasher729: I assume you mean the nested-function extension and not C++ lambdas :-) But nested functions certainly exist in the Apple-developed Swift language. Maybe they didn't like the fact that a nested function can't outlive the scope in which it was created. Anyway, the irony (imho) is that c++ lambdas are now implemented by the same compilers which didn't want to copy GCC's nested function extension. $\endgroup$ – rici Jun 3 at 22:02
  • $\begingroup$ "strangely bloated" -- you're being ironic, right? :) $\endgroup$ – fearless_fool Jun 3 at 23:04
  • $\begingroup$ @fearless_fool: A bit. But it's odd that the compiler isn't able to do a better job of common-code elimination in the second example, which has exactly the same semantics but significantly more opcodes. $\endgroup$ – rici Jun 3 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.