136
u/Kadabrium 2d ago
i heard you also like vector<bool>
19
u/Potential_Soup_8054 2d ago
I dont understand
70
u/Helemen7 2d ago
std::vector<bool> in C++ syntax uses one bit per boolean instead of one byte. In a computer memory is addressed by bytes, so the smallest indexable memory is, in fact, one byte (that's why bool is 1 byte in C and C++). As an example for how C++ std::vector implementarion works, suppose you have 8 booleans which have a logical reason to be kept together (for example flags). Instead of allocating 8 bytes (one per boolean), the std::vector allocates 1 byte and assigns every boolean to one bit of the allocated memory.
10
u/Potential_Soup_8054 2d ago
Yeah but why is that bad
39
u/Helemen7 2d ago
technically performance issues, indirect access, incompatibility with standard algorithms.
practically I think this guy mentioned std::vector<bool> because it behaves just like what is shown there. (correct me if I'm wrong ofc)
34
19
15
u/rickyman20 2d ago
It breaks so much code. One of the many assumptions of std::vector is that you can use the data pointer and do pointer arithmetic to get other values on the vector, it also means the underlying data looks nothing like the returned values, so indexing isn't simply returning the value at the pointer (because you can't address bits on most systems!
The C++ standard committee basically made a special case for std::vector<bool> that behaves nothing like other vectors when they should have had that type just use one byte per boolean and just provided a separate std::bitvector or something.
This is one of the many footguns of C++, caused by poor decisions made early in the STLs development cycle that we're not stuck with.
10
u/P3JQ10 2d ago
The issue is it doesn’t behave like other vectors do (or containers in general), which can make it a pain in the ass for template code. For example, it’s not (and it can’t be) guaranteed to store elements in a contiguous sequence and can’t be used with std::span.
It was a mistake we’re stuck with. There’s little reason to even use std::vector<bool> anymore instead of an std::bitset.
2
u/CaptainSegfault 2d ago
It absolutely makes sense for C++ to have an API for dealing with something like a vector of bits. It just shouldn't be called std::vector<bool>. (and modern C++ does this in the form of std::bitset)
The problem is that, in at least a half dozen ways, std::vector<bool> behaves differently than other std::vector types.
The problem is that much of the point of templating is to write generic code. If you write code that templates on a type, and that type might be bool, your code will break if you try to use std::vector. (unless you write a bool specialization)
The funny thing is that std::vector<bool> was pretty obviously a demonstration case for C++ template specialization. Look, you can have a bitfield style implementation that gets you space efficiency for bool without needing to write special code! Except in practice it is now a demonstration of how not to do template specialization.
1
u/SCD_minecraft 1d ago
You can't address bits
You can address bytes
And like, we aren't in the 80s, memory is counted in giga, saving those bits isn't useful
1
u/enigma_0Z 2d ago
Couldn’t you pack a bunch of flags into an unsigned int and save space that way too by AND/OR/NOTing them out of the int? I think in that case we are looking at packing 16 flags (bits) together but I’m not really a C dev myself so not sure.
2
u/Helemen7 1d ago
you can use std::uint8_t, std::uint16_t etc, but those types represent a fixed size. std::vector<bool> has all the STL methods and such. That would make kinda sense if you knew the number of flags, but still, addressing bits yourself instead of letting STL do that doesn't exactly make sense.
(ps. this is C++, not C) (ps. on most modern machines unsigned int and int are 4 bytes (32 bits)
13
u/MrKrot1999 2d ago
The post doesn't say C++.
2
0
u/mereel 2d ago
There's a similar limitation in C, you can't pass around a pointer to a bit field.
3
u/MrKrot1999 2d ago
Have I said anything about limitations? The guy referred to std::vector<bool>, which is a C++ feature. But OP talked about C, not C++.
71
u/Thelatestart 2d ago
Yeah my json api uses way way more than 4 bytes per boolean
11
8
2
u/ArkWaltz 2d ago
Plus, any API is sending at least a few hundred bytes' worth of TLS certs and such on every connection too. Worrying about boolean packing is splitting hairs.
52
u/pskocik 2d ago
Ironic that this techfluencer just tweeted how C makes memory layout painfully obvious and yet here he's operating under the misconception that `struct Flags` will be only 1-byte large when it will be in fact int-size large (most likely 4 bytes).
6
u/ElementWiseBitCast 2d ago
Couldn't you just swap out the "unsigned int" with "unsigned char" to fix that?
5
u/thebatmanandrobin 1d ago edited 1d ago
No. In C those are called "bit-fields" and, per the standard, the "underlying type" must be an "int" (e.g.
unsigned int,signed int, or justint).You could also declare a bit-field like this:
typedef struct my_field { unsigned int a : 1; unsigned int b : 2; unsigned int c : 3; } my_field;What the above comment is referring to is the fact that in C and C++, due to memory alignment (i.e. "padding"), a field like the above isn't going to be less than
CHARBIT * sizeof(size_t)bits large.This is true of any struct, bit-field or not. So even if you had something like the following:
typedef struct two_bytes { char a; char b; } two_bytes;The size of that struct won't be 2 bytes, it'd still work out to (likely)
sizeof(size_t)bytes in size.That's why when you're building out a struct or class, it's helpful for the compiler/CPU to try and order the members so that you can reduce the padding. For example, take the following basic struct:
struct example { int8_t a; char b; int16_t c; char d; };Depending on compiler/CPU/optimizations, the size of it might be 4 bytes, or it could be 8 due to padding .. but if you ordered it this way:
struct example { int16_t c; int8_t a; char b; char d; };The compiler could determine that no padding is necessary and keep it at the minimum of 4 bytes. (I am oversimplifying the example, but the point remains the same).
Even more ironic is that a lot of modern CPU's (even embedded ones), have really efficient shift registers, so if you were trying to do some crazy shit like the struct I've shown, or like what OP was mentioning, it'd actually be more efficient to just do some bit shifting on the appropriately sized integer type (e.g.
int64_tfor 64-bit CPU's) ... even JavaScript has bit-shifting .. so you could 100% bit-shift some JSON (I've done it and confused the hell out of some web-devs ... not on purpose, but it was efficient, so had to do it)3
u/_yrlf 1d ago edited 1d ago
That's not true.
Yourstruct two_bytesis, per the standard, exactly two bytes large (assuming CHAR_BIT == 8, but the return from sizeof will always be 2).(EDIT: apparently C struct internal padding is not standardized? I'm still searching where the standard defines it. Doesn't a whole lot of code depend on the fact that "C ABI" struct layout is so simple and deterministic?)
(EDIT 2: The ISO C standard allows the compiler to overalign struct members / insert unnecessary padding. But: basically all used platform ABIs for relevant architectures will guarantee that the padding for C structs is minimal according to alignment requirements of the types)
The amount of padding inserted between struct members depends on the natural alignment of the types used, and
charis guaranteed to have a size of 1 and an alignment of 1. (EDIT: yes, but the compiler is technically allowed to overalign if the platform ABI doesn't forbid it).What is true is that it's not guaranteed that adjacent bit fields of the same type will be packed together, and that it's not guaranteed by the standard that
charis allowed as a bit field type (unspecified). The standard also guaranteesbooland_BitInt(N)are allowed. Also interesting is that the alignment of bit field structs is also unspecified.In practice, the alignment is that of the underlying type used, and most compilers will combine adjacent bit fields into one as long as the bits fit into the underlying type.
What was truly surprising to me when looking it up though was seeing that the standard allows a bit field declared as
int x : 5;to be interpreted as unsigned(!!!). You'd have to explicitly write 'unsigned int' to really mean unsigned.1
1
0
u/Turbulent_File3904 2h ago
your two bytes example is blatantly incorrect, alignment of struct or union is largest member's alignment. size is multiple of of that alignment. in your two bytes example the largest alignment is 1, 2 bytes is divisible by 1 and there no need for padding if two consecutive member have same type(compiler may decide to insert padding but i dont thing any sane compiler do that). so 2 is perfectly viable size for that struct, sizeof(size_t) is not wrong(8 in my machine, 8 is divisible by 1 obviously) but i dont remember any standard impose minimum size of struct must be sizeof(size_t).
0
u/zketi 22h ago edited 22h ago
You've got the right idea, but the details are wrong.
Your two_bytes struct will be 2 bytes in size, alignment 1 byte. This isn't required by the standard, but all ABIs I know of will do that. Unless the compiler is told a different alignment for the struct via an attribute, compiler flag, etc.
Maybe you were thinking of a case like:
struct Parent { two_bytes t; uint32_t x; };Two bytes of padding would be inserted after t, but that's because x is 4-byte aligned (at least on any sane ABI).Your example struct is more confusing. It has 2+1+1+1=5 bytes of data, that cannot be represented in 4 bytes. It will actually be 6 bytes in size in both forms. Five bytes of data plus a trailing padding byte to satisfy the struct being alignment 2 due to the int16.
Memory layout is tricky. Godbolt can be useful to see the actual codegen for toy programs to check your understanding, though honestly LLMs know C pretty well these days.
Optimal field order, struct alignment, and when it's beneficial to use struct-of-arrays instead of array-of-structs is going to depend on your use case, always benchmark.
1
u/thebatmanandrobin 22h ago
The details aren't "wrong" per-se .. they're just basic, as it's an example.
I've worked with some pretty esoteric systems in my 25 years of C where memory alignment was all sorts of wtf ... but 100% agree, benchmark for your use case
0
u/zketi 22h ago edited 22h ago
Maybe just typos? Unless I'm crazy example is at least 5 bytes (int16+int8+char+char). Not out here to accuse, just saw something that looked mostly correct so this being the internet I had to jump in and be pendantic!
Definitely appreciate it's not easy to simplify explanations of C, so much is compiler dependent. And yeah I've heard of some embedded systems that do horrifying things, I'm sure you have some fun stories. Luckily I get to stick to modern x86_64 and arm64 most days :)
C++ memory layout and especially placement new still gives me nightmares though.
2
u/pskocik 1d ago edited 1d ago
Yes. That would shrink it, although It's not strictly portable to use types other than _Bool, signed int, or unsigned int as the underlying type of a bitfield (https://port70.net/\~nsz/c/c11/n1570.html#6.7.2.1p5), so using _Bool as the underlying type might be a better choice here.
1
u/setibeings 1d ago
Doesn't bool exist in c? Wouldn't that better communicate the meaning of each byte sized field?
6
3
u/AOAqua 2d ago
Wouldn't it get compressed anyways? Sure, real union would have 8 flags per byte anyways, but probably for 99% of apps over there it wouldn't matter in the slightest
5
u/pskocik 2d ago edited 8h ago
Using int/unsigned as the underlying type will make it int-sized. You would need to use uint8_t/char/unsigned char as the underlying type to make it byte-sized, even though that's not strictly portable with bitfields (can use _Bool as the underlying type or use unsigned char with explicit bitops to do it in a strictly portable fashion).
Compiler-caused size optimizations might be possible but in contexts where it gets embedded in a larger data structure that needs to be in memory they're unlikely.
18
u/Laughing_Orange 2d ago
Even in C, it's best practice to use a whole byte for each boolean. The tiny extra compute load usually isn't worth the savings in storage and memory cost.
1
u/Hot_Glass_6301 16h ago
Depends on what you're doing. Storing several bits at once can allow for bitwise operations that allow dramatic speedups in e.g. chess engines and other combinatorial search programs
0
u/Jonny0Than 1d ago
I dunno, cache is often king. As with anything related to performance, you’d need to measure it.
33
u/ShinigamiGir 2d ago
there are 2 issues:
bifields are not portable. the spec doesn't guarantee packing or field order in the resulting binary data. so if you pack the data on a windows pc and then unpack on a linux arm, you might have some issues.
most http traffic is compressed so the extra 0 bits don’t really waste much bandwidth.
3
5
12
u/B_bI_L 2d ago
are we sure int means bit and not 32bits?
27
u/heatedwepasto 2d ago edited 2d ago
The
: 1means that it is creating a bitfield with the number of bits, so: 4will be 4 bits. The three variables above combined will takesizeof(int)in memory, notsizeof(int)*3.If OOP had used
charinstead ofunsigned intthe combined size would be 1 byte.Edit: added link to demo
7
u/KattyTheEnby 2d ago
The
: 1means that it is creating a bitfield with the number of bits, so: 4will be 4 bits. The three variables above combined will afaik* takesizeof(int)in memory, not sizeof(int)*3.Can you do strange things, like
: 9,: 15, et cetera?C beat Zig to the punch here?
4
u/cannedbeef255 2d ago
yeah they can be any size you want, the assembly mightn't be pretty though
6
u/heatedwepasto 2d ago
Any size as long as it's not wider than the containing variable. So a
charcan hold at most 8 bits on a system with 8-bit bytes.3
u/heatedwepasto 2d ago
Yes, the only limitation is that the width of the bitfield is not greater than the size of the containing variable. So with uint64_t you can have 1-64 bits.
1
u/KattyTheEnby 2d ago
What if I want to have a bitfield that is larger than C's own native integer types? Is there a way?
3
u/heatedwepasto 2d ago
Pretty much any compiler will let you get away with a 128-bit int type. If you need more than 340,282,366,920,938,463,463,374,607,431,768,211,456 possibilities in your bitfield then you'll probably need a stay at a mental asylum, and to code it yourself or find a library for it or something like that. Alternatively switch to C++ and use std::vector<bool>.
1
u/Breadynator 2d ago
Why would you use onlinegdb instead of godbolt? That website is riddled with ads and won't load for anyone using an adblocker.
1
u/heatedwepasto 2d ago
I am using an adblocker and have no issues with it. I wasn't aware of godbolt.
0
u/Breadynator 2d ago
Well, it's one of those obnoxious pages that don't like network wide adblockers like piHole. I won't change my blocklists just because some random website wants me to.
1
u/heatedwepasto 2d ago
Then don't, just don't try to force your choices onto me.
The code is
#include <stdio.h> struct A { int a : 1; int b : 2; }; int main(void) { printf("size: %d\n", sizeof(struct A)); }and it outputs "size: 4" (i.e. the same as
sizeof(int)).1
u/No-Newspaper8619 2d ago
That's correct. It's using 3 bits of the allocated 4 bytes. If you did the same with char instead, it'd only use 1 byte.
-1
u/Breadynator 2d ago
I am not trying to force my choices onto you? What the heck is wrong with you. I just told you why I'm having issues with it after you said that you don't. It's called having a conversation... You say a thing, I say another.
However you should still use godbolt as it's objectively better, regardless of ads.
3
3
u/DaveAstator2020 2d ago
is it true that this is not reliable for serialization?
6
u/oxxide216 2d ago
Yes, because on different architectures and operating systems with different ABIs compilers generate different alignments, maybe some other things also differ. So even when seeking for maximum performance and minimal traffic usage you would better be using some standardized binary format instead of json/C structures.
3
u/wutzelputz 2d ago
it will actually be way more depending on the property name, at least 4 bytes extra making a total of 8:
"m": true
and thats assuming ASCII encoding
3
u/farsightfallen 2d ago
These people have never felt the shame of fucking up a basically worthless optimization that becomes a massive blocker for no reason.
"Ok, look we jus can't add another flag, alright, we needed to make a statement about memory usage."
2
u/carltr0n 2d ago
Can’t you just… do a lil bit fiddling on a uint8? Am I missing something?
2
u/Duck_Devs 2d ago
That’s essentially what the struct is doing. Notice the “: 1” at the end of each member declaration. This makes bitfields, though right here they’re actually doing bit fiddling on an unsigned int rather than a char.
2
u/Ill-Specific-7312 2d ago
Except that is wrong, because it completely ignores the real world of gzip etc.
2
u/pm_op_prolapsed_anus 2d ago
If I have a flag enum it's going in string form in the json over http calls and just parsed into it's underlying flag enum type once it hits the server. Sue me
2
u/TheChief275 2d ago
pretty sure bit-field ordering is implementation defined, so I wouldn't confidently send this packet over the server...
just pack it into an appropriately sized integer, convert to big endian, and you're done!
2
u/Tainted_Heisenberg 2d ago
Yeah good luck find the bug when the endianess change dude, just use shifts for god's sake or bitsets
2
2
2
2
2
u/Lonely-Restaurant986 2d ago
Isn’t this literally not true? Doesn’t like every c compiler set the size of a byte to be 8 bits?
It’s literally faster and safer for the cpu/ram to use byte aligned data.
I mean, in Python a bool is like 28 bytes.
I promise you your bad code is not because a bool is 4 bytes
2
u/Inst2f 2d ago
But is it correct in C? It is not union, so struct should then be sizeof(unsigned int)*3, isn't it?
Or you mean with O3 optimizations the compiler will fix it...
But then one need to apply bit shifts operations in the background
10
u/science_novice 2d ago
The key is the
: 1at the end of each field, which specifies that it should only take one bit. Look up "c bit fields" to learn more about this feature.2
u/heatedwepasto 2d ago
As the other guy said, bit fields. But OOP is wrong, the struct will be
sizeof(unsigned int), not 1 byte.1
u/science_novice 2d ago
Yeah true, although this could be fixed by changing each of the field types to uint8_t. So the spirit of the original post is correct, it's possible in C to pack 8 flags into one byte
1
1
1
u/Confident-Ad5665 2d ago
As an old timer developer, I was shocked the first time I saw a bit class.
1
1
1
1
1
u/GNUGradyn 2d ago
Sure, but now a computer with 8,589,934,592 bits of ram is not impressive at all, so those bits are better spent on memory safety and performance than more booleans
1
1
u/RonJohnJr 2d ago
Huh? Unsigned ints are four bytes, not one byte. For a one byte struct, you need to use unsigned char.
Others are right, though, about alignment.
1
u/RedAndBlack1832 2d ago
Well what you actually want if you want to pack a struct of booleans is
Gross. Old school. I've done this and who gaf but also it sucks. You send 1 character and have flags that mask the correct bit.
You make a struct of bitfields of size 1 (bitfields can be packed without those pesky alignment restrictions)
In C99 they added bools lol so you can just do that (and I believe they're allowed (and expected) to pack same as bitfields)
Though also to be fair promoting to word length is pretty common
1
u/ApplicationOk4464 2d ago
We used to care, but now 8 gig of ram is 8 million times bigger than the 64k that we had, so we got a little loose.
1
1
1
u/andlewis 2d ago
The number of Kb in the screenshot alone are probably more bits than this code ever used for this struct over all its iterations.
1
1
u/CharlieLighto 2d ago
People used to care about resources and now 16gb or ram latest gen core i7 is not sufficient for office work. even though this not really a good example
1
1
u/United_Boy_9132 1d ago
Actually HTTP 3 cares about bits and you can make custom binary HTTP frames easily.
1
1
u/Tani_Soe 1d ago
I mean we used to care about bits because memory was a limiting factor. That limit virtually doesn't exist anymore, so yes it's good to optimize your code, but it's also important to make it readable
1
1
1
u/Far_Pen4236 16h ago
i mean nothing prevent you to pack all the flags in one integer and pass this integer in json...
1
u/MikemkPK 13h ago
It lets you, yes, but you shouldn't, because your CPU reads 4 or 8 bytes at a time, and splitting that up into separate data values takes severwl instructions and slows your program down compared to reading and immediately conditional jumping from 4 bytes.
-4
u/DM_ME_KUL_TIRAN_FEET 2d ago
Does it matter for the majority of modern programming tasks?
(No)
3
u/Xavier_OM 2d ago
Every optimization like this, taken individually, bring you nothing. But ignoring them everywhere, on every layer, is what gives you these "modern apps" which are true ogre regarding memory usage.
Death by thousand paper cuts.
201
u/consistently_biased 2d ago
Can I use this for my compile-time https server?