Sunday, December 13, 2009

avoiding address range checks in the copying collector

I added this hack years ago, in another project; so I don't remember if I came up with the idea myself or borrowed it from elsewhere.

The Cheney algorithm leaves a 'forwarding' pointer in fromspace to identify objects which have been evacuated to tospace. When looking at a pointer in fromspace, you need to do an address range check on it to figure out which space it points to. This is relatively expensive. What I do instead is store a sentinel in place of the object header, and store the forwarding address immediately after it. Then the scan can identify forwarded objects by just looking for the sentinel.

Unfortunately, this breaks for zero-element tuples - there's nowhere to store the forwarding pointer.

Normally, zero-element tuples shouldn't exist - it's more efficient to represent such an object by an immediate object (like 'nil'). This works for everything - except for vectors. Vectors are by their nature run-time beasts that must support zero length.

So I've added support for a new immediate type - TC_EMPTY_VECTOR, which will have to be checked for at runtime, for example in "vector-length".

No comments:

Post a Comment