Bit arrays


(Daryle Walker) #1

Since objects aren't addressable by default, there wouldn't be the problems with a bit-packed Boolean collection that C++'s "vector<bool>" has. Does "[Bool]" currently have the option of packed optimization, or would it have to be added via a proposal? Or does it have to be a separate type instead?

This also brings to mind bit fields and fixed-sized bit sets, but those might have to wait for value-based generic parameters, and that's at least until Swift 4....

···

Sent from my iPhone


(Chris Lattner) #2

It has to be a separate “bitvector” type.

FWIW, C++’s vector<bool> optimization is widely considered to be a bad idea, and many people have talked about trying to remove it from the C++ standard entirely.

-Chris

···

On Jul 3, 2016, at 2:42 PM, Daryle Walker via swift-evolution <swift-evolution@swift.org> wrote:

Since objects aren't addressable by default, there wouldn't be the problems with a bit-packed Boolean collection that C++'s "vector<bool>" has. Does "[Bool]" currently have the option of packed optimization, or would it have to be added via a proposal? Or does it have to be a separate type instead?


(Xiaodi Wu) #3

As an additive thing, probably not much chance of seeing it in Swift 3,
then?

I tried wrapping CFBitVector just the other day but found performance to be
rather lacking for a number of operations because CF doesn't expose the
underlying storage. It would be nice to have something in the stdlib and
I'd be happy to contribute to proposal and/or implementation.

···

On Sun, Jul 3, 2016 at 17:45 Chris Lattner via swift-evolution < swift-evolution@swift.org> wrote:

> On Jul 3, 2016, at 2:42 PM, Daryle Walker via swift-evolution < > swift-evolution@swift.org> wrote:
>
> Since objects aren't addressable by default, there wouldn't be the
problems with a bit-packed Boolean collection that C++'s "vector<bool>"
has. Does "[Bool]" currently have the option of packed optimization, or
would it have to be added via a proposal? Or does it have to be a
separate type instead?

It has to be a separate “bitvector” type.

FWIW, C++’s vector<bool> optimization is widely considered to be a bad
idea, and many people have talked about trying to remove it from the C++
standard entirely.

-Chris
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Taras Zakharko) #4

AFAIK, the problem lies within the vector<bool> implementation. Other bit-packed implementations (e.g. boost:dynamic_bitset) are much more efficient. In certain cases, there are performance advantages to the bit packed representation as it is more cache-friendly.

That said, I don’t think that such specialised data structures should be part of the standard library. I’d leave this to a third-party solution.

— Taras

···

On 04 Jul 2016, at 00:44, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

On Jul 3, 2016, at 2:42 PM, Daryle Walker via swift-evolution <swift-evolution@swift.org> wrote:

Since objects aren't addressable by default, there wouldn't be the problems with a bit-packed Boolean collection that C++'s "vector<bool>" has. Does "[Bool]" currently have the option of packed optimization, or would it have to be added via a proposal? Or does it have to be a separate type instead?

It has to be a separate “bitvector” type.

FWIW, C++’s vector<bool> optimization is widely considered to be a bad idea, and many people have talked about trying to remove it from the C++ standard entirely.


(Chris Lattner) #5

Right.

-Chris

···

On Jul 3, 2016, at 3:49 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

As an additive thing, probably not much chance of seeing it in Swift 3, then?