17
$\begingroup$

I've been wondering about this for a while now, so I'm going to ask. This is a question about the design of Mathematica, which perhaps cannot be directly answered by anyone but the designers, however similar queries have been fruitful in the past.

Simply: why aren't arrays of True and False values packed? Compile handles True | False so it seems Mathematica has some understanding of optimizing for this type, yet:

boolean = Developer`ToPackedArray @ RandomChoice[{True, False}, 1*^6];

Developer`PackedArrayQ @ boolean

False

This is rather frustrating because packing would be particularly effective on binary data:

bigint = FromDigits[Boole@boolean, 2];

ByteCount[boolean]

ByteCount[bigint]

8000032

125040

Yes, one can sometimes fall back to this storage format and use Bit* operations, but that is inconvenient and it doesn't always help; data must be converted for functions that expect True or False and the opportunity for internal optimizations may be lost.

Is there some reason I fail to comprehend that makes implementing packing of Boolean arrays a bad idea?

Improve this question
$\endgroup$
2
  • $\begingroup$ I thought that packing optimized speed and not memory. Packing boolean arrays would reduce memory consumption but would probably increase access time. $\endgroup$ Commented Aug 24, 2012 at 21:54
  • 5
    $\begingroup$ @SjoerdC.deVries Packing hugely optimizes memory as well. Whenever it can be used, it wins both performance - wise and memory - wise, there is no tradeoff. $\endgroup$ Commented Aug 24, 2012 at 22:04

1 Answer 1

Reset to default
16
$\begingroup$

As I suggested in my answer to a related packed-array question, the main problem is IMO not in the data structure (packed array) per se, but in all the functions which must work with this data structure together and in concert, to make it really well-integrated into the language. Notice that there isn't a separate boolean atomic type in Mathematica, True and False are just special symbols. I suspect that one would need to introduce an atomic Boolean head, and perform a re-design and enhancements to a whole lot of core functions, to make boolean packed arrays really work.

Besides being a fundamental design choice (change of an existing design), this is a lot of work and a lot of places where bugs may be introduced. This has to be weighted against the benefits of having separate boolean type. While I can see some such benefits, I don't think the outweigh the associated difficulties, some of which I just listed. Anyone who needs efficient boolean arrays can use integer arrays of 0-s and
1-s consistently in their functions. My two cents, as usual.

Improve this answer
$\endgroup$
12
  • 4
    $\begingroup$ I agree with Leonid, especially the work part and I would not want to implement that - that would eat month of development time. Time that could spend on other projects. I think the work/benefit ratio is not high enough. $\endgroup$ Commented Aug 24, 2012 at 15:50
  • 1
    $\begingroup$ A reasonable argument, but I strongly disagree with your penultimate sentence: Integer arrays are not efficient here, taking 32 bits per value even when packed. A binary data type that can be accessed normally (like packed integer arrays are) would be ideal in many applications. $\endgroup$ Commented Aug 24, 2012 at 17:20
  • 2
    $\begingroup$ @Mr.Wizard I meant run-time efficiency. Memory efficiency is less often a problem, particularly in the context of boolean arrays taken separately - my guess is that if you have boolean arrays so large that packed arrays of integers are taking too much memory, then you will have other and more serious memory issues with some other parts of your problem / code. But, even assuming these are the main memory hogs, you can always design your own custom functions based on bit manipulations, and consistently use those. Some extra work indeed, but does not seem formidable. $\endgroup$ Commented Aug 24, 2012 at 17:25
  • 3
    $\begingroup$ I agree wholeheartedly with everything Leonid has said (to the point where I almost regret having downvoted his response. All three times.) I will add a couple of points. (1) It is not obvious what should be the fundamental "unit", or container, for such an array. The numeric types pack into basic C-language types, and arbitrary dimension (non-ragged) arrays thereof. For bits I suppose we could emulate this using arrays of unsigned ints. For higher dimensions this could become problematic since non-raggedness is crucial. I'm nearly out of space so I'll make point #2 in a separate comment. $\endgroup$ Commented Aug 24, 2012 at 19:29
  • 3
    $\begingroup$ My second point: We unrolled packed arrays I believe in version 4, around 1998-9. We were still fixing bugs from that endeavor several years later. Some still show up in various dark corners (usually from code not prepared to see both variants, packed and unpacked, of a List argument). There are a number of implementation-related reasons for such trouble. Maybe it could have been done differently. I suspect even so that the problems we've encountered were, at a minimum, not easily avoided, given that this was a retrofitting of functionality. Upshot: be careful what you ask for. $\endgroup$ Commented Aug 24, 2012 at 19:34

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.