Re: RFR 8170159 Improve the performance of BitSet traversal

[Martin Buchholz]

+1

On Fri, Jun 15, 2018 at 2:52 PM, Paul Sandoz  wrote:

>
>
> On Jun 15, 2018, at 2:24 PM, Martin Buchholz  wrote:
>
> Still looks correct, but I might keep looking for something  more elegant.
> What bothers me a little now is
>
> 1290 long word = words[u] & (WORD_MASK << i);
>
>
> which is part of the initial setup and is not necessary on each iteration.
>
>
> I was looking at this too. From a performance perspective i am not very
> concerned. Aesthetically it bothers me, but at this point i am willing to
> declare victory and patch later if there is a better way.
>
> Paul.
>

Re: RFR 8170159 Improve the performance of BitSet traversal

[Paul Sandoz]

> On Jun 15, 2018, at 2:24 PM, Martin Buchholz  wrote:
> 
> Still looks correct, but I might keep looking for something  more elegant.
> What bothers me a little now is
> 
> 1290 long word = words[u] & (WORD_MASK << i);
> 
> which is part of the initial setup and is not necessary on each iteration. 
> 

I was looking at this too. From a performance perspective i am not very 
concerned. Aesthetically it bothers me, but at this point i am willing to 
declare victory and patch later if there is a better way.

Paul.

Re: RFR 8170159 Improve the performance of BitSet traversal

[Martin Buchholz]

Still looks correct, but I might keep looking for something  more elegant.
What bothers me a little now is

1290 long word = words[u] & (WORD_MASK << i);


which is part of the initial setup and is not necessary on each iteration.

On Fri, Jun 15, 2018 at 1:13 PM, Paul Sandoz  wrote:

> Thanks! Doh, obvious in hindsight.
>
> On Jun 15, 2018, at 11:05 AM, Martin Buchholz  wrote:
>
> It took me a while to realize why you were checking tz < 63.  It's because
> the shift by 64 that might occur below would be a no-op!
>
>
> Right!
>
> 1301 action.accept(i++);1302  
>word &= (WORD_MASK << i);
>
> Can we rewrite to simply flip the one bit via
>
> word &= ~(1L << i);
> action.accept(i++);
>
> and then we can simplify the tz handling?
>
>
> Yes, and there is no need to increment i:
>
>   http://cr.openjdk.java.net/~psandoz/jdk/JDK-8170159-
> bitset-traverse/webrev/src/java.base/share/classes/java/
> util/BitSet.java.sdiff.html
>
> Paul.
>

Re: RFR 8170159 Improve the performance of BitSet traversal

[Paul Sandoz]

Thanks! Doh, obvious in hindsight.

> On Jun 15, 2018, at 11:05 AM, Martin Buchholz  wrote:
> 
> It took me a while to realize why you were checking tz < 63.  It's because 
> the shift by 64 that might occur below would be a no-op!

Right!

> 1301 action.accept(i++);
> 1302 word &= (WORD_MASK << i);
> Can we rewrite to simply flip the one bit via
> 
> word &= ~(1L << i);
> action.accept(i++);
> 
> and then we can simplify the tz handling?
> 


Yes, and there is no need to increment i:

  
http://cr.openjdk.java.net/~psandoz/jdk/JDK-8170159-bitset-traverse/webrev/src/java.base/share/classes/java/util/BitSet.java.sdiff.html
 


Paul.

Re: RFR 8170159 Improve the performance of BitSet traversal

[Martin Buchholz]

It took me a while to realize why you were checking tz < 63.  It's because
the shift by 64 that might occur below would be a no-op!

1301 action.accept(i++);1302
  word &= (WORD_MASK << i);

Can we rewrite to simply flip the one bit via

word &= ~(1L << i);
action.accept(i++);

and then we can simplify the tz handling?

Re: RFR 8170159 Improve the performance of BitSet traversal

[Paul Sandoz]

Hi Martin,

Thanks for reviewing.

> On Jun 15, 2018, at 7:57 AM, Martin Buchholz  wrote:
> 
> Code looks correct to me, but as usual there are some things I would try to 
> do differently,  
> 

Indeed, i tried a few different approaches before settling on this code shape.

> 1292 while (word != 0 && tz < 63) {
> 
> I'd try to make this loop simply
> while (word != 0)
> 

I started out like that but in the end preferred that both loop conditions were 
upfront, to avoid another break or explicitly setting word to 0, then the only 
break is the weird one to deal with the annoying bug magnet :-)


> ---
> 
> Probably neither of us is fond of the bug magnet special case for 
> Integer.MAX_VALUE.  Maybe just store fence as a long or as a wordindex which 
> can't overflow (while giving up on intra-word splitting?)
> 
> Here's a fun program demonstrating cardinality overflow:
> 
> import java.util.BitSet;
> 
> public class BitSetCardinality {
> public static void main(String[] args) throws Throwable {
> BitSet s = new BitSet();
> s.flip(0, Integer.MAX_VALUE);
> System.out.println(s.cardinality());
> s.flip(Integer.MAX_VALUE);
> System.out.println(s.cardinality());
> }
> }
> 
> 
> ==> java -Xmx20g -esa -ea BitSetCardinality
> 2147483647
> -2147483648
> 

Oh dear!

Thanks,
Paul.


> 
> On Thu, Jun 14, 2018 at 2:35 PM, Paul Sandoz  > wrote:
> Hi,
> 
> Please review this enhancement to improve the performance of BitSet traversal 
> when using a stream.
> 
>   http://cr.openjdk.java.net/~psandoz/jdk/JDK-8170159-bitset-traverse/webrev/ 
>  
>  >
> 
> The associated issue started out life referring to the BitSet’s spliterator 
> reporting SIZED, and to report that the cardinality has to be computed. This 
> has some cost but performance analysis (see issue for attached benchmark) has 
> shown that the cost is small compared to the cost of traversal. It is 
> recognized that the cost is higher for smaller BitSets but not unduly so. 
> Thus it was concluded that it was reasonable for the spliterator to report 
> SIZED. 
> 
> The issue was adjusted to focus on improving the performance of the BitSet’s 
> spliterator forEachRemaining method. For large randomized BitSets a 1.6x 
> speedup can be observed, and for smaller sizes a more modest speed up. The 
> prior conclusion about reporting SIZED still holds.
> 
> Thanks,
> Paul.
> 

Re: RFR 8170159 Improve the performance of BitSet traversal

[Martin Buchholz]

Code looks correct to me, but as usual there are some things I would try to
do differently,

1292 while (word != 0 && tz < 63) {


I'd try to make this loop simply
while (word != 0)

---

Probably neither of us is fond of the bug magnet special case for
Integer.MAX_VALUE.  Maybe just store fence as a long or as a wordindex
which can't overflow (while giving up on intra-word splitting?)

Here's a fun program demonstrating cardinality overflow:

import java.util.BitSet;

public class BitSetCardinality {
public static void main(String[] args) throws Throwable {
BitSet s = new BitSet();
s.flip(0, Integer.MAX_VALUE);
System.out.println(s.cardinality());
s.flip(Integer.MAX_VALUE);
System.out.println(s.cardinality());
}
}


==> java -Xmx20g -esa -ea BitSetCardinality
2147483647
-2147483648


On Thu, Jun 14, 2018 at 2:35 PM, Paul Sandoz  wrote:

> Hi,
>
> Please review this enhancement to improve the performance of BitSet
> traversal when using a stream.
>
>   http://cr.openjdk.java.net/~psandoz/jdk/JDK-8170159-
> bitset-traverse/webrev/  psandoz/jdk/JDK-8170159-bitset-traverse/webrev/>
>
> The associated issue started out life referring to the BitSet’s
> spliterator reporting SIZED, and to report that the cardinality has to be
> computed. This has some cost but performance analysis (see issue for
> attached benchmark) has shown that the cost is small compared to the cost
> of traversal. It is recognized that the cost is higher for smaller BitSets
> but not unduly so. Thus it was concluded that it was reasonable for the
> spliterator to report SIZED.
>
> The issue was adjusted to focus on improving the performance of the
> BitSet’s spliterator forEachRemaining method. For large randomized BitSets
> a 1.6x speedup can be observed, and for smaller sizes a more modest speed
> up. The prior conclusion about reporting SIZED still holds.
>
> Thanks,
> Paul.