The old PDP-10 had 36-bit words but you could write pointers to any range of bits inside a word. On that machine you could write a pointer to a single bit.
I was thinking about a fantasy computer that could run under JavaScript and have 48 bit words (fit in a double) and pointers like the PDP-10 but that could hang off one word into the next word. [1] First I was thinking “screw C” but came to the conclusion that supporting C would not be so hard after all with that kind of pointer.
[1] Think of a Chinese home computer from an alternate timeline where a strange mainframe had a baby with a NeoGeo arcade machine.
> Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning
C99 §6.7.2.1.13
> An implementation may allocate any addressable storage unit large enough to hold a bit-field. If enough space remains, a bit-field that immediately follows another bit-field in a structure shall be packed into adjacent bits of the same unit. If insufficient space remains, whether a bit-field that does not fit is put into the next unit or overlaps adjacent units is implementation-defined. The order of allocation of bit-fields within a unit (high-order to low-order or low-order to high-order) is implementation-defined. The alignment of the addressable storage unit is unspecified.
Which is standardese for pretty much exactly everything you said :)
The consequence of the first rule is that there's only one sane way to lay out structs. The only way to break that rule which I can imagine would be to add extra padding - you can't swap the order of any members under these rules.
In theory you could use 3 extra bits for a bit pointer. Although the fact that a void* could hold it (or you need to make void* larger) would likely be an issue.
The funny thing is that there are much more than 3 wasted bits on 64 bit pointers anyways. So we could just use bit pointers. Of course this has costs in the hardware.
For a long time I've thought about various sorts of weird pointer organization (think of the compressed pointers used in modern JVMs or "tiny pointers" [1] or 8086 code that uses a 16-byte aligned segment pointer to point to a struct or array and uses and ordinary pointer to point to things inside that structure)
It doesn't seem too weird to me to make some kind of composite pointer that is a pointer plus some extra stuff. I've done some design work for a fantasy computer that has
- 48-bit words (fills up most of a Javascript double)
- 24-bit pointers (point to a 96 Mbyte address space)
- a "deep" extension that adds 6 bits to point to a starting bit and a 6 bit length field for an up to a 48 bit long extent -- extravagantly and maybe unrealistic for hardware these could extend into the next word. A zero length deep bit pointer could point to a UTF-8 character inside a word and there would be a load instruction that unpacks the next codepoint [2]
- a "wide" extension of 6 bits that points to one of 64 "address spaces" which are the unit of virtual memory management and could be contiguous to emulate a big address space bigger than 4GB with some room left for I/O spaces, video ram, etc.
- you're still left with 6 bits of "tag" to fill out a 48 bit word used for something defined by the OS or application
The backstory is that something like the IBM 360 had a baby with the PDP-10, had the word size doubled to get to VAX/370 XA size then had a baby with the Neo Geo arcade console to make a "home computer" that supports single/double width Unicode text. There would be extra points for there being a 24-bit instruction subset built in.
This isn't an outlandish idea. For example V8 has "pointer compression" https://v8.dev/blog/pointer-compression/. This is basically just 32-bit pointers with a know base offset. They still point at bytes (but known alignment is used for tag bits, so they don't really point at bytes, but more some VM-defined word)
Compressed pointers in 64-bit Java are exactly that. You save 4 bytes per reference at the cost of losing some bytes per object in overhead, how favorable that is at various heap sizes depends on the references/object ratio.
The IBM 360 settled the 8-bit byte as the industry standard, but Digital Equipment Equipment kept making stragglers up to about 1980s. The only machines with oddball word sizes I ever got my hands on were the 12-bit PDP-8 (my high school when I was in elementary school) and the 36-bit PDP-10 (Children's museum in Boston.) DEC also made the PDP-11 which seemed a lot like an 8-bit micro in mindset (RSTS/E let you code BASIC in your own 64k address space) and the VAX which was the OG 32-bit architecture which inspired the 68k, 80386 and the "workstations" of the 1980s. DEC struggled with the microprocessor revolution because they didn't want to undercut sales of their old machines, but they struck back with the 64-bit Alpha architecture.
It would be slower to get or set one bit in a byte than to treat the whole byte as a bit. Pipelining could hide the read overhead but memory operations are slow and setting one bit would be mean reading the byte, doing an AND or OR and then writing the byte back.
... and it's not just the overhead but also that a memory update on just part of a "word" is not atomic which is a problem for a multiprocessor machine but also for a single processor machine which is multitasking if there isn't some barrier to stop the process from being interrupted between the read and the write.
As hinted by another commenter this is because a byte is usually the smallest unit addressable in memory so using a whole byte even if the type does not require it simplifies everything.
As others have said: The way CPUs fetch and access memory is in larger word sizes. Even 1 8-bit byte can be inefficient depending on how that byte aligns in the larger structure and which ISA you're talking about.
Memory is cheap, so. shrug
In embedded this can be a very different story though. There we are often working with tiny memories and lower clock speeds and the concern is packing everything in tighter.
Because engineering is all about making choices. Making a boolean 1 bit would be space efficient. However, memory is being read at least 1 byte at a time. If you want 1 bit of that byte, that's an extra instruction.
So storing a boolean in one byte is more speed efficient!
(In C you can store a boolean in one bit. If, for example, you need to store a great number of booleans and memory size is more important than speed. )
The minimum access in modern computers is 1 byte of 8 bits, which means that to losslessly change the value of an 1-bit bool you need three instructions:
1. load byte at $address into $register
2. use whatever native instructions there are to change just that single bit in $register - in the worst case you need multiple of them
3. write byte from $register into $address
In contrast, all modern platforms have a single "store immediate (=hardcoded in the bytecode) value" instruction, so it's either two (set register to 0 / 1, write register to RAM) or even one (write value directly to RAM) instruction.
Bit-packing structures (another poster showed an example here in the thread) used to be done pretty much everywhere and you'll notice it if you deal with reverse engineering code even from the Windows 98 era... but in anything more modern it's not needed because computers nowadays have more than 640 KB of RAM [1].
By the way, accessing / modifying small values in large(r) containers is a common problem in computing in general, so if it interests you, you might want to look into "SSD write amplification", "SMR HDD write amplification" or "flash wear leveling".
I think the better question is why use a single bit or byte for a single bool when sum types exist?
You're pulling in an entire cache line (64 bytes) with any load. Why would you not just turn the bool into sum type that carries the payload with them? That way you can actually use the rest of the cache line instead of loading 64 bytes to work with a single bit, throwing the other 511 bits in the trash, and then doing another load on top for the data.
It's even worse when you do multithreading with packed bools because threads can keep trashing each other's cache lines forcing them to wait for the load from L3, or worse, DRAM.
It'd have to be a really old one. Almost every CPU with an L1 cache loads in cache lines and loads don't have to be cache line aligned because it's supposed to be transparent to the programmer. So there's little to no penalty on modern architectures for non-aligned words. I know there hasn't been one on ARM or Intel for at least a decade.
If you try to load and use consecutive words in a hot loop that are, say, 72 bytes apart you'll see a huge performance drop but that's more because you're only using 1/8th of the cache line and not because they're unaligned.
I hate to be that guy, but seriously, googling $subj yields thousands of fully detailed answers right away. This question is from the "answered countless times" category. Recognizing this may be hard though when you start, so next time try giving web search a chance, cause it may save lots of time.
Take a look at the Intel 8052 Microcontroller.
It has a part of its internal RAM that can be addressed as bytes with normal instructions, but also has special bit-instructions. You could set and clear a bit and jump if is was set or not set.
I used this feature a lot when making a little tetris game for the processor, but it was not essential.
Unless you're dealing with packed data (i.e., long arrays), there is no point in having scalars be less than 32 bits wide on modern architectures. This is due to architectures being optimized for 32 or 64 bit wide registers and even wider data buses. Writing a single byte to memory is in fact more expensive than writing 64 bytes.
Most video games compress booleans to bitfields in the save files to save space. Depending on the game, a save file can contain thousands of objects, so it makes sense to keep it small.
At runtime, booleans are 1 byte each. The additional work of shifting and masking to get to the bit you want simply isn't worth it. When reading from memory, the CPU will read a whole cache lines of 64 bytes anyways. So unless you want to process a lot of booleans (and only booleans) at once, it's simply not worth having them 1 bit each.
Because aligned data runs faster, a single boolean sandwiched inbetween integers or pointers can even take up 4 or 8 bytes of memory.
Note: Some languages have built-in optimisations where an array of booleans is actually 1 bit each. C++'s `std::vector<bool>` is such a case and I'm sure there are more.
I've seen people advise to never use booleans, simply because a number (or enum) can convey more meaning while taking up the same amount of space.
Bit fields are also common in live service network communication and other large data arrays like graphics calls in video games. Depending on what is being done, packets may not be inflated into proper data structures and left as raw bits to remove processing overhead. That’s my experience with actual 1 bit booleans, but yeah the vast majority of the time the “higher level” byte abstraction is just fine.
Other answers go into detail about why, but you have a more fundamental misconception: nearly all use at least 1 byte, the majority of which use 4 bytes.
Using 4 bytes is partially historical, x86 used to suffer from several performance pitfalls if pointer accesses weren't aligned (multiples of 4). While his generally isn't an issue on x86 any more, other architectures do still have this limitation. ABIs designed during that era (i.e. many of the ones we use today) inherited that limitation out of nessecity. Furthermore some instructions (including on recent x86 designs, I think) need to be 4 byte aligned.
34 comments
[ 2.7 ms ] story [ 72.3 ms ] threadYou can get a single-bit bools in a C++ struct, with eg
but you can't take a pointer to such a member.I was thinking about a fantasy computer that could run under JavaScript and have 48 bit words (fit in a double) and pointers like the PDP-10 but that could hang off one word into the next word. [1] First I was thinking “screw C” but came to the conclusion that supporting C would not be so hard after all with that kind of pointer.
[1] Think of a Chinese home computer from an alternate timeline where a strange mainframe had a baby with a NeoGeo arcade machine.
Their most "obnoxious" feature is that the layout is implementation defined, so they are not very portable between compilers and/or architectures.
Often used in an embedded setting to model hardware registers, when you can know/control what compiler implementation is used.
[1]: https://en.wikipedia.org/wiki/Bit_field#C_programming_langua...
Edit: more with the words.
C itself doesn't specify any ABI. A given platform simply uses one as a matter of convention.
C99 §6.7.2.1.13
> Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning
C99 §6.7.2.1.13
> An implementation may allocate any addressable storage unit large enough to hold a bit-field. If enough space remains, a bit-field that immediately follows another bit-field in a structure shall be packed into adjacent bits of the same unit. If insufficient space remains, whether a bit-field that does not fit is put into the next unit or overlaps adjacent units is implementation-defined. The order of allocation of bit-fields within a unit (high-order to low-order or low-order to high-order) is implementation-defined. The alignment of the addressable storage unit is unspecified.
Which is standardese for pretty much exactly everything you said :)
The consequence of the first rule is that there's only one sane way to lay out structs. The only way to break that rule which I can imagine would be to add extra padding - you can't swap the order of any members under these rules.
The funny thing is that there are much more than 3 wasted bits on 64 bit pointers anyways. So we could just use bit pointers. Of course this has costs in the hardware.
It doesn't seem too weird to me to make some kind of composite pointer that is a pointer plus some extra stuff. I've done some design work for a fantasy computer that has
- 48-bit words (fills up most of a Javascript double)
- 24-bit pointers (point to a 96 Mbyte address space)
- a "deep" extension that adds 6 bits to point to a starting bit and a 6 bit length field for an up to a 48 bit long extent -- extravagantly and maybe unrealistic for hardware these could extend into the next word. A zero length deep bit pointer could point to a UTF-8 character inside a word and there would be a load instruction that unpacks the next codepoint [2]
- a "wide" extension of 6 bits that points to one of 64 "address spaces" which are the unit of virtual memory management and could be contiguous to emulate a big address space bigger than 4GB with some room left for I/O spaces, video ram, etc.
- you're still left with 6 bits of "tag" to fill out a 48 bit word used for something defined by the OS or application
The backstory is that something like the IBM 360 had a baby with the PDP-10, had the word size doubled to get to VAX/370 XA size then had a baby with the Neo Geo arcade console to make a "home computer" that supports single/double width Unicode text. There would be extra points for there being a 24-bit instruction subset built in.
[1] https://arxiv.org/abs/2111.12800
[2] ... wouldn't it be nice to find a use for the illegal offset+length combinations?
The IBM 360 settled the 8-bit byte as the industry standard, but Digital Equipment Equipment kept making stragglers up to about 1980s. The only machines with oddball word sizes I ever got my hands on were the 12-bit PDP-8 (my high school when I was in elementary school) and the 36-bit PDP-10 (Children's museum in Boston.) DEC also made the PDP-11 which seemed a lot like an 8-bit micro in mindset (RSTS/E let you code BASIC in your own 64k address space) and the VAX which was the OG 32-bit architecture which inspired the 68k, 80386 and the "workstations" of the 1980s. DEC struggled with the microprocessor revolution because they didn't want to undercut sales of their old machines, but they struck back with the 64-bit Alpha architecture.
Memory is cheap, so. shrug
In embedded this can be a very different story though. There we are often working with tiny memories and lower clock speeds and the concern is packing everything in tighter.
So storing a boolean in one byte is more speed efficient!
(In C you can store a boolean in one bit. If, for example, you need to store a great number of booleans and memory size is more important than speed. )
1. load byte at $address into $register
2. use whatever native instructions there are to change just that single bit in $register - in the worst case you need multiple of them
3. write byte from $register into $address
In contrast, all modern platforms have a single "store immediate (=hardcoded in the bytecode) value" instruction, so it's either two (set register to 0 / 1, write register to RAM) or even one (write value directly to RAM) instruction.
Bit-packing structures (another poster showed an example here in the thread) used to be done pretty much everywhere and you'll notice it if you deal with reverse engineering code even from the Windows 98 era... but in anything more modern it's not needed because computers nowadays have more than 640 KB of RAM [1].
By the way, accessing / modifying small values in large(r) containers is a common problem in computing in general, so if it interests you, you might want to look into "SSD write amplification", "SMR HDD write amplification" or "flash wear leveling".
[1] https://lunduke.locals.com/post/5488507/myth-bill-gates-said...
You're pulling in an entire cache line (64 bytes) with any load. Why would you not just turn the bool into sum type that carries the payload with them? That way you can actually use the rest of the cache line instead of loading 64 bytes to work with a single bit, throwing the other 511 bits in the trash, and then doing another load on top for the data.
It's even worse when you do multithreading with packed bools because threads can keep trashing each other's cache lines forcing them to wait for the load from L3, or worse, DRAM.
If you try to load and use consecutive words in a hot loop that are, say, 72 bytes apart you'll see a huge performance drop but that's more because you're only using 1/8th of the cache line and not because they're unaligned.
Then don't :)
I Googled it and all of the first handful of links lack the combination of brevity and insight that some of the HN comments have so far.
At runtime, booleans are 1 byte each. The additional work of shifting and masking to get to the bit you want simply isn't worth it. When reading from memory, the CPU will read a whole cache lines of 64 bytes anyways. So unless you want to process a lot of booleans (and only booleans) at once, it's simply not worth having them 1 bit each.
Because aligned data runs faster, a single boolean sandwiched inbetween integers or pointers can even take up 4 or 8 bytes of memory.
Note: Some languages have built-in optimisations where an array of booleans is actually 1 bit each. C++'s `std::vector<bool>` is such a case and I'm sure there are more.
I've seen people advise to never use booleans, simply because a number (or enum) can convey more meaning while taking up the same amount of space.
Other answers go into detail about why, but you have a more fundamental misconception: nearly all use at least 1 byte, the majority of which use 4 bytes.
Using 4 bytes is partially historical, x86 used to suffer from several performance pitfalls if pointer accesses weren't aligned (multiples of 4). While his generally isn't an issue on x86 any more, other architectures do still have this limitation. ABIs designed during that era (i.e. many of the ones we use today) inherited that limitation out of nessecity. Furthermore some instructions (including on recent x86 designs, I think) need to be 4 byte aligned.