Further, array lookup time is not affected by array size: It is always a constant.
That reassurance was probably part of what I was looking for. I get what you're saying about the reclaiming of IDs, but I can imagine a corner case: say that some object in the inheritance tree only gets instantiated once in a while, and others in the tree are instantiated far more often, but they share the ID generator and ID pool.
Then, any array holding instance data in the class that is only instantiated ever so often will be a fairly sparse array. I wonder if that's more memory-efficient than a hash. I don't know enough about the perl guts to be able to say whether memory is also allocated for the unused array elements in that class. Anyone?