SpscGrowableArrayQueue on failed check for look ahead the next element availability check is reversed leading to incorrect estimation of capacity

[akarnokd]

I found two more bugs:

L91: should allow initial size to be equal to max size and thus not growing.

L138-145: there is a missing case when the queue is at max capacity and there is exactly one space left: L138 checks if the index + 1 is occupied thus in the max capacity case, one can't have 128 elements in the queue but only 127; in the below max case, it won't use cell at index unless index + 1 is occupied, which is odd. I think the correct check would be:

if (null == lvElement(buffer, calcElementOffset(index + 1, mask))) { // buffer is not full
    return writeToQueue(buffer, e, index, offset);
} else if (mask == maxSize) {
    if (null == lvElement(buffer, offset)) {
        return writeToQueue(buffer, e, index, offset);
    }
    // we're full and can't grow
    return false;
}

Note the == check.

[nitsanw]

I'd say L91 check is valid, if intial == max than this is not growable and you should not use this queue.
L138: The maxCapacity is in fact 127 to avoid the special case. There's no issue to my mind as long as the capacity is fixed. You could argue there's some waste here, but I'm OK with wasting 1 slot to avoid the special case.

[akarnokd]

Okay. In that case, I'll use the modified version in RxJava where the queue must hold the number of elements its capacity provides.

[nitsanw]

I was under the impression we're moving towards RxJava depending on JCTools?

[nitsanw]

@akarnokd Also, did you re-benchmark for your use case using new implementation?

[akarnokd]

First of all, the JCTools implementation failed/hung RxJava tests and the OperatorMergePerf benchmark because the incorrect capacity management. I did post some experimental results here. In that particular benchmark, it didn't really matter if the queue can grow since they are all pooled so in case of some reader slowdown, all pooled queues may eventually end up maxed out.

I haven't rerun the RxRingBufferPerf test this time because the aim was to make object pooling/release work correctly. In my observation, even if one saves on the allocated amount in a non-pooled case, the volume of GC still makes Ben uncomfortable.

[nitsanw]

I'm not sure what you mean by the 'full capacity' issue. The queue interface doesn't have a notion of capacity, and all the queues already take some liberty with the requested capacity when they allocate to the nearest power of 2. Spsc in its current version utilizes the array up to the last element and grow able doesn't but since it's not specified as a requirement anywhere that they should I'm not sure there's a bug here. Perhaps more of an expected behaviour issue?
The implementations do conform to having a stable capacity in the sense that you will not be able to exceed a certain capacity in one time and then hit a full queue on the same capacity later, but that is not a stated feature either.
I've not had time to review the benchmark code, thanks for linking to latest results.

[akarnokd]

Sure, it is an expected behavior issue and since my use case is different, I did the necessary adjustments locally and closed this issue.

Still, L138 feels a bit odd. Apart from this under-utilization property, let's assume the buffer is at its full size and the lookahead step is 25% of it. Now if the queue gets 75% full, the look-ahead will find a non-null element ahead and falls through to L138 where the check says if the element after the insertion point (index) is occupied, insert the element at the index. However, since the queue is 25% empty, this check will be false and thus the offer rejects the insertion until the queue is drained below 75%. I'm not certain if L138 would ever pass unless the buffer size is really small (8?).

[nitsanw]

Ok, i was confused about your initial comment, the check:
Null!= buffer[tail+1] is incorrect, will fix.
In which case the queue capacity will be mask.
I have had a longish rant on the futility on C&P dependencies previously so I'll leave for you and Ben to make up your minds.

On 5 Jan 2015, at 17:43, David Karnok [email protected] wrote:

Sure, it is an expected behavior issue and since my use case is different, I did the necessary adjustments locally and closed this issue.

Still, L138 feels a bit odd. Apart from this under-utilization property, let's assume the buffer is at its full size and the lookahead step is 25% of it. Now if the queue gets 75% full, the look-ahead will find a non-null element ahead and falls through to L138 where the check says if the element after the insertion point (index) is occupied, insert the element at the index. However, since the queue is 25% empty, this check will be false and thus the offer rejects the insertion until the queue is drained below 75%. I'm not certain if L138 would ever pass unless the buffer size is really small (8?).

—
Reply to this email directly or view it on GitHub.

[nitsanw]

Fixed