Optimizing delegates

[Andrei Alexandrescu]

On 12/19/10 11:35 AM, Ary Borenszweig wrote:
> On 12/19/2010 02:28 PM, Andrei Alexandrescu wrote:
>> On 12/19/10 11:23 AM, Ary Borenszweig wrote:
>>> On 12/19/2010 02:17 PM, Andrei Alexandrescu wrote:
>>>> On 12/19/10 11:13 AM, Ary Borenszweig wrote:
>>>>> On 12/19/2010 01:44 PM, Andrei Alexandrescu wrote:
>>>>>> On 12/19/10 10:35 AM, Ary Borenszweig wrote:
>>>>>>> On 12/19/2010 01:21 PM, Andrei Alexandrescu wrote:
>>>>>>>> On 12/19/10 9:32 AM, Ary Borenszweig wrote:
>>>>>>>>> I have this code:
>>>>>>>>>
>>>>>>>>> ---
>>>>>>>>> import std.stdio;
>>>>>>>>>
>>>>>>>>> int foobar(int delegate(int) f) {
>>>>>>>>> return f(1);
>>>>>>>>> }
>>>>>>>>>
>>>>>>>>> int foobar2(string s)() {
>>>>>>>>> int x = 1;
>>>>>>>>> mixin("return " ~ s ~ ";");
>>>>>>>>> }
>>>>>>>>>
>>>>>>>>> void main() {
>>>>>>>>> writefln("%d", foobar((int x) { return 2*x; }));
>>>>>>>>> writefln("%d", foobar2!("9876*x"));
>>>>>>>>> }
>>>>>>>>> ---
>>>>>>>>>
>>>>>>>>> When I compile it with -O -inline I can see with obj2asm that for
>>>>>>>>> the
>>>>>>>>> first writefln the delegate is being called. However, for the
>>>>>>>>> second
>>>>>>>>> it just passes
>>>>>>>>> 9876 to writefln.
>>>>>>>>>
>>>>>>>>> From this I can say many things:
>>>>>>>>> - It seems that if I want hyper-high performance in my code I must
>>>>>>>>> use
>>>>>>>>> string mixins because delegate calls, even if they are very simple
>>>>>>>>> and
>>>>>>>>> the
>>>>>>>>> functions that uses them are also very simple, are not inlined.
>>>>>>>>> This
>>>>>>>>> has the drawback that each call to foobar2 with a different string
>>>>>>>>> will generate a
>>>>>>>>> different method in the object file.
>>>>>>>>
>>>>>>>> You forgot:
>>>>>>>>
>>>>>>>> writefln("%d", foobar2!((x) { return 2*x; })());
>>>>>>>>
>>>>>>>> That's a real delegate, not a string, but it will be inlined.
>>>>>>>>
>>>>>>>>
>>>>>>>> Andrei
>>>>>>>
>>>>>>> Sorry, I don't understand. I tried these:
>>>>>>>
>>>>>>> 1.
>>>>>>> int foobar3(int delegate(int) f)() {
>>>>>>> return f(1);
>>>>>>> }
>>>>>>>
>>>>>>> writefln("%d", foobar3!((int x) { return 2*x; })());
>>>>>>>
>>>>>>> => foo.d(12): Error: arithmetic/string type expected for
>>>>>>> value-parameter, not int delegate(int)
>>>>>>>
>>>>>>> 2.
>>>>>>> int foobar3()(int delegate(int) f) {
>>>>>>> return f(1);
>>>>>>> }
>>>>>>>
>>>>>>> writefln("%d", foobar3!()((int x) { return 2*x; }));
>>>>>>>
>>>>>>> => Works, but it doesn't get inlined.
>>>>>>>
>>>>>>> And I tried that "(x) { ... }" syntax and it doesn't work.
>>>>>>>
>>>>>>> Sorry, it must be my fault I'm doing something wrong. What's the
>>>>>>> correct
>>>>>>> way of writing optimized code in D, code that I'm sure the compiler
>>>>>>> will
>>>>>>> know how to optimize?
>>>>>>
>>>>>> void foobar3(alias fun)() {
>>>>>> return fun(1);
>>>>>> }
>>>>>>
>>>>>>
>>>>>> Andrei
>>>>>
>>>>> This of course has the following problem:
>>>>>
>>>>> int foobar2(int delegate(int x) f) {
>>>>> }
>>>>>
>>>>> foobar2((int x, int y) { ... });
>>>>>
>>>>> Error: function foobar2 (int delegate(int) f) is not callable using
>>>>> argument types (int delegate(int x, int y))
>>>>>
>>>>> ---
>>>>>
>>>>> int foobar3(alias f)() {
>>>>> f(1);
>>>>> }
>>>>>
>>>>> foobar3((x, y) { ... });
>>>>>
>>>>> foo.d(8): Error: template foo.main.__dgliteral1(__T2,__T3) does not
>>>>> match any function template declaration
>>>>> foo.d(8): Error: template foo.main.__dgliteral1(__T2,__T3) cannot
>>>>> deduce
>>>>> template function from argument types !()(int)
>>>>> foo.d(12): Error: template instance foo.main.foobar3!(__dgliteral1)
>>>>> error instantiating
>>>>>
>>>>> So I have to go to foo.d(8) to see what the problem is, understand
>>>>> what
>>>>> is being invoked (in this case it was easy but it get can harder), or
>>>>> otherwise say "Hey, the one that implemented foo, please do a static
>>>>> assert msg if f is not what you expect". Basically "Implement the
>>>>> error
>>>>> message that the compiler would have given you for free if you didn't
>>>>> use a template".
>>>>
>>>> Template constraints are meant to assuage that problem.
>>>>
>>>> Inlining delegates is technically much more difficult than inlining
>>>> aliases. This is because a different function will be generated for
>>>> each
>>>> alias argument, whereas only one function would be used for all
>>>> delegates. There are techniques to address that in the compiler, but
>>>> they are rather complex.
>>>>
>>>>
>>>> Andrei
>>>
>>> I understand.
>>>
>>> So why do I have to use a whole different syntax to make something
>>> accepting a delegate a function or a template?
>>>
>>> Why can't this be accepted?
>>>
>>> int foobar2(int delegate(int x) f)() {
>>> }
>>>
>>> and let the compiler interpret it as:
>>>
>>> int foobar2(alias f) if ("the correct constraint which I don't want to
>>> learn how to write because the above SHOULD work") {
>>> }
>>>
>>> ?
>>
>> Because that would be unlike everything else in D.
>>
>> Andrei
>
> What do you mean? It's not unlike everything else in D. It's *exactly*
> like a function call in D.

No function definition expands into a template.

Andrei