0

Intro

The following assumes C# as a reference language, or any other statically typed language. This is not a question specific to Unity's API, but it is used as an example.

In Unity's API, most people come across the Raycast function. This has an argument, of type int called layerMask. This is an integer, that works as a bitwise mask (if there's 1 at the n-th place, the n-th place is included in the calculation).

I always thought that this was a very weird design choice for their API.

First of all, I should clarify, that there can only be 32 layers in Unity, thus, those layers are finite, but you can have any number of layers (below 32).

Personally, I would ask as an argument, an array of integers, whose elements would be the layers that you wish to raycast against (identical to the actual implementation, just without it being bitwise). Another way, would be to have variardic arguments, if the language supports it. (these points also apply to dynamically typed languages). (I have read a few arguments against the use of variardic arguments, so I wouldn't choose this one)


The actual question

Why would one choose a bitwise mask as a representation of a selection of a (finite/bound) amount of items, instead of an array of the selected items?

Given that you are sacrificing usability and readability*, what are the benefits?


Assumptions

Since Raycast is a very useful function and used widely, I'm guessing that they chose this for performance reasons (bitwise operations can be much faster than iterating over an array). In this particular case, given that the maximum length of the array would be 32, I doubt that the difference would be huge, but I'm guessing that every bit of performance counts in this case.

The other benefit is certainly memory footprint (one integer vs a whole array of them), but I doubt that this is generally important (in this and other cases).


I'll also notice, that both arrays and integers, do not enforce the size boundary of the items. The array, can be as large as you want, and the integer has a certain, implementation/machine specific size, so if you wanted to toggle 17 items, no size of integer would be enforcing that there is no element 18.


*Example: To signify the third and fourth items, instead of the argument 12 (1100 in binary), you could have [3,4]

  • 1
    You've said the answer already: performance and memory. There is also the possibility that an API is wrapping a lower-level API, which expects a bitmask, but that's just pushing the argument down a level. And the performance difference between a single 32 bit number and 32 32 bit numbers can be massive, if you consider things like cache line lengths and locality of access. – biziclop Mar 29 '16 at 13:27
  • Ok, I guess. So, in this case bitmasks should be avoided in general, unless you have very specific optimization needs. – K. Gkinis Mar 29 '16 at 13:30
  • That is my opinion, yes. And things like raycasting do have quite heavy optimization needs. – biziclop Mar 29 '16 at 13:33
3

Bitmasks are certainly a C-ism that takes a bit getting used to. However, bit-level operations can be performed within a few machine code instructions without any branching or pointer indirection, unlike operations that involve collections. In performance-sensitive code such as graphics engines, this can make a huge difference.

Avoiding branching is good because modern CPUs use long pipelines for instruction decoding, and therefore try to guess which path through your code will be taken. If the CPU guesses wrong, the pipeline is flushed and you have to wait a couple of instructions before the CPU is up to maximum throughput again.

If we were dealing with an array, checking whether that array contains a specific layer is expensive in terms of branching. As pseudocode:

func contains(Array xs, uint x) -> bool {
  for (Index i = 0; i < xs.length; ++i) {
    if (xs[i] == x) return true;
  }
  return false;
}

An invocation contains([4, 3], 5) would check the array size, first element, array size, second element, array size, then finally return in negative.

To be fair, this loop can be unrolled given the fixed upper size:

func contains(Array xs, uint x) -> bool {
  switch (xs.length) {
  case 32: if (xs[31] == x) return true;
  ...
  case  2: if (xs[ 1] == x) return true;
  case  1: if (xs[ 0] == x) return true;
  default: return false;
}

But you will still need a branch for each element. With a bit mask, contains(mask, x) can be implemented without any branches as (mask & (1 << x)) != 0. If your x is known, this can be constant-folded so that the test can be done in one or two machine code instructions. It doesn't get any better than that.

The other part to the efficiency considerations is memory accesses. An integer fits into a register. An array doesn't. Unless the array contents are in the cache (and even then), memory accesses are a magnitude slower than performing CPU instructions. A single memory access is enough to read the whole bitmask; with arrays we'd just have a pointer to the contents by now. Depending on how cleverly this can be done, we'd need one or more accesses after that to actually get at the contents.

Not only is using bitmasks more efficient, it can also be seen as better API design. In particular, using arrays has the following problems:

  • an element can occur more than once (we aren't dealing with a set).
  • the elements aren't ordered, making it more expensive to test for membership since we have to check all elements.
  • creating and initializing arrays uses cumbersome syntax in many languages
  • input validation is more expensive. Just consider all the bounds checking for each argument.

The usability of bitmasks is not terrible. If you know a layer only by index, you can easily create the bit pattern by a left shift. Layer n uses the bit pattern 1 << n. You might also name the layers in your code. A mask can then easily be constructed like mask = PLAYER_LAYER | WATER_LAYER | (1 << 12). This can be substantially more readable than many boolean options (layer8: true, waterLayer: true, layer12: true), can be easily stored in a variable and adapted (defaultMask | additionalLayer, defaultMask & ~excludedLayer), and the order of masks and duplication of masks doesn't matter. The only problem of bitmasks is that they are limited to the number of bits in the backing integer type.

  • Excellent points, I hadn't thought of ordering and input validation at all! I can't really comment on the ease of usability for bitmasks; as I've used them extensively in the past, I'm familiar with them, but I'm guessing that they're much harder for "higher level" taught programmers. – K. Gkinis Mar 29 '16 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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