Forgive if this topic is covered extensively in a multitude of different locations, but perhaps this will get everyone thinking fundamental language implementation:
why is a Boolean a subset of Integer with 8 bits.
Clearly only one bit is needed, so what’s the purpose of dedicating 7 more bits to the interpreter
It is unclear what you mean by this. Subtype? But Bool isn’t a subtype of either Int8 or UInt8.
It is, however, implemented as an 8-bit primitive type:
The declaration of
Boolabove therefore means that a boolean value takes eight bits to store, and hasIntegeras its immediate supertype. Currently, only sizes that are multiples of 8 bits are supported. Therefore, boolean values, although they really need just a single bit, cannot be declared to be any smaller than eight bits.
What interpreter?
Also, see BitArray. The choice between that and an array of Bool depends on whether speed or memory use is more important, as querying and flipping a single bit is comparatively more expensive.
Computers typically work in units of Bytes and not in units of Bits, and 1 byte = 8 bits. Therefore, multiples of 8 bits or 1 byte is used.
You can’t address less than 8 bits in memory.
Julia
Thank you
I meant to write subtype not subset
@chakravala okay I think I get it, so although there are 256 possible values, 1 byte is the minimum size that can be addressed? So back to the Boolean
julia> x = true::Bool
true
julia> bitstring(x)
“00000001”
julia> y = false::Bool
false
julia> bitstring(y)
“00000000”
Perhaps you meant the compiler.
Did you expect a different interpretation? What do you want to use it for?
If you just want to use ::Bool values in computation, they behave like the number 0 and 1 for practical purposes, except that they have a specific type, which is required in some contexts (eg if), and cannot accept any other value (I am ignoring some corner cases here).
The actual representation is not that important, except if you are interfacing with C or in some corner cases.
(Also, please quote your code.)
I faced now this “problem” as well. I wanted to have a variable with 4 bits, and then created a struct containing four Bool variables. The purpose was to be able to store very large arrays of these variables, which in my case can assume only 20 different values, so that 4 bits are enough.
However, I noticed that a Bool variable uses 8 bits in Julia, so it is not possible to define variables which take less memory than that.
Other languages (Fortran and C, for instance) also follow that behavior?
I have to compare very large arrays, and I thought that having the most compact representation of the values would provide the fastest code. Perhaps there are more deep reasons for the comparison of two bits not been faster than the comparison of two sets of 8 bits?
Still, after learning that, I was surprised that a function that counts the number of equal elements using my four-Boolean structure is faster than the same function comparing Int8 elements. Here is the code:
using BenchmarkTools
# Returns the number of equal elements
function compare( x, y )
n = length(x)
m = 0
for i in 1:n
if x[i] == y[i]
m = m + 1
end
end
return m
end
#n = 1000000000
n = 10000
println(" Int8: ")
x = rand(Int8,n)
y = rand(Int8,n)
@btime compare(x,y)
println(" End ")
println(" Char: ")
x = rand(Char,n)
y = rand(Char,n)
@btime compare(x,y)
println(" End ")
struct Quad{T <: Bool}
a :: T
b :: T
c :: T
d :: T
end
random_quad() = Quad(rand(Bool,4)...)
import Base.==
function ==( A :: Quad, B :: Quad )
if A.a != B.a
return false
elseif A.b != B.b
return false
elseif A.c != B.c
return false
else A.d != B.d
return false
end
return true
end
x = [ random_quad() for i in 1:n ]
y = [ random_quad() for i in 1:n ]
println(" Quad: ")
@btime compare(x,y)
println(" End ")
Result:
julia> include("./compare.jl")
Int8:
7.597 μs (0 allocations: 0 bytes)
End
Char:
7.614 μs (0 allocations: 0 bytes)
End
Quad:
5.089 μs (0 allocations: 0 bytes)
End
I guess the reason in Julia is the same as this one:
https://stackoverflow.com/questions/2064550/c-why-bool-is-8-bits-long
With the @inbounds flag in the loop of the compare function the difference is still greater:
Int8:
1.900 μs (0 allocations: 0 bytes)
End
Char:
1.435 μs (0 allocations: 0 bytes)
End
Quad:
15.431 ns (0 allocations: 0 bytes)
End
There is something fishy in your code. Comparing 10000 random numbers in 15 ns is suspiciously fast.
Notice that the == function is not behaving as intended:
julia> a = Quad(true, true, true, true)
Quad{Bool}(true, true, true, true)
julia> a == a
false
julia> a = Quad(false, false, false, false)
Quad{Bool}(false, false, false, false)
julia> a == a
false
Btw. I noticed it when I checked with @inbounds and 100000 elements. Of course, a random tuple of 4 Chars is less likely to match another random one, that’s why you most probably get 0 for the sum, but there I realised that the 0-sum for you Quad version must be incorrect:
░ tgal@staticbox:~/tmp py-3.7.3 took 1m 55s
░ 17:08:57 > julia p.jl
Int8:
19.847 μs (0 allocations: 0 bytes)
result: 391
End
Char:
16.512 μs (0 allocations: 0 bytes)
result: 0
End
Quad:
1.336 ns (0 allocations: 0 bytes)
result: 0
End
Thank you, actually the last “else” was to be an “elseif”, and then everything is back to normal.
Sorry for that.
Int8:
1.899 μs (0 allocations: 0 bytes)
End
Char:
1.377 μs (0 allocations: 0 bytes)
End
Quad:
35.233 μs (1 allocation: 16 bytes)
End
No worries, that was a bit tricky to spot, I scratched my head already 
The fact that Bool is 8 bit just reflects that almost all hardware has this as the minimal addressable unit. Your CPU literally lacks instructions to operate on single bits.
You can simply pack your values into a single UInt8:
struct Quad x::UInt8 end
Quad(a,b,c,d) = Quad((0x01 & a) | (0x02 & b) | (0x04 & c) | (0x08 & d))
@inline function Base.getproperty(a::Quad, s::Symbol)
if s == :a
return (a.x & 0x01)==0
elseif s==:b
return (a.x & 0x02)==0
elseif s==:c
return (a.x & 0x04)==0
elseif s==:d
return (a.x & 0x08)==0
else
return getfield(a, s)
end
Thank you. But what I was thinking was the possibility of representing a number between 1 and 20 in a more compact form than a Int8. If it is not possible to define a variable with less than 8 bits, then using Int8 is ok.
You can’t define a struct field with fewer than 8 bits in Julia. However, you can define an 8-bit field and use getproperty to pull out pieces of it. For example:
struct Foo
_data::UInt8 # 4 bits for a, 1 bit for b, and 3 bits for c
end
Foo(a::Integer, b::Bool, c::Integer) = Foo(a | b << 4 | c << 5)
function Base.getproperty(foo::Foo, field::Symbol)
data = getfield(foo, :_data)
if field === :a
return data & 0x0f # first 4 bits
elseif field === :b
return Bool(data & 0x10 == 0x10) # 5th bit
elseif field === :c
return data >> 5 # last 3 bits
else
error("type Foo has no property $field")
end
end
Then you can do:
julia> foo = Foo(3, true, 4)
Foo(0x93)
julia> foo.a
0x03
julia> foo.b
true
julia> foo.c
0x04
You can similarly define Base.setproperty!(foo::Foo, field::Symbol, val) to support assignment.
Note that in an expression like foo.c, the if field === ... checks get optimized out at compile-time thanks to constant propagation, so there is no runtime cost for these comparisons.
Basically, this is what a C compiler is doing under the hood for bitfield structs.
You could probably create a package with a macro to simplify defining bitfield structs in Julia. There is BitsFields.jl, but it doesn’t define a getproperty interface and I’m not sure it’s optimized to obtain performance similar to a C bitfield. I’m thinking of a macro that would let you do something like:
@bitfield struct Foo
a::4
b::1
c::3
end
and it would generate something like the code I wrote manually above.