[Ecls-list] Work in progress...

[Juan Jose Garcia-Ripoll]

Hi,

there are now significant news lately, but the fact is that I am
trying to get a mayor optimization in ECL and this takes time. My plan
is to achieve on the following two major milestones:

1) Eliminate the type t_cons and create a type t_list. We would thus have

   CONS = (AND LIST (NOT (MEMBER NIL)))
   SYMBOL = (OR BASE-SYMBOL (MEMBER NIL))

Here BASE-SYMBOL represents objects whose memory representation is
that of current symbols; LIST is a cell of three memory words one for
the type tag, one for CAR and one for CDR. NIL is an object which has
the memory representation of a LIST, but with things like symbol name
and package stored separately. This seems probably ridiculous, but it
makes CAR and CDR way faster, for one only has to check whether an
object is of type LIST, instead of, as currently, checking the NIL and
CONS cases separately.

2) Once the previous step is implemented we can think of coding list
cells as two-word objects, with a pointer that implicelty stores the
type tag t_list = 3 in the least significant bits. That means lists
would leave the ecl_lispunion type and be treated differently. We
would save space (a word) because of the immediate type tag and also
time, because checking whether an object is of type LIST would be fast
and require no access to memory.

Step 1) is complicated for functions like SYMBOL-NAME, SYMBOL-PACKAGE,
etc, have to treat the object NIL separately. Both steps 1) and 2)
have the disadvantage of changing the inner representation of objects,
so that people that currently write x->cons.car instead of CAR(x), or
x->symbol.name instead of cl_symbol_name(x), would have to adapt their
code.

Finally, there is the issue of whether these changes do really provide
any real improvement on either speed or memory usage. As development
goes on, seems 1) is not affecting speed yet, but I have not optimize
many of the loops that currently use CONSP() or ATOM(). In addition to
this, it is not yet clear whether the Boehm-Weiser garbage collector
will support step 2), or do it without significant slowdown -- mainly
because it implies activating the detection of pointers to the
interior of an object.

Regards,

Juanjo

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