[ANN] EnumSets.jl

Package Announcements
,
1

I am pleased to announce EnumSets.jl. From the readme:

EnumSets

Build Status
Coverage

This packages allows to create a very fast immutable type that represents a set of enum values.

julia> using EnumSets

julia> @enum Lang Python Julia C

julia> @enumset LangSet <: EnumSet{Lang}

julia> s = LangSet((Python, Julia))
LangSet with 2 elements:
  Python
  Julia

julia> push(s, C) # s is immutable, but we can create modified copies
LangSet with 3 elements:
  Python
  Julia
  C

julia> s
LangSet with 2 elements:
  Python
  Julia

julia> s2 = LangSet((C, Python))
LangSet with 2 elements:
  Python
  C

julia> s ∪ s2
LangSet with 3 elements:
  Python
  Julia
  C

julia> s ∩ s2
LangSet with 1 element:
  Python

...

Performance

using EnumSets

@enum Alphabet A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

function workout(sets)
    s = first(sets)
    b = false
    ESet = eltype(sets)
    E = eltype(ESet)
    for s1 in sets
        for s2 in sets
            for e in instances(E)
                s = (s ∩ s2) ∪ s1
                s = s ∪ s1
                s = symdiff(s, ESet((e,)))
                b = b ⊻ (s1 ⊆ s2)
                b = b ⊻ (s1 ⊊ s2)
                b = b ⊻ (e in s)
            end
        end
    end
    s, b
end

@enumset AlphabetSet <: EnumSet{Alphabet}

sets = [AlphabetSet(rand(instances(Alphabet)) for _ in 0:length(instances(Alphabet))) for _ in 1:100]
basesets = map(Set, sets)

# warmup
workout(sets, )
workout(basesets, )
# benchmark
println(eltype(sets))
res1 = @time workout(sets, )
println(eltype(basesets))
res2 = @time workout(basesets, )

@assert res1 == res2 # both yield the same result

# AlphabetSet
#   0.000279 seconds (1 allocation: 16 bytes)
# Set{Alphabet}
#   0.503022 seconds (8.15 M allocations: 756.469 MiB, 13.51% gc time)
7 Likes
2

If I take a guess, are you representing a set of enum values by storing a boolean array (or possibly a static array / tuple) indicating whether each enum value is present in the set?

1 Like
3

Not quite, I use the bits of an integer to store membership. Say an NTuple{64, Bool} would take 64 bytes of storage, while an UInt64 is able to represent the same information in only 64 bits. Also using integers gives direct hardware support for many operations. E.g. an intersection is just a single and.

2 Likes
4

If you care about speed in particular, then consider replacing EnumSets.jl/src/EnumSets.jl at 54ac214573eb812bc51a22f880fbaa169fa25642 · jw3126/EnumSets.jl · GitHub with the variant from base/BitSet julia/base/bitset.jl at d269d7d375827a0279dc1fee7bb24c9418f06f03 · JuliaLang/julia · GitHub

1 Like
5

Thanks for the suggestion. What are the key speed advantages of the bitset code you link? Is it about @inbounds or is there additional stuff I should borrow from?

6

In order to iterate over the indices of all set bits in an integer, you keep the current index as state, and to get the next one you increment until you find a set bit. Hence, you can expect roughly one branch-miss per output bit.

The alternative keeps as state the remaining integer, with all consumed bits chopped off. To get the next one, you simply count the number of trailing zero-bits (Base.trailing_zeros), and to get the next state you clear the lowest set bit (Base._blsr). Both of these have dedicated instructions in x86. You can expect roughly one branch-miss per integer, i.e. per for s in A.

You should expect ~10x speedup from that.

3 Likes
7

Awesome thanks a lot for these insights!