Add tombstones to VectorMap. #7193
Conversation
|
It should be noted that this performance improvement is not enough to make |
odd
force-pushed
the
vectormap-tombstones
branch
from
c87b3ff to
3417fae
Compare
|
Awesome work, I actually had a local branch open with slightly different implementation, just didn't get around to finishing it (been a bit busy in the last week unfortunately). My implementation basically stored the tombstones as I will likely have time to compare this weekend (which is when I will review it), but I suspect that this implementation may be a bit faster. |
This comment has been minimized.
This comment has been minimized.
|
Unfortunately I haven't had much time to look into this in extensive detail (I have been very busy this weekend). I did some modifications on this PR around a week ago but it appears that as usual its a matter of tradeoffs. I think that consecutive removes are likely to be the least common operation, so personally I am satisfied with the tradeoff. @Ichoran would you be able to look into this? |
|
I generally don't think the However, with the limited look I've taken, this looks good to me for this approach, and the approach I describe doesn't exist right now. So this PR is better than not, I think. |
odd
force-pushed
the
vectormap-tombstones
branch
from
19f0406 to
3d90137
Compare
| extends AbstractMap[K, V] | ||
| final class VectorMap[K, +V] private ( | ||
| private[immutable] val fields: Vector[Any], | ||
| private[immutable] val underlying: Map[K, (Int, V)], dummy: Boolean) |
There was a problem hiding this comment.
What's the purpose of the dummy parameter?
There was a problem hiding this comment.
I imagine to disambiguate with the secondary constructor
private[immutable] def this(fields: Vector[K], underlying: Map[K, (Int, V)]) = {
this(fields, underlying, false)
}There was a problem hiding this comment.
@szeiger, @hrhino Yes, thats right, the dummy parameter is there to make the erased signatures of the primary and secondary constructors different from each other. Only the secondary constructor having the ostensible correct type of the fields vector should be available to other members of the immutable package, while the primary constructor using the relaxed type of the fields vector should only be available to the VectorMap class itself.
|
looks like this needs a run through scala-collections-laws |
8 participants
Add tombstones to mark removed slots in the fields vector. The tombstones carry a distance that points to the next occupied slot. If the distance is zero any following slots are also tombstones. This scheme adds at most one indirection for lookup (if slot
sis requested and slotsis a tombstone with distanced, return slots + dinstead), but will require adjusting the distance for all immediately preceding tombstones to the current slot upon removal. It has similar or slightly better performance compared to the currentVectorMapimplementation for all operations exceptremovewhere this implementation has a significant advantage (especially for removal of non-consecutive elements) since no shifting of all following elements is necessary as in the current implementation.