OrderedTickQueue: resize logic?
vadcx opened this issue · 1 comments
- Link to file on develop branch: OrderedTickQueue.java
- Current version, permalink: OrderedTickQueue.java @ 81c3253a75
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.
