haskell
Unboxed array of Bool
I'd love to have bit vectors (i.e., unboxed arrays and mutable arrays of Bool) in here. The implementations of bit vectors around Hackage seem almost always to be pure and fairly lousy (e.g., backed by Integer). It would be great to get a really careful implementation that addresses, e.g., aliasing issues.
Unboxed vector of bool, or storable vectors of bool, already provide that ... What are you looking for that isn't that? If you want a bit set data structure explicitly , I think that's something that should be easy to write on top of primitive, but I dont think it should be in primitive itself
On Tuesday, August 30, 2016, David Feuer [email protected] wrote:
I'd love to have bit vectors (i.e., unboxed arrays and mutable arrays of Bool) in here. The implementations of bit vectors around Hackage seem almost always to be pure and fairly lousy (e.g., backed by Integer). It would be great to get a really careful implementation that addresses, e.g., aliasing issues.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/issues/42, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAQwmQnApYTNr9F8iuy2KY-HE5DCtBoks5qk-3sgaJpZM4JwSSt .
The unboxed vectors of Bool store Bool as Word8. Often, I want to get 64 Bools per word instead of just eight of them. I don't really care where that's done, as long as it's done well and I can find it.
On Aug 30, 2016 10:14 AM, "Carter Tazio Schonwald" [email protected] wrote:
Unboxed vector of bool, or storable vectors of bool, already provide that ... What are you looking for that isn't that? If you want a bit set data structure explicitly , I think that's something that should be easy to write on top of primitive, but I dont think it should be in primitive itself
On Tuesday, August 30, 2016, David Feuer [email protected] wrote:
I'd love to have bit vectors (i.e., unboxed arrays and mutable arrays of Bool) in here. The implementations of bit vectors around Hackage seem almost always to be pure and fairly lousy (e.g., backed by Integer). It would be great to get a really careful implementation that addresses, e.g., aliasing issues.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/issues/42, or mute the thread <https://github.com/notifications/unsubscribe- auth/AAAQwmQnApYTNr9F8iuy2KY-HE5DCtBoks5qk-3sgaJpZM4JwSSt> .
— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/issues/42#issuecomment-243452939, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_XWUzVupjrK8b_ZTezB9OluLzg9Zks5qlDrcgaJpZM4JwSSt .
There's one in foundation https://github.com/haskell-foundation/foundation/blob/master/Foundation/Array/Bitmap.hs :-)
Bit level bools are not atomic or thread safe. On most CPU architectures the smallest granularity atomic memory operations are on the word or byte size.
On Aug 30, 2016 7:52 PM, "David Feuer" [email protected] wrote:
The unboxed vectors of Bool store Bool as Word8. Often, I want to get 64 Bools per word instead of just eight of them. I don't really care where that's done, as long as it's done well and I can find it.
On Aug 30, 2016 10:14 AM, "Carter Tazio Schonwald" < [email protected]> wrote:
Unboxed vector of bool, or storable vectors of bool, already provide that ... What are you looking for that isn't that? If you want a bit set data structure explicitly , I think that's something that should be easy to write on top of primitive, but I dont think it should be in primitive itself
On Tuesday, August 30, 2016, David Feuer [email protected] wrote:
I'd love to have bit vectors (i.e., unboxed arrays and mutable arrays of Bool) in here. The implementations of bit vectors around Hackage seem almost always to be pure and fairly lousy (e.g., backed by Integer). It would be great to get a really careful implementation that addresses, e.g., aliasing issues.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/issues/42, or mute the thread <https://github.com/notifications/unsubscribe- auth/AAAQwmQnApYTNr9F8iuy2KY-HE5DCtBoks5qk-3sgaJpZM4JwSSt> .
— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/issues/42#issuecomment-243452939, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABzi_XWUzVupjrK8b_ ZTezB9OluLzg9Zks5qlDrcgaJpZM4JwSSt> .
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/issues/42#issuecomment-243508375, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAQwnAu4hqi29FHs5GEa5LiUgNNud6fks5qlGJ9gaJpZM4JwSSt .
huh ? not sure how that relate to anything, but even then that's non-sense: you can have atomic & thread-safe bitmap if you want.
I think what Carter means is that you need to lock or CAS the whole word, not just a bit. There are times when that matters, but there are also single-threaded situations where it's not. You may want to arrange the bits specially to reduce data dependencies (spreading adjacent bits across different words, or whatever approach is best these days), but for single-threaded or low-contention use, compactness can be a huge performance advantage.
On Wed, Aug 31, 2016 at 10:49 AM, Vincent Hanquez [email protected] wrote:
huh ? not sure how that relate to anything, but even then that's non-sense: you can have atomic & thread-safe bitmap if you want.
— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/issues/42#issuecomment-243788889, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_aPTFuyAIwanAtc0DhMJulyxQrvAks5qlZSPgaJpZM4JwSSt .
yes, CAS would works pretty well here I think.
Related to the rest; never seen bitmap like bit-operations not done on word size stuff though (for obvious cpu reasons).
I think it's fine to have bit packed arrays of booleans in primitive. However, if you're looking for a more fleshed out bit-vector-specific API, I don't think that's really what this package aims to be. The packed vectors could be used as a building block for such a thing though, of course.
I'm also not really interested in exposing the CAS stuff GHC has here. It's non-trivial to get right, and there's already a package (perhaps more than one) building on it by people who are more expert in the subject (probably some who designed it).
The main question in my mind is whether it's worth keeping the byte-per-boolean arrays around, and if so, which gets used for Bool and which gets used for some other equivalent (new)type?
I think that it's worth keeping both around. Since the sizeOf# method measures size in bytes, I don't think that the machinery in primitive can be used for this. It seems like the implementation would need to be entirely separate from the existing bytearrays.
The implementations of bit vectors around Hackage seem almost always to be pure and fairly lousy (e.g., backed by Integer).
I used http://hackage.haskell.org/package/bitvec once. @treeowl do you know any particular flaws in it?
Since January I took over the maintainership of bitvec and put it into shape. Hopefully, the latest release is mature enough and addresses most of concerns raised above. Any feedback will be much appreciated.