On Fri, 9 Oct 2020 22:59:37 GMT, Kevin Rushforth <k...@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