CLOS standard class cleanup

[Michael J. Beckerle <BECKERLE@XX.LCS.MIT.EDU>]

Issue:		STANDARD-CLASS-OVERHEAD
References:     CLOS 88-002R pg 1-43, 1-46.
Category: 	CHANGE
Edit History:   v0 27june88  mike beckerle


Problem Description:

The class STANDARD-CLASS allows not only for object-oriented
programming, with multiple-inheritance, but also allows for
non-trivial meta-object programming, including the operation
CHANGE-CLASS.

It is likely that many applications will make no use of
class-redefinition. All pre-CLOS common lisp applications are
examples of this. Given the new Condition/Error component of CL they
will have to run in a world which has error/condition objects in it,
yet since they are pre-clos, they will certainly make no-use of
class-redefinition. 

Unfortunately, the code for accessing/updating instance-variables of
an object is significantly more complex if the class can be changed
at run time. See discussion item below on instance-variable-access-
overhead.

Proposal: Standard-class-made-simpler.

The class standard-class should be defined to not-allow
class-redefinition at run time. Compilers would be authorized
to issue compile-time errors if they could determine that
a class of meta-class standard-class was being 
redefined programatically.


Proposal: Change-class-names

The name Standard-class is misleading. Eliminate the
name standard class and introduce two names for "predefined"
classes. One of which does not support class-redefinition
and the other of which does.
Suggested names are:

a)  non redefinable class      redefinable class
b)  standard-class             standard-redefinable-class
c)  simple-class 	       changeable-class
d)  static-class	       dynamic-class
  

Discussion: instance-variable-access-overhead.

This issue of standard-class overhead was raised prior to the
june 88 x3j13 meeting. The CLOS committee replied to this 
issue as follows:

  "In addition, we don't believe that this functionality causes any
   performance problems. Experience with New Flavors and PCL has shown
   that there is no performance penalty incurred by including this
   functionality in CLOS."

This discussion is intended to provide a more detailed notion of the
kinds of overhead involved.
 
Using a simple model of instance variable access, If classes cannot
be redefined at program run-time, then instance-variable access can
be coded into 3 unchecked indirections, and instances can be stored
as linear vectors of slots.

Using similar technology, but allowing class-redefinition requires 2
unchecked indirections, and 1 checked indirection, thereby requiring
a conditional branch.  In addition, instances must be represented
using an extra indirection (or an optional indirection) to the actual
slots, thereby requiring 1 extra pointer in each object
representation.

Example:

(defclass foo
    (x y z))

(defun bar (&optional (obj (make-instance 'foo)))
   (foo-x obj))

Without class redefinition, foo-x can be inline coded as the following 
common-lisp code:

(defmacro foo-x (obj)
  `(let* ((obj ,obj)
          (perm-vector (svref *perm-vectors* (object-class-number obj)))
          (i-v-offset (svref perm-vector ,(i-v-number 'x 'foo)))
      (instance-slot obj i-v-offset)))

where instance-slot is like svref, it just indexes instance objects
directly the way svref indexes simple vectors.  This assumes that
instances have a flat structure, containing no indirections to the
instance variables themselves. They are like structures, but the
access mechanism allows for multiple-inheritance.

Machine-code wise, this can be inline coded as something like:
 
   move r1, <obj>                 ; r1 points at the object.
   move r2, (r1 object-class-num) ; absolute offset from r1 base.
                                  ; r2 = class number
   movad r3, *perm-vectors*       ; absolute address load.
   move r2, (r3+r2)               ; indexed off r3 base.
   				  ; r2 = permutation vector
   move r2, (r2 i-v-number)       ; absolute offset from r3 base 
   				  ; r2 = instance-var offset in object.
   move r1, (r1+r2)               ; indexed off r1 base.
   				  ; r1 = instance-var value.

This is a six instruction sequence involving no jumps, hence, no
pipeline breaks on processors with instruction pipelining.

To support class-redefinition using similar technology:

(defmacro foo-x (obj)
  `(let* ((obj ,obj)
          (perm-vector (svref *perm-vectors* (object-class-number obj)))
          (i-v-offset (svref perm-vector ,(i-v-number 'x 'foo)))
      (if (slot-exists-p i-v-offset)
         (let ((i-v-structure (instance-slot ,i-v-structure-offset)))
           (svref i-v-structure i-v-offset))
	 (error "Slot ~A no longer exists in object ~S"
	        'x obj))))

This assumes that instances have an indirected structure, that is, in
order to get at an instance variable, one must always indirect
through a fixed location in each instance to obtain a vector of the
slots. This allows the number of instance variables to increase if
needed.

Machine-code wise, this would be coded as something like:
 
   move r1, <obj>                 ; r1 points at the object.
   move r2, (r1 object-class-num) ; absolute offset from r1 base.
                                  ; r2 = class number
   movad r3, *perm-vectors*       ; absolute address load.
   move r2, (r3+r2)               ; indexed off r3 base.
   				  ; r2 = permutation vector
   move r2, (r2 i-v-number)       ; absolute offset from r3 base 
   cmp  r2, invalid-slot          ; absolute comparison.
   je :noslot			  ; conditional branch.
   				  ; r2 = instance-var offset in i-v-structure.
   move r1, (r1 i-v-structure)    ; absolute offset from r1 base
   				  ; r1 = i-v-structure.
   move r1, (r1+r2)               ; indexed off r1 base.
   				  ; r1 = instance-var value.
   jmp :done			  ; unconditional jump
:noslot
   .... call error ....
:done       
   
Note that this involves 4 more instructions, not including any
to report the error, plus 1 jump (hence pipeline break on pipelined
processors.). There is no way to rearrange this code so that there
is no branch required. 

I make no claims that these code sequences are optimal, but only that
they are representative of the relative complexity of instance
variable access when supporting and not-supporting class redefinition.
I belive that on conventional machine architectures, instance-variable
access could be twice as fast if the compiler could insure that
the class could not be redefined at run-time. In addition, each
instance can be smaller.

If a CLOS application used only the non-redefinable class, then
the functions involved in the class-change operations can be removed
 from run-time systems.

To sumarize, there seems to be significant enough overhead required to
support class-redefinition, both in object representation, code-size,
and execution speed to justify inclusion of a meta-class which 
does not allow class-redefinition in the standard.

Cost of Adoption:

Effectively zero, as CLOS was only accepted into the standard recently.
In addition, an implementation should be free to implement the
non-redefinable class in the exact same way as the redefinable class,
(possibly signaling an error on redefinition attempts).

Cost of Non-Adoption:

Due to runtime delivery considerations it is likely that vendors
will provide implementation specific class definitions which do not
have the class-redefinition capability. 



-------