[vector] #26: Vector should bit pack unboxed boolean vectors

[vector]

#26: Vector should bit pack unboxed boolean vectors
------------------------+---------------------------------------------------
Reporter:  ezyang       |        Owner:         
    Type:  enhancement  |       Status:  closed 
Priority:  major        |    Milestone:         
 Version:               |   Resolution:  wontfix
Keywords:               |  
------------------------+---------------------------------------------------
Changes (by rl):

  * status:  new => closed
  * resolution:  => wontfix

Comment:

 Actually, the decision not to use a bit-packed representation is a very
 deliberate one. There are several reasons for this.

 Firstly, this is usually a trade-off between size (bit-packed arrays use
 less memory) and speed (accessing individual elements is slower). Usually,
 and 8x increase in the size of Bool arrays is not really a concern but the
 performance hit is. There are, of course, many cases where the opposite is
 true and a bit-packed representation is faster sometimes because of
 cache/memory effects but in my experience, bit packing is usually not
 worth it.

 Secondly, bit-packed arrays don't fit very well into the current framework
 which always reads and writes individual elements. An operation like
 `zipWith (&&)` would be horribly inefficient with a bit-packed
 representation. It would be possible to optimise this but it's a lot of
 work.

 Lastly, the (currently undocumented) intention is to guarantee that
 writing array elements of primitive types is an atomic operation. This is
 really important for multithreaded programs and I would really like Bool
 to be treated as a primitive type. This rules out a bit-packed
 representation.

 As a final data point, `vector<bool>` uses a packed representation in C++
 and that decision seems to be widely regarded as a mistake.

 I'm closing the ticket although, of course, it would be great to also
 provide bit-packed arrays. But in my opinion, they are really a different
 data structure and, incidentally, much harder to implement efficiently.

-- 
Ticket URL: <http://trac.haskell.org/vector/ticket/26#comment:1>
vector <http://trac.haskell.org/vector>
Package vector