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

[Kevin Rushforth]

On Wed, 7 Oct 2020 21:14:14 GMT, yosbits <github.com+7517141+yososs at openjdk.org> wrote:

>> **The next implementation will probably have a good balance between space and time.**
>> Unless you do something like delete the even or odd indexes
>> The space efficiency is very high.
>> 
>> Currently being tested.
>> 
>>  Java
>>     @Override
>>     public boolean removeAll(Collection<?> c) {
>>     	// Throw NullPointerException if c is null
>>         if (c.isEmpty() || this.isEmpty()) {
>>             return false;
>>         }
>>         List<Integer> runLengths = new java.util.ArrayList<>();
>>         {
>>             int run = 0;
>>             boolean flag = true;
>>             for (int i=size()-1; i>=0; i--) {
>>                 if (c.contains(get(i))==flag) {
>>                     run++;
>>                 } else {
>>                     runLengths.add(run);
>>                     run = 1;
>>                     flag = !flag;
>>                 }
>>             }
>>             if (run>0 && flag) {
>>                 runLengths.add(run);
>>             }
>>         }
>>         boolean flag = true;
>>         boolean removed = false;
>>         if(runLengths.size()>0) {
>>             beginChange();
>>             int cur = size()-1;
>>             for (int run:runLengths) {
>>                 if(flag) {
>>                     for(int to=cur-run; cur > to; cur--) {
>>                         remove(cur);
>>                         removed = true;
>>                     }
>>                 }else {
>>                     cur -= run;
>>                 }
>>                 flag = !flag;
>>             }
>>             endChange();
>>             return removed;
>>         }
>>         return false;
>>     }
>> This implementation is more efficient by using an int [] array instead of an ArrayList.
>> 
>> I'm planning to push it in a few days.
>
> 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.

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

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