Bitmaps in the Linux Kernel | Hacker News Reader

Bitmaps in the Linux Kernel

0xax.dev

12 pointsmatt_d6 comments

I wish someone would design a CPU where pointers refer to individual bits instead of 8-bit bytes. Sure, most instructions may still enforce that pointers are multiples of 8, but that’s no different from how existing instructions may have alignment requirements. I fail to see how such a design would be any less efficient if executed properly.

I think it’s silly that we always need to jump through hoops to declare and interact with bitmaps. Why can’t I just write the following?

bool my_bitmap[1024];

In an ideal world C++ wouldn’t need template specialization to make vector<bool> efficient.

Sacrificing three extra bits in every pointer also wouldn’t really lead to exhaustion of the address space. Intel and ARM CPUs don’t offer a full 64-bit address space anyway.

That really has nothing to do with what processors do not currently provide. As the headlined article explains, Intel CPUs have had instructions that can point to individual bits for donkey's years. The second operand to BTS (for example) is a bit address.

std::vector<bool> was its own special Hell, because it was invented as a way to try to expose what processors could do, instead of every compiler vendor having its own set of processor-specific intrinsics. Which meant, as Scott Meyers famously said, that it was not a standard container and it didn't contain any actual bools.

The world has long since come up with replacements. There are non-container bit vectors in C++, now, such as std::bitset and boost::dynamic_bitset.

It does, in as much as the desire is for uniformity. CPUs might have instructions to load a single bit but they can't take a standard pointer because a standard pointer does not include enough information. You would need to change the addressing of the entire ISA to make this consistent.

Many microcontrollers offer something a bit like that. There's typically a special part of physical memory that can also be addressed as bits using a separate address window.

Bitbanding is the term you're looking for, I think. Or the magic of FPGA where anything can be however many bits wide I need.

starred & followed

Reply on news.ycombinator.com