950716 - Misc. BitSet optimizations

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, enhancement)

Description

[Dan Gohman [:sunfish]]

The following are a few micro-optimization patches for BitSet.

Comment 1

[Dan Gohman [:sunfish]]

Attachment: bitset-iterator-refactor.patch

This is just a little simplification in BitSet::Iterator.

Comment 2

[Dan Gohman [:sunfish]]

Attachment: bitset-optimize.patch

This patch manually hoists several loads out of loops in BitSet code. Compilers can't easily do this automatically because type-based alias analysis (aka TBAA aka -fstrict-aliasing) is insufficient.

As an aside, this is actually a nice example of one reason why TBAA is not a nice language feature in C++.

Comment 3

[Dan Gohman [:sunfish]]

Attachment: reorder-struct-fields.patch

This just reorders a few struct members so that the pointer member comes before the length member, since the pointer member is accessed more.

Comment 4

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8348107 [details] [diff] [review]
bitset-iterator-refactor.patch

Review of attachment 8348107 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/BitSet.h
@@ +126,5 @@
> +            word_++;
> +            if (!more())
> +                return;
> +
> +            index_ = word_ * sizeof(value_) * 8;

Add a static assert that checks:
  sizeof(value) == BitSet::BitsPerWord

Comment 5

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8348108 [details] [diff] [review]
bitset-optimize.patch

Review of attachment 8348108 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/BitSet.cpp
@@ +37,5 @@
>  {
>      JS_ASSERT(bits_);
> +    const uint32_t *bits = bits_;
> +    for (unsigned int i = 0, e = numWords(); i < e; i++) {
> +        if (bits[i])

Is this really necessary here, knowing that this is a const method?

Comment 6

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8348109 [details] [diff] [review]
reorder-struct-fields.patch

Review of attachment 8348109 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/BitSet.h
@@ +36,1 @@
>      unsigned int numBits_;

nit: numBits is set by the constructor, and we do not resize BitSet, so we can mark it as constant too.

Comment 7

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #4)
> Comment on attachment 8348107 [details] [diff] [review]
> bitset-iterator-refactor.patch
> 
> Review of attachment 8348107 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/BitSet.h
> @@ +126,5 @@
> > +            word_++;
> > +            if (!more())
> > +                return;
> > +
> > +            index_ = word_ * sizeof(value_) * 8;
> 
> Add a static assert that checks:
>   sizeof(value) == BitSet::BitsPerWord

Done.

(In reply to Nicolas B. Pierron [:nbp] from comment #5)
> Comment on attachment 8348108 [details] [diff] [review]
> bitset-optimize.patch
> 
> Review of attachment 8348108 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/BitSet.cpp
> @@ +37,5 @@
> >  {
> >      JS_ASSERT(bits_);
> > +    const uint32_t *bits = bits_;
> > +    for (unsigned int i = 0, e = numWords(); i < e; i++) {
> > +        if (bits[i])
> 
> Is this really necessary here, knowing that this is a const method?

No, this one that's read-only doesn't, but it's nice to keep the code consistent.

(In reply to Nicolas B. Pierron [:nbp] from comment #6)
> Comment on attachment 8348109 [details] [diff] [review]
> reorder-struct-fields.patch
> 
> Review of attachment 8348109 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/BitSet.h
> @@ +36,1 @@
> >      unsigned int numBits_;
> 
> nit: numBits is set by the constructor, and we do not resize BitSet, so we
> can mark it as constant too.

Done.

https://hg.mozilla.org/integration/mozilla-inbound/rev/b63e9c3e67ac
https://hg.mozilla.org/integration/mozilla-inbound/rev/4361abf1909a
https://hg.mozilla.org/integration/mozilla-inbound/rev/cf2cf0c49610

Comment 8

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/b63e9c3e67ac
https://hg.mozilla.org/mozilla-central/rev/4361abf1909a
https://hg.mozilla.org/mozilla-central/rev/cf2cf0c49610