This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Faster compilation speed


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]