Need guidance/suggestions for optimizing speed of set intersections

Hi Friends,
I am new to Elixir & Erlang but have been reading up on it for a while now and building small projects on the side. I have some experience with Akka framework in Scala so I have appreciation for the Actor model in OTP.

I am prototyping an Ad Server in Elixir at work and am wondering if anyone has suggestions on how I could achieve fast set intersections.

One of things I have to do in my server is find an intersection of close to 1000 integer sets for each incoming request. Each of the sets has about 10k items. The existing service that we have is written in Scala and it uses BitSet to model these sets. I could not find a BitSet implementation in Elixir or Erlang that supported intersections so I settled for MapSet to model my integer sets.

I benchmarked the MapSet intersection function with the Set intersection function in Scala and also did a benchmark of the BitSet intersection in Scala. Following are the results to do 1000 intersections for each of the above implementations. Also I have constructed the sets such that they have 5000 items in common. Note that following times are for doing each intersection

Elixir MapSet
1.2 millisecond

Scala Set
0.4 millisecond

Scala BitSet
0.1 millisecond

So the Elixir implementation is not exactly slow but I was wondering if anyone has suggestions on making this part of my service faster ?

Following is the elixir sample code I used.
`
def intersection_benchmark do
mset1 = 1…10000 |> Enum.into(MapSet.new)
mset2 = 5000…15000 |> Enum.into(MapSet.new)

test_fun = fn ->
  1..1000 |> Enum.each(fn _ ->
    MapSet.intersection(mset1,mset2)
  end)
end

:timer.tc(fn -> test_fun.() end)

end`

My apologies for not being able to format the code snippet above correctly :frowning:

  1. Make sure to use a proper benchmarking tool, right now you’re also including the time required to iterate through the list of 1000 items and call the Enum.each function it on it.
  2. Scala is still gonna be faster. Elixir is not built to win single threaded performance speed races.
1 Like

Using a benchmark library like benchfella makes this kind of testing much easier.

For raw single threaded performance, MapSet is unlikely to come close to a tuned implementation like BitSet. However, where Elixir can catch up so to speak is that it can easily do 10K separate checks
concurrently.

Using Elixir’s simple concurrency model to achieve parallel speed ups does require some understanding of your problem and correctly partitioning the work into chunks of the appropriate
size.

However, Elixir/Erlang also has excellent support for slicing and dicing binaries, so creating a bitset implementation would also be a possiblity. I’m not aware of a library that does that.

3 Likes

thanks bbense! I will try to parallelize my intersections and see what kind of speed I get. will also try to do better benchmarking.

Due to the way the BEAM scheduler works, you generally need to chunk things in sizes bigger than you might expect at first to get reasonable performance. As a rough rule of thumb each “time slice” in the BEAM for a process is 2000 reductions or function calls.

To get effective parallel performance you need to chunk the work into processes that have at least 3-4 time slices of work. It’s generally better to start with bigger chunks than smaller. What I have seen in various tests I’ve done is that for each problem there is a work size at which the performance curve flattens out.

2 Likes

A bitset intersection should be simple as set_a &&& set_b.

NB: But I think, bitsets of the sizes mentioned above will cause some other problems due to BEAMs immutability. For every single element you insert into the set, you need to copy copy a BigInt representing at least the value of the biggest element in the set.

Hi NobbZ I will try that out! thanks for the suggestion