[ANN] EmulatedBitIntegers.jl

Package Announcements
1

I am happy to announce that we open-sourced EmulatedBitIntegers.jl. The package allows defining arbitrary bit width integers like UInt3 or Int7 which behave mathematically as you would expect, by overflowing and underflowing like a native implementation would do.

Internally, the package stores the values in a storage type which is a regular (non-emulated) primitive bit integer like UInt8. By implementing the Julia Base methods, the user normally does not need to know this except for two things

  • Storage space might be larger than expected, e.g. if you have a struct with two UInt4 values it will be 2 bytes instead of a single byte. But see the announcement for PackedStructs.jl how to avoid this.
  • Using them can be a bit slower due to the overflow and underflow guarantee which needs additional instructions in general.

That being said the package is highly performance optimized and for all I know generates the same machine code as a future Julia-native LLVM-based approach will generate (at least with Julia 1.12 and 1.13; Julia 1.10 lacks some LLVM optimizations). With all the progresses in superscalar processor architectures we have seen in the last two decades, there is no performance difference between the emulated bit integers and the native bit integers more often than not.

Related Work

Thanks to the nice people in JuliaData, who kindly allowed me to move and maintain the code there.

2

Int 7 ??? Gaccckk… I hate odd numbers.

In fact my scheme for increasing LLM performance is a number system with no odd numbers

3

The combination EmulatedBitIntegers.jl + PackedStructs.jl seems somewhat related to the type PackedVector from SmallCollections.jl. (Disclaimer: I’m the author.) For example

julia> v = PackedVector{UInt16,5,Int8}([1,9])
2-element PackedVector{UInt16, 5, Int8}:
 1
 9

defines a vector with 5-bit integers that are packed into an UInt16 (hence with maximal length 3) and appear to the outside as Int8. Besides vector operations like

julia> Int8(3) * v
2-element PackedVector{UInt16, 5, Int8}:
  3
 -5

(note the overflow) there are functions like push, filter or findfirst.

Maybe one can combine PackedVector with EmulatedBitIntegers.jl to declare an honest element type Int5 instead of the fake Int8.

4

Can you please give some examples where this is useful?

(I am not questioning that it is useful, I just want to learn new things. This is outside my field of expertise and I am being curious.)

5

Although I don’t think that I’ve seen Int7 in particular, these kinds of “weird” integers are somewhat common when dealing with certain protocols or with data-aware serialization. If you know your data distribution is heavily skewed, you can use small integers as codewords for the most common information, thereby saving bandwidth. It’s of course also common when interfacing with certain hardware, since they sometimes only have limited precision for their output registers.

6

Thanks, @matthias314, this is an interesting idea, as a PackedVector is the logical pendant to a PackedStruct. I haven’t looked into the code of PackedStructs, but there seems at least to be an overly restrictive type check:

julia> using SmallCollections, EmulatedBitIntegers

julia> @emulate Int2

julia> (1, -1, 0, 1) |> PackedVector{UInt8, 2, Int2}
ERROR: TypeError: in PackedVector, in T, expected T<:Union{Bool, Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8}, got Type{Int2}
Stacktrace:
 [1] top-level scope
   @ REPL[22]:1

I don’t know how the interface for a generic PackedStruct would look like. If you don’t want to restrict yourself to small collections, I think it would at least not contain the first parameter. It should also be able to auto-group, which PackedStruct from SmallCollections.jl already does, If I understood this correctly.

7

In addition to @Sukera’s answer, I’d say these kind of types can be useful whenever you consider using something else than Int, so e.g. when you

  • want to make use of the modulo behavior, e.g. the index of a ring buffer
  • want to limit the allowed values with the type instead of with additional constructor constraint in immutable structs and/or with additional setindex! constraints in mutable structs
  • want to accelerate your code by optimizing caching together with e.g. PackedStructs
  • want to ensure correctness with the type system without exploding the sizes, by e.g. widen by a single bit when doing addition instead of doubling the bit size
8

I’ve added support for EmulatedBitIntegers.jl to PackedVector. I haven’t done much testing yet, but it appears to work in principle:

julia> using SmallCollections, EmulatedBitIntegers

julia> @emulate Int5

julia> v = PackedVector{6, Int5}(3:5)  # (at least) 6 elements of type Int5
3-element PackedVector{UInt32, 5, Int5}:
 3
 4
 5

julia> v[1], typeof(v[1])
(3, Int5)

To get this branch, say add SmallCollections#emulated in the package manager.

9

That sounds totally great!

However, I seem to be doing something wrong. Any idea?

julia> using SmallCollections, EmulatedBitIntegers

julia> @emulate Int5

julia> PackedVector{UInt16, 3, Int5}(3:5)
ERROR: TypeError: in PackedVector, in T, expected T<:Union{Bool, Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8}, got Type{Int5}
Stacktrace:
 [1] top-level scope
   @ REPL[2]:1

julia> PackedVector{6, Int5}(3:5)
ERROR: TypeError: in PackedVector, in U, expected U<:Unsigned, got a value of type Int64
Stacktrace:
 [1] top-level scope
   @ REPL[3]:1

(@v1.13) pkg> status SmallCollections
Status `~/.julia/environments/v1.13/Project.toml`
  [2b935e18] SmallCollections v0.6.3-DEV `https://github.com/matthias314/SmallCollections.jl.git#emulated`
10

@PatrickHaecker Sorry, forgot to commit. Now it should work.

Caveat: I’ve tried several machines, and on one I get an InexactError. No idea why. On other machines it works.

EDIT: This seems to be an issue with bit truncation in EmulatedBitIntegers.jl.

11

Thanks for the report, @matthias314! I fixed the problem. It turned out, that here we could get even faster code, because we never need to throw and therefore even in the good case we can skip the branch.

12

Now it works. Thanks, @matthias314!

I probably do not understand the package well enough, but isn’t it at least by default quite wasteful for being a small collection? In this example 3 (practically 4) bytes would suffice, but 16 bytes are used:

julia> v = PackedVector{3, Int5}(3:5)
3-element PackedVector{UInt16, 5, Int5}:
 3
 4
 5

julia> v |> about
3-element PackedVector{UInt16, 5, Int5} (<: AbstractVector{Int5} <: Any), occupies 16B.
 m::UInt16 8B 0001010010000011                                                 0x1483
 n::Int64  8B 0000000000000000000000000000000000000000000000000000000000000011 3

 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
       2B+6B            8B
13

You are right. The length should definitely not be stored as an Int. Thanks for catching this!

14

I can imagine It should be stored in a type defined by a parameter, which might by default be an Int.