[Ecls-list] Consing source identified

[Juan Jose Garcia-Ripoll]

Hi,

as explained in previous emails, ECL seems to be consing too much when
performing simple operations, such as invoking a method or
pretty-printing an object. Using CMUCL's newly ported library,
PROFILE, I have been able to determine the cause of consing and they
are method combinations.

When a generic function is invoked, it never translates to a function
being directly called. The lisp implementation has to create a closure
that contains a list of methods, and invokes them in some order,
determined by the kind of method-combination that this function uses.
For instance, take the simplest case

(defmethod foo ((a t))
  (print a))

This is a generic function with a single method which applies to any
object. Evaluating a form such as (foo 1.0) will result in 1.0 being
printed on the terminal. How this happens, is not a simple issue.
Basically:

1) ECL determines the types of the arguments.
2) From these types, a list of potential mehods is created.
3) This list is sorted.
4) A closure function is created that contains this list.
5) The closure function is actually invoked, with the argumens of the
method: 1.0
6) The closure function calls the first method, which may then call
other methods.

Steps 1-4 are only performed the first time a method is invoked. On
later uses of this method, this closure is taken from a cache.
However, the real problem lays in 5-6). The simplest method
combination is created by (src/clos/combin.lsp)

(defun combine-method-functions (method rest-methods)
  (declare (si::c-local))
  #'(lambda (&rest .combined-method-args.)
      (let ((*next-methods* rest-methods))
	(declare (special *next-methods*))
	(apply method .combined-method-args.))))

This function will almost always "cons",because it has to create the
list of arguments to the method (.combined-method-args.), and pass it
down to the actual functions that do the job.

I am currently researching different techniques to avoid building
these lists. This is done in a branch called "new_apply", to avoid
breaking ECL, but I hope development will proceed fast.

The most promising idea is to have what I call "stack frames". These
are lisp objects, allocated on the stack and with a dynamic extent,
which are similar to an adjustable array and which can be used as a
buffer to build a function call. The C code for implementing something
like (APPLY f ob1 ob2 l) would look as follows when using frames

{ECL_BUILD_STACK_FRAME(frame);
ecl_stack_frame_push(frame, ob1);
ecl_stack_frame_push(frame, ob2);
ecl_stack_frame_push_list(frame, l);
ecl_apply_from_stack_frame(frame, f);
ecl_stack_frame_close(frame);
}

Typically, frames will be created as chunks of the interpreter stack,
which are deallocated when ecl_stack_frame_close is called. Having
these objects, though, has a nice advantage, which is that they can be
passed down to other functions and used to call many different
functions with the same arguments.  Thus, a standard combination would
now look as follows, with absolutely no consing in the compiled
version:

(defun combine-method-functions (method rest-methods)
  (declare (si::c-local))
  #'(lambda (.combined-method-args-frame.)
      (let ((*next-methods* rest-methods))
	(declare (special *next-methods*))
	(apply-from-stack-frame method .combined-method-args-frame.))))

Development is scheduled to proceed as follows:

1) Implement stack frames and ecl_apply_from_stack_frame()
2) Rewrite cl_funcall to use stack frames
3) Rewrite cl_apply to use stack frames
4) Change the mapping functions (src/c/mapfun) to use stack frames
5) Remove cl_apply_from_stack()
6) Change the compiler to use stack frames in MULTIPLE-VALUE-CALL,
7) Change the compiler to use stack frames in function invocations
8) Rewrite method combinations using stack frames

In my tentative implementation, steps 1-7 seem already to work, though
further testing is required.

I would like to hear your ideas regarding this new implementation.

BTW, none of this code has yet been committed.

Juanjo

-- 
Facultad de Fisicas, Universidad Complutense,
Ciudad Universitaria s/n Madrid 28040 (Spain)
http://juanjose.garciaripoll.googlepages.com