Lithium (Fabric)

Lithium (Fabric)

Mods
22M Downloads

OrderedTickQueue: resize logic?

vadcx opened this issue · 1 comments

commented

lithium-fabric/src/main/java/me/jellysquid/mods/lithium/common/world/scheduler/OrderedTickQueue.java

Lines 118 to 138 in 81c3253

private void resize(int size) {
// Only compact the array if it is completely empty or is less than 50% filled
if (size == 0 || size < this.arr.length / 2) {
this.arr = copyArray(this.arr, size);
} else {
// Fill the unused array elements with nulls to release our references to the elements in it
for (int i = size; i < this.arr.length; i++) {
this.arr[i] = null;
}
}
this.firstIndex = 0;
this.lastIndexExclusive = size;
if (size == 0 || !this.isSorted) {
this.currentMaxSubTickOrder = Long.MIN_VALUE;
} else {
OrderedTick<T> tick = this.arr[size - 1];
this.currentMaxSubTickOrder = tick == null ? Long.MIN_VALUE : tick.subTickOrder();
}
}

Resize is supposed to shrink the array to reduce memory consumption. A couple things that made me stumble:

If size is 0, then following copyArray() with size=0 will allocate new OrderedTick[0];. At first I thought this could be improved (instead: resize to an initial size), but with the current code it seems intentional to actually get a size 0 array.

Upon further inspection, it appears the entire class could be rewritten to reduce the amount of reallocations, because it already tracks first/lastIndex? Since the backing array is kept private and all accesses happen through the interface, the functions could be rewritten to rely on the indexes more and update them, rather than resizing/copying the array. Then the reallocation may only happen when the occupied size drops below a threshold (e.g. in removeNullsAndConsumed) or new values are added. Sorting would operate on a part of the array etc. (There are no null holes, right?)

Further, if the array happens to be resized to zero, the size increases in offer(...) will start very slow, despite being powers of two (0 → 1 → 2 → 4 → 8 → 16 (initial size constant)). The rewrite based on indexes would allow to have a backing array of any minimum size while not performing any operations when it's isEmpty().

I think the entire copyArray function can be replaced with Arrays.copyOf​(T[] original, int newLength), no? (jdk source).

Similarly, the manual looping in L123 to set null could be replaced with Arrays.fill(...) - that's just for readability, if anything.

commented

Thanks for the suggestions

  • 👍1