RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]

[yosbits]

On Fri, 9 Oct 2020 13:37:57 GMT, Kevin Rushforth <kcr at openjdk.org> wrote:

>> The performance improvements of the first change were self-evident, but
>> I agree that the current changes need to be explained.
>> 
>> BitSet Features
>> * When using BitSet, memory usage (N/8) is wasted in the case of removing the last one in the list. This is often caused
>>   by user actions.
>> 
>> PR Features
>> * The proposal records the run length of the flag, so the memory usage can be kept small in the case of consecutive
>>   deletion indexes. The worst case is the case where the deletion indexes are not contiguous, which results in 4*N memory
>>   consumption, but this happens very rarely. It's also the same as the memory usage of getSelectedIndices(). (Memory
>>   usage is further improved by setting it to int[]).
>> * Also, the delete loop is less CPU intensive and faster than BitSet's flag scan.
>> 
>> I will attach a test, but you'll have to wait until my next leisure time.
>
> I understand that this will improve the performance of this method in some cases (but not all as you correctly point
> out), but what I really meant by my questions was: When does this matter to an application's overall performance and
> what is the performance gain you would expect to see?  As a general rule, we do not make this sort of performance
> optimization without a compelling reason. Improving the performance of a method is not by itself compelling unless
> there is a demonstrable (not theoretical) improvement to applications. I look forward to seeing the test program that
> shows the performance problem with the current implementation and allows us to measure the improvement with your
> proposed patch.

### Improved space efficiency

* The BitSet approach has a problem where the last delete index determines the size of the internal BitSet array; the
  Run-Length approach eliminates this memory waste.

* The Run-Lengths approach has its drawbacks, but the worst case can be avoided by switching to the BitSet approach when
  the array is expanded.

* **The BitSet approach (original source) has the wrong initial size.** The exact initialization size can be determined by
    evaluating from the end of the index. As a result, the expansion of the internal array can be suppressed and
    unnecessary memory copy does not occur. Therefore, there is still room for optimization in the BitSet approach.

* The worst case of the BitSet approach is likely to occur, and the worst case of the Run-Length approach is unlikely.
  Because the worst case of the BitSet approach happens at least one, but Run-Length requires N / 2 deletions.

* The point at which the space efficiency of Run-Length and BitSet switches can be determined during the execution of the
  Run-Length approach.

#### Memory consumption to remove the last item in the list.

**The BitSet approach**

ceil(N/64)*8

* 12,504 B for 100,000 items
* 1,256 B for 10,000 items
* 1,28 B for 1000 items
* 16 B in 100 items

**Run-Lengths Approach**
For consecutive indexes, regardless of N

4 * 4
= 16 B

4 * (N +1) in the worst case

* The Run-Lengths approach has its drawbacks, but the worst case can be avoided by switching to the BitSet approach at
  the time of array expansion (hybrid approach).

-------------

PR: https://git.openjdk.java.net/jfx/pull/305