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
