Continual Compaction

Issue #38 new
Rob Eden created an issue

One of the trickier aspects of using Trove (and all similar implementations) is keeping the structure compact as removes as performed (see issue #35).

I believe a way to minimize this would be to do immediate compaction when items are removed. This would shift the penalty to remove time and distribute it over the quantity of removes so that it doesn't come in one big spike.

The way this would be accomplished would be to find the last item in the bucket and pull it into the removed slot, if applicable. Here's an example of what a bucket would look like (obviously there are no references, so this is a logic view):

Before remove:

 -----       -----       -----
|  A  | --> |  B  | --> |  C  | 
 -----       -----       ----- 

First step of remove, find element to remove:

 ---------       -----       -----
| REMOVED | --> |  B  | --> |  C  | 
 ---------       -----       ----- 

Second step of remove, find last element in chain and move it up:

 -----       -----
|  C  | --> |  B  |
 -----       -----

This does away with REMOVED slot markers so they never have to be dealt with. It also has the advantage of not creating new backing arrays which the current implementation of compact() does.

Comments (1)

  1. Log in to comment