Closures - Revision history

Manus at 10:15, 11 April 2007

2007-04-11T10:15:07Z

Konradm: /* Melted agent creator */

2007-01-22T14:37:20Z

‎Melted agent creator

Konradm: /* Melted agent creator */

2007-01-22T14:37:07Z

‎Melted agent creator

Konradm: /* Strategy for optimizing dotnet Agent Calls */

2007-01-22T14:36:09Z

‎Strategy for optimizing dotnet Agent Calls

Konradm: /* The wrapper */

2007-01-22T14:35:22Z

‎The wrapper

Konradm: /* The data structure */

2007-01-22T14:34:08Z

‎The data structure

Konradm: /* The data structure */

2007-01-22T14:32:09Z

‎The data structure

Konradm: /* Introduction */

2007-01-22T14:30:23Z

‎Introduction

Konradm: /* Introduction */

2007-01-22T14:29:37Z

‎Introduction

Konradm at 14:29, 22 January 2007

2007-01-22T14:29:08Z

New page

[[Category:Compiler]]
{{Warning|'''Warning''': Article under development}}

====Introduction====
The Eiffel programming language supports closures with agents. As a reminder, an agent is a normal Eiffel object of one of the types:
*FUNCTION
*PROCEDURE
Some terminology is needed: The place where an agent is created (with the agent keyword or the tilde operator) is called the '''agent creation'''. The feature to which the agent points is the '''agent callee''' and the place (or places) where the agent is called is denoted '''agent call'''.

An example that clarifies these terms:

{|border="0" cellpadding="2" cellspacing="0" align="center"
|-valign="top" -halign="center"
|
<code>[eiffel,N]class
TERMINOLOGY

feature

f1
local
p: PROCEDURE [ANY, TUPLE]
do
p := agent target -- agent creation
end

f2 (p: PROCEDURE [ANY, TUPLE])
do
p.call ([]) -- agent call
end

target -- callee
do
end
end</code>
|
|}

====The problem====
It is again helpful to focus on the differences between the Eiffel and C language. Eiffel supports closures, C only supports function pointers. A way is needed thus to construct closures based on function pointers. Dynamic binding also contributes its part to the problem. It is not known at compile time which exact feature an agent (when looking at its '''agent creation''') refers to. But it gets even worse, sometimes the feature is not known until the agent is called (at runtime). This is the case for agents with open targets.
====The data structure====
Class C will be used for the following examples:

{|border="0" cellpadding="2" cellspacing="0" align="center"
|-valign="top" -halign="center"
|
<code>[eiffel,N]class
C

feature
f (p1, p2: INTEGER; p3: STRING): STRING
do
...
end
end</code>
|
|}

There are three data structures needed for an agent:
* The open_map (member of class ROUTINE)
* The closed_operands (member of class ROUTINE)
* The open_operands
The open_map is known at compile time when an '''agent_creation''' is detected. The closed_operands are known at '''agent creation''' time. The open_operands are not known until the agent is called.

The content of these structures will be given for agent one and two:

{|border="0" cellpadding="2" cellspacing="0" align="center"
|-valign="top" -halign="center"
! Agent one !! Agent two
|-
|
<code>[eiffel, N]
agent c.f (?, 1, ?)
</code>
|
<code>[eiffel, N]
agent {C}.f (1, ?, "hello")
</code>
|}

The open_map is an array that has an entry for every open parameter. Its content for agents one and two are:
#{2,4}
#{1,3}
The closed_operands is a TUPLE that has an entry for every closed operand. Its content for agents one and two again:
#{c, 1}
#{1, "hello"}

====The wrapper====
It comes by no surprise that the compiler creates special wrapper functions for agents. It is interesting though that these wrappers are created per '''agent creation'''. This has the advantage that it is known whether a given formal argument is open or closed.

In workbench mode, for every '''agent creation''' a C-function is generated. This wrapper function does the following:
*Arrange the closed and open arguments in the right order.
*Calculate the proper '''agent callee''' based on the dynamic type of the target.
*Call the '''agent callee'''.

For the '''agent creation''':
{|border="0" cellpadding="2" cellspacing="0" align="center"
|-valign="top" -halign="center"
|
<code>[eiffel, N]
agent c.f (?, 1, ?)
</code>
|
|}
the following wrapper function is generated:
{|border="0" cellpadding="2" cellspacing="0" align="center"
|-valign="top" -halign="center"
|<code>[c, N]EIF_REFERENCE _fAaatpmf_2_4 (
EIF_REFERENCE (*f_ptr)(EIF_REFERENCE, //can be ignored
EIF_INTEGER_32,
EIF_INTEGER_32,
EIF_REFERENCE),
EIF_TYPED_ELEMENT* closed, //Closed arguments
EIF_TYPED_ELEMENT* open) //Open arguments
{
return
(FUNCTION_CAST(EIF_REFERENCE, (EIF_REFERENCE,
EIF_INTEGER_32,
EIF_INTEGER_32,
EIF_REFERENCE))
//Dynamic binding using the target:
RTVF(350, 30, "f", closed [1].element.rarg))(
//Arranging the open and closed arguments:
closed [1].element.rarg,
open [1].element.i32arg,
closed [2].element.i32arg,
open [2].element.rarg);
}
</code>
|
|}
This example shows how the wrapper does its three tasks. The suffix "_2_4" of the wrapper comes from the fact that the second and forth parameter (first and third argument) are open.

A second example is given:
{|border="0" cellpadding="2" cellspacing="0" align="center"
|-valign="top" -halign="center"
|<code>[eiffel, N]
agent {C}.f (1, ?, "hello")
</code>
|}
For this '''agent creation''' the wrapper function looks like:
{|border="0" cellpadding="2" cellspacing="0" align="center"
|-valign="top" -halign="center"
|<code>[c, N]
EIF_REFERENCE _fAaatpmf_1_3 (
EIF_REFERENCE (*f_ptr)(EIF_REFERENCE, //can be ignored
EIF_INTEGER_32,
EIF_INTEGER_32,
EIF_REFERENCE),
EIF_TYPED_ELEMENT* closed, //Closed arguments
EIF_TYPED_ELEMENT* open) //Open arguments
{
return
(FUNCTION_CAST(EIF_REFERENCE, (EIF_REFERENCE,
EIF_INTEGER_32,
EIF_INTEGER_32,
EIF_REFERENCE))
//Dynamic binding using the target:
RTVF(350, 30, "f", open [1].element.rarg))(
//Arranging the open and closed arguments:
open [1].element.rarg,
closed [1].element.i32arg,
open [2].element.i32arg,
closed [2].element.rarg);
}
</code>
|}
This time the suffix is "_1_3" since the first and third parameter (target and second argument) are open.

====Agent call====
An '''agent call''' like the following:
{|border="0" cellpadding="2" cellspacing="0" align="center"
|-valign="top" -halign="center"
|
<eiffel>
local
f: FUNCTION [ANY, TUPLE [INTEGER], INTEGER]
b: BOOLEAN
do
b := f.item ([10])
end
</eiffel>
|
|}
Obviously calls feature <eiffel>item</eiffel> of class <eiffel>FUNCTION</eiffel>:

{|border="0" cellpadding="2" cellspacing="0" align="center"
|-valign="top" -halign="center"
|
<eiffel>
item (args: OPEN_ARGS): RESULT_TYPE is
-- Result of calling function with `args' as operands.
require
valid_operands: valid_operands (args)
local
l_closed_count: INTEGER
do
l_closed_count := closed_operands.count
Result := fast_item (encaps_rout_disp, calc_rout_addr,
$closed_operands, $args, class_id, feature_id,
is_precompiled, is_basic, is_inline_agent,
l_closed_count, open_count, $open_map)
end
</eiffel>
|
|}

This leads to a call to the external C feature <eiffel>fast_item</eiffel> of class <eiffel>FUNCTION</eiffel>:

{|border="0" cellpadding="2" cellspacing="0" align="center"
|-valign="top" -halign="center"
|
<eiffel>fast_item (a_rout_disp, a_calc_rout_addr: POINTER
a_closed_operands: POINTER; a_operands: POINTER
a_class_id, a_feature_id: INTEGER
a_is_precompiled, a_is_basic, a_is_inline_agent: BOOLEAN
a_closed_count, a_open_count: INTEGER; a_open_map: POINTER): RESULT_TYPE
external
"C inline use %"eif_rout_obj.h%""
alias
"[
#ifdef WORKBENCH
$$_result_type result;
if ($a_rout_disp != 0) {
return (FUNCTION_CAST($$_result_type,
(EIF_POINTER, EIF_REFERENCE, EIF_REFERENCE)) $a_rout_disp)(
$a_calc_rout_addr, $a_closed_operands, $a_operands);
} else {
...
}
#else
...
#endif
]"
end</eiffel>
|
|}

When there is a valid function pointer to the wrapper (<c>a_rout_disp != 0</c>) it is called with the closed and open operands as parameters. The wrapper will then call the actual '''agent callee'''. The case when there is no valid function pointer will be considered later.

====Improving the dynamic binding====
When at '''agent creation''' the target is closed, the exact '''agent callee''' can be calculated at '''agent creation'''. This improves performance when the agent is called more than once. This optimization is only done when in final mode.

====Eradicating manifest tuple creation====
In finalized mode there is a simple optimization that speeds things up significantly. It is not uncommon, that an '''agent calls''' passes a manifest tuple as parameter, see the following call:

{|border="0" cellpadding="2" cellspacing="0" align="center"
|-valign="top" -halign="center"
|
<eiffel>
b := f.item ([10, 20, "hello"])
</eiffel>
|
|}

The lifetime of this tuple is short. It is only used throughout the call to <eiffel>item</eiffel>. Tuple creations are not that fast, they take several times longer than the '''agent call''' itself. Thats why the EiffelStudio in finalized mode replaces these calls to <eiffel>item</eiffel> by a direct call to wrapper function. If the open parameters in Eiffel code are passed in the form of a manifest tuple, they are directly passed to the wrapper function in the translated code, to get rid of the slow tuple creation.

{|border="0" cellpadding="2" cellspacing="0" align="center"
|-valign="top" -halign="center"
|
<c>
tp1 = RTMS_EX_H("hello",5,1702403183);
tp2 = tp1;
tp1 = (FUNCTION_CAST(EIF_REFERENCE, (EIF_POINTER,
EIF_REFERENCE,
EIF_INTEGER_32,
EIF_INTEGER_32,
EIF_REFERENCE))
*(EIF_POINTER *)(loc3+ @PTROFF(5,4,0,3,0,0)))( //calling the wrapper function
*(EIF_POINTER *)(loc3+ @PTROFF(5,4,0,3,0,1)), //passing the calculated agent callee
*(EIF_REFERENCE *)(loc3 + @REFACS(1)), //passing the closed parameters
((EIF_INTEGER_32) 10L), //passing 10
((EIF_INTEGER_32) 11L), //passing 11
tp2); //passing "hello"
</c>
|
|}

====Wrapper functions in final mode====
Due to the potential optimization described above, in final mode two C wrapper functions are generated:
*one which expects the closed arguments as a tuple (encapsulated). The only difference to the frozen wrapper is how the '''agent callee''' is calculated.
*and one that expects them as separate parameters.

For the '''agent creation''':
{|border="0" cellpadding="2" cellspacing="0" align="center"
|-valign="top" -halign="center"
|
<eiffel>
agent c.f (?, 1, ?)
</eiffel>
|}
the following wrapper functions are generated:
{|border="0" cellpadding="2" cellspacing="0" align="center"
|-valign="top" -halign="center"
|
<c>
EIF_REFERENCE _fAaatpmf_2_4 (
EIF_REFERENCE (*f_ptr)(EIF_REFERENCE,
EIF_INTEGER_32,
EIF_INTEGER_32,
EIF_REFERENCE),
EIF_TYPED_ELEMENT* closed,
EIF_TYPED_ELEMENT* open)
{
return f_ptr (closed [1].element.rarg,
open [1].element.i32arg,
closed [2].element.i32arg,
open [2].element.rarg);
}
</c>
|
<c>
EIF_REFERENCE __fAaatpmf_2_4 (
EIF_REFERENCE (*f_ptr)(EIF_REFERENCE,
EIF_INTEGER_32,
EIF_INTEGER_32,
EIF_REFERENCE),
EIF_TYPED_ELEMENT* closed,
EIF_INTEGER_32 op_2,
EIF_REFERENCE op_4)
{
return f_ptr (closed [1].element.rarg,
op_2,
closed [2].element.i32arg,
op_4);
}
</c>
|}
The name of the wrapper for the encapsulated closed arguments always starts with one '_', whereas the other one starts with two underlines.

====Melted agent creator====
Of course it is possible that the '''agent creation''' is melted and hence there is no wrapper. For this situation the Eiffel runtime provides two generic wrapper functions:

<code>[c, N]
RT_LNK void rout_obj_call_procedure_dynamic (
int stype_id, int feature_id, int is_precompiled, int is_basic_type, int is_inline_agent, EIF_TYPED_ELEMENT* closed_args,
int closed_count, EIF_TYPED_ELEMENT* open_args, int open_count, EIF_REFERENCE open_map);

RT_LNK void rout_obj_call_function_dynamic (
int stype_id, int feature_id, int is_precompiled, int is_basic_type, int is_inline_agent, EIF_TYPED_ELEMENT* closed_args,
int closed_count, EIF_TYPED_ELEMENT* open_args, int open_count, EIF_REFERENCE open_map, void* res);
</code>

These functions calculate the '''agent callee''' with the static type id and a feature id. Furthermore the reordering of open and closed arguments has to be done at agent call time with help of the open_map.

== Strategy for optimizing dotnet Agent Calls ==
Work in progress!
Compared to the Classic version, dotnet Agent Calls are slow. The a short look at feature apply of class FUNCTION shows why:

<code>[eiffel,N]
apply
-- Call function with `operands' as last set.
do
last_result ?= rout_disp.invoke (target_object, internal_operands)
end
</code>

The actual call is done through reflection. Additionally, in dotnet the two major optimizations are missing:

*Directly passing the elements of manifest tuples as parameters. (And hence not creating the tuple)
*Computing the reordering of closed and open operands at compile time. (By generating the proper wrapper)

All these three issues can be removed.

For every '''agent creation''' we create:
* A delegate type that requires two Tuples (closed and open arguments) as arguments.
* A static method that conforms to this delegate type. This method does the ordering of closed and open arguments and calls the '''agent callee'''.
* A second delegate type, that requires one Tuple (closed arguments) and all the open arguments as arguments.
* A second static method which conforms to the second delegate type and does the ordering and '''agent callee''' call.

@@ Line 1: / Line 1: @@
 [[Category:Compiler]]
-{{Warning|'''Warning''': Article under development}}
+{{UnderConstruction}}
 ====Introduction====

@@ Line 349: / Line 349: @@
 </code>
-These functions calculate the '''agent callee''' with the static type id and a feature id. Furthermore the reordering of open and closed arguments has to be done at agent call time with help of the open_map.
+These functions calculate the '''agent callee''' with the static type id and a feature id. Furthermore the reordering of open and closed arguments has to be done at agent call time with help of the <eiffel>open_map</eiffel>.
 == Strategy for optimizing dotnet Agent Calls ==

@@ Line 335: / Line 335: @@
 <code>[c, N]
 RT_LNK void rout_obj_call_procedure_dynamic (
-     int stype_id, int feature_id, int is_precompiled, int is_basic_type, int is_inline_agent, EIF_TYPED_ELEMENT* closed_args,
+     int stype_id, int feature_id, int is_precompiled,
-    int closed_count, EIF_TYPED_ELEMENT* open_args, int open_count, EIF_REFERENCE open_map);
+    int is_basic_type, int is_inline_agent,
 RT_LNK void rout_obj_call_function_dynamic (
-     int stype_id, int feature_id, int is_precompiled, int is_basic_type, int is_inline_agent, EIF_TYPED_ELEMENT* closed_args,
+     int stype_id, int feature_id, int is_precompiled,
-    int closed_count, EIF_TYPED_ELEMENT* open_args, int open_count, EIF_REFERENCE open_map, void* res);
+    int is_basic_type, int is_inline_agent,
 </code>

@@ Line 349: / Line 349: @@
 Compared to the Classic version, dotnet Agent Calls are slow. The a short look at feature apply of class FUNCTION shows why:
-<code>[eiffel,N]
+<eiffel>
 apply
          -- Call function with `operands' as last set.
@@ Line 355: / Line 355: @@
          last_result ?= rout_disp.invoke (target_object, internal_operands)
      end
-</code>
+</eiffel>
 The actual call is done through reflection. Additionally, in dotnet the two major optimizations are missing:

@@ Line 99: / Line 99: @@
 |-valign="top" -halign="center"
+|
-<code>[eiffel, N]
+<eiffel>
              agent c.f (?, 1, ?)
-</code>
+</eiffel>
+|
 |}
@@ Line 107: / Line 107: @@
 {|border="0" cellpadding="2" cellspacing="0" align="center"
 |-valign="top" -halign="center"
-|<code>[c, N]EIF_REFERENCE _fAaatpmf_2_4 (
+|<c>EIF_REFERENCE _fAaatpmf_2_4 (
     EIF_REFERENCE (*f_ptr)(EIF_REFERENCE, //can be ignored
                            EIF_INTEGER_32,
@@ Line 128: / Line 128: @@
              open [2].element.rarg);
+}
-</code>
+</c>
+|
 |}
@@ Line 136: / Line 136: @@
 {|border="0" cellpadding="2" cellspacing="0" align="center"
 |-valign="top" -halign="center"
-|<code>[eiffel, N]
+|<eiffel>
              agent {C}.f (1, ?, "hello")
-</code>
+</eiffel>
 |}
 For this '''agent creation''' the wrapper function looks like:
 {|border="0" cellpadding="2" cellspacing="0" align="center"
 |-valign="top" -halign="center"
-|<code>[c, N]
+|<c>
 EIF_REFERENCE _fAaatpmf_1_3 (
     EIF_REFERENCE (*f_ptr)(EIF_REFERENCE,  //can be ignored
@@ Line 165: / Line 165: @@
           closed [2].element.rarg);
+}
-</code>
+</c>
 |}
 This time the suffix is "_1_3" since the first and third parameter (target and second argument) are open.
 ====Agent call====

@@ Line 82: / Line 82: @@
 #{2,4}
 #{1,3}
-The <eiffel>closed_operands</eiffel> is a TUPLE that has an entry for every closed operand. Its content for agents one and two again:
+The <eiffel>closed_operands</eiffel> is a <eiffel>TUPLE</eiffel> that has an entry for every closed operand. Its content for agents one and two again:
 #{c, 1}
 #{1, "hello"}
 ====The wrapper====

@@ Line 45: / Line 45: @@
 |-valign="top" -halign="center"
+|
-<code>[eiffel,N]class
+<eiffel>class
+     C
@@ Line 53: / Line 53: @@
              ...
          end
-end</code>
+end</eiffel>
+|
 |}
 There are three data structures needed for an agent:
-* The open_map (member of class ROUTINE)
+* The <eiffel>open_map</eiffel> (member of class <eiffel>ROUTINE</eiffel>)
-* The closed_operands (member of class ROUTINE)
+* The <eiffel>closed_operands</eiffel> (member of class <eiffel>ROUTINE</eiffel>)
 * The open_operands
-The open_map is known at compile time when an '''agent_creation''' is detected. The closed_operands are known at '''agent creation''' time. The open_operands are not known until the agent is called.
+The <eiffel>open_map</eiffel> is known at compile time when an '''agent_creation''' is detected. The <eiffel>closed_operands</eiffel> are known at '''agent creation''' time. The open_operands are not known until the agent is called.
 The content of these structures will be given for agent one and two:
@@ Line 70: / Line 70: @@
 |-
+|
-<code>[eiffel, N]
+<eiffel>
 agent c.f (?, 1, ?)
-</code>
+</eiffel>
+|
-<code>[eiffel, N]
+<eiffel>
 agent {C}.f (1, ?, "hello")
-</code>
+</eiffel>
 |}
-The open_map is an array that has an entry for every open parameter. Its content for agents one and two are:
+The <eiffel>open_map</eiffel> is an array that has an entry for every open parameter. Its content for agents one and two are:
 #{2,4}
 #{1,3}
-The closed_operands is a TUPLE that has an entry for every closed operand. Its content for agents one and two again:
+The <eiffel>closed_operands</eiffel> is a TUPLE that has an entry for every closed operand. Its content for agents one and two again:
 #{c, 1}
 #{1, "hello"}

@@ Line 4: / Line 4: @@
 ====Introduction====
 The Eiffel programming language supports closures by agents. As a reminder, an agent is a normal Eiffel object of one of the types:
-*FUNCTION
+*<eiffel>FUNCTION</eiffel>
-*PROCEDURE
+*<eiffel>PROCEDURE</eiffel>
 Some terminology is needed: The place where an agent is created (with the agent keyword or the tilde operator) is called the '''agent creation'''. The feature to which the agent points is the '''agent callee''' and the place (or places) where the agent is called is denoted '''agent call'''.
@@ Line 13: / Line 13: @@
 |-valign="top" -halign="center"
+|
-<code>[eiffel,N]class
+<eiffel>class
      TERMINOLOGY
@@ Line 33: / Line 33: @@
          do
          end
-end</code>
+end</eiffel>
+|
 |}