Given this: FastBitVector a; FastBitVector b; FastBitVector c; I want to be able to say things like: Set a to some weird combination of the others, with the implementation being a single loop and no copying: a = ((~a) & b) + c; Express merge, filter, and exclude using operators, to be consistent: a &= ~c; Rapidly iterate over some combination of vectors. (a & ~(b | c)).forEachSetBit([&] (size_t index) { ... }); We can make this work by having operator&, operator|, and operator~ return a view of the input bitvectors, which supports all immutable FastBitVector operations and combines the uint32_t* words array on-the-fly. For example, if you do: auto merge = a | b; Then 'merge' will have an internal FastBitVector type that supports all const FastBitVector ops. While a FastBitVector points to a uint32_t* m_words and accesses that words array directly on each bit access, the 'merge' vector uses a FastBitVectorOWords adapter that, when asked for a word at an index, will or together the words at that index in a and b. Template magic makes this invisible and free.
Created attachment 288529 [details] work in progress
Created attachment 288536 [details] the patch
Attachment 288536 [details] did not pass style-queue: ERROR: Source/WTF/wtf/FastBitVector.h:330: Missing spaces around | [whitespace/operators] [3] ERROR: Source/JavaScriptCore/dfg/DFGLiveCatchVariablePreservationPhase.cpp:76: When wrapping a line, only indent 4 spaces. [whitespace/indent] [3] Total errors found: 2 in 15 files If any of these errors are false positives, please file a bug against check-webkit-style.
(In reply to comment #3) > Attachment 288536 [details] did not pass style-queue: > > > ERROR: Source/WTF/wtf/FastBitVector.h:330: Missing spaces around | > [whitespace/operators] [3] No. > ERROR: > Source/JavaScriptCore/dfg/DFGLiveCatchVariablePreservationPhase.cpp:76: > When wrapping a line, only indent 4 spaces. [whitespace/indent] [3] Fixed. > Total errors found: 2 in 15 files > > > If any of these errors are false positives, please file a bug against > check-webkit-style.
Comment on attachment 288536 [details] the patch View in context: https://bugs.webkit.org/attachment.cgi?id=288536&action=review r=me with comments/suggestions. > Source/WTF/ChangeLog:38 > + uint32_t word(size_t index) { return b.m_words.word(index) | ~c.m_words.word(index); } It's cool to do this on the fly, I like that strategy. > Source/WTF/ChangeLog:52 > + I think that it's harder to see what is going on here, then using operators, because infix I agree. FWIW, I've never been a fan of the name 'filter' over set language like 'intersection'. > Source/WTF/wtf/FastBitVector.h:37 > +inline size_t fastBitVectorArrayLength(size_t numBits) { return (numBits + 31) >> 5; } Nit: I think it is easier to understand what this is doing if you wrote it as "/ 32" instead of ">> 5". > Source/WTF/wtf/FastBitVector.h:96 > + memcpy(m_words, other.m_words, length * 4); Style: I'm not a big fan of using 4 everywhere. Even though it's more verbose, I think everything is clearer if you defined a constant somewhere as sizeof(uint32_t) and used it instead of 4. > Source/WTF/wtf/FastBitVector.h:99 > uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(length, 4)); Why calloc if you're going to memcpy afterwords? Why not just fast malloc? > Source/WTF/wtf/FastBitVector.h:117 > + memset(m_words, 255, arrayLength() * 4); Nit: I'd use std::numeric_limits here or UCHAR_MAX > Source/WTF/wtf/FastBitVector.h:180 > +template<typename Left, typename Right> > +class FastBitVectorAndWords { > +public: Suggestion: another possibility is to define a template over a third type which is some sort of enum like: BinaryOp { And, Or } and then have the `uint32_t word(size_t index)` switch over the BinaryOp. That way you don't have two classes that are doing almost the same thing. > Source/WTF/wtf/FastBitVector.h:255 > + return !m_view.word(index); This should be "~", right? > Source/WTF/wtf/FastBitVector.h:346 > unsigned j = i << 5; Style: ditto about *32 instead of <<. And this should be a size_t and not unsigned. > Source/WTF/wtf/FastBitVector.h:359 > + // I'm pretty sure that this is the most efficient way to do this. I don't think this comment adds anything. I also think I agree with it since the above loop bails on words early if they are empty. I'm not sure how you'd do the same thing if you manually wrote such a loop for clear bits. > Source/WTF/wtf/FastBitVector.h:370 > + void forEachBit(bool value, const Func& func) const > + { > + if (value) > + forEachSetBit(func); > + else > + forEachClearBit(func); > + } What's this going to be used for? > Source/WTF/wtf/FastBitVector.h:378 > + ALWAYS_INLINE size_t findBit(size_t startIndex, bool value) const Is this going to be used for some GC stuff? If the only use is that loop, then shouldn't we just use forEachSetBit instead? > Source/WTF/wtf/FastBitVector.h:380 > + uint32_t skipValue = -(static_cast<uint32_t>(value) ^ 1); Since this will always be inlined, I'd just write this as: uint32_t skipValue = value ? 0 : UINT_MAX; Otherwise, it's just super confusing to read what this code is doing. At first, I thought it was a bug for it to be "-", and not "~", but then I realized that's intended. > Source/WTF/wtf/FastBitVector.h:384 > + size_t wordIndex = startIndex >> 5; > + size_t startIndexInWord = startIndex - (wordIndex << 5); Style: ditto shifts for division/multiplication. > Source/WTF/wtf/FastBitVector.h:419 > + // You'd think that we could remove this friend if we used protected, but you'd be wrong, > + // because templates. Nit: I don't think this comment adds much. But it is quite funny that templates cause this. > Source/WTF/wtf/FastBitVector.h:487 > + for (unsigned i = arrayLength(); i--;) > + m_words.word(i) |= other.m_words.word(i); I wonder if there is any way to do this lazily like you do with "|" and "&" and "~" operators. Do you think it'd be worth it? > Source/WTF/wtf/FastBitVector.h:543 > + BitReference at(size_t index) > + { > + ASSERT_WITH_SECURITY_IMPLICATION(index < numBits()); > + return BitReference(&m_words.word(index >> 5), 1 << (index & 31)); > + } Why not just return a bool? Or is this a way to cache a live update view on the bit vector? > Source/WTF/wtf/StdLibExtras.h:321 > +bool findBitInWord(T word, size_t& index, size_t endIndex, bool value) I wonder if we should enforce unsigned type here. Otherwise, the shift below can cause a loop to never terminate. Maybe it's worth a static_assert that T is unsigned?
(In reply to comment #5) > Comment on attachment 288536 [details] > the patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=288536&action=review > > r=me with comments/suggestions. > > > Source/WTF/ChangeLog:38 > > + uint32_t word(size_t index) { return b.m_words.word(index) | ~c.m_words.word(index); } > > It's cool to do this on the fly, I like that strategy. > > > Source/WTF/ChangeLog:52 > > + I think that it's harder to see what is going on here, then using operators, because infix > > I agree. FWIW, I've never been a fan of the name 'filter' over set language > like 'intersection'. > > > Source/WTF/wtf/FastBitVector.h:37 > > +inline size_t fastBitVectorArrayLength(size_t numBits) { return (numBits + 31) >> 5; } > > Nit: I think it is easier to understand what this is doing if you wrote it > as "/ 32" instead of ">> 5". I once got bit by expecting this strength reduction to happen, but forgetting that I was using signed. Once I realized my mistake I vowed to always say ">>" when that's what I meant. I guess that was a long time ago. I'll change it. > > > Source/WTF/wtf/FastBitVector.h:96 > > + memcpy(m_words, other.m_words, length * 4); > > Style: I'm not a big fan of using 4 everywhere. Even though it's more > verbose, I think everything is clearer if you defined a constant somewhere > as sizeof(uint32_t) and used it instead of 4. FWIW that was copied from the code that was there already. I'll change it. > > > Source/WTF/wtf/FastBitVector.h:99 > > uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(length, 4)); > > Why calloc if you're going to memcpy afterwords? Why not just fast malloc? Security shmecurity: fastCalloc() does the length * 4 in an overflow-safe way. We could make this call fastMalloc, but then we'd have to be careful. I'd rather not worry about it in this patch. > > > Source/WTF/wtf/FastBitVector.h:117 > > + memset(m_words, 255, arrayLength() * 4); > > Nit: I'd use std::numeric_limits here or UCHAR_MAX I'll keep this one alone. I think that 255 is pretty clear. > > > Source/WTF/wtf/FastBitVector.h:180 > > +template<typename Left, typename Right> > > +class FastBitVectorAndWords { > > +public: > > Suggestion: another possibility is to define a template over a third type > which is some sort of enum like: > BinaryOp { > And, Or > } > and then have the `uint32_t word(size_t index)` switch over the BinaryOp. > That way you don't > have two classes that are doing almost the same thing. True. I was already getting lost in the abstractions in this code, so I didn't want to add any more abstractions on top of that. To me, the code duplication here is less evil than additional abstraction. > > > Source/WTF/wtf/FastBitVector.h:255 > > + return !m_view.word(index); > > This should be "~", right? Of course! Ooops! > > > Source/WTF/wtf/FastBitVector.h:346 > > unsigned j = i << 5; > > Style: ditto about *32 instead of <<. And this should be a size_t and not > unsigned. Right. > > > Source/WTF/wtf/FastBitVector.h:359 > > + // I'm pretty sure that this is the most efficient way to do this. > > I don't think this comment adds anything. I also think I agree with it since > the above loop bails on words early if they are empty. I'm not sure how > you'd do the same thing if you manually wrote such a loop for clear bits. That's the thing, there is possibly a better way: downshift with carry. Just as you can downshift with zero extend or sign extend, you can also downshift with arbitrary bits used as the extend. This is used for implementing 64-bit >> on 32-bit systems: you do a 32-bit downshift "with carry", which fills the upper part of the word with bits shifted out of some other register. Here we'd want the word>>=1 to do a 1-fill. I think we could do that with an rshift w/ carry. That would let us avoid the bitnot instruction. And here's the kicker: this would mean that we could have common code for the forEachSetBit and forEachClearBit paths, because we could do either 0-fill or 1-fill depending on 'value' (0-fill if the skip value is 0 or 1-fill if the skip value is -1). I'll remove the comment. > > > Source/WTF/wtf/FastBitVector.h:370 > > + void forEachBit(bool value, const Func& func) const > > + { > > + if (value) > > + forEachSetBit(func); > > + else > > + forEachClearBit(func); > > + } > > What's this going to be used for? Probably one of the GC passes. I wanted an API that felt complete so that I could start brainstorming the GC stuff. Here's a possible example: void forEachBlockIn(Generation generation, const Func& func) { m_eden.forEachBit(generation == Eden, [&] (size_t blockIndex) { func(m_blocks[blockIndex]); }); } > > > Source/WTF/wtf/FastBitVector.h:378 > > + ALWAYS_INLINE size_t findBit(size_t startIndex, bool value) const > > Is this going to be used for some GC stuff? If the only use is that loop, > then shouldn't we just use forEachSetBit instead? This is going to be used in the GC. It's not supposed to be used for that loop, but it's useful to remember that loop when understanding the semantics of findBit(). Our GC does lots of incremental block walks. With the bitvector approach, you'd remember the last index you looked at, and then you'd findBit(lastIndex + 1, true). > > > Source/WTF/wtf/FastBitVector.h:380 > > + uint32_t skipValue = -(static_cast<uint32_t>(value) ^ 1); > > Since this will always be inlined, I'd just write this as: > uint32_t skipValue = value ? 0 : UINT_MAX; No, because your code isn't necessarily as efficient when 'value' is a variable. Just because the code is inlined does not mean that the caller statically knew the value of 'value'! Maybe LLVM would know how to reduce select(value, 0, UINT_MAX) to what I wrote. But why risk that? > > Otherwise, it's just super confusing to read what this code is doing. At > first, I thought it was a bug for it to be "-", and not "~", but then I > realized that's intended. I know it's confusing, but I think we need it. > > > Source/WTF/wtf/FastBitVector.h:384 > > + size_t wordIndex = startIndex >> 5; > > + size_t startIndexInWord = startIndex - (wordIndex << 5); > > Style: ditto shifts for division/multiplication. OK. > > > Source/WTF/wtf/FastBitVector.h:419 > > + // You'd think that we could remove this friend if we used protected, but you'd be wrong, > > + // because templates. > > Nit: I don't think this comment adds much. But it is quite funny that > templates cause this. > > > Source/WTF/wtf/FastBitVector.h:487 > > + for (unsigned i = arrayLength(); i--;) > > + m_words.word(i) |= other.m_words.word(i); > > I wonder if there is any way to do this lazily like you do with "|" and "&" > and "~" operators. Do you think it'd be worth it? This is easier to compile, and makes it way obvious to the compiler that the load from m_words.word(i) and the store back to m_words.word(i) can be combined into a single instruction without changing program behavior. If we abstracted this behind operator= and operator|, then the load wouldn't be so obviously close to the store anymore. > > > Source/WTF/wtf/FastBitVector.h:543 > > + BitReference at(size_t index) > > + { > > + ASSERT_WITH_SECURITY_IMPLICATION(index < numBits()); > > + return BitReference(&m_words.word(index >> 5), 1 << (index & 31)); > > + } > > Why not just return a bool? Or is this a way to cache a live update view on > the bit vector? Then 'bitVector[index] = true' wouldn't work. > > > Source/WTF/wtf/StdLibExtras.h:321 > > +bool findBitInWord(T word, size_t& index, size_t endIndex, bool value) > > I wonder if we should enforce unsigned type here. Otherwise, the shift below > can cause a loop to never terminate. Maybe it's worth a static_assert that T > is unsigned? OK.
(In reply to comment #6) > (In reply to comment #5) > > Comment on attachment 288536 [details] > > the patch > > > > View in context: > > https://bugs.webkit.org/attachment.cgi?id=288536&action=review > > > > r=me with comments/suggestions. > > > > > Source/WTF/ChangeLog:38 > > > + uint32_t word(size_t index) { return b.m_words.word(index) | ~c.m_words.word(index); } > > > > It's cool to do this on the fly, I like that strategy. > > > > > Source/WTF/ChangeLog:52 > > > + I think that it's harder to see what is going on here, then using operators, because infix > > > > I agree. FWIW, I've never been a fan of the name 'filter' over set language > > like 'intersection'. > > > > > Source/WTF/wtf/FastBitVector.h:37 > > > +inline size_t fastBitVectorArrayLength(size_t numBits) { return (numBits + 31) >> 5; } > > > > Nit: I think it is easier to understand what this is doing if you wrote it > > as "/ 32" instead of ">> 5". > > I once got bit by expecting this strength reduction to happen, but > forgetting that I was using signed. Once I realized my mistake I vowed to > always say ">>" when that's what I meant. > > I guess that was a long time ago. I'll change it. > > > > > > Source/WTF/wtf/FastBitVector.h:96 > > > + memcpy(m_words, other.m_words, length * 4); > > > > Style: I'm not a big fan of using 4 everywhere. Even though it's more > > verbose, I think everything is clearer if you defined a constant somewhere > > as sizeof(uint32_t) and used it instead of 4. > > FWIW that was copied from the code that was there already. I'll change it. > > > > > > Source/WTF/wtf/FastBitVector.h:99 > > > uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(length, 4)); > > > > Why calloc if you're going to memcpy afterwords? Why not just fast malloc? > > Security shmecurity: fastCalloc() does the length * 4 in an overflow-safe > way. > > We could make this call fastMalloc, but then we'd have to be careful. I'd > rather not worry about it in this patch. > > > > > > Source/WTF/wtf/FastBitVector.h:117 > > > + memset(m_words, 255, arrayLength() * 4); > > > > Nit: I'd use std::numeric_limits here or UCHAR_MAX > > I'll keep this one alone. I think that 255 is pretty clear. > > > > > > Source/WTF/wtf/FastBitVector.h:180 > > > +template<typename Left, typename Right> > > > +class FastBitVectorAndWords { > > > +public: > > > > Suggestion: another possibility is to define a template over a third type > > which is some sort of enum like: > > BinaryOp { > > And, Or > > } > > and then have the `uint32_t word(size_t index)` switch over the BinaryOp. > > That way you don't > > have two classes that are doing almost the same thing. > > True. I was already getting lost in the abstractions in this code, so I > didn't want to add any more abstractions on top of that. To me, the code > duplication here is less evil than additional abstraction. > > > > > > Source/WTF/wtf/FastBitVector.h:255 > > > + return !m_view.word(index); > > > > This should be "~", right? > > Of course! Ooops! > > > > > > Source/WTF/wtf/FastBitVector.h:346 > > > unsigned j = i << 5; > > > > Style: ditto about *32 instead of <<. And this should be a size_t and not > > unsigned. > > Right. > > > > > > Source/WTF/wtf/FastBitVector.h:359 > > > + // I'm pretty sure that this is the most efficient way to do this. > > > > I don't think this comment adds anything. I also think I agree with it since > > the above loop bails on words early if they are empty. I'm not sure how > > you'd do the same thing if you manually wrote such a loop for clear bits. > > That's the thing, there is possibly a better way: downshift with carry. Just > as you can downshift with zero extend or sign extend, you can also downshift > with arbitrary bits used as the extend. This is used for implementing 64-bit > >> on 32-bit systems: you do a 32-bit downshift "with carry", which fills > the upper part of the word with bits shifted out of some other register. > > Here we'd want the word>>=1 to do a 1-fill. I think we could do that with > an rshift w/ carry. > > That would let us avoid the bitnot instruction. > > And here's the kicker: this would mean that we could have common code for > the forEachSetBit and forEachClearBit paths, because we could do either > 0-fill or 1-fill depending on 'value' (0-fill if the skip value is 0 or > 1-fill if the skip value is -1). > > I'll remove the comment. > > > > > > Source/WTF/wtf/FastBitVector.h:370 > > > + void forEachBit(bool value, const Func& func) const > > > + { > > > + if (value) > > > + forEachSetBit(func); > > > + else > > > + forEachClearBit(func); > > > + } > > > > What's this going to be used for? > > Probably one of the GC passes. I wanted an API that felt complete so that I > could start brainstorming the GC stuff. > > Here's a possible example: > > void forEachBlockIn(Generation generation, const Func& func) > { > m_eden.forEachBit(generation == Eden, [&] (size_t blockIndex) { > func(m_blocks[blockIndex]); }); > } > > > > > > Source/WTF/wtf/FastBitVector.h:378 > > > + ALWAYS_INLINE size_t findBit(size_t startIndex, bool value) const > > > > Is this going to be used for some GC stuff? If the only use is that loop, > > then shouldn't we just use forEachSetBit instead? > > This is going to be used in the GC. It's not supposed to be used for that > loop, but it's useful to remember that loop when understanding the semantics > of findBit(). > > Our GC does lots of incremental block walks. With the bitvector approach, > you'd remember the last index you looked at, and then you'd > findBit(lastIndex + 1, true). > > > > > > Source/WTF/wtf/FastBitVector.h:380 > > > + uint32_t skipValue = -(static_cast<uint32_t>(value) ^ 1); > > > > Since this will always be inlined, I'd just write this as: > > uint32_t skipValue = value ? 0 : UINT_MAX; > > No, because your code isn't necessarily as efficient when 'value' is a > variable. Just because the code is inlined does not mean that the caller > statically knew the value of 'value'! > > Maybe LLVM would know how to reduce select(value, 0, UINT_MAX) to what I > wrote. But why risk that? Yeah, I wasn't thinking about the case where 'value' wasn't a constant. I agree with keeping this how it is. However, this is one of those rare occasions where I'd advocate for a comment with the more obvious code above it to describe what's happening. > > > > > Otherwise, it's just super confusing to read what this code is doing. At > > first, I thought it was a bug for it to be "-", and not "~", but then I > > realized that's intended. > > I know it's confusing, but I think we need it. > > > > > > Source/WTF/wtf/FastBitVector.h:384 > > > + size_t wordIndex = startIndex >> 5; > > > + size_t startIndexInWord = startIndex - (wordIndex << 5); > > > > Style: ditto shifts for division/multiplication. > > OK. > > > > > > Source/WTF/wtf/FastBitVector.h:419 > > > + // You'd think that we could remove this friend if we used protected, but you'd be wrong, > > > + // because templates. > > > > Nit: I don't think this comment adds much. But it is quite funny that > > templates cause this. > > > > > Source/WTF/wtf/FastBitVector.h:487 > > > + for (unsigned i = arrayLength(); i--;) > > > + m_words.word(i) |= other.m_words.word(i); > > > > I wonder if there is any way to do this lazily like you do with "|" and "&" > > and "~" operators. Do you think it'd be worth it? > > This is easier to compile, and makes it way obvious to the compiler that the > load from m_words.word(i) and the store back to m_words.word(i) can be > combined into a single instruction without changing program behavior. If we > abstracted this behind operator= and operator|, then the load wouldn't be so > obviously close to the store anymore. > > > > > > Source/WTF/wtf/FastBitVector.h:543 > > > + BitReference at(size_t index) > > > + { > > > + ASSERT_WITH_SECURITY_IMPLICATION(index < numBits()); > > > + return BitReference(&m_words.word(index >> 5), 1 << (index & 31)); > > > + } > > > > Why not just return a bool? Or is this a way to cache a live update view on > > the bit vector? > > Then 'bitVector[index] = true' wouldn't work. > > > > > > Source/WTF/wtf/StdLibExtras.h:321 > > > +bool findBitInWord(T word, size_t& index, size_t endIndex, bool value) > > > > I wonder if we should enforce unsigned type here. Otherwise, the shift below > > can cause a loop to never terminate. Maybe it's worth a static_assert that T > > is unsigned? > > OK.
Landed in https://trac.webkit.org/changeset/205794