[rucksack-devel] Re: Fwd: State of the nation and heap patch

[Arthur Lemmens]

Cyrus Harmon wrote:

> What do class indexes buy us?

They let us find all instances of a class (and they implicitly
tell the garbage collector that instances of that class are
alive, even if nothing else refers to such instances).

This is not always necessary (for example if all instances of a
class are always referred to by other persistent objects), but it
can be very handy.

> We can locate an instance (given an identifier of some sort I
> presume) quickly with or without an index, right?

Yes (assuming I understand your question).  The object table always
lets us locate an instance quickly, given an object identifier.

> The indices allow us to do rucksack-map-instances, but it's not
> clear to me why this needs to be an index per se. A hash-table or
> other (unordered) could do the trick just as well

Yes, that's right.  Or some other persistent datastructure that
can represent a set.  But at the moment we only have persistent
conses, persistent arrays and persistent b-trees.

Hmm, now that you mention it... We could probably just push every
new instance of an indexed class on a persistent list, instead of
doing the whole btree insertion dance.  Very good point, thank
you!  (The only problem with this idea is that it would make
deleting an object from an index an O(n) instead of an O(log n)
operation.)

> although the mapping would then no longer be in order.

Yeah, but we don't need that for class indices, do we?

> It would be nice if the index functionality were exposed through
> functions and methods allowing for adding/removing indices, rather
> than by modifying the class definition

Yes, I've been thinking about this too.  The disadvantage of this
would be that the (Rucksack-specific part of the) class definition
no longer corresponds to the Rucksack reality.  But I agree with
you that the advantages of exposing such functions are probably
greater than the disadvantage.

> Why wouldn't it be possible to add class indices after the fact?

Hmm... The only way to do it would be to iterate over the entire
object table.  Which is not impossible, but it is a bit expensive.
I was also thinking that you wouldn't want to index an object
that's dead (i.e. unreferenced by other objects), but I guess that
could be solved by doing a complete garbage collection immediately
before adding a class index.

So: it's probably not impossible, but it would be quite expensive.

Thanks for the feedback.  Very interesting.

Arthur