10
$\begingroup$

Historically, processors often increase in bit-size by powers of 2, such as 8-bit, then 16-bit, 32-bit, 64-bit. Although this has not always been the case, it is a well known trend. One benefit is backwards compatibility. Another is that components can be scaled by combining two 8-bit components into a 16-bit, and so on, such as two 8-bit shift registers. I have also heard that some types of mathematical algorithms benefit from using powers of 2 bit sizes, but I cannot find anything about it, nor think of any. Is anyone here aware of any such algorithms, or such an argument for "powers of 2 bit sizes" in general?

$\endgroup$
7

7 Answers 7

11
$\begingroup$

Multiplying and dividing binary integers by powers of 2 is very cheap, like multiplying and dividing by 10 for decimal numbers.

It's qualitatively different from other factors because the other bits don't change, you just move digits left or right (shifting). In hardware for fixed shift counts, it's literally just wiring.

As I mentioned below, array indexing like arr[i] with an index that counts in elements will involve (in hardware or software) scaling by the element size, if memory is byte addressable. (If it's not in a loop, it can't be optimized to a pointer increment). IDK if you'd call this an "algorithm", though.


https://superuser.com/questions/1735122/why-are-most-of-the-common-processors-bit-counts-powers-of-2/1735399#1735399 and other answers discuss some of the engineering problems you'd have with e.g. 24-bit words on a byte-addressable machine. (24-bit DSPs use word-addressable memory) - some 3-byte words will span wider boundaries, differing in higher bits of the address. But CPU caches and memory systems really want to group binary addresses by ignoring some low bits, not by doing a full division.

In algorithm terms, this is optimization of i / sizeof(int) into a right shift for unsigned i, and i * sizeof(int) into a left shift.

Another algorithm where this is relevant is a bit-array: given an integer bit-index, you need to break that up into a byte index or word index, and a bit number within the byte (to use as a shift count).

#include <limits>
int get_bit(unsigned int *bit_array, size_t n)
{
    size_t element_idx = n / std::numeric_limits<unsigned int>::digits;
    int bit_idx = n % std::numeric_limits<unsigned int>::digits;
    unsigned chunk = bit_array[element_idx];
    return  (chunk >> bit_idx) & 1;
}

When numeric_limits<unsigned int>::digits is a power of 2, like 32 on typical C++ implementations, this unsigned division and remainder become simple right-shift and bitwise AND, like n >> 5 and n & 31.

This wouldn't be the case for 24-bit unsigned int, for example, unless you choose to only use 16 of the 24 bits per unsigned int. Division by a constant 24 or 3 is not very expensive if you have a fast multiplier, but it's non-trivial.

In hardware it's even more significant: splitting a value into multiple fields is literally just wiring. But for n%24, the remainder depends on all 24 bits, not just the low 5 bits, as well as requiring some significant computation.


std::vector's .size() member function, and indexing

Another more widely used data structure that benefits from it being very cheap to convert between element index and addresses is C++'s std::vector<T>, a dynamic array that knows its size and can reallocate when push_back exceeds the current capacity. Typical implementations have 3 pointer members, perhaps named T *m_begin, m_end, and m_capacity.

The API includes .begin() and .data() which are trivial, just return the the start pointer. Similarly .end() can just return the end pointer. (C++ library functions that loop over a range take a start and end pointer, rather than a pointer + length). .push_back can increment m_end += sizeof(T) and check m_end < m_capacity is still true. (The size in bytes to pass to allocator functions can be obtained by casting to char* before subtracting.) None of that benefits from sizeof(T) being a power of 2, which is good for use-cases with T = an odd sized struct.

But std::vector also has a .size() API, typically implemented as return end - begin;. In C++, subtracting pointers returns the distance in elements, not bytes, so in asm it typically looks like sub r0, r1 / sra r0, 2 or something to arithmetic right shift the subtraction result to scale by sizeof(T). If sizeof(T) isn't a power of 2, a right shift won't work for this division. (It is at least a compile-time constant so a multiply and shift can do the trick.)

It's not rare for code to do for (size_t i = 0 ; i < vec.size() ; i++) do stuff with vec[i], or to use .size() for other things. Compilers might transform this loop into a pointer increment, avoiding the division by sizeof(vec[0]), but some uses of .size() won't optimize away.

A non-power-of-2 sizeof(T) for common primitive types like int and int * would make some uses of vectors of those types less efficient. (But implementations would probably keep the 3-pointer design, rather than needing to multiply by sizeof(T) more often with one pointer and size_t length, capacity.

It would also mean alignof(int) had to be 1, unless an implementation padded 3-byte int to a larger size. Unless you redefine alignment to mean multiple-of-3 instead of multiple-of-2.

Also, array indexing by an integer is normally just a left-shift to multiply by sizeof(T) to get a byte offset.

Perhaps such a machine would include scaled-index addressing modes so asm that could scale by 3 and 6, with a shift+add like i + (i<<1) instead of just a shift. For example current x86-64 can do mov eax, [rdi + rcx*4]. (The asm syntax is a multiply, but the only valid multipliers are 1, 2, 4, and 8; the machine code uses a 2-bit shift count.) So a 24-bit machine might allow [rx + ry * 3] or *6 or *12. Otherwise software would need to do more operations to generate addresses.

Many RISCs like MIPS and RISC-V only have 1-register addressing modes so scaling needs software, but maybe they'd provide a single instruction scale-by-3 for address-generation. (Maybe also including a shift count to scale by 6 or 12 or whatever.) 3 only has two set bits, so a fixed shift (trivial in hardware) and an adder will do the trick.

Dividing by 3 is expensive, though.

If the caches on a byte-addressable machine with odd-sized words was still sized to a power-of-2 number of bytes, it could work a lot like a modern x86 which allows efficient unaligned loads/stores, with fairly efficient handling of cases where a load spans the boundary between two cache lines or even pages. Addresses break into offset-within-cache-line vs. index vs. tag by treating the binary address as separate fields.

If cache line sizes were a multiple of 3, like 48 bytes, none of the int in an array will span a cache-line boundary. (As long as the start of the array is "aligned" to a multiple-of-3 address!) But if addresses are still binary numbers, cache indexing is no longer simple. index = (address / 48) % num_sets, and tag = (address / 48) / num_sets. (Assuming for simplicity physical index and tagging.) Paging has a similar problem, power of 2 page size vs. multiple of 3.

(This is the same problem as for a bit-array where the unsigned int chunks aren't a power-of-2 size.)

$\endgroup$
4
$\begingroup$

On top of what everyone else has said, bit shift circuits are easier to design if the "shift amount" is a whole number of bits in size.

$\endgroup$
6
  • 4
    $\begingroup$ Not necessarily. You can just cut off the circuitry for the extra bits. $\endgroup$
    – user253751
    Dec 18, 2023 at 5:24
  • $\begingroup$ Yes, you can always shift-in zeroes (or the high bit if it's an arithmetic shift), but it's an inefficient use of circuitry. $\endgroup$
    – Pseudonym
    Dec 18, 2023 at 22:54
  • 2
    $\begingroup$ What do you mean by “shift in zeroes”? If you have 48 bit numbers you need a circuit for 48 bits, not 64. $\endgroup$
    – gnasher729
    Dec 19, 2023 at 15:25
  • 1
    $\begingroup$ I worded that badly, sorry. My point is that if you have 48 bit words, you need 6 bits to represent the "shift amount", and you still ned 6 stages in a barrel shifter, but you're not really "using" all of those 6 bits. There is precedent, of course, because FPUs often shift by amounts that are not $2^{2^k}$. $\endgroup$
    – Pseudonym
    Dec 19, 2023 at 22:55
  • $\begingroup$ Well, with 48 bit words we wouldn’t have the very unsatisfactory situation that a shift by the number of bits in a word is undefined behaviour. $\endgroup$
    – gnasher729
    Dec 22, 2023 at 20:56
4
$\begingroup$

The fast Fourier transform and its relatives, such as the discrete Fourier transform used in JPEG compression, work best with data sizes that are powers of two. So, if you were to implement the FFT on, say, a DEC PDP-10, with its 9-bit bytes and 36-bit words, you'd have to "waste" 11% of the bits available (and you might also run into some difficulties with masking the unused bits, etc.--it's been a very long time since I programmed a PDP-10, so I don't remember the specifics).

$\endgroup$
2
  • 1
    $\begingroup$ Unless you do a FFT on an array of bits (bit wise) , this is a non-argument. Most FFTs are run on integers of the corresponding platforms. There are some applicaitons for bit-wise FFT but i dont think that JPEG compression is one of these. $\endgroup$
    – Sascha
    Dec 22, 2023 at 14:36
  • $\begingroup$ And if everyone used nine bit bytes, JPEG would operate on nine bit bytes and an architecture with 8 bit bytes would look completely unreasonable. $\endgroup$
    – gnasher729
    Dec 22, 2023 at 20:54
3
$\begingroup$

It’s beneficial if you can combine smaller units into a larger unit. Imagine you had 12 bit and 20 bit numbers. 20 bits could hold one 12 bit number and waste 8 bit. 24 bits could hold one twenty bit number and waste four bit. You’d need to go up to 60 bits to hold 5x12 or 3x20 bits.

You wouldn’t have that problem with 8, 24, 48 and 96 bit numbers. But then calculating the address of item #n is slightly more complicated.

Having 12 bit bytes and 12, 24, 48 and 96 bits would actually be quite good. UTF-12 would store all characters in two units. 48 bit floating point would very often be enough, and 96 bit would have lots of extra precision.

The only slight disadvantage is storing bit arrays because you often divide a bit number by the byte size or word size in bits, and typical hardware can divide by a constant power of two faster. On the other hand I would expect this hardware to have a fast “divide by 96 / modulo 96” instruction.

$\endgroup$
3
  • $\begingroup$ Right but that benefit of combining smaller units into larger, seems like it has to do with the backwards (and forwards...) compatibility I mentioned, rather than working within a certain processor. What I'm fishing for is the third benefit case, which I heard mentioned was certain mathematical algorithms, but I cannot find anything about which ones. $\endgroup$
    – BipedalJoe
    Dec 17, 2023 at 19:19
  • $\begingroup$ I very much doubt that any mathematical algorithms have affected hardware designs. $\endgroup$
    – gnasher729
    Dec 22, 2023 at 20:58
  • $\begingroup$ Well that could be an answer then to the question of math benefits to CPU that increases by powers of 2. I think I was asking more broadly about what math benefits from that, and Steve-OH pointed out that Fast Fourier Transform actually does, but that it hasn't been an important factor in CPUs could very well be true. It was a factor I did not know enough about myself, whereas I can understand all the other arguments like backwards/forwards compatibility. $\endgroup$
    – BipedalJoe
    Dec 22, 2023 at 22:28
3
$\begingroup$

On the level of assembly code, having $2^k$ bits in a word is convenient for bit operations. The result is that if you have an assembly command like "set bit $i$ of register $r$", then $k$ bits of the opcode will be devoted to specifying $i$. If the number of bits is not a power of $2$, then either some opcodes are wasted, or else the processor has a slightly harder time interpreting the opcodes.

If I wanted to make a case $2^n$-bit words based on mathematical algorithms, though, I'd bring up Hadamard codes. For all $k$, this is an error-correcting code that takes a $k$-bit input and encodes it as a $2^k$-bit codeword, with the property that any two codewords differ in at least $2^{k-1}$ bits. So, for example, we could take $6$-bit inputs and encode them as $64$-bit outputs; we get a rather inefficient but very error-resilient code in this way. The dual of a Hadamard code is a Hamming code, which also benefits from numbering the bits in a codeword in binary.

Finally, here's a very niche benefit: chess engines use bitboards to represent game state, which encodes a binary property like "which squares of the chessboard contain white pawns?" in a $64$-bit vector.

$\endgroup$
3
$\begingroup$

I think the story may be more complicated than some other answers suggest, even if they contain a lot of good arguments.

I add some observations:

  • systems with 12,18,24,36 and other bit sizes exist

  • Nibbles are the minimum needed for BCD arithmetic. it may sound like a distant memory from the past, but doing BCD arithmetic really simplifies building calculators and other hardware constrained machines, so using a multiple of a nibble was an efficient choice

  • Many processor series first (or as a cheaper version -> 8088) had an ALU being able to operate on the double size internally, and then got an external bus later (68000 was 16 bit data bus and had some 32 bit registers/arithmetic, 6809 hast 16 bit arithmetic with an 8 bit data bus, Z80 had some 16 bit registers/operations, 8088 was 8 bit data bus but had 16 bit registers)

The latter point is IMHO mainly responsible related to economics of designing computers:

  • Having internal register sizes multiples the data bus means that you can use these registers as fast internal memory for applications requiring the lower bit number and not waste transfers.
  • having these at a low multiple means that your processing is not out-pacing your RAM access (it does not make sense to waste space for an ALU processing the data faster than you can fetch them)
  • having versions of your processor data bus at the register and half the size is good - it doesn't make sense to have a 1.5 times wide version

All in all this means that if you run 8 bit SW on a 16 bit data bus, you may have some wasted space, but not as mus as if you had 24 bits.

So i think doubling the bus/register width is the cheapest upgrade path for compatible designs.

$\endgroup$
0
$\begingroup$

General Situation

Since computers use a binary system to represent data, a heavy use of powers of 2 results in easier optimizations in general.

The key reason for this is that when you multiply by 2 (0b10[1] in binary), all you need to do is shift the bits in the number. For example, 3 is 0b011 and 6 is 0b110. Multiplication in binary is a vastly more complex operation, where-as shifting is a simpler one.

Word-Size in Hardware

As you mentioned, there are many answers describing the hardware reasons. I'd like to call out specifically that the hardware reasons are mostly about alignment to known data-type sizes.

Word-size specifically benefits from having all data sizes as factors. This means all of the following need to divide into word size:

  • 1-bit (bool)
  • 8-bit (char/byte)
  • 32-bit (float/int), and
  • 64-bit (double/long)

So, in general all of today's chips will use multiples of 64. There have been several pieces of hardware that deviate from powers of 2. As you mentioned, this comes with costs for hardware design every time you choose a new bit-size. So, going from one bit size to another will require all new circuits for many operations unless you always align to data-type sizes.

Word-Size in Software

All algorithms are using optimization that depend on hardware configurations. Hardware is the "reality of compute". So, we'll look at some reasons that span the hardware/software boundary. In these situations, there's a hardware design issue that makes either the software more complicated to optimize OR requires more customized hardware to equal the performance of a similar system that uses a power-of-2 bit size.

Data Spanning Words is costly

Now, imagine you're storing bytes (8-bits) in a CPU that uses a non-power-of-2 word-size. In this case, you would have to pack your bytes such that they span across multiple words. In a 36 bit system, you'd span 9 bytes over 2 words, with the 5th byte split over the last for bits of word 1 and the first 4 bits of word 2.

For the visually inclined:

   WORD 1    |   WORD 2
vvvvvvvvvvvvv|vvvvvvvvvvvvv
11 22 33 44 5|5 66 77 88 99
            ^ ^
           BYTE 5

This means that to get the 5th byte, you need to retrieve from both words and combine the data to create a byte. This results in less optimal access to any data that spans multiple words in memory. This results in loading more data into all caches and then into CPU registers, reducing the performance of all programs that use arrays like this one.

SIMD is more costly

CPUs also provide instructions that operate on multiple data in a single register. Consider a CPU today that has a 128 bit architecture. It supports instructions that allow you to operate on multiple data being stuffed into these bits. In this case, it can operate on 4 32-bit ints or floats simultaneously.

Now, if we had non-power-of-2 bits, this would be an inefficient use of the word.

Instead of using the word inefficiently, if we decided to pack as described in the previous point, the hardware would require further complexity to perform SIMD operations with different configurations. For example, with the setup described above (36-bit system), we'd need to have a circuit that supports both word configurations. With other bit-counts, it could be even more complex. 2 word configurations is the best we can do when we deviate from powers of 2.

Counting Data and Pointers

When data neatly packs into words, counting data and pointer-math become easy. It also means that you can (without knowing the index of data), have the same unpack logic for packed data. The reason why this is important is having a for loop like this would make branch prediction harder. Based on the 36-bit example above:

for (i in indices) {
  if (i % 2 == 0) {
    // unpack logic
  } else {
    // different unpack logic
  }
}

Conclusion

It's all about the hardware. Optimizing software is about learning your hardware and writing your software accordingly.

[1] 0bxx is a notation used in some languages to represent binary numbers. So, 0b01 == 1, 0b10 == 2, and so on. I am often trimming the leading 0s so that I don't have to write a full byte/word/etc of bits.

[2] CPUs don't execute exactly 1 instruction per clock cycle. Modern CPUs execute instructions in phases. The phases enable higher instruction throughput. CPU features like branch prediction can speculatively execute later instructions assuming your branch will take a particular path.

$\endgroup$
1
  • $\begingroup$ With a non-power-of-2 word-size, why would bytes be 8 bits? $\endgroup$
    – greybeard
    Dec 23, 2023 at 10:41

Your Answer

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

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