Skip to content

improve slot allocation #19

@jll63

Description

@jll63

From Steven Watanabe:

Considering the optimization of not storing leading unused slots,
filling the lowest available slot is a suboptimal strategy. We can pack
it tighter by finding the ranges from bases (and derived) and filling in
holes.

Notice that the algorithm's correctness does not depend on visiting the
nodes in any particular order. If we're allocating from 0, it's probably
most effective to visit types bases first instead of depth first. If
we're trying to allocate contiguous ranges, we can move both up and down
from types that are already visited. I believe that in the absence of
virtual inheritance, this is guaranteed to assign slots contiguously
without leaving any holes.

After assigning a slot, we only need to propagate a single bit across
the hierarchy. We don't need to merge all the bit vectors.

Finally, we could pull reserved slots up from transitive derived before
allocating slots instead of pushing them up to transitive bases of
transitive derived after slot allocation. This would reduce the nesting
depth of the loops.

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions