34

For a vector of logical values, why does R allocate 4 bytes, when a bit vector would consume 1 bit per entry? (See this question for examples.)

Now, I realize that R also facilitates storage of NA values, but couldn't that be done with an additional bit vector? In other words, why isn't it enough to just use a cheap two bit data structure?

For what it's worth, Matlab uses 1 byte for logicals, though it doesn't facilitate NA values. I'm not sure why MathWorks isn't satisfied with one bit functionality, much less a two bit data structure, but they have fancy pants marketers... [I'm gonna milk "two bit" for all it's worth in this question. ;-)]


Update 1. I think that the architecture reasons offered make some sense, but that feels a little ex post facto. I haven't checked 32 bit or 16 bit R to see how large their logicals are - that could lend some support to the idea. It seems, from the R Internals manual that logical vectors (LGLSXP) and integers (INTSXP) are 32 bits on every platform. I can understand a universal size for integers, independent of word size. Similarly, storage of logicals also seems to be independent of word size. But it's so BIG. :)

In addition, if the word size argument is so powerful, it seems strange to me to see Matlab (I think it's a 32 bit Matlab) consume only 1 byte - I wonder if MathWorks chose to be more memory efficient with a tradeoff for programming complexity and some other overhead for finding sub-word objects.

Also, there are certainly other options in are: as Brian Diggs notes, the bit package facilitates bit vectors, which was very useful for the problem in the question above (an 8X-10X speedup for the task was obtained by converting from 4 byte logical values to bit vectors). Although speed of accessing memory is important, moving 30-31 extra uninformative bits (from an information theory perspective) is wasteful. For instance, one could use something like the memory tricks used for integers described here - grab a bunch of extra memory (V cells) and then process things at the bit level (a la bit()). Why not do that and save 30 bits (1 for the value, 1 for NA) for a long vector?

To the extent that my RAM and computational speed are affected by booleans, I intend to switch over to using bit, but that's because a 97% savings in space matters in some cases. :)

I think that the answer to this question will come from someone with a deeper understanding of R's design or internals. The best example is that Matlab uses a different size for their logical, and memory word sizes wouldn't be the answer in that case. Python may be similar to R, for what it's worth.

A related way to phrase this might be: why would LGLSXP be 4 bytes on all platforms? (Is CHARSXP typically smaller, and wouldn't that work as well? Why not go even smaller, and just over-allocate?) (Updated The idea of using CHARSXP is likely bogus, because operations on CHARSXP aren't as fully useful as those for integers, such as sum. Using the same data structure as characters might save space, but would constrain which existing methods could operate on it. A more appropriate consideration is the use of smaller integers, as discussed below.)


Update 2. There have been some very good and enlightening answers here, especially relative to how one should implement retrieval and processing of booleans for the goals of speed and programming efficiency. I think that Tommy's answer is particularly plausible regarding the why it appears this way in R, which seems to arise from 2 premises:

  1. In order to support addition on a logical vector (note that "logical" is defined by programming language / environment, and is not the same as a boolean), one is best served by reusing code for adding integers. In the case of R, integers consume 4 bytes. In the case of Matlab, the smallest integer is 1 byte (i.e. int8). This would explain why something different would be a nuisance to write for logicals. [To those not familiar with R, it supports many numerical operations on logicals, such as sum(myVector), mean(myVector), etc.]

  2. Legacy support makes it exceedingly difficult to do something other than what has been done in R and S-Plus for a long time now. Moreover, I suspect that in the early days of S, S-Plus, and R, if someone was doing a lot of boolean operations, they did them in C, rather than trying to do so much work with logicals in R.

The other answers are fantastic for the purposes of how one might implement better boolean handling - don't naively assume that one can get at any individual bit: it's most efficient to load a word, then mask the bits that are not of interest, as Dervall has described. This is very, very useful advice should one write specialized code for boolean manipulation for R (e.g. my question on cross tabulations): don't iterate over bits, but instead work at the word level.

Thanks to all for a very thorough set of answers and insights.

3
  • 1
    It's much harder to address a single bit than a single byte.
    – SLaks
    Feb 7, 2012 at 14:47
  • @SLaks Can you elaborate? I think I understand what you mean, but that is a lot of wasted space and cycles for very large vectors.
    – Iterator
    Feb 7, 2012 at 14:48
  • 1
    If you addressed bits, you would max out at 512Mb of memory on a 32-bit system.
    – James
    Feb 7, 2012 at 15:08

3 Answers 3

17

Knowing a little something about R and S-Plus, I'd say that R most likely did it to be compatible with S-Plus, and S-Plus most likely did it because it was the easiest thing to do...

Basically, a logical vector is identical to an integer vector, so sum and other algorithms for integers work pretty much unchanged on logical vectors.

In 64-bit S-Plus, the integers are 64-bit and thus also the logical vectors! That's 8 bytes per logical value...

@Iterator is of course correct that a logical vector should be represented in a more compact form. Since there is already a raw vector type which is 1-byte, it would seem like a very simple change to use that one for logicals too. And 2 bits per value would of course be even better - I'd probably keep them as two separate bit vectors (TRUE/FALSE and NA/Valid), and the NA bit vector could be NULL if there are no NAs...

Anyway, that's mostly a dream since there are so many RAPI packages (packages that use the R C/FORTRAN APIs) out there that would break...

3
  • 2
    "8 bytes per logical value...": please warn me to get smelling salts the next time you're about to do that to me. :) Btw, can you clarify for all the meaning of "RAPI"? I assume you mean the C interface to R, correct?
    – Iterator
    Feb 7, 2012 at 17:30
  • Yes the 8 bytes bool is an abomination, and R might still copy it... And yes, with RAPI I meant the R API which is the C/FORTRAN interface to R.
    – Tommy
    Feb 7, 2012 at 19:51
  • This legacy idea is very plausible. Along with the re-use of sum for the purposes of addition of integers, I am inclined to believe this may explain things. In fact, another issue is that this is the smallest numerical type offered in R, whereas Matlab has 1 byte integers.
    – Iterator
    Feb 7, 2012 at 19:58
16

Without knowing R at all, I suspect for much the same reason as C does, because it's way faster to load a size equal to the processors native word size.

Loading a single bit would be slow, especially from a bitfield since you'd have to mask out the bits that do not apply to your particular query. With a whole word you can just load it in a registry and be done with it. Since the size difference usually is not a problem the default implementation is to use a word sized variable. If the user wants something else there is always the option to do the bit-shifting required manually.

Concerning packing, at least on some processors it will cause a fault to read from a non-aligned address. So while you might declare a structure with a single byte in it surrounded by two int the byte might be padded to be 4 bytes in size regardless. Again, I don't know anything about R in particular, but I suspect the behaviour might be the same for performance reasons.

Addressing a single byte in an array is quite more involved, say you have an array bitfield and want to address bit x in it, the code would be something like this:

bit b = (bitfield[x/8] >> (x % 8)) & 1

to obtain either 0 or 1 for the bit you requested. In comparison to the straightforward array addressing of from a boolean array obtaining value number x: bool a = array[x]

4
  • Thanks, this is quite interesting, along with the other feedback. Still, 4 bytes is a massive waste of space. I understand the bit addressing difference, but what could justify 4 bytes versus 1 byte, e.g. as with characters, or a short int? In my other question, the task was performed a LOT faster by switching from 4 byte logicals to bit vectors, because moving around data takes a lot of time. I have a feeling that there's a tradeoff decision made by the R developers that we're not yet aware of.
    – Iterator
    Feb 7, 2012 at 15:33
  • With characters, size is of importance. Since these usually represents a lot more data it is important to keep the size down. It might be the case in very specific applications a bit vector might get improved performance due to locality of reference and such, but those cases are probably few and far between. Usually you want a boolean in local use and in that context a four byte variable is way faster.
    – Dervall
    Feb 7, 2012 at 15:35
  • This is a very useful answer. Although I can only select one, it it seems that Tommy has given the answer most suited to the why things are the way they are in R, from a context/historical perspective. However, your answer is very useful guidance for speed and ease issues that matter when one gets into the implementation of boolean processing, which is more useful for future specialized code, and is much appreciated.
    – Iterator
    Feb 7, 2012 at 20:17
  • 1
    If you actually try to do some real operations on a compact bit vector vs. "an int per value", you'll see that the compact bit vector usually wins performance wise. On current processors, memory access is slow, bit manipulation is fast... And you can often manipulate several bits at once (an AND operation for example).
    – Tommy
    Feb 7, 2012 at 20:50
10

Other answers have gotten at the (likely) architectural reasons that logical vectors are implemented taking the same space as integers. I wanted to point out the bit package which implements a one-bit (no NA) logical.

1
  • That is true. I should have been precise: in my mind, a bit vector is the "naive" (i.e. baseline) data structure for a boolean. I'm curious why anyone would consume 31 extra bits. The more precise answer here would also point out that a logical and a boolean are not the same thing: R's logical() supports NA, for instance. But I could get that with 2 vectors from bit(), so it seems there are still 30 excess bits per entry, and this seems gluttonous.
    – Iterator
    Feb 7, 2012 at 16:56

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.