Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Fri, 9 Oct 2020 22:59:37 GMT, Kevin Rushforth 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/3
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Fri, 9 Oct 2020 17:47:31 GMT, yosbits wrote: > * 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. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Fri, 9 Oct 2020 16:51:05 GMT, yosbits
wrote:
>> I understand that this will improve the performance of this method in some
>> cases (but not all as you correctly point
>> out), but what I really meant by my questions was: When does this matter to
>> an application's overall performance and
>> what is the performance gain you would expect to see? As a general rule, we
>> do not make this sort of performance
>> optimization without a compelling reason. Improving the performance of a
>> method is not by itself compelling unless
>> there is a demonstrable (not theoretical) improvement to applications. I
>> look forward to seeing the test program that
>> shows the performance problem with the current implementation and allows us
>> to measure the improvement with your
>> proposed patch.
>
> ### Improved space efficiency
>
> * The BitSet approach has a problem where the last delete index determines
> the size of the internal BitSet array; the
> Run-Length approach eliminates this memory waste.
>
> * The Run-Lengths approach has its drawbacks, but the worst case can be
> avoided by switching to the BitSet approach when
> the array is expanded.
>
> * **The BitSet approach (original source) has the wrong initial size.** The
> exact initialization size can be determined by
> evaluating from the end of the index. As a result, the expansion of the
> internal array can be suppressed and
> unnecessary memory copy does not occur. Therefore, there is still room
> for optimization in the BitSet approach.
>
> * The worst case of the BitSet approach is likely to occur, and the worst
> case of the Run-Length approach is unlikely.
> Because the worst case of the BitSet approach happens at least one, but
> Run-Length requires N / 2 deletions.
>
> * The point at which the space efficiency of Run-Length and BitSet switches
> can be determined during the execution of the
> Run-Length approach.
>
> Memory consumption to remove the last item in the list.
>
> **The BitSet approach**
>
> ceil(N/64)*8
>
> * 12,504 B for 100,000 items
> * 1,256 B for 10,000 items
> * 1,28 B for 1000 items
> * 16 B in 100 items
>
> **Run-Lengths Approach**
> For consecutive indexes, regardless of N
>
> 4 * 4
> = 16 B
>
> 4 * (N +1) in the worst case
>
> * The Run-Lengths approach has its drawbacks, but the worst case can be
> avoided by switching to the BitSet approach at
> the time of array expansion (hybrid approach).
@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?
-
PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Fri, 9 Oct 2020 13:37:57 GMT, Kevin Rushforth wrote: >> The performance improvements of the first change were self-evident, but >> I agree that the current changes need to be explained. >> >> BitSet Features >> * When using BitSet, memory usage (N/8) is wasted in the case of removing >> the last one in the list. This is often caused >> by user actions. >> >> PR Features >> * The proposal records the run length of the flag, so the memory usage can >> be kept small in the case of consecutive >> deletion indexes. The worst case is the case where the deletion indexes >> are not contiguous, which results in 4*N memory >> consumption, but this happens very rarely. It's also the same as the >> memory usage of getSelectedIndices(). (Memory >> usage is further improved by setting it to int[]). >> * Also, the delete loop is less CPU intensive and faster than BitSet's flag >> scan. >> >> I will attach a test, but you'll have to wait until my next leisure time. > > I understand that this will improve the performance of this method in some > cases (but not all as you correctly point > out), but what I really meant by my questions was: When does this matter to > an application's overall performance and > what is the performance gain you would expect to see? As a general rule, we > do not make this sort of performance > optimization without a compelling reason. Improving the performance of a > method is not by itself compelling unless > there is a demonstrable (not theoretical) improvement to applications. I look > forward to seeing the test program that > shows the performance problem with the current implementation and allows us > to measure the improvement with your > proposed patch. ### Improved space efficiency * The BitSet approach has a problem where the last delete index determines the size of the internal BitSet array; the Run-Length approach eliminates this memory waste. * The Run-Lengths approach has its drawbacks, but the worst case can be avoided by switching to the BitSet approach when the array is expanded. * **The BitSet approach (original source) has the wrong initial size.** The exact initialization size can be determined by evaluating from the end of the index. As a result, the expansion of the internal array can be suppressed and unnecessary memory copy does not occur. Therefore, there is still room for optimization in the BitSet approach. * The worst case of the BitSet approach is likely to occur, and the worst case of the Run-Length approach is unlikely. Because the worst case of the BitSet approach happens at least one, but Run-Length requires N / 2 deletions. * The point at which the space efficiency of Run-Length and BitSet switches can be determined during the execution of the Run-Length approach. Memory consumption to remove the last item in the list. **The BitSet approach** ceil(N/64)*8 * 12,504 B for 100,000 items * 1,256 B for 10,000 items * 1,28 B for 1000 items * 16 B in 100 items **Run-Lengths Approach** For consecutive indexes, regardless of N 4 * 4 = 16 B 4 * (N +1) in the worst case * The Run-Lengths approach has its drawbacks, but the worst case can be avoided by switching to the BitSet approach at the time of array expansion (hybrid approach). - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Fri, 9 Oct 2020 05:31:54 GMT, yosbits wrote: >> 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. > > The performance improvements of the first change were self-evident, but > I agree that the current changes need to be explained. > > BitSet Features > * When using BitSet, memory usage (N/8) is wasted in the case of removing the > last one in the list. This is often caused > by user actions. > > PR Features > * The proposal records the run length of the flag, so the memory usage can be > kept small in the case of consecutive > deletion indexes. The worst case is the case where the deletion indexes are > not contiguous, which results in 4*N memory > consumption, but this happens very rarely. It's also the same as the memory > usage of getSelectedIndices(). (Memory > usage is further improved by setting it to int[]). > * Also, the delete loop is less CPU intensive and faster than BitSet's flag > scan. > > I will attach a test, but you'll have to wait until my next leisure time. I understand that this will improve the performance of this method in some cases (but not all as you correctly point out), but what I really meant by my questions was: When does this matter to an application's overall performance and what is the performance gain you would expect to see? As a general rule, we do not make this sort of performance optimization without a compelling reason. Improving the performance of a method is not by itself compelling unless there is a demonstrable (not theoretical) improvement to applications. I look forward to seeing the test program that shows the performance problem with the current implementation and allows us to measure the improvement with your proposed patch. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Fri, 9 Oct 2020 01:06:54 GMT, Kevin Rushforth wrote:
>> 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.
The performance improvements of the first change were self-evident, but
I agree that the current changes need to be explained.
BitSet Features
* When using BitSet, memory usage (N/8) is wasted in the case of removing the
last one in the list. This is often caused
by user actions.
PR Features
* The proposal records the run length of the flag, so the memory usage can be
kept small in the case of consecutive
deletion indexes. The worst case is the case where the deletion indexes are
not contiguous, which results in 4*N memory
consumption, but this happens very rarely. It's also the same as the memory
usage of getSelectedIndices(). (Memory
usage is further improved by setting it to int[]).
* Also, the delete loop is less CPU intensive and faster than BitSet's flag
scan.
I will attach a test, but you'll have to wait until my next leisure time.
-
PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Wed, 7 Oct 2020 21:14:14 GMT, yosbits
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 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
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Wed, 7 Oct 2020 18:34:23 GMT, yosbits
wrote:
>> 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.**
> 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 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.
-
PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Wed, 7 Oct 2020 14:24:36 GMT, yosbits
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()” 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 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 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
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Wed, 7 Oct 2020 12:11:12 GMT, Eric Bresie wrote: >>> >>> >>> I'm preparing a change that won't break compatibility, so stay tuned. >>> The test seems to need to be added. >> >> sounds good :) Note, that I'm working on >> [JDK-8254040](https://bugs.openjdk.java.net/browse/JDK-8254040) which will >> add >> regression tests that your change will have to pass (turned out that f.i. >> FilteredList also relies on the two-pass >> approach). Until you are done, you might consider changing the state of >> this to Draft. > > 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()” 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 selectIndices () is more advantageous in terms of performance than selectedItems (). Therefore, this context should normally be avoided, Seems like less important compatibility. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Wed, 7 Oct 2020 12:06:09 GMT, Jeanette Winzenburg wrote: >> I'm preparing a change that won't break compatibility, so stay tuned. >> The test seems to need to be added. > >> >> >> I'm preparing a change that won't break compatibility, so stay tuned. >> The test seems to need to be added. > > sounds good :) Note, that I'm working on > [JDK-8254040](https://bugs.openjdk.java.net/browse/JDK-8254040) which will add > regression tests that your change will have to pass (turned out that f.i. > FilteredList also relies on the two-pass > approach). Until you are done, you might consider changing the state of this > to Draft. 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()” 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. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Wed, 7 Oct 2020 11:39:29 GMT, yosbits wrote: > > > I'm preparing a change that won't break compatibility, so stay tuned. > The test seems to need to be added. sounds good :) Note, that I'm working on [JDK-8254040](https://bugs.openjdk.java.net/browse/JDK-8254040) which will add regression tests that your change will have to pass (turned out that f.i. FilteredList also relies on the two-pass approach). Until you are done, you might consider changing the state of this to Draft. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Wed, 7 Oct 2020 11:30:16 GMT, Jeanette Winzenburg wrote: >>> >>> >>> did anyone look into Java-Collection-Frameworks (ArrayList and friends or >>> Eclipse-Collections) how they handle this >>> situation effeciently? >> >> not me - but good idea, provided they support modifications to the source >> list while removing. >> >> BTW, just noticed that Tree/Table/View never had the issue that was fixed >> with introducing the two-pass approach, can't >> nail why not - they are using the same selectedItems (from >> MultipleSelectionModelBase), any ideas? > >> BTW, just noticed that Tree/Table/View never had the issue that was fixed >> with introducing the two-pass approach, can't >> nail why not - they are using the same selectedItems (from >> MultipleSelectionModelBase), any ideas? > > because it's not a live-lookup: TreeView keeps some cache of exposed > treeItems - that's to where the getModelItem() in > selectedItems is delegated to - which is updated on receiving a listChange, > that is not during the modification. I'm preparing a change that won't break compatibility, so stay tuned. The test seems to need to be added. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Wed, 7 Oct 2020 11:12:43 GMT, Jeanette Winzenburg wrote: > BTW, just noticed that Tree/Table/View never had the issue that was fixed > with introducing the two-pass approach, can't > nail why not - they are using the same selectedItems (from > MultipleSelectionModelBase), any ideas? because it's not a live-lookup: TreeView keeps some cache of exposed treeItems - that's to where the getModelItem() in selectedItems is delegated to - which is updated on receiving a listChange, that is not during the modification. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Wed, 7 Oct 2020 10:39:02 GMT, Tom Schindl wrote: > > > did anyone look into Java-Collection-Frameworks (ArrayList and friends or > Eclipse-Collections) how they handle this > situation effeciently? not me - but good idea, provided they support modifications to the source list while removing. BTW, just noticed that Tree/Table/View never had the issue that was fixed with introducing the two-pass approach, can't nail why not - they are using the same selectedItems (from MultipleSelectionModelBase), any ideas? - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Wed, 7 Oct 2020 09:38:40 GMT, Jeanette Winzenburg wrote: >> The error occurs as specified in getSelectedItems(). It seems to be correct >> to write the following >> >> `listView.getItems().removeAll(new HashSet<>(selectedItems)) >> ` >> >> (or ArrayList) >> >> It could be interpreted that the intention was to mitigate the side effects >> associated with the getSelectedItems() >> specification. >> The use of BitSet should be avoided when the list is large, as it is not a >> sparse implementation and therefore wastes a >> lot of memory. For example, when removing the last item in the list. >> `BitSet bs = new BitSet(c.size()); >> ` >> The previous change was an incorrect initialization size for BitSet. > >> >> >> The error occurs as specified in getSelectedItems(). > > no, both spec and implementation (at least as far as its relation to this > issue) is correct. > >> It seems to be correct to write the following >> >> `listView.getItems().removeAll(new HashSet<>(selectedItems)) ` >> >> (or ArrayList) >> > > asking client code to adopt to changes in the framework is not an option > >> It could be interpreted that the intention was to mitigate the side effects >> associated with the getSelectedItems() >> specification. > > no side-effects, nothing mitigated, : it's a deliberate, full-fledged support > of source lists that change on removing > items from the target list >> The use of BitSet should be avoided when the list is large, as it is not a >> sparse implementation and therefore wastes a >> lot of memory. For example, when removing the last item in the list. >> `BitSet bs = new BitSet(c.size()); ` >> The previous change was an incorrect initialization size for BitSet. > > feel free to suggest another (working without requiring changes to client > code) two-pass approach in remove/retainAll. did anyone look into Java-Collection-Frameworks (ArrayList and friends or Eclipse-Collections) how they handle this situation effeciently? - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Wed, 7 Oct 2020 08:07:52 GMT, yosbits wrote: > > > The error occurs as specified in getSelectedItems(). no, both spec and implementation (at least as far as its relation to this issue) is correct. > It seems to be correct to write the following > > `listView.getItems().removeAll(new HashSet<>(selectedItems)) ` > > (or ArrayList) > asking client code to adopt to changes in the framework is not an option > It could be interpreted that the intention was to mitigate the side effects > associated with the getSelectedItems() > specification. no side-effects, nothing mitigated, : it's a deliberate, full-fledged support of source lists that change on removing items from the target list > The use of BitSet should be avoided when the list is large, as it is not a > sparse implementation and therefore wastes a > lot of memory. For example, when removing the last item in the list. > `BitSet bs = new BitSet(c.size()); ` > The previous change was an incorrect initialization size for BitSet. feel free to suggest another (working without requiring changes to client code) two-pass approach in remove/retainAll. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Tue, 6 Oct 2020 16:36:44 GMT, Kevin Rushforth wrote: >> yosbits has refreshed the contents of this pull request, and previous >> commits have been removed. The incremental views >> will show differences compared to the previous content of the PR. > > As mentioned in a reply to a comment by @kleopatra , this fix will cause a > regression in behavior, and cannot be > integrated in its current form. > A two-pass algorithm is still needed: the first pass collects the elements to > be removed, the second pass actually > removes them. While it isn't necessary to use a BitSet to collect the indexes > to be removed, that does seems a > reasonable approach. Unless there is a good reason to change it to some other > two-pass algorithm, it's probably best to > leave it as-is, in which case this PR and the associated JBS issue can be > withdrawn. The error occurs as specified in getSelectedItems(). It seems to be correct to write the following `listView.getItems().removeAll(new HashSet<>(selectedItems)) ` It could be interpreted that the intention was to mitigate the side effects associated with the getSelectedItems() specification. The use of BitSet should be avoided when the list is large, as it is not a sparse implementation and therefore wastes a lot of memory. For example, when removing the last item in the list. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Mon, 5 Oct 2020 19:22:41 GMT, Kevin Rushforth wrote:
>>> The listView test is passing for the bitSet and for the back-to-front
>>> approach. Can we imagine a context where the
>>> broken selectedItems impl would add wreckage to the latter?
>>
>> To answer my own question: yes. A failing test with the back-to-front
>> approach (the existing test in ListViewTest
>> modified in having the last item selected)
>> @Test public void test_rt35857Back() {
>> ObservableList fxList =
>> FXCollections.observableArrayList("A", "B", "C");
>> final ListView listView = new ListView(fxList);
>>
>> listView.getSelectionModel().select(2);
>>
>> ObservableList selectedItems =
>> listView.getSelectionModel().getSelectedItems();
>> assertEquals(1, selectedItems.size());
>> assertEquals("C", selectedItems.get(0));
>>
>> listView.getItems().removeAll(selectedItems);
>> assertEquals(2, fxList.size());
>> assertEquals("A", fxList.get(0));
>> assertEquals("B", fxList.get(1));
>> }
>>
>> Feels like coming nearer to the why of the BitSet approach: it guards
>> against the scenario where changing the current
>> list implicitly changes the list given as parameter - in that case, it's
>> unsafe to query the parameter list while
>> removing items (c.contains simply reports nonsense). This may happen
>> whenever the parameter list does some kind of
>> live lookup into the current list (such as f.i.
>> SelectedItemsReadOnlyObservableList) - which is not as evil as I
>> thought yesterday (did it myself in custom selectionModels ;) The BitSet
>> solves it by a two-pass approach: first
>> collect all items to remove/retain without (that is keep the parameter list
>> in a valid state, allowing to safely access
>> it), then do the removal without further accessing the (then invalid)
>> parameter list. The fix at that time was a
>> deliberate decision by the designer of the collections, so the context when
>> it happens was deemed a valid use-case.
>> Looks like we should **not** revert it.
>
> Nice catch! So now it's clear that the current approach was adopted because
> the source list itself can change as a
> result of removing an element from the target list in some cases, such as the
> one you pointed out above. I filed
> [JDK-8254040](https://bugs.openjdk.java.net/browse/JDK-8254040) to add the
> test case you listed above so we avoid a
> possible future regression. So a two-pass algorithm is still needed: the
> first one to collect the elements to be
> removed, the second to actually remove them. While it isn't necessary to use
> a BitSet to collect the indexes to be
> removed, that does seems a reasonable approach. Unless there is a good reason
> to change it to some other two-pass
> algorithm, it's probably best to leave it as-is, in which case this PR and
> the associated JBS issue can be withdrawn.
@kleopatra Thanks for the investigation. I had a feeling there is a practical
reason and not a lack of skill :)
If there is no way to do removal simultaneously then we indeed need to keep the
2-pass approach.
-
PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Tue, 22 Sep 2020 07:35:49 GMT, yosbits wrote: >> https://bugs.openjdk.java.net/browse/JDK-8253086 >> >> ObservableListWrapper.java >> * public boolean removeAll(Collection c) >> * public boolean retainAll(Collection c) >> >> These two methods use BitSet, but it doesn't make sense. >> By rewriting to the equivalent behavior that does not use BitSet, it is >> possible to reduce the CPU load in a wide range >> of use cases. >> The test is done with the following command. >> >> * gradle base: test >> * gradle controls: test > > yosbits has refreshed the contents of this pull request, and previous commits > have been removed. The incremental views > will show differences compared to the previous content of the PR. As mentioned in a reply to a comment by @kleopatra , this fix will cause a regression in behavior, and cannot be integrated in its current form. A two-pass algorithm is still needed: the first pass collects the elements to be removed, the second pass actually removes them. While it isn't necessary to use a BitSet to collect the indexes to be removed, that does seems a reasonable approach. Unless there is a good reason to change it to some other two-pass algorithm, it's probably best to leave it as-is, in which case this PR and the associated JBS issue can be withdrawn. - Changes requested by kcr (Lead). PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Sun, 4 Oct 2020 09:24:16 GMT, Jeanette Winzenburg
wrote:
>> the problem was (and still is) in MultipleSelectionModelBase:
>>
>> selectedItems = new
>> SelectedItemsReadOnlyObservableList(selectedIndices, () ->
>> getItemCount()) {
>> @Override protected T getModelItem(int index) {
>> return MultipleSelectionModelBase.this.getModelItem(index);
>> }
>> };
>>
>> meaning that the selectedItems change during the removal of items (that's
>> plain wrong!) which shows when removing the
>> items from the start:
>>
>> // removeAll before fix of
>> for (int i = 0; i < size(); ++i) {
>> if (c.contains(get(i))) {
>> remove(i);
>> --i;
>> modified = true;
>> }
>> }
>>
>> doing so is basically valid (note the decremented i). Just the selectedItems
>> look into the underlying model, so **c**
>> is changing during the removal which is a no-go.
>> Returning to the old (pre
>> [JDK-8093144](https://bugs.openjdk.java.net/browse/JDK-8093144)) still makes
>> the tests
>> against it fail (ListViewTest.test_rt35857 f.i.).
>> Still wondering why the detour over the BitSet was choosen as fix (vs. the
>> more natural remove-from-last). The listView
>> test is passing for the bitSet and for the back-to-front approach. Can we
>> imagine a context where the broken
>> selectedItems impl would add wreckage to the latter?
>
>> The listView test is passing for the bitSet and for the back-to-front
>> approach. Can we imagine a context where the
>> broken selectedItems impl would add wreckage to the latter?
>
> To answer my own question: yes. A failing test with the back-to-front
> approach (the existing test in ListViewTest
> modified in having the last item selected)
> @Test public void test_rt35857Back() {
> ObservableList fxList =
> FXCollections.observableArrayList("A", "B", "C");
> final ListView listView = new ListView(fxList);
>
> listView.getSelectionModel().select(2);
>
> ObservableList selectedItems =
> listView.getSelectionModel().getSelectedItems();
> assertEquals(1, selectedItems.size());
> assertEquals("C", selectedItems.get(0));
>
> listView.getItems().removeAll(selectedItems);
> assertEquals(2, fxList.size());
> assertEquals("A", fxList.get(0));
> assertEquals("B", fxList.get(1));
> }
>
> Feels like coming nearer to the why of the BitSet approach: it guards against
> the scenario where changing the current
> list implicitly changes the list given as parameter - in that case, it's
> unsafe to query the parameter list while
> removing items (c.contains simply reports nonsense). This may happen
> whenever the parameter list does some kind of
> live lookup into the current list (such as f.i.
> SelectedItemsReadOnlyObservableList) - which is not as evil as I
> thought yesterday (did it myself in custom selectionModels ;) The BitSet
> solves it by a two-pass approach: first
> collect all items to remove/retain without (that is keep the parameter list
> in a valid state, allowing to safely access
> it), then do the removal without further accessing the (then invalid)
> parameter list. The fix at that time was a
> deliberate decision by the designer of the collections, so the context when
> it happens was deemed a valid use-case.
> Looks like we should **not** revert it.
Nice catch! So now it's clear that the current approach was adopted because the
source list itself can change as a
result of removing an element from the target list in some cases, such as the
one you pointed out above. I filed
[JDK-8254040](https://bugs.openjdk.java.net/browse/JDK-8254040) to add the test
case you listed above so we avoid a
possible future regression.
So a two-pass algorithm is still needed: the first one to collect the elements
to be removed, the second to actually
remove them. While it isn't necessary to use a BitSet to collect the indexes to
be removed, that does seems a
reasonable approach. Unless there is a good reason to change it to some other
two-pass algorithm, it's probably best to
leave it as-is, in which case this PR and the associated JBS issue can be
withdrawn.
-
PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Sat, 3 Oct 2020 11:13:28 GMT, Jeanette Winzenburg
wrote:
> The listView test is passing for the bitSet and for the back-to-front
> approach. Can we imagine a context where the
> broken selectedItems impl would add wreckage to the latter?
To answer my own question: yes. A failing test with the back-to-front approach
(the existing test in ListViewTest
modified in having the last item selected)
@Test public void test_rt35857Back() {
ObservableList fxList = FXCollections.observableArrayList("A",
"B", "C");
final ListView listView = new ListView(fxList);
listView.getSelectionModel().select(2);
ObservableList selectedItems =
listView.getSelectionModel().getSelectedItems();
assertEquals(1, selectedItems.size());
assertEquals("C", selectedItems.get(0));
listView.getItems().removeAll(selectedItems);
assertEquals(2, fxList.size());
assertEquals("A", fxList.get(0));
assertEquals("B", fxList.get(1));
}
Feels like coming nearer to the why of the BitSet approach: it guards against
the scenario where changing the current
list implicitly changes the list given as parameter - in that case, it's unsafe
to query the parameter list while
removing items (c.contains simply reports nonsense).
This may happen whenever the parameter list does some kind of live lookup into
the current list (such as f.i.
SelectedItemsReadOnlyObservableList) - which is not as evil as I thought
yesterday (did it myself in custom
selectionModels ;) The BitSet solves it by a two-pass approach: first collect
all items to remove/retain without (that
is keep the parameter list in a valid state, allowing to safely access it),
then do the removal without further
accessing the (then invalid) parameter list.
The fix at that time was a deliberate decision by the designer of the
collections, so the context when it happens was
deemed a valid use-case. Looks like we should **not** revert it.
-
PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Fri, 2 Oct 2020 16:29:56 GMT, Kevin Rushforth wrote: >> The fix looks good to me. I left a few comments on the test, but it looks >> like a great start. > > One meta-comment: > >> @yososs yososs force-pushed the >> yososs:8253086_Optimization_of_removeAll_and_retainAll_of_ObservableListWrapper >> branch >> ... > > As indicated in the [CONTRIBUTING > guidelines](https://github.com/openjdk/jfx/blob/master/CONTRIBUTING.md#submitting-your-changes-via-a-pull-request), > please don't force-push to your branch. I understand that your testing requirements are higher than when this tested class was implemented. The fix will be pushed in the next few days. I hope I can check the coding style (including spaces) with the gradle task before git push. Let me know if there is a way to make jcheck work on my device. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Sat, 3 Oct 2020 10:09:40 GMT, Jeanette Winzenburg wrote: >> modules/javafx.base/src/test/java/test/com/sun/javafx/collections/ObservableListWrapperTest.java >> line 110: >> >>> 108: assertTrue(list.retainAll(Collections.EMPTY_SET)); >>> 109: assertEquals(0, list.size()); >>> 110: } >> >> Can you add a test for `retainAll` (in a separate test method) that removes >> multiple elements in a single call? >> Something like the following: >> * set list to `(1, 2, 3, 4, 5)` >> * remove `(2, 4)` >> * verify that the list equals `(1, 3, 5)` >> * remove `(1, 5)` >> * verify that the list equals `(3)` >> >> Similarly, a test for `retainAll` that removes multiple elements in a single >> call? >> >> * set list to `(1, 2, 3, 4, 5)` >> * retain `(1, 3, 5)` >> * verify that the list equals `(1, 3, 5)` >> * retain `(3)` >> * verify that the list equals `(3)` > > wondering why a new test? All concrete implementations are tested in the > parameterized (on the implementations) > ObservableListTest - would suggest to add to it what's not yet done (there > are several around removeAll, a bit scarce > on retainAll). Also would be easier to include notification testing (by > following the example of the available tests) > which should be done as well as the state testing (don't expect much trouble, > though). That's a good suggestion. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Fri, 2 Oct 2020 16:23:23 GMT, Kevin Rushforth wrote: >> yosbits has refreshed the contents of this pull request, and previous >> commits have been removed. The incremental views >> will show differences compared to the previous content of the PR. > > modules/javafx.base/src/test/java/test/com/sun/javafx/collections/ObservableListWrapperTest.java > line 110: > >> 108: assertTrue(list.retainAll(Collections.EMPTY_SET)); >> 109: assertEquals(0, list.size()); >> 110: } > > Can you add a test for `retainAll` (in a separate test method) that removes > multiple elements in a single call? > Something like the following: > * set list to `(1, 2, 3, 4, 5)` > * remove `(2, 4)` > * verify that the list equals `(1, 3, 5)` > * remove `(1, 5)` > * verify that the list equals `(3)` > > Similarly, a test for `retainAll` that removes multiple elements in a single > call? > > * set list to `(1, 2, 3, 4, 5)` > * retain `(1, 3, 5)` > * verify that the list equals `(1, 3, 5)` > * retain `(3)` > * verify that the list equals `(3)` wondering why a new test? All concrete implementations are tested in the parameterized (on the implementations) ObservableListTest - would suggest to add to it what's not yet done (there are several around removeAll, a bit scarce on retainAll). Also would be easier to include notification testing (by following the example of the available tests) which should be done as well as the state testing (don't expect much trouble, though). - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Fri, 2 Oct 2020 18:20:18 GMT, Kevin Rushforth wrote:
>>> the reason BitSet was introduced was to ensure that the elements are
>>> removed from this List in reverse order (prior to
>>> that fix, they were removed in forward order with the loop index being
>>> messed up).
>>
>> But why do they need to be removed in reverse order to begin with? The super
>> implementation does forward removal, or
>> just use `removeIf`.
>
> It might not matter any more (presuming that it was done correctly), but it
> seems safer to leave the logic as-is to
> match the existing behavior.
the problem was (and still is) in MultipleSelectionModelBase:
selectedItems = new
SelectedItemsReadOnlyObservableList(selectedIndices, () -> getItemCount()) {
@Override protected T getModelItem(int index) {
return MultipleSelectionModelBase.this.getModelItem(index);
}
};
meaning that the selectedItems change during the removal of items (that's plain
wrong!) which shows when removing the
items from the start:
// removeAll before fix of
for (int i = 0; i < size(); ++i) {
if (c.contains(get(i))) {
remove(i);
--i;
modified = true;
}
}
doing so is basically valid (note the decremented i). Just the selectedItems
look into the underlying model, so **c**
is changing during the removal which is a no-go.
Returning to the old (pre
[JDK-8093144](https://bugs.openjdk.java.net/browse/JDK-8093144)) still makes
the tests
against it fail (ListViewTest.test_rt35857 f.i.).
Still wondering why the detour over the BitSet was choosen as fix (vs. the more
natural remove-from-last). The listView
test is passing for the bitSet and for the back-to-front approach. Can we
imagine a context where the broken
selectedItems impl would add wreckage to the latter?
-
PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Fri, 2 Oct 2020 17:16:03 GMT, Nir Lisker wrote: >> I looked at the fix for >> [JDK-8093144](https://bugs.openjdk.java.net/browse/JDK-8093144), and the >> reason BitSet was >> introduced was to ensure that the elements are removed from this List in >> reverse order (prior to that fix, they were >> removed in forward order with the loop index being messed up). This patch >> preserves the correct behavior, and just >> looks to be a better fix for that earlier problem. I do recommend running >> the failing test case from >> [JDK-8093144](https://bugs.openjdk.java.net/browse/JDK-8093144) to verify no >> regressions, but it looks like a good and >> safe fix to me. @yososs I marked this discussion thread as unresolved >> mainly to make this comment, but also because >> you didn't fix the spacing suggested by @nlisker -- please do that. > >> the reason BitSet was introduced was to ensure that the elements are removed >> from this List in reverse order (prior to >> that fix, they were removed in forward order with the loop index being >> messed up). > > But why do they need to be removed in reverse order to begin with? The super > implementation does forward removal, or > just use `removeIf`. It might not matter any more (presuming that it was done correctly), but it seems safer to leave the logic as-is to match the existing behavior. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Fri, 2 Oct 2020 16:01:20 GMT, Kevin Rushforth wrote: > the reason BitSet was introduced was to ensure that the elements are removed > from this List in reverse order (prior to > that fix, they were removed in forward order with the loop index being messed > up). But why do they need to be removed in reverse order to begin with? The super implementation does forward removal, or just use `removeIf`. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Fri, 2 Oct 2020 16:27:09 GMT, Kevin Rushforth wrote: >> yosbits has refreshed the contents of this pull request, and previous >> commits have been removed. The incremental views >> will show differences compared to the previous content of the PR. > > The fix looks good to me. I left a few comments on the test, but it looks > like a great start. One meta-comment: > @yososs yososs force-pushed the > yososs:8253086_Optimization_of_removeAll_and_retainAll_of_ObservableListWrapper > branch > ... As indicated in the [CONTRIBUTING guidelines](https://github.com/openjdk/jfx/blob/master/CONTRIBUTING.md#submitting-your-changes-via-a-pull-request), please don't force-push to your branch. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Tue, 22 Sep 2020 07:35:49 GMT, yosbits
wrote:
>> https://bugs.openjdk.java.net/browse/JDK-8253086
>>
>> ObservableListWrapper.java
>> * public boolean removeAll(Collection c)
>> * public boolean retainAll(Collection c)
>>
>> These two methods use BitSet, but it doesn't make sense.
>> By rewriting to the equivalent behavior that does not use BitSet, it is
>> possible to reduce the CPU load in a wide range
>> of use cases.
>> The test is done with the following command.
>>
>> * gradle base: test
>> * gradle controls: test
>
> yosbits has refreshed the contents of this pull request, and previous commits
> have been removed. The incremental views
> will show differences compared to the previous content of the PR.
The fix looks good to me. I left a few comments on the test, but it looks like
a great start.
modules/javafx.base/src/main/java/com/sun/javafx/collections/ObservableListWrapper.java
line 203:
> 201: boolean retained = false;
> 202: beginChange();
> 203: for (int i = size()-1; i>=0; i--) {
Please fix the spacing. Per our coding guidelines, this should be:
for (int i = size() - 1; i >= 0; i--) {
modules/javafx.base/src/test/java/test/com/sun/javafx/collections/ObservableListWrapperTest.java
line 38:
> 36: import java.util.Arrays;
> 37: import java.util.Collection;
> 38: import java.util.Collections;
Can you sort the imports?
modules/javafx.base/src/test/java/test/com/sun/javafx/collections/ObservableListWrapperTest.java
line 110:
> 108: assertTrue(list.retainAll(Collections.EMPTY_SET));
> 109: assertEquals(0, list.size());
> 110: }
Can you add a test for `retainAll` (in a separate test method) that removes
multiple elements in a single call?
Something like the following:
* set list to `(1, 2, 3, 4, 5)`
* remove `(2, 4)`
* verify that the list equals `(1, 3, 5)`
* remove `(1, 5)`
* verify that the list equals `(3)`
Similarly, a test for `retainAll` that removes multiple elements in a single
call?
* set list to `(1, 2, 3, 4, 5)`
* retain `(1, 3, 5)`
* verify that the list equals `(1, 3, 5)`
* retain `(3)`
* verify that the list equals `(3)`
modules/javafx.base/src/test/java/test/com/sun/javafx/collections/ObservableListWrapperTest.java
line 78:
> 76: assertEquals(3, list.size());
> 77: assertTrue(list.removeAll(1));
> 78: assertEquals(2, list.size());
Can you add a check that the correct element was removed (i.e., check that the
list equals `(2, 3)`)?
-
PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
On Tue, 22 Sep 2020 01:58:48 GMT, yosbits wrote: >> digging a bit: the BitSet was introduced with >> https://bugs.openjdk.java.net/browse/JDK-8093144 to solve some problem >> with selectionModels - don't know whether those still hold (there had been >> extensive changes to selection since then). > > Thank you for searching for the origin of this strange code. However, as far > as I read the comments, my intuition seems > to be correct. I looked at the fix for [JDK-8093144](https://bugs.openjdk.java.net/browse/JDK-8093144), and the reason BitSet was introduced was to ensure that the elements are removed from this List in reverse order (prior to that fix, they were removed in forward order with the loop index being messed up). This patch preserves the correct behavior, and just looks to be a better fix for that earlier problem. I do recommend running the failing test case from [JDK-8093144](https://bugs.openjdk.java.net/browse/JDK-8093144) to verify no regressions, but it looks like a good and safe fix to me. @yososs I marked this discussion thread as unresolved mainly to make this comment, but also because you didn't fix the spacing suggested by @nlisker -- please do that. - PR: https://git.openjdk.java.net/jfx/pull/305
Re: RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
> https://bugs.openjdk.java.net/browse/JDK-8253086 > > ObservableListWrapper.java > * public boolean removeAll(Collection c) > * public boolean retainAll(Collection c) > > These two methods use BitSet, but it doesn't make sense. > By rewriting to the equivalent behavior that does not use BitSet, it is > possible to reduce the CPU load in a wide range > of use cases. > The test is done with the following command. > > * gradle base: test > * gradle controls: test yosbits has refreshed the contents of this pull request, and previous commits have been removed. The incremental views will show differences compared to the previous content of the PR. The pull request contains one new commit since the last revision: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper - Changes: - all: https://git.openjdk.java.net/jfx/pull/305/files - new: https://git.openjdk.java.net/jfx/pull/305/files/4c61c071..8b319c6d Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jfx&pr=305&range=03 - incr: https://webrevs.openjdk.java.net/?repo=jfx&pr=305&range=02-03 Stats: 0 lines in 0 files changed: 0 ins; 0 del; 0 mod Patch: https://git.openjdk.java.net/jfx/pull/305.diff Fetch: git fetch https://git.openjdk.java.net/jfx pull/305/head:pull/305 PR: https://git.openjdk.java.net/jfx/pull/305
