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

[yosbits]

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

>> @kevinrushforth
>> 
>> To show an improvement in time efficiency, the
>> We need to fix the other high-priority hotspots first. I have determined that the current proposed change in the
>> Run-Length approach needs a lot of time to be accepted. I will change my approach.
>> I will switch to an approach that focuses solely on fixing the BitSet initialization size issue. The previous post
>> explains.
>>     @Override
>>     public boolean removeAll(Collection<?> c) {
>>         beginChange();
>>         BitSet bs = new BitSet(c.size());
>> 
>> * new BitSet(c.size())
>> 
>> Don't you notice this mistake?
>
>> * new BitSet(c.size())
>> 
>> Don't you notice this mistake?
> 
> It certainly isn't an exact size, and probably not a very good guess in many cases (e.g., a small number of objects
> where one near the end is chosen), but it is at least a lower limit on the memory you need.
> So I take it you propose to allocate the BitSet the first time you need it, while looping in the reverse order of this
> array list? That will work, at the (fairly minor) expense of having to do a null check in the loop (or the added
> complexity of an initial loop that runs until you find one and a second loop from that point to the end).  I'm still
> not convinced that this is worth the effort, at least not without a test case showing some gain that we can measure.

Here's an improvement on BitSet:

 java
	private boolean remove(Collection<?> c, boolean isRemoveAll) {
		BitSet bs = null;
		// find last index
		final int max = size();
		int i;
		for (i = max - 1; i >= 0; i--) {
			if (c.contains(get(i)) == isRemoveAll) {
				bs = new BitSet(i);
				bs.set(i--);
				break;
			}
		}
		final boolean removed = bs != null;
		beginChange();
		if (removed) {
			for (; i >= 0; i--) {
				if (c.contains(get(i)) == isRemoveAll) {
					bs.set(i);
				}
			}
			int cur = max;
			while ((cur = bs.previousSetBit(cur - 1)) >= 0) {
				remove(cur);
			}
		}
		endChange();
		return removed;
	}
Extreme test cases that show the most improvement.

 Java
			for (; olist.size() > 0;) {
				olist.removeAll(olist.get(olist.size() - 1));
			}

Here's an improvement on Run-Lengths:
 java
	private boolean remove(Collection<?> c, boolean isRemoveAll) {
		int[] runLength = new int[4];
		int size = 0;
		final int n = size();
		{
			int run = 0;
			boolean flag = isRemoveAll;
			for (int i = n - 1; i >= 0; i--) {
				if (c.contains(get(i)) == flag) {
					run++;
				} else {
					if (runLength.length <= size) {
						runLength = Arrays.copyOf(runLength, Math.min(runLength.length << 1, n + 1));
					}
					runLength[size++] = run;
					run = 1;
					flag = !flag;
				}
			}
			if (run > 0 && flag == isRemoveAll) {
				if (runLength.length <= size) {
					runLength = Arrays.copyOf(runLength, Math.min(runLength.length << 1, n + 1));
				}
				runLength[size++] = run;
			}
		}
		boolean flag = true;
		boolean removed = false;
		beginChange();
		int cur = n - 1;
		for (int i = 0; i < size; i++) {
			final int run = runLength[i];
			if (flag) {
				removed = run > 0;
				for (int to = cur - run; cur > to; cur--) {
					remove(cur);
				}
			} else {
				cur -= run;
			}
			flag = !flag;
		}
		endChange();
		return removed;
	}

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

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