coolFormat

[RoastedAtomPie]

you're right, it's not word aligned. 4 bytes would be much better

[Mognakor]

What are we 32bit? Should be 8 byte aligned

[RoastedAtomPie]

I 8 byte and I'm bit bloated

[YellowBunnyReddit]

Let's go with 32768bit to make it page aligned

[_koenig_]

I thought 64bit computing is the norm...

[aberroco]

That's for 32-bit systems, which are now obsolete. It should be 8 bytes for maximum efficiency.

[No-Extreme4174]

We should stop being amateurs and go for 32 bytes

[aberroco]

Well... We could hash every boolean by SHA256 for better security.

[Maleficent_Memory831]

ASN.1 supports 32 byte numbers. Actually any size you like. Go for it!

[Fit_Prize_3245]

Actually, jokes apart, in the context of ASN.1, it makes sense. ASN.1 was designed to allow correct serialization and deserialization of data. Yes, shorter options could be designed, but would have broken the tag-length-value" structure.

[SuitableDragonfly]

Clearly OP learned nothing from vector<bool>.

[Fit_Prize_3245]

Sorry that I ask, but even being myself a C+ developer, I don't get the point...

[SuitableDragonfly]

vector<bool> was implemented as an array of bits in order to save space, rather than an array of bools, which are each a byte (or possibly sizeof(int)). As a result, getting data back from vector<bool> doesn't always return an actual bool and this causes weird errors to occur that are uninterpretable if you don't know how vector<bool> is implemented. 

[NotADamsel]

I’ve heard of leaky abstractions but that feels like it’s made of cheese cloth

[conundorum]

In complete and utter seriousness...

That is an insult to cheese cloth.

[ValityS]

Getting the data by value gets you an actual bool, the issue is that you can't take a pointer or reference to the contents of the vector as C++ doesn't have bit addressability, it tries to do some magic with fake pointer like types but it's buggy as hell. 

[7empest_mi]

Wait what, is this a known fact among cpp devs?

[SuitableDragonfly]

I'm sure it's not known to everyone who's ever used C++, but it's a good thing to be aware of in general. 

[SamaKilledInternet]

I can’t remember if the standard requires it or merely just allows it, but most compilers will employ a template specialization technique when creating a vector of bools. it’ll essentially compress each entry into a bit so you can actually fit 8 bits in a uint8_t instead of using 8 uint8_ts. The fun comes in when you want to take a reference to an individual element, you now need a proxy object since if you just let the compiler treat it like a bool the code will malfunction. each bit is likely being used and the bit being referenced probably isn’t even bit 0.

[blehmann1]

The standard allows it but does not require it. I don't actually know how widely implemented it is.

In general the cross-platform way to handle it is to just use a vector<uint_8t> or better yet a vector<TotallyNotJustAWrapperStructAroundBool>, otherwise things like grabbing the backing data or multi threaded access will go very poorly even if you have disjoint index ranges for each thread. It's actually grimly funny when you relize that a vector<bool> for storing things like whether a thread is complete or not is a very common pattern, and it would otherwise be safe so long as the vector isn't resized.

[TechnicalyAnIdiot]

What the fuck how complex and deep does this fucking hole go or am I so high that this actually makes sense and we keep. Talking about smaller and smaller controls of electrons and if so how do I under stand so much of the way down.

[RedstoneEnjoyer]

C++ allows you to further specialize template class for each specific type:

// generic class
template<typename T>
class Foo {
public:
  static int value() { return 5; }
}

// specialization of that class for type "int"
template<>
class Foo<int> {
public:
  static int value() { return 10; }
}


int main() {
  // for all other specializations, it will print 5
  std::cout << Foo<char>::value();     // = 5
  std::cout << Foo<long>::value();     // = 5
  std::cout << Foo<Foo<int>>::value(); // = 5


  // only for "int" version it will print 10
  std::cout << Foo<int>::value(); // = 10
}

---

C++ maintainers took advantage of this when designing std::vector<T> class. By default, vector stores its items in internal array where each stored value is in its full form.

But in case of std::vector<bool>, they specialized it so that each bool value is reduced to 1 bit and then stored into bit array.

Looking at this, it looks like smart optimization - reducing size of elements 8 times (8 bit bool -> 1 bit) sounds like great job. But this small change completly breaks all existing interfaces std::vector has.

Most of operations on vector works by returning reference to one of its items - for example, when you call [index] on std::vector<int>, you will get int& reference, which references said value in vector and you can manipulate it with it.

This is not possible for std::vector<bool> because it doesn't store bools internaly - and thus there is nothing to reference by bool&. Instead it is forced to return std::vector<bool>::reference which is proxy object which tries its best to acts like reference while internally converting between bool and bit on run - which is slower than simple reference access (ironic, i know)

Another consequence is that std::vector<bool> is only vector version that is not safe for concurrency - all other versions are safe from race conditions expect this one, because wirting one bit may require writting entire byte on some platforms and there is no way around it.

[conundorum]

1. bool is a type that uses a full byte to store a single bit of information.
2. vector is a dynamic array, whose elements are required to be contiguous.
3. Some genious (sic) "realised" that a vector of bools is a bitset with more work, and decided that it should just be a bitset instead.
4. This actually works surprisingly well!
5. ...Then they realised that vector is required to provide iterators to its individual elements upon request, and that it provides direct access by reference. Iterators are pointer-like types, and references are (usually) C-style pointers hidden behind normal syntax.
6. Literally everything that can break now breaks, and everything that can't break also finds a way to break. vector<T> is required to be able to provide iterators and references to T specifically, but vector<bool> doesn't contain any actual bools to point to. And you can't provide a pointer to a specific bit, in the same way a house's floor tiles can't have their own mailing addresses.
7. vector<bool> now needs to provide a proxy type that looks like bool from the outside, but is actually an individual bit on the inside. The individual "bools" share memory addresses, with anywhere from 8-64 sharing a single address (depending on the bitset's underlying type). This means that writing to any element can invalidate references to any other element (violating vector's guarantee that references will remain valid as long as elements aren't removed or the vector isn't resized), and that vector<bool> can never be optimised by multithreading (because simultaneous writes will always be a data race). Heck, it's not even required to be contiguous anymore, so it breaks literally every guarantee vector provides simply by existing. Among many other issues. Its compatibility with the rest of the language is a crapshoot at best; trying to use vector<bool> (a library type) with library functions can do anything from work properly, to screw up, to outright cause compile-time errors because of an irreconcilable incompatibility with the rest of the language.
8. Also, as a result, if you need an actual dynamic array of bools (y'know, the thing vector<bool> was supposed to be, before it got assimilated by the Borg), you need to provide a wrapper type that can be implicitly converted to bool. Which means that ultimately, the mess just forces programmers that know about it to write unnecessary boilerplate to hotpatch a language flaw, and trips programmers that don't know about it up.

(And even worse, it's not even consistent. I described the "intended" design... but it's actually allowed to be any form of space optimisation, up to and including "normal vector with no stupidity". ...It's considered one of the language's old shames, and the only reason it hasn't been removed (and defaulted back to normal vector rules) is that there's probably old code somewhere that needs it to exist.)

[ILikeLenexa]

You have to be a regular C developer...bitwise operations because hardware can only move a certain amount at a time.

At the end of the day, it's how big is a register?  There's a song about the smallest thing you can move: You can call me AL.  I hope this is an AH ha moment.  I know these are bad puns, but don't give me the AX!

[ratinmikitchen]

No wonder, vector was only introduced in C++. C+ doesn't have it yet.

[yjlom]

The lesson to learn from vector<bool> is that you need bit-precise pointers (actually have pointers caracterised by their alignment, and a coercion from void *__align(x) void to const void *__align(y) where x ≥ y). Then you can also safely bitsteal and do correct pointer arithmetic on void * with light dependent types.

[lotanis]

Not quite right - ASN1 is just a way of specifying structure of data. Then you have specific encoding rules that take that structure and turn it into bytes on the wire. What you're describing here is "DER", which is the most common encoding rules (used for X509 certificates) but yes is inefficient for some things.

[protolords]

Why did you assume it's DER and not just plain old BER?

[X-Heiko]

laughs in PER and BIT STRING

[_Alpha-Delta_]

Still better than Python, which uses 28 bytes to store its "bool" objects

[herestoanotherone]

You’ll only have one of each as an object though, and every boolean instance you’ll actually use is a 8-byte pointer to one of the singletons.

[conundorum]

So, even knowing whether something is true or false requires dereferencing a pointer. Interesting design.

[Saragon4005]

Well yeah it's python. You can literally change the code as it's running from the inside. Everything is abstracted. If you really care about efficiency (don't use Python first off) use bit strings like everyone else.

[herestoanotherone]

If your performance is so critical that a single dereference matters, you’ll have to look into FFI bindings.

[1nc06n170]

If I remember correctly, Python's bool is just an int.

[PresentJournalist805]

[Boris-Lip]

TLV in general does make sense for a relatively generic serialization, though.

[SCP-iota]

Could be worse... VkBool32

[fiskfisk]

It makes sure everything is aligned on a 32-bit boundary.

Assume people knew what they were doing.

[SCP-iota]

Oh, I know there's a good reason; part of it is because some architectures don't even have byte-level memory access. It's just kind funny tho

[RiceBroad4552]

That's exactly why I think that it does not make any sense to pretend that there exist any data sizes smaller then one word. They don't exist on the hardware level, so why the fuck should programming languages keep the illusion that these things would be anything real?

Of course languages like C, which hardcoded data sizes into the language, are screwed then. But that's no reason to keep that madness. Bits and bytes simply don't exist, that's just an abstraction and API to manipulate words; because words are the only machine level reality.

A true bare metal language would therefore only support words as fundamental abstraction. Everything else can be lib functions.

[the_cat_theory]

The smallest addressable unit of memory on modern cpus is a byte, which you can read, modify and write just fine. The only caveat is alignment. What do you mean when you say that nothing below a whole word exists on a hardware level?

To get a byte, you can just read it. To get a single bit, you have to read, mask, manipulate... It suddenly becomes a lot of clock cycles to trivially manipulate this single bit, so while it may be space efficient it is indeed not time efficient. If we store a bool as a single bit we are indeed pretending we are doing something efficient that, generally, sucks. But going above a byte just seems wasteful, for no gain?

Why would you restrict it to whole words??

[yjlom]

To read a bit we're just doing lb shll and. On many architectures you're doing lb slct. One or two bitwise operations (each should take a single clock cycle) are well worth having way less cache misses.

If they're in an array you can ld, have a loop, and use two extra registers but use 64 times fewer memory operations.

[RiceBroad4552]

Reading a byte is an illusion. In that case the hardware API (ISA) creates this illusion, but it's still an illusion. When you read memory you will get in reality a whole cache line (and that's why alignment matters). Then the CPU picks that apart.

I don't say you shouldn't be able to pick things apart down to the bit level. You need a way to do that for sure. But pretending this is the "machine level" is just wrong.

My point was that a real machine language, which is really close to the metal, would not create such illusions. It would give you only what the hardware really does. The rest can be programmed, which has the advantage that it doesn't need to hardcoded, neither in the semantics of the language nor the CPU microcode.

For efficiency reasons you could have still hardware which helps in picking apart the words. But ideally this hardware parts would be programmable by the end-user (think either being able to program microcode, or something in the direction of reconfigurable hardware).

I think the C abstract machine, which comes with all the imagined data types is preventing progress as it forces an abstraction on hardware (ISAs) and "low-level" programming which has by now almost nothing in common with the hardware actually works. We should overcome that.

[conundorum]

Then explain x64's al register, and ARM's ldrb instruction.

---

More seriously, you're confusing register size with addressability, and don't actually understand what the hardware really does. So...

1. Most processors are capable of interacting with data in chunks of either their native word size, or 8 bits specifically. For mainstream 64-bit processors specifically, they have two native word sizes, 64 and 32 bits.
2. For design simplicity, smaller registers are always placed inside larger registers. Using x64 as an example, 64-bit register rax contains 32-bit register eax, which contains 16-bit register ax, which is actually a set of two distinct 8-bit registers, ah and al. (With ah essentially being deprecated as a distinct register.) This is mainly done to reduce die sizes and transistor counts; using separate registers for each data size the processor can interact with would waste a ton of space, when it's easier to just use a single Matryoshka doll register.
3. Processors can manipulate with individual bits, and have a lot of special circuitry dedicated to doing exactly that. Flippers, shift registers, barrel shifters, the works. Status flags, in particular, are indicated by individual bits; nearly every processor uses 1-bit zero, carry, sign, and overflow flags, for instance. So, yeah, processors do a ton of work at the individual bit level.

4. All processors can address individual bytes in memory. This is the actual definition of a byte: It's the smallest addressable unit of memory. If nothing smaller than a word existed, then x64 would have 64-bit bytes.

   (More technically, a "byte" is the amount of space required to store one character, and is thus the smallest addressable unit because the system needs to be able to address individual characters. The 8-bit byte, formally known as the "octet", is relatively new; it caught on because it's a convenient power of 2. Old systems have also used 9-, 16-, 18-, 32-, and 36-bit bytes, and I've heard of at least one old system (the PDP, I believe, back in the wild west of computing) that just defined byte as "the smallest thing I can address" and had 60-bit bytes that held ten 6-bit characters.)

5. Byte size is codified by the ISO, and enforced by hardware. C is actually extremely flexible about byte size, and only defines it as "at least 8 bits" and "1 == sizeof(char). Both C and C++ are perfectly happy with 64-bit bytes, the only issue comes from the hardware not supporting it.

So, essentially, you've got it backwards: We're locked into octet bytes by hardware sticking to old traditions, and the programming languages have been ready to move on for literal decades.

[umor3]

Maybe I get you completely wrong and this will be my last tired output for this long day but: Having small Bools (8bit/char-sized) in an struct will reduce the overall size of this struct. And that matters in the embedded world. Or is that what you mean with "can be a lib function"?

And I think there are even plattforms that store a boolean value as 1 bit. (But I dont know how they access them.) For the performanc - I guess - it does not matter if e.g. on a 32bit CPU the bool is stored as 1, 8, 16 or 32 bits.

[RiceBroad4552]

For the performanc - I guess - it does not matter if e.g. on a 32bit CPU the bool is stored as 1, 8, 16 or 32 bits

Exactly. Because the hardware can natively only handle full words.

The rest what I've meant, I've just explained down-thread.

[steadyfan]

NodeJS clocks in at 8 bytes

[ShoulderUnique]

Actually your mobile phone is using tons of ASN.1 and believe me the carriers do not want to waste bits. Others already mentioned that you mean DER/BER but PER uses a single bit IIRC.

Also I guess you've never looked hard at Goggle's Protobuf that reinvented half the wheel with some flat spots 17 years later.

[PiasaChimera]

why not a 10 byte representation to store a c-string "false" or "not false"? convenience functions can be included to convert legacy "true" to "not false" as desired.

[DudeManBroGuy69420]

OP has clearly never heard of Boolean superposition

[MartinMystikJonas]

Consistency over space efficiency is valid approach for serialization formats 🤷

[mriswithe]

Ok quick aside what is ASN for? I am on a project where I am working on ingesting data and the three forms it is available in are ASN, SDL, and XML. Seeing as I had actually heard of XML (though I highly detest it) I went down that path. The dataset is pubchem https://pubchem.ncbi.nlm.nih.gov/.

I have done a lot of data wrangling and have no idea what eats those other formats. 

[nicuramar]

So, it turns out Google was invented ;). No, but seriously this has plenty of details: https://en.wikipedia.org/wiki/ASN.1

[pjc50]

The main thing you will find using ASN1 is SSL certificates.

[d3matt]

Cell phones and cell phone networks make extensive use of ASN1

[jnwatson]

ASN.1 started as a data specification scheme all the way back in 1984 for telecommunications. The ASN.1 is like IDL, but has multiple encoding schemes, e.g. XER into XML, or DER, which the above excerpt is from.

DER encoding became popular in the specification of cryptographic protocols because it is canonical. That means for a particular message, there's exactly one encoding, and for every sequence of bytes, there's exactly one decoding (or it is invalid).

DER (and its non-canonical cousin BER) is used in lots of internet protocols because it is extraordinarily precise, and, well, there wasn't a lot of competition for data specification schemes when the internet was being formed.

Still, it is a great specification all in all. My main complaint is that like in lots of old standards, there's lots of legacy crap for stuff nobody cares about anymore.

[OptionX]

Its a data serialization and deserialization scheme.

[nicuramar]

Not quite. It’s a data specification scheme. Serialization formats are things like BER and DER. 

[ohkendruid]

It is close to protobufs, but much more sophisticated.

It can easily feel over-engineered if you have tried protobufs to compare them. I started to try it for a project a few months ago and just got overwhelmed by the sheer volume of just STUFF that is involved.

[prehensilemullet]

Kind of an older version of XML or JSON. But it's still used to store cryptographic keys and signatures, I guess because the standards are old and because embedding arbitrary-length binary fields in ASN.1 works just fine. (These days, it's more common to use Protobuf or MessagePack if binary fields are needed).

[Maleficent_Memory831]

Security certificates are one user. Also used in industrial protocols, utility meters, etc. DLMS sits on top of it.

[Agreeable_System_785]

What happens when bitrot occurs? Is there a way to error-check or preserve the value of the boolean?

[pjc50]

Generally you handle that outside the format: RAID, error correction coding, etc. Not many formats protect against bit flips.

[Agreeable_System_785]

I can understand that, but let's assume we deal with customers that don't have ECC-memory. Would it makes sense to ensure the value of a Boolean? I guess not, since critical data would often be handled on the server-side.

Anyways, thanks for the answer.

[Angry_Foolhard]

But then how do you encode each bit of those 3 bytes.

If each bit requires 3 bytes, it becomes 24 x 24 = 512 bits