steven7

Efficient way to perform vector dot product

Hi I recently have the requirement to perform dot-product on two vectors in Elixir and I was wondering what would be the most efficient way. Imagine the following scenario,

Say I have ~1M vectors stored in memory, each with the following format [{"foo", 0.123}, {"bar", 0.777}, .........]. I now have a query vector with the same format and I need to compute the dot product of the query vector and each of the ~1M stored vectors. By dot-product I mean, if both vectors contains the same string key, multiple their float value and sum it all up.

Now my most naive/straightforward solutions is something like, instead of storing them as array of tuples, I convert them into Map and store them in memory as before, so my vector would become something like a hash-table %{"foo" => 0.123, "bar" => 0.777} and then:

Enum.filter(stored_vectors, fn -> vector 
  # Since we only need to process the "overlapped keys"
  query = Map.take(query_vector, Map.keys(vector))

  Enum.map(query, fn {k, v} -> 
      v * vector[k]
  end)
  |> Enum.sum
  |> Kernel.>(0.5)
end)

Now my issue is that Map.take is extremely slow when I am querying against 1M vectors. But if I remove that code and just do multiplication anyway like this:

Enum.filter(stored_vectors, fn -> vector 

  Enum.map(query_vector, fn {k, v} -> 
      v * (vector[k] || 0)
  end)
  |> Enum.sum
  |> Kernel.>(0.5)
end)

Its even slower. I am running out of options and was wondering how can I optimise my code.

P/S: I also tried one more thing like this but to no avail:

keys1 = query_vector |> Map.keys |> MapSet.new()

Enum.filter(stored_vectors, fn -> vector 
  overlapped_keys = MapSet.intersection(keys1, vector |> Map.keys |> MapSet.new())
  Enum.map(overlapped_keys, fn k-> 
      query_vector[k] * vector[k]
  end)
  |> Enum.sum
  |> Kernel.>(0.5)
end)

33 comments

#data-structures

20 3313 33

2025-09-18 17:59:51 UTC

Marked As Solved

sasajuric

Author of Elixir In Action

OK, it makes more sense now.

First, it seems that you might profit from running comparisons between different documents concurrently. You could use Task.async_stream for this, which would ensure that you’re not running too many things at once. This should give you a speed up of x, where x is close to the number of CPU cores.

This means that you’d need to store the documents in ETS tables. However, it doesn’t mean you need 1M of ETS tables. In a simple solution, you could have just one table, where keys would be e.g. {table_id, term}, and the values would be frequencies. Since a single table could be very big, you may want to resort to sharding, for example by using 1000 tables for 1M documents.

If you take the ETS approach, when you’re looking up a term, make sure to return only frequency, and not the key. Also, if you’re using it with multiple processes, turn on read_concurrency. You’ll also probably need write_concurrency, but it’s best if you determine this experimentally.

When it comes to recursion, I mentioned it in a context of a single comparison between two documents. In your case you have a situation where each step of the loop is simple and short (a lookup followed by a product), while the loop itself takes a lot of steps. In such scenarios, it can happen that the overhead of Enum becomes visible. So instead, you can try to hand-roll the loop by using recursion. That might shave off a bit of time, though I wouldn’t hold my breath The fact remains that you need to do 1M lookups (if I understand correctly, a vector can have 1M entries, right?), so this is probably where you’re spending most of your time.

Finally, it’s worth considering if Elixir is really a good tool for the job here. If I got it right, you have 1M documents, and each new document will produce a 1M map which needs to be compared against the existing documents. This means that if comparison between a vector and one document takes 1ms, the total time in a sequential version would be 1000sec (~ 17 minutes). If you take a concurrent approach, you can reduce this to a few minutes on a solid machine.

However, I’m highly skeptical that you can bring down a single comparison to 1ms. Something in the area of few tens, or maybe even few hundreds of milliseconds seems more realistic. This is just gut feeling, I don’t have hard numbers, so you obviously need to experiment. But if I’m right, the total time to process a single document would skyrocket to a few hours, which I presume is not acceptable.

So this is the point where you may want to consider implementing this entire logic in something else. For example, you could have a Rust program which keeps these documents in memory, and performs the comparisons. You could still use Elixir as a tool which manages the entire system. So for example, Elixir could queue pending documents, sending one by one to Rust in a demand driven fashion. Elixir could also be the place where you implement the web server (assuming you have such needs).

So in summary, I’d advise the following course of actions:

Focus on a single comparison between a large vector and a large document. Try to optimize this as much as you can. Try with maps, and try with ETS tables, to see which version works faster, and what are the differences.
Once you have the numbers, you can estimate if Elixir is even a good fit.
If yes, then try to work on making it concurrent.
If not, then try to do it in a faster language. C, C++, or Rust would be my choices.

Hope this helps!

Post #21

Also Liked

sasajuric

Author of Elixir In Action

My first question is where do these stored_vectors come from? Or more precisely, do you even need to store them in memory?

If you could instead process them directly as you read them (whether from a file, db, user input, or what not), you might be able to get some interesting savings. In particular, by not storing vectors into memory, and also by not creating intermediate maps and lists, you can reduce GC pressure significantly, and also stabilize the memory usage.

This approach might still take long, but since you’re processing while you’re reading the input, it can be significantly shorter, because you’ll replace time_to_load_a_vector + time_to_process_it with a single pass over the original input. In the worst case scenario, it would be similar to the original time_to_load_a_vector, so you could possible halve the total execution time.

This approach makes sense only if you don’t need stored vectors for anything else. If you do need to keep them around for other purposes, you can try iterating over the map with :maps.iterator. The idea is basically the same, you want to compute the result in a single pass through the input vector, without allocating a lot of memory.

Notice that you still need to keep the query_vector in memory (whether as a map or in ETS), since you need to repeatedly read from it.

In all these approaches (and even in your own attempts), I’d recommend using plain recursion. You do a lot of iterations with relatively simple processing, so Enum & friends might add a significant overhead.

The proposed approach also paves way to handle things in multiple processes. You could have one process which produces k-v pairs (by iterating the original source or the in-memory map), and another (or more of them) to look up the query vector and return the product. Not sure if this would help for such simple computation, but it’s worth trying out. If you go for this approach, I’d suggest avoiding Flow/GenStage. I presume you don’t particularly care about backpressure, and since processing of a single element is so simple (lookup and a product of two integers), any overhead of such abstractions might bring more harm than good.

Finally, if all else fails, you might consider implementing this piece of logic in another language (e.g. Rust or C). You do a lot of intensive CPU processing, and Elixir/Erlang don’t exactly shine here. IME (and I did my share of intensive processing), one can most often get acceptable results with a combination of proper algorithms and technical optimizations (such as the ones proposed here), but if it’s still not enough, then I don’t see other options.

Best of luck!

Post #18

sorentwo

Oban Core Team

Computing the dot product for that many rows without native support will always be pretty slow. Have you looked at Matrex for computation?

Post #15

bottlenecked

I believe the 1400 ets tables limitation has been lifted in the latter erlang versions

http://erlang.org/doc/man/ets.html

The number of tables stored at one Erlang node used to be limited. This is no longer the case (except by memory usage). The previous default limit was about 1400 tables and could be increased by setting the environment variable ERL_MAX_ETS_TABLES or the command line option +e before starting the Erlang runtime system. This hard limit has been removed, but it is currently useful to set the ERL_MAX_ETS_TABLES anyway. It should be set to an approximate of the maximum amount of tables used. This since an internal table for named tables is sized using this value. If large amounts of named tables are used and ERL_MAX_ETS_TABLES hasn’t been increased, the performance of named table lookup will degrade.

Post #17

LostKobrakai

If sounded like Map.take was your problem and :ets.lookup would be a faster alternative. I wasn’t suggesting that ets should do the calculation, but rather the storage.

Post #4

LostKobrakai

Is there a limit to ETS? I mean the data seems to fit into memory already and the references for the ets table should also not sweat with that number. But I’ve not have had to deal with such amounts of data as well.

Post #11