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

[yosbits]

On Fri, 9 Oct 2020 01:06:54 GMT, Kevin Rushforth <kcr at openjdk.org> wrote:

>> It seems that many people are interested, so I pushed the change.
>> I don't understand how to proceed with the review on Github correctly, so if I have anything to do, please comment.
>> 
>>  java
>>                     for(int to=cur-run; cur > to; cur--) {
>>                         remove(cur);
>>                     }
>>                     removed = true;
>> 
>> 
>> 
>> This can be moved out of the loop and will be included in the next change.
>
> Before I review the actual proposed change, I have a pair of related high-level questions that I should have asked at
> the beginning of this review.
> 1. What is the expected performance gain, and under what conditions would you see the gain?
> 2. Do you have a program that demonstrates / measures the performance gain?
> 
> It doesn't need to be something that would be suitable for including as part of the PR, but we will need some test
> program that shows enough of a performance gain to justify making this change.

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.

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

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