Closed Bug 950716 Opened 7 years ago Closed 7 years ago

Misc. BitSet optimizations

Categories

(Core :: JavaScript Engine: JIT, enhancement)

enhancement
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla29

People

(Reporter: sunfish, Assigned: sunfish)

References

Details

Attachments

(3 files)

The following are a few micro-optimization patches for BitSet.
This is just a little simplification in BitSet::Iterator.
Attachment #8348107 - Flags: review?(nicolas.b.pierron)
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++.
Attachment #8348108 - Flags: review?(nicolas.b.pierron)
This just reorders a few struct members so that the pointer member comes before the length member, since the pointer member is accessed more.
Attachment #8348109 - Flags: review?(nicolas.b.pierron)
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
Attachment #8348107 - Flags: review?(nicolas.b.pierron) → review+
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?
Attachment #8348108 - Flags: review?(nicolas.b.pierron) → review+
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.
Attachment #8348109 - Flags: review?(nicolas.b.pierron) → review+
(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
Depends on: 953145
You need to log in before you can comment on or make changes to this bug.