[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 UInt5

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.

EDIT: One now also needs to define the unsigned version of every new integer type (UInt5 above).

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.

15

The master version of SmallCollections.jl now stores the length of a PackedVector as a 2-byte integer.

16

That looks awesome! Thanks, @matthias314. Sorry for being behind with processing all the progress from you.

Any reason why the length is not a type parameter of PackedVector with the constructors defaulting to master’s Int16? I don’t think that there are too many Int32 use cases, but I definitely see UInt8 use cases.

I also wondered whether you might be able to get rid of your type parameter M by adopting EmulatedBitIntegers’ bits interface. We could also extract that interface into a separate package to keep your dependencies smaller (and cleaner) until the Base interface is available in the Julia LTS version. Or wouldn’t this work because you want to be able to allow padding by M > bits(T)?

17

Yes, that would be sufficient for most (but not all) use cases. However, I wonder how much difference it would make. Unless the bit mask has only one byte, alignment rules prevent memory savings for smaller length types (without packed structs, that is).

Introducing an additional parameter for the length type would make PackedVector{U,M,T} an abstract type, which is somewhat inconvenient. More importantly, I’m thinking of storing the length inside the bit mask and not as a separate field. That would solve the alignment issue.

get rid of your type parameter M

I agree. The current first step is to make the existing API work with EmulatedBitIntegers.jl. If the parameter M is removed, then one has no choice but to use EmulatedInteger types. There are still some open issues with them. I’d like to wait until they are sorted out before I make that switch.

18

However, I wonder how much difference it would make. Unless the bit mask has only one byte, alignment rules prevent memory savings for smaller length types (without packed structs, that is).

Ah, indeed, good point. The primary use cases I see are around a collection of small, fixed-sized (but not static) different-length collections, i.e. a ragged array. If the elements are 8 bits each, it would be unfortunate if the length increased the alignment to 16 bits. However, you are right that this would probably imply a clever collaboration of multiple packages, as it won’t work with the large bitmask.

I’d like to wait until they are sorted out before I make that switch.

Thanks for that extra motivation. I think I addressed the open issues, but I’ve already identified some more, which I still need to look into in more detail.

But anyway, it’s not clear whether the bits interface belongs into EmulatedBitIntegers.jl or should be separate. On the one hand, every type can have a non-byte size, not only the primitive types EmulatedBitIngers.jl focuses on. On the other hand, basically all relevant types build on these primitive types (with maybe the exception of union tags and the like).
We should probably clarify this question first, because extracting the interface in a separate package is easier if there is only a single user which needs to be coordinated.