Re: Faster compilation speed

["Timothy J. Wood" <tjw at omnigroup dot com>]

On Wednesday, August 14, 2002, at 10:17  AM, Dale Johannesen wrote:
> And I know this is blindingly obvious, but RC takes an extra field 
> (word,
> probably) in each node.  I suspect this is going to eat up a lot of
> whatever gain there might be.
  I'm all in favor of making the IL tighter, but as far as RC goes...

  You can easily use much less than a full word.  Foundation on 
OpenStep/Mach 4.2 started storing partial ref counts in whatever spare 
bits were available in each object.

  In the common case, an object will have only a single reference.  
Additionally, it is very rare for an object to have a huge number of 
references.  So, you can store 7 bits of reference in the object and one 
bit that signifies whether there are any entries in the external 
reference table.  Any high-order bits of the RC are stored in an 
external hash table (which is much more expensive than the inline ref 
count, but is rarely used).

  So, you end up with the following rules:

- Upon creation, set the internal RC=0 and HasExternal=0.
- To compute the current real RC:

	RC = internal RC + 1
	if (HasExternal)
		RC += external RC * scale

- To add a reference:

	if (internal RC == max internal RC) {
		internal RC = 0;
		HasExternal = TRUE;
		// This function adds an entry of 1 to the external hash table 
if there
		// was no entry, otherwise it increments the existing entry.
		IncrementExternalRC(this);
	} else {
		internal RC++;
	}

- To delete a reference:

	if (internal RC == 0) {
		if (HasExternal == FALSE) {
			// The real RC was 1, this is the last reference
			Deallocate the object
		} else {
			// This function decrements the external RC count and returns TRUE
			// if there are remaining external bits (if the external 
count goes to zero
			// it removes the object from the external ref count hash 
table entirely).
			HasExternal = DecrementExternalRC(this);
			internalRC = max internal RC;
		}
	} else {
		internal RC--;
	}


 You can, of course, use however many bits you want for the internal RC 
(but the more bits you use, the less likely you are to overflow and 
cause the occasional hash lookup).  The HasExternal bit avoids the cost 
of hash lookups in the common case that an object is created, used, and 
then released.


-tim