Dominik

Seeking for advice to understand why my parallel running demo code is slower than the sequential one

Hi,

I’m currently learning Elixir and I’ve come along this code (from the book “Programming Elixir >= 1.6”):

defmodule Parallel do
  def pmap(collection, func) do
    collection
    |> Enum.map(&(Task.async(fn -> func.(&1) end)))
    |> Enum.map(&Task.await/1)
  end
end

When running the following command:

iex> result = Parallel.pmap 1..1000000, &(&1 * &1)

it creates 1 million processes to calculate the square sum of each number (1 to 1 million).

I’ve added this sequential function called smap to check how much faster the parallel one is:

defmodule Parallel do
  def pmap(collection, func) do
    collection
    |> Enum.map(&(Task.async(fn -> func.(&1) end)))
    |> Enum.map(&Task.await/1)
  end

  def smap(collection, func) do
    collection
    # |> Enum.map(&(fn -> func.(&1) end))
    |> Enum.map(&(func.(&1)))
  end
end

I was astonished that the sequential function runs much faster. I went up to 10 million square numbers and it even gets worse! I’m running this code on a 2 GHz Quad-Core Intel Core i5 on macOS.

Am I doing something wrong? Is the overhead of creating, managing and (a)waiting for all the processes causing the parallel version to run slower?

I’d really appreciate any feedback.

Best regards,
Dominik

Side note:
I’ve searched in this forum but the only related topic I can find was this one but the problem there seems to be, that this user is using a single-core machine.

15 comments

#parallelism

34 1742 15

2021-06-19 12:53:02 UTC

Marked As Solved

fuelen

The issue here is that you’re trying to parallelize too primitive operation. The cost of multiplication of two numbers is tiny comparing to spawning a new process of the VM. Also, in the pmap Enum.map is invoked twice.

Post #2

Also Liked

amnu3387

A couple of notes that can perhaps help you thinking about processes in the beam (they’re not rules though):

Usually you want to parallelise things that have longer running time than the overhead of spawning processes (as others mentioned here)
Besides the overhead of spawning there’s also the overhead for the scheduler of the VM, in this case it has to guarantee that these 1M processes get scheduled, executed, removed, etc.
The last point is why usually it’s said whenever you have a queuable/parallel workload, to start about the same number of worker processes as you have logical CPUs. This is mostly true for work that is purely CPU bound, but due to scheduling, messaging, etc, I found that you might have gains even when you go a little beyond the number of CPUs (for pure CPU work).
When the work interleaves CPU/IO you can have many more worker processes and see a speedup although testing and knowing the workloads helps to decide correctly
Workers with an Orchestrator and/or Pool sometimes are used not for the speedup, but for managing memory usage to a reasonable level while still being able to process an unbound source of tasks/work or cleaning. (in the same vein, streams for instance are about controlling the memory usage, they’re slower than plain iteration)

One thing that helped me see how these things impact (I think it was in Joe Armstrong’s book Programming Erlang) was to build a program that md5’ed the contents of all files on your computer by doing directory traversal split by processes. Perhaps to around a few hundred (can’t remember what the number was in my tests) concurrent processes resulted in a speedup, but after a certain number, it became slower as the scheduling, yielding, sending back the results to the “main process” etc amounted to an higher overhead than the “lulls” when doing IO to get the filesystem information.

Since this also depends on the underlying system (soft&hardware) you usually have to test a bit to get the optimal settings for your particular use case, in that particular configuration.

Post #6

dimitarvp

Couldn’t resist and made a small GitHub repo that tests both of @Dominik’s functions and a naive implementation of a parallel chunk algorithm by myself here: GitHub - dimitarvp/elixir-benchmark-collection-algorithms: Small project that can test your collection processing algorithm (in Elixir)

Here are my results (check the README for how to run the benchmarks, it’s mega-simple):

Operating System: macOS
CPU Information: Intel(R) Xeon(R) W-2150B CPU @ 3.00GHz
Number of Available Cores: 20
Available memory: 64 GB
Elixir 1.12.1
Erlang 23.3.4.4

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 30 s
memory time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 1.60 min

Benchmarking dominik_serial_0...
Benchmarking dominik_parallel_0...
Benchmarking dimitarvp_parallel_chunk...

Name                               ips        average  deviation         median         99th %
dominik_serial_0                 12.87       77.69 ms     ±9.53%       76.04 ms       92.04 ms
dimitarvp_parallel_chunk          4.71      212.50 ms     ±6.31%      208.92 ms      252.02 ms
dominik_parallel_0               0.157     6359.22 ms     ±8.46%     6258.66 ms     7200.11 ms

Comparison:
dominik_serial_0                 12.87
dimitarvp_parallel_chunk          4.71 - 2.74x slower +134.81 ms
dominik_parallel_0               0.157 - 81.85x slower +6281.53 ms

So while mine is much better than the original (81.85x better) it’s still 2.74x slower than a simple serial implementation – because, as others have said, just squaring a number is simply not worth the parallelization.

I can guarantee (because I’ve seen it many times) that the moment the function becomes even slightly complex – and the elements of the list are not plain numbers – then “my” (of course it’s not mine!) naive algorithm has won consistently against many home-grown other algorithms, simply because it divides the work between all available CPU threads in chunks.

Post #8

hauleth

2 articles for you today:

Everything others said are in short real life examples of these laws at work.

Post #11

JeyHey

Distributing a tiny calculation such as the square on a million processes makes little sense in my opinion. I would try a more heavy and long running task.

Post #3

IloSophiep

Apart from everything already said: I would think this is a good place to use Task.await_many/1?

The way you do it, i would think it waits for all the tasks in the order of the collection. So it does spawn the 1,000,000 tasks, but then waits for the first one and blocks the await for all the other tasks during it.

Although I do have to say, i don’t really know if this would actually speed up anything in your case, sorry