Linux kernel design patterns - lack of red/black tree search function

Posted Jun 20, 2009 19:47 UTC (Sat) by giraffedata (guest, #1954)
In reply to: Linux kernel design patterns - part 2 by madscientist
Parent article: Linux kernel design patterns - part 2

... or guaranteed function cloning and cross-module inlining ...

I don't think it's cross-moduleness or variable-argumentness that make the common search function slow. It's the function pointer.

Does gcc inline even a locally defined used-once function when you call it via a constant function pointer? Didn't used to.

to post comments

Linux kernel design patterns - lack of red/black tree search function

Posted Jun 21, 2009 22:26 UTC (Sun) by nix (subscriber, #2304) [Link] (3 responses)

No, it doesn't, but a sufficiently clever compiler could. The key is the
cross-module inlining.

(Even there, you'd be in trouble if the function doing the call was in a
different shared library than the caller. I don't see any way to fix
that.)

Linux kernel design patterns - lack of red/black tree search function

Posted Jun 21, 2009 22:46 UTC (Sun) by giraffedata (guest, #1954) [Link] (2 responses)

The key is the cross-module inlining.

Why is that the key? The pointed-to function would be in the main .c file and the library function that takes the function pointer as its argument would be in an included .h file like all the other functions we like to have inlined.

Linux kernel design patterns - lack of red/black tree search function

Posted Jun 22, 2009 22:21 UTC (Mon) by nix (subscriber, #2304) [Link] (1 responses)

Yes: and if the compiler was sufficiently clever, and all the .c files in
the application were presented to it at once, it would recognise instances
of this function that were frequently called with a particular function
pointer and clone a variant of that function that had that function
inlined into it: said variant would then get used only by the particular
call site in question.

This is way beyond what, say, GCC can do now, but is not disallowed nor
impossible to implement.

Linux kernel design patterns - lack of red/black tree search function

Posted Aug 22, 2009 15:32 UTC (Sat) by quotemstr (subscriber, #45331) [Link]

-fwhole-program