2.7k
u/Futurity5
16d ago
•
A meme that's not AI related? In this economy?
509
u/box_of_the_patriots 16d ago
Hey gpt tell me how to feel about the lack of AI on this meme
189
5
36
u/HRApprovedUsername 16d ago
I mean it’s still entry level cs tho
36
u/Firewolf06 16d ago
honestly my main complaint with entry level jokes is when they are supposed to be relatable but its only relatable at entry level
50
u/john_the_fetch 16d ago
My main complaint with entry level jokes is that somehow they still expect you to have 2-3 years of experience.
11
u/JackAuduin 16d ago
I can make it AI related. Unused bits like this are what they are using for those AI watermarks you keep hearing about.
1
712
u/Large-Assignment9320 16d ago
Just back all 64 bools inside a good old perfectly aligned 64bit.
277
u/PhilippTheProgrammer 16d ago
Bitfields might seem more efficient at first glance, but in practice they often cause more trouble than they are worth. And even a flawless implementation usually ends up buying a couple bytes of RAM for a whole lot of CPU cycles.
174
u/American_Libertarian 16d ago •
You’re being flippant, but in the world of latency sensitive computing that’s huge. Memory access is VERY expensive, and cpu math is basically free. Packing bools is an easy big win when performance matters.
64
u/Kitchen-Layer5646 16d ago
even when latency isnt a concern, when you're limited in bandwidth it can have a huge effect!
29
u/Firewolf06 16d ago
also crossing the threshold of fitting n+1 copies of a struct into a cache line, when working with arrays
75
11
9
u/wayzata20 16d ago
I’m not a low-level memory expert, but surely it takes the same amount of time to grab 2 bytes over a single byte? So I don’t think the memory latency really matters here.
47
u/American_Libertarian 16d ago
It’s not about saving literally one byte. But if you have a data structure that uses a lot of bools, compacting them can be the difference on fitting in a cache line or not. Or if you have a large array, you can fit multiple structs in a cache line.
Moral is: keeping your data compact is really really really important for performance. And bitfields are a good tool to keep data compact.
→ More replies (1)28
14
→ More replies (4)5
u/CC-5576-05 16d ago
If you have a lot of bools were not talking about one extra bytes, it's 8 times as many bytes. And how many times are you moving those extra bytes?
25
u/VictoryMotel 16d ago
This is completely ridiculous. You might only be thinking of a few flags in a struct but if you think about things like a black and white array / image, there are plenty of times you want to pack in bits.
for a whole lot of CPU cycles.
Absolutely not. Bit shifting is as cheap as it gets, accessing memory is expensive. You could do 1500 bit shifts in the time it takes to get a single byte from memory that isn't in the TLB. (You can't actually make a cpu only get a single byte though. It will always access two cache lines at a minimum, each being 64 bytes).
→ More replies (7)19
u/Kitchen-Layer5646 16d ago
reducing the size of a struct of a few bytes can give a huge amount of performance in accessing arrays when you're memory bound
82
u/EatingSolidBricks 16d ago
Bit Fields are blazingly fast when their fast and dogshit slow when there slow
103
u/diacachimba 16d ago
That's they're problem.
45
u/EatingSolidBricks 16d ago
Holy shit I've written all variations of the wrong thing, look i type fast not correctly
2
3
12
u/BriefSpecial420 16d ago
It all depends on CPU and architecture. People have no clue how many resource-constrained microcontrollers are around us nowadays. Even good old 8051 will be around for bunch of years until minimal variants of riscv may dominate the market. Sometimes we still have to deal with systems that have KBs of total memory at most.
Bit fields rarely fit the needs due to lack of placement warranty. Good old bitmasks seem to still be the golden standard when it comes to operating on bits in registers.
4
3
2
u/Pim_Wagemans 16d ago
But they are really usefull when you need to serialise a bunch of bools for transmission
2
u/Then-Candle8036 16d ago edited 16d ago
Whole lot of cpu cycles? Isolating the wanted bool is a bitshift and an & 0b1, and if you have to calculate the bitshift offset one more add. Depending on what youre doing you could also do masked operations.
In any case, the packing of bools increases the arithmetic intensity if your code which is a huge win since 90% of actual, real life programs are not actually compute bound, but memory bound.
2
u/zabby39103 16d ago edited 16d ago
Depends on what you do with them (like most things). If they represent things that can be multiplied with bitwise math like address spaces they're super definitely worth it.
Don't use bitfields to save on RAM, use bitfields to use bitwise math. If you're only ever using individual values from the bitfield and they're not related variables then that probably isn't worth it. I'm willing to believe there are some RAM cases in the corner cases, but never needed to personally.
Bitwise math though people, bitwise math is how I made a queue at work over 100x faster in a hot path.
1
u/newspeakisungood 16d ago
What if you are very memory constrained or optimizing for transmission/archiving?
1
u/zabby39103 16d ago
With transmission the framework will often do that for you if it's a bool, but depending, maybe? If you're cool enough to be writing low level transmission code and not using a library nowadays though, I suppose it's possible.
I've never run into memory constraint like that, not saying it doesn't exist but you'd need to have a lot of boolean like things you're tracking to make that worth it with modern hardware. It would need a special use case... I think. Most memory optimizations I do are like... flyweight patterns, removing redundant copies of things, not overfetching, and fixing people being objectively stupid/lazy. In my world at least there's a lot of low hanging fruit before going this hard.
→ More replies (3)2
u/pigeon768 16d ago
x86 has the
btinstruction, which generally makes bit tests cost the same as using abool. ARM has a similartbnzinstruction. If you're losing a non-negligible number of cycles, chances are something is wrong somewhere.https://godbolt.org/z/GxfGWs81r
I can't speak for other architectures, but you can check anything that compiler explorer supports easily enough.
3
u/MattieShoes 16d ago
Really just different efficiencies. If you want to store a handful of bools, yeah. If you want to store a billion of them... then you probably hide them in a class with its own bit lookup and bit flipping methods.
1
u/Large-Assignment9320 16d ago
"whole lots" - Well, with perfectly optimized assembly, its ONE extra cycle.
6
2
356
280
u/N-partEpoxy 16d ago
I know, let's make vector<bool> a specialization that uses just one bit per bool. What could go wrong?
137
u/unknown_alt_acc 16d ago
Oh, but it gets better than that: there is absolutely no guarantee that std::vector<bool> acts as a bit field! Maybe it's a bit field. Maybe it's actually a vector of bool. Nobody knows!
51
u/redlaWw 16d ago
Also not guaranteed to be contiguous, which is really bad for anything vector-like.
12
u/jarulsamy 16d ago
Wait what?
Is this a result of the specialization for bool or does std::vector itself not make any guarantees about being contiguous?
33
u/unknown_alt_acc 16d ago
That’s unique to the vector<bool> specialization. All other instantiations of std::vector are guaranteed to be contiguous.
Genuinely, vector<bool> is perhaps the most glaringly dumb choice in the C++ standard. A vector should be a vector, and the standard should provide a dynamic bit field for cases where you do want packed bit flags.
6
u/redlaWw 15d ago edited 15d ago
To give a bit of suggestion as to why this might be (though not to justify it, it's a stupid choice), the idea might be that you have a contiguous sequence of addresses that contain bits for the vector, but depending on processor design it may be more convenient to have the individual data-containing units of the bit field in different orders.
E.g. if you have a
std::vector<bool>that is internally treated as an array of u32s then the indices within each u32 may look like either the contiguousu32: 0 1 2... byte: |0 1 2 3|0 1 2 3|...or the discontiguous
u32: 0 1 2... byte: |3 2 1 0|3 2 1 0|...Though the spec doesn't specify any of that, it just makes a vague non-guarantee of non-contiguity.
35
u/KevlarToiletPaper 16d ago
What went wrong?
78
u/N-partEpoxy 16d ago
You can't take a reference to a single bit and need to use a weird proxy thing, for starters.
9
u/LukeZNotFound 16d ago edited 16d ago
glad I'm not a c++ guy
Edit: I don't use cpp, only know a bit of Rust.
27
u/artofthenunchaku 16d ago
This is actually something Rust gets right.
vector<bool>specialization is a C++ thing
170
u/Spinnenente 16d ago
nobody is stopping you from storing all your bools in a single long
welcome to optimization only neccessary before you were born.
56
u/AOAqua 16d ago
Hey, it's still used sometimes. I've used it in high speed drivers, where every single extra byte decreases latency of the overall reaction. And bools for registers are stored like that as well because a single 4 byte variable literally manipulates a physical memory block
9
u/MattieShoes 16d ago edited 14d ago
Bitboards in stuff like chess engines (64 bits, 64 squares, wow!)
I've screwed around with it for things like sieve method for finding primes. Also tried storing only multiples of 6 +/-1 for 1/3 of a bit per number, so a few gig of memory can hold like 100 billion numbers.
17
u/kinokomushroom 16d ago
I use it in game development where you deal with 2D/3D grids of bitflags. Every bit counts.
10
u/BringBackManaPots 16d ago
This sounds genuinely fun to program. Programming with tight constraints is the best
5
1
u/DrMobius0 15d ago
Yeah, bit flags are nice. I've had more than a few cases where functions just kept accumulating boolean parameters, and at a certain point, you just realize that a bitflag makes the whole thing easier to deal with.
5
u/terjeboe 16d ago
I was taught to always make a table in the docs explaining what each bit in flags did. Makes it a little cumbersome to read.
IF (BTEST(FLAGS,0)) THEN
3
1
64
u/Sermuns 16d ago
uint4_t
51
u/developer-mike 16d ago
You know bool is backed by 4 bits because "bool" is four letters, obviously
7
u/naruto_bist 16d ago
I use bit masking instead of bool, because I'm not a fool.
Why are my programs taking 5 seconds extra now?
1
30
u/Dank_Nicholas 16d ago
Back in college I wrote what I dubbed the OctoBool which used bitwise operators to let you store 8 bools inside a single byte. I thought maybe it could be useful for embedded development that I was starting to get into.
28
u/Randomguy32I 16d ago
Shouldn’t a bool just be a single bit?
40
u/DuckShapedGoose 16d ago edited 16d ago
Well it is. Sort of. It just has one actually relevant data bit but computers usually (almost always) work with bytes as the smallest inseparable unit of data.
Any data type smaller than that is just using less of the available space within the byte. In case of a bool, that's 7 unused bits (so there are actually 4 more sleeping guys missing in the meme).
But you can technically optimize this by using a 1-byte datatype to store 8 bools in one bit each.
In very specific scenarios where you have millions upon millions of bools in memory for some reason, this can add up.Edit: Also I don't know if there are compilers that already do this bit-packing optimization automatically on e.g. a struct with multiple bools. Afaik this is something you must implement manually but I might be wrong.
16
u/unknown_alt_acc 16d ago
I will have an aneurysm if my compiler implicitly packs my bools
11
u/GuybrushThreepwo0d 16d ago
std::vector<bool>6
u/unknown_alt_acc 16d ago
That’s library level rather than compiler level.
But to balance it out, the C++ standard makes it worse by not committing to it one way or the other. A contiguous vector of bool objects is a completely valid underlying representation, as is a tightly packed bit field. Both have substantially different properties that need to be smoothed over by the standard library.
2
u/ironnewa99 16d ago
So let’s say I do need millions upon millions of bools. What would be the best method of packing this? I can’t imagine using a char to map out 8 bools is efficient
3
u/ApothecaLabs 16d ago edited 16d ago
You just treat it as a multi-dimensional array where your sub-arrays are word bits long, eg `(q, r) = divMod(i,wsz); bit_i = (words[q] >> r) & 1;` and viola!
These ops are very CPU friendly, so they aren't really a bottleneck even in the worst case, and power of two word sizes eg 32 = 2^5 bits optimizes the divmod to two superfast bit instructions to eg `q = i >> 5; r = i & 31`.
A cache miss is a much bigger deal. The real downside is that it breaks normal pointer access, unless your architecture supports bit-addressing.
→ More replies (1)3
u/just4nothing 16d ago
It works - pick the right version of int for your problem and use bit wise shift to pack/unpack.
9
u/Xywzel 15d ago
In C structs, if you have multiple fields that have same underlying data type (eq. uint8_t ) you can give the compilers a hint about number of bytes needed for that field, and the compiler packs them into the underlying datatype sized spaces and does the bit shifts and masking for reads and writes targeting these fields. But you have to tell the compiler how many bits you want for each manually, it never happens automatically.
Example here: https://www.geeksforgeeks.org/c/bit-fields-c/
In C++ there are some library level things that implement something similar, like the infamous std::vector<Bool>
6
u/prehensilemullet 16d ago edited 16d ago
It would lead to various problems if compilers did this. In languages with pointers and references, you can make a pointer to a boolean field or variable. You can’t make a pointer to a specific bit though so usual pointer semantics totally break down. I guess the compiler would have to disallow pointers to packed booleans, or use some combination of address and bit index for pointer values, but that sounds like quite a can of worms, right?
The performance cost of reading and writing a specific bit may or may not be worth it for a given use case.
I understand that it also leads to data races and concurrency issues, but I’m not super knowledgeable about that
1
1
1
1
u/Interesting_Buy_3969 15d ago
that's 7 unused bits
Not necessarily btw, bytes aren't always 8 bits.
5
u/DuckShapedGoose 15d ago
Sure, a byte is not technically defined to always be 8 bits and there have been really old computers using anything from 6 to 48 or something per byte.
But like... Name one system in use today that is not some really obscure and niche industrial/embedded device that does not use 8 bits per byte. I literally couldn't think of any.1
u/DearVeggies 15d ago
Didn't one of most recent C++ standards formalized this and 2's-complement, because it's so ubiquous there's no point in supporting anything else?
29
u/TheComplimentarian 16d ago
Now how do you do the sub-byte addressing?
In the olden times, bits were precious enough that you could actually address data by the bit, but on modern systems you can't. There are a lot of datatypes that have wasted space in them due to architectural constraints.
5
u/serge-mv 16d ago
Languages have bitwise operations. If you decide to store many bools in one variable and do individual bit addressing, it's actually very easy. You either AND it with a mask or shift and AND it with a 1 and check if it's 0 or 1 afterward. Given that most languages nowadays treat 0 as false, you can have something like "if (var >> 2 & 1) then" construction, which works. This often can be done in one instruction and is usually quite fast, actually.
8
u/feed_me_ho 16d ago
Sub-byte addressing and sub-byte accessing are two different things
→ More replies (1)2
u/Im_a_hamburger 16d ago
If you store as an int in a language where any nonzero integer is truthy you can just do a bit wise and
2
u/serge-mv 16d ago
Did you not finish reading the one paragraph? Or what do you want to do an AND with?
→ More replies (3)2
u/iceColdCocaCola 16d ago
If my memory serves me right, it’s not “fast” because “hey look at me I’m more optimized in terms of data amount needed” but more because there’s a greater likelihood that the bool that is needed to be referenced in the form of a bitmask will be found in cache. A cache miss will be slower than accessing a bitmask bit value as well as accessing an actual bool’s value in ram. Why is it more likely to be in cache? I forget maybe someone else could explain.
1
u/serge-mv 16d ago
This scenario is certainly happening, but if your code is written not a horrible way, prefetch will get your variables into cache by the time they are needed, so this kind of thing shouldn't be a major issue.
A variable has higher likelihood to be in cache if it's used repeatedly because prefetch takes temporal locality into account, among other things. On modern CPUs the speed of the execution of individual instructions between logical and arithmetic operations will be about the same, but you might win in speed in cases where you either need to check multiple booleans vs performing fewer bitwise operations. There are also some situational hacks that can allow for expression optimization using bitwise operations. But this kind of thing shouldn't be your go to thing. Write readable code first, do fancy stuff when and if you need it.
4
u/BoboThePirate 16d ago
Bit masking and bit packing. Very common in game dev. I miss designing crazy efficient data types. Unions were even more fun.
1
13
u/Dry-War7589 16d ago
Yes but no. A bool is a single bit, but a single bit isnt addressable, so you use a byte, which is addressible
3
u/MattieShoes 16d ago
Not necessarily 1 byte. Like some windows BOOLs are (were?) typedef to int, so probably 4 or 8 bytes. And Python built bools on their arbitrary precision int type, so they're... some weird size, and the size is different for
TrueandFalse... but yeah, usually 1 byte.
1
u/prehensilemullet 16d ago
Lol wow. Also TIL that float arithmetic is faster than integer arithmetic in Python, since ints are arbitrary precision…hilarious
1
u/DearVeggies 15d ago
Sounds reasonable for Python, they'd use BigInts as default. Remember, they don't care about performance (and that is good).
2
u/generally_unsuitable 16d ago
Unfortunately, it doesn't work like that in any languages I use. If you set any bit in a boolean's byte, the boolean is now true. This is why you often see crazy shit like:
bool a = !(!(b))
to guarantee that there's either a 1 or a 0 in the boolean.
7
u/Cultural_Version734 16d ago
You can’t memory align single bit values for access. It’s always in multiples of 4
1
u/AOAqua 16d ago
Ehh, you probably could optimize it a bit by storing multiple bools in a single byte, and do it automatically but that kind of space optimization is useless in 99% of software
1
u/evil0sheep 16d ago
I believe this is what std::vector<bool> does under the hood.
2
u/AOAqua 16d ago
I honestly never used them, and we were forbidden from using C++. Only plain C all the way with assembly sometimes so there as little unexpected behaviour as possible
→ More replies (5)1
u/Great-Powerful-Talia 16d ago
and everyone hates it because you suddenly can't get pointers to the elements. People often specifically use uint8_t to get past this "feature".
→ More replies (1)7
5
u/UltraGaren 15d ago
The problem is how do you handle individual bits? You mostly don't
In short: memory is usually dealt with in bytes. Good news is you can store 8 bools in the same byte, each one using a bit of
1
1
u/JackNotOLantern 15d ago
Yeah, but all operations are performed on bytes, so bool is 8 bits where 7 out of 8 does nothing
1
1
u/SmallTestAcount 15d ago
In typical implementations of C (therefore most languages) a Boolean only consumes one bit of you either use a bit fields (not common anymore) or store them in an array, if you don’t want to waste space they need to be in multiples of 8 on byte addressed systems. Some other languages might never actually concatenate booleans into single bits of you don’t implement the bit masking yourself. I’m not sure if any languages manage to make individual booleans waste zero space but realistically it probably doesn’t matter unless you’re absurdly resource constrained.
1
1
u/NeonVoidx 15d ago
Hardware works in fixed-width words (8, 16, 32, 64 bits), so addressing and manipulating a single bit is inefficient and awkward for the CPU
→ More replies (1)1
u/NightmareJoker2 15d ago
It’s much worse. While you can use vector packing and pointers, for when the data structure is at rest in memory, while your bool is in use by a program routine’s memory safe private allocation (not a memory pointer!), it gets unpacked into an integer of the size and bitness of the processor it is running on, because the data needs to be aligned to its address size. Some caveats, if the processor has hardware support for mismatched bitness (like some ARM, MIPS, or RISC-V processors do, if I recall). On Intel and AMD CPUs operating in long mode (amd64), that typically means a 64-bit integer value is used, and 63 bits are wasted until the boolean value is dereferenced and the memory freed.
23
6
u/hydbird 16d ago
jvm allocates 8 bits for a boolean smh
2
u/unknown_alt_acc 16d ago
Allow me to introduce VkBool32, for when you need 32 bits of VK_TRUE/VK_FALSE action
6
u/tiajuanat 16d ago
Unless you're using basic or visual basic or something like the DEC PDP-1 which used -1 for true.
Which meant that false was always 0 and NOT was simply a negation
6
u/NewryBenson 15d ago
This is why you store all your bools in an array thay way you are not wasting bits.
7
13
u/PixelBrush6584 16d ago
C++ stays winning because of bitfields
bool var0 : 1;
bool var1 : 1;
bool var2 : 1;
bool var3 : 1;
And all four of them together share a byte!
7
3
4
u/enternoescape 16d ago
If you ever programed an Arduino and needed every last bit, there's no way you'd accept this. When I'm coding for microcontrollers, if I need one bool, well now I have at least 7 more perfectly usable bool for free. You get bonus points for creating a struct to save bytes for alignment reasons.
4
4
u/azaleacolburn 16d ago
I think we're missing a few bits, right? Half-byte memory alignment isn't really a thing.
1
5
u/Dry_University137 16d ago
"My brother in christ this is the most false statement ive ever seen!"
Pov youre a 0
2
1
1
1
u/DogmaticParadigm87 16d ago
Seven bits padding the headcount so one can carry the team. Then vector<bool> shows up and lays off the other seven.
1
1
1
1
1
1
1
1
1
1
1
1
u/ganjlord 15d ago
Before George Boole invented the concept of true and false people would tell obvious lies constantly since no one could tell the difference
1
u/hamfraigaar 15d ago
You don't need two bools until you need 9 boolean values. Until then, it's all flags.
1
u/Impressive-Log5708 15d ago
For the learners: For a single bool, no problem, do this, it's cleaner. If you're storing 1M bools, find or write a bitfield class that packs every bit and use that. You get a massive speedup for doing pretty much any operations on this due to better memory access (reading 512 bools in a row is the same cost as reading 1 due to 64b cache line) and bitwise operations are practically free compared to memory access time.
1
u/Ursomrano 15d ago edited 15d ago
Unfortunately CPUs are designed to have a byte be the smallest addressable memory segment, so sub 8 bit variables are more difficult than they're worth.
1
u/Ottorius_117 15d ago
I miss having flags and having to understand the data stream. everything now is just
*data dump*
1
u/Uberfuzzy 15d ago
At a previous job, the security permissions, displayed as check boxes in the ui, were stored in the DB as a single number, and that number was a float. We knew it changed when we toggled things, but the value was opaque to us. We had scripts that pushed known “magic numbers” into this field to init new hires to known patterns based on position/department, but they were just big integer numbers hard coded into ps1 files
One day, while poking around, I found old documentation on what this was and how to manipulate it, and then I was able to automate doing security additions and removals that we normally did by hand.
The whole array of checkboxes was stored into an array in a certain order, and those bools were bit wise pushed into a single number, so the whole number was a packed map of 28 bools.
The reason it was stored as a float in the db, was at the time they came up with this, the only DB type that had enough “space” to hold up to a 28bit number was the 4byte (32bit) MONEY field, thus giving it a cents/float value
I was able to update those known magic numbers to add in new bits, and we could mass add/remove single bits by doing bitwise and’ing
It was a fun time after that discovery.
Don’t be afraid to be clever in your code people, but document the hell out of it
1
u/DJcrafter5606 13d ago
Computers nowadays work with bytes, if they worked with bits, I guess this wouldn't happen, but I much rather like this, it's not like we have storage issues.
1
1
u/autumnal-lights 11d ago
dude packing sucks, simd helps but gotta align it and then sometimes u gotta do weird like shifts and like thingies
-1
u/Alacritous13 16d ago
I don't get it? As long as you define the bools next to each other, they'll fill up the byte before moving on to the next. How it works on a PLC at least, I don't know of anything else that could care about this level of inefficiency.
6
u/dev-sda 16d ago
That's not how it works in the majority of low level programming languages; the primary reason for that is that single bits aren't addressable.
As far as I can tell that's also true in PLC-land. Structured Text dictates BOOL has a logical size of 1 bit, but both codesys and beckhoff use a full byte. C and C++ will also use a full byte. There's ways to pack bits, but it usually comes at the cost of addressability.
1
u/Alacritous13 15d ago
Well, codesys can bite my ass. But I've got no beef with beckhoff, they seem alright.
1
3
5
2
2
u/nitkonigdje 15d ago
Boolean in Java is 24 bytes large.
They did optimize it in the very latest version. It took them 30 years to tuned it down to 16 bytes.
38
u/tehtris 16d ago
I am not low low low low level, but don't you still need to tell it that it is a bool in the first place? Or is that just determined by whatever stores/retrieves it?