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

[yosbits]

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

>> Hopefully not looking in the wrong version but:
>> (1) When dealing with BitSets previously, maybe this was by design butI didn’t see any usage of BitSet’s
>> “clear(<index>)” to remove items from the BitSet.  Although given move to remove it may be moot now. (2) If no longer
>> using the BitSet, may want to remove the import for this (3) In context, usage of HashSet was suggested.  I don’t
>> believe HashSet is thread safe.  If using it, may want to consider ConcurrentHashSet.  Although not sure if this is
>> more efficient either.
>
> I plan to push changes that remain compatible, respecting the judgment of the project leader, but I would like to point
> out the following:
> There seems to be a problem with the reproduction code as follows.
> 
> * If there are duplicate items, the unselected parts will also be deleted.
> * Using getSelectedIndices() is more advantageous in terms of performance than getSelectedItems ().
> 
> Therefore, this context should normally be avoided,
> Seems like less important compatibility.

The next implementation will probably have a good balance between space and time.
Currently being tested.
Performance can be further improved by using ArrayList and int [].

 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;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        // Throw NullPointerException if c is null
        if (c.isEmpty()) {
            boolean retained = !this.isEmpty();
            if (retained) {
                clear();
            }
            return retained;
        }
        if (this.isEmpty()) {
            return false;
        }
        List<Integer> runLengths = new java.util.ArrayList<>();
        {
            int run = 0;
            boolean flag = false;
            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 = false;
        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;
    }

I'm planning to push it in a few days.

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

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