In addition to what @michallepicki noted, when parallelizing, you should avoid sending huge data structures as messages between processes, as that would involve a lot of copying. Often it is a good idea to implement the algorithm without parallelization, using it as a benchmark, and adding parallelization as an optimization.

One big change from other languages is that lists are immutable linked lists, so some operations become very expensive and take time (and sometimes space!) proportional to the length of the list.

Some examples:

a = [1]
b = [2 | a]

Prepending to the beginning of a list is fast - it allocates a single new cons cell. Takes constant time.

a = [1]
b = [1] ++ [2]

Concatenating two lists is more expensive - all the cells in the left-hand argument to ++ need to be reallocated, taking time and space proportional to the size of that list.

a = [1,2,3]
b = hd(a)

This is efficient, since the head is the first cons cell. Takes constant time. Note that tl(a) is also efficient, since those are the SAME cons cells as in a.

a = [1,2,3]
b = List.at(a, -1)

in order to access “the end” of a list, all the cons cells need to to be walked. List.at will take time proportional to the size of the list.

You’ll need to modify your algorithm to avoid doing the inefficient kind of operations; for instance, popping from the end might instead be represented with a constant-time functional queue like Erlang’s :queue (docs)

Also note (at least according to Wikipedia) the time complexity of this algorithm is exponential in the number of unique values in the input…

Re: the usage of spawn_link - consider using Task instead, it’s specifically tuned to the “take input, process, send message and then shut down” pattern you’ve implemented. Task.async_stream may prove useful as well.

It’s actually easy to make things slower by trying to parallelize things. Modern processors are usually really fast but are bottlenecked by memory access and bad data layouts. In Elixir most of this is abstracted away but in general you want to make sure that the overhead of parallelizing is lower than what you gain from running on multiple cores/machines at the same time (I hope that makes sense). So you need to find the balance of how much work you parallelize and how many workers to create. The gains may be bigger on bigger data sets.