Closed Bug 662648 Opened 13 years ago Closed 13 years ago

IonMonkey: Add fixed-size, fast, lightweight bit-set datastructure

Categories

(Core :: JavaScript Engine, defect)

x86_64
Linux
defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: adrake, Assigned: adrake)

Details

Attachments

(1 file, 1 obsolete file)

This is currently part of my register allocation patch, but I'm splitting it out so that it can be used in other analyses.
Attached patch Extracted from regalloc. (obsolete) — Splinter Review
If you need any other operations on it, let me know.
Assignee: general → adrake
Status: NEW → ASSIGNED
Attachment #537886 - Flags: review?(rpearl)
Comment on attachment 537886 [details] [diff] [review]
Extracted from regalloc.

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

Looks good!

::: js/src/ion/BitSet.cpp
@@ +52,5 @@
> +    unsigned int otherWords = 1 + other->max_ / (8 * sizeof(*bits_));
> +    for (unsigned int i = 0; i < otherWords; i++)
> +        bits_[i] |= other->bits_[i];
> +}
> +

The one thing my algorithm needs that's not in here is intersection (trivially similar to insertAll). 

Might as well throw set difference in as well?
Attachment #537886 - Flags: review?(rpearl) → review+
I added 'removeAll' and 'intersect' as suggested, and factored the nasty size calculation that was duplicated. I also strengthened the size invariant to require two BitSets to have the same maximum to be unioned/intersected/differenced/etc -- if you need otherwise I can add the code to handle it..
Attachment #537886 - Attachment is obsolete: true
Attachment #537894 - Flags: review?(rpearl)
Comment on attachment 537894 [details] [diff] [review]
Added new operations, cleaned up a little.

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

Looks good!
Attachment #537894 - Flags: review?(rpearl) → review+
http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/e36878a02ac6
Status: ASSIGNED → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.