Comment by Panzerschrek
12 hours ago
Bool should be logically 1-bit, when stored in memory only least significant bit should be used and the rest is allowed to be garbage. Such approach gives compilers as much room for optimizations as possible. Forcing them writing some specific bit-pattern may lead to suboptimal code generation.
Bool is 1-bit, but that bit can be defined as signed or as unsigned.
If bool is defined as unsigned, casting it to any size of integers will give 0 for false and 1 for true (using the standard zero-extension operation that converts smaller unsigned integers to bigger unsigned integers).
If bool is defined as signed, casting it to any size of integers will give 0 for false and -1 for true (i.e. an all-1 bit pattern) (using the standard sign-extension operation that converts smaller signed integers to bigger signed integers).
Defining bool to ignore the other bits except the LSB leads to a lower performance on most processors, because in almost all instruction sets it is more efficient to test whether an integer is null or non-null, than to test the value of a bit.
The only efficient way to use a single bit and to ignore the others would be to store the boolean in the most-significant bit, i.e. in the sign bit of a signed integer, because testing the sign is normally as simple as testing whether a value is null. If this convention were used, a boolean result could be 0 for false and -1 for true, but in input arguments negative would be true and non-negative would be false.
« to test whether an integer is null or non-null »
Shouldn't this more correctly read zero or non-zero ?
Null and zero are synonymous, but null is preferable when used as an adjective and zero is preferable when used as a noun.
There are 2 words for the same concept because "null" comes from Latin, while "zero" comes from Sanskrit through Arabic.
Etymologically, "null" means "not even one" (by being a diminutive form of "not one").
The use of "null" in some programming languages to mean things like "undefined", "not applicable" or "nothing" is incorrect. For those the right choice is NIL, as in LISP (NIL means nothing).
While LISP had made the right choice by using NIL, it made later the mistake of calling NULL the predicate that tests if something is NIL. That predicate should have been called something like "is_nil".
When C.A.R. Hoare had introduced the word "null", he applied "null" to references, i.e. to pointers, not to the things pointed by those pointers. So a "null" pointer, whose value is zero, points to NIL, i.e. to nothing, and this is an alternative to devising an encoding for the things that are pointed to, where a special value is reserved to encode NIL (like the Not-a-Number values of floating-point numbers).
1 reply →
This reminds me of my favorite arcane C test: what value is TRUE and FALSE on X bullshit tool chain. My a favorite was 0=TRUE, 2=FALSE. I'd like to shake the hand of the joker who came up with that.
x86-64 and ARM64, at least, let you test an arbitrary bit in a register with one instruction.
The fact that bit testing also needs one instruction does not mean that it is equally efficient.
On x86-64, there are 2 ways to test the value of a bit. If you use the bit testing instruction (BT), that instruction is both longer and slower than testing if a register or memory value is null.
If you use the test-under-mask instruction (TEST), this is fast, but the instruction is significantly longer (by including an immediate constant for the mask). Longer instructions can also cause lower speeds, when various bottlenecks are encountered, e.g. the maximum number of bytes fetched per clock cycle or the capacity of the instruction cache or of the micro-operation cache.
Moreover, testing whether a value is null frequently requires zero instructions, not one instruction, because if the value is the result of computing some expression then the flags register already stores if the value is null or not (and its sign).
On ARM Aarch64, the instruction that tests a bit in a register has a much smaller jumping range than the one that tests whether the whole register is null, so testing a bit in a register may require the insertion of an extra jump instruction to reach the target where execution should continue.
Once upon a time testing whether all bits of a number are zero was slower than checking a single sign bit. Even when MIPS was originally designed, Hennessy and his team had some trouble with making BEQZ/BNEZ fast enough for their intended pipeline.
1 reply →
That's how gcc does it (at least in this one case), but as TFA points out, this is not standard-conforming.
I vaguely remember that Clang and GCC used to disagree what the contents of the upper parts of x64 registers when returning some integer types should be (zeroes or garabge), because the PDF that defined Sys V ABI on x64 left such irrelevant details out, so linking together objects produced by those compilers, both of which claimed to follow the same ABI, would produce malfunctioning executable.
> Forcing them writing some specific bit-pattern may lead to suboptimal code generation.
So? Forcing them to compile "return 42;" as "mov eax, 42; ret" also leads to suboptimal code generation: a plain "ret", returning whatever is in rax already, is optimal. It doesn't generate the specific bit pattern for 42 but that's a small price for the improved efficiency, isn't it?
The in-memory representation is a completely different question. The language could easily say that true has an integer value of -1 while still storing it as a single bit.