Boolean subtype confusion

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 Bool above therefore means that a boolean value takes eight bits to store, and has Integer as 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

1 Like

@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.)

@Tamas_Papp thanks for the input

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:

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 
1 Like

No worries, that was a bit tricky to spot, I scratched my head already :wink:

1 Like

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
2 Likes

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.

5 Likes