Parallel programming for beginners on the Elixir / Erlang VM YP using the example of the “Euler horse” problem



Introduction


A little over a year ago, I did a very important thing in my life - I downloaded Visual Studio from the Microsoft IDE website and wrote in C ++ my first program in my life, oddly enough - “Hello, World!”. Over the next six months, I read Straustrup's notorious book, got a job as a C ++ junior developer, tried to write in Lua, Python, but did not achieve any significant success - my libraries did not work, the programs hardly compiled and crashed into runtime, the pointers indicated not to those parts of the memory (which, by the way, always leaked somewhere), but attempts to use more than one stream (C ++ 11!) led to memory corruption and deadlocks. It’s better to just keep silent about how the code looked.

Why am I? To the fact that in my personal opinion / experience, imperative languages, due to their characteristics, are completely unsuitable for novice developers. Without knowledge of industrial programming patterns, some information about the operation of the operating system and the elementary culture of the code, writing something tolerable on them is very difficult. They give too much freedom and space for crutches and bicycles, while functional languages ​​severely restricting the developer in some things leave him not so much opportunity to write poor code, forcing him to think and develop.

About six months ago, I realized that it was time to change something, and after half an hour of searching the Internet I found Erlang specifications. In the article, the author presented Erlang as a “wonderful pill” from all the problems described above, and in general, for the most part, he was right. So I started programming in Erlang, and then in Elixir.

Elixir language


Elixir is a language built on top of Erlang, the compilation result is the Erlang VM bytecode. It compares favorably with Erlang by its simple syntax and powerful tools for meta-programming (people familiar with Lisp will immediately recognize quote-unquote constructs). Accordingly, all Erlang functionality, any of its modules and, most importantly, the OTP framework is available for use.

Data types are the same as in Erlang. Data is immutable, the result of actions with them is new data. In Elixir, as in many functional languages, the principle of “Everything is expression” works. Any expression will return a value.

Elixir has an excellent interpreter that is installed with the language, you can try examples in it.

Basic data types


int, float
1 + 1 	# => 2
3 / 2 	# => 1.5
1.0 + 3 # => 4.0


binary
"Hello"<>" World!" 	# => "Hello World!"
"Hello #{World!}"	# => "Hello World!"
"""
hello
""" # => "hello\n"


atom
Constant representing only its value and nothing more. There is no separate logical type: true, false, nil are also atoms, just for them in the language there are corresponding conventions.
is_atom(true) # => true
is_atom(:true) # => true
is_atom(:hello) # => true


list
[1,2,3,4,"five"]++[6, "seven"] # => [1, 2, 3, 4, "five", 6, "seven"]
[1,1,2,3,4]--[1,2,3,5] # => [1, 4]

For historical reasons, strings in Erlang are represented in the form of a list, and not in the form of binary (in Elixir it’s vice versa), and therefore list can be represented as follows
is_list 'this is list' # => true
'lst'++[10000] # => [108, 115, 116, 10000]


tuple
Something like list, the difference in the organization of data storage in memory, and, accordingly, in the library means of working with data.
{:hello, "world"}


map
%{2 => 2, :c => {1, 2, 3}, "key1" => 1} 
#при использовании в качестве ключей только атомов, синтаксис упрощается, а скорость работы увеличивается
%{a: 1, b: 3, c: "qweqwe"}


PID
VM Erlang process identifier. The interactive shell of the interpreter is also a process, so we will use the self function that returns the PID of the process from which it was called
self # => #PID<0.95.0> (конечно число может отличаться от данного)


It is possible to explicitly do some type conversions.
:erlang.tuple_to_list {1,2,3} # => [1, 2, 3]
:erlang.integer_to_binary 123 # => "123"
:erlang.binary_to_list "abc" # => :abc


Also, one of the amenities of the language is that any term can be completely painlessly converted to binary and vice versa. Serialization of any data in one line.
res = :erlang.term_to_binary [:hello, {"world", '!!!'}] # => <<131, 108, 0, 0, 0, 2, 100, 0, 5, 104, 101, 108, 108, 111, 104, 2, 109, 0, 0, 0, 5, 119, 111, 114, 108, 100, 107, 0, 3, 33, 33, 33, 106>>
:erlang.binary_to_term res # => [:hello, {"world", '!!!'}]


Pattern matching



Data can be assigned locally to variables (there are no global variables and shared memory here and cannot be)
x = 1 # => 1
# теперь x связана c 1
x # => 1
# Можно написать даже так как в императивных языках (и оно заработает)
x = 1+x # => 2


But you do not need to do this at all. The code is simpler, more beautiful and more expressive if you do not use variables at all . Strictly speaking, the operator "=" in Elixir is not an assignment in the usual sense for imperative languages. This is where pattern matching takes place. Its essence is easier to show with an example.
%{a: x, b: 1} = %{a: 1, b: 1} # => %{a: 1, b: 1}
%{a: x, b: 1} = %{a: 1, b: 2} # => ** (MatchError) no match of right hand side value: %{a: 1, b: 2}
%{a: x, b: 1} = %{b: 1} # => ** (MatchError) no match of right hand side value: %{b: 1}


In terms of imperative languages, pattern matching is a combination of comparison and assignment: structure elements associated with a value to the left of "=" are compared with the corresponding structure elements to the right of "=", and not related - they are associated with the corresponding values ​​of structure elements to the right . It is logical that the structure on the right cannot have elements that are not connected with any value. If any of the comparisons returns false, an exception is thrown.

Pattern matching can also (and should) be done on binary data.
<< a :: binary-size(5), rest :: binary >> = "hello, world" # => "hello, world"
a # => "hello"
rest # => ", world"


By the way, pay attention to this example:
x = 1 # => 1
x == 1 # => true
%{a: x, b: y} = %{a: 12, b: 1} # => %{a: 12, b: 1}
x # => 12


Pattern matching was successful, there is no exception. Although it would seem that x should be associated with 1, and 1! = 12. In this sense, Elixir differs from more strict functional languages ​​(including Erlang), and that is why the use of pattern matching inside functions often leads to confusion and clutter code; this should be avoided. You can only feel the real power of pattern matching if you use it in function declarations and case expressions.

Functions and Modules


The language is functional, therefore the main expressive means of the language is function. Functions can be taken by functions as arguments and returned as values. Functions are defined inside modules, modules can also be defined inside other modules.

defmodule Some do
	defp priv_func(arg) do
		arg<>"Hello from priv_func!"
	end
	def pub_func(arg) when is_binary(arg) do
		arg<>priv_func("Hello from pub_func!\n")
	end
end


To define a public function that can be called outside of this module, you need to use def, and defp allows you to redo the function that is available only inside this module (see how much easier it is compared to Erlang). After the function name and arguments there may be expressions called guard-expressions (look at the definition of pub_func), they allow you to narrow the scope of the function (in the mathematical sense).

Some.pub_func "Hello from shell!\n" # => "Hello from shell!\nHello from pub_func!\nHello from priv_func!"
Some.pub_func 1 # => ** (FunctionClauseError) no function clause matching in Some.pub_func/1
Some.priv_func "Hello" # => ** (UndefinedFunctionError) undefined function: Some.priv_func/1 Some.priv_func("Hello")


In Elixir PL there are 2 almost equivalent ways to define a lambda (anonymous function):

sum = &(&1+&2) # => &:erlang.+/2
sum.(1,2) # => 3
sum = fn(x,y) -> x + y end # => #Function<12.106461118/2 in :erl_eval.expr/5>
sum.(1,2) # => 3


As you can see from the example, calling a lambda differs from calling a regular function only with the "." Functions can be passed as arguments not only lambdas, but also ordinary functions. To do this, put a "&" sign in front of the function name, and then indicate its arity.

defmodule Some do
	def actor(arg1, arg2, func) do
		func.(arg1, arg2)
	end
	def div(arg1, arg2) do
		arg1 / arg2
	end
end
sum = &(&1+&2) # => &:erlang.+/2
Some.actor(1,2,sum) # => 3
Some.actor(3,4, &Some.div/2 ) # => 0.75


Detailed documentation on Elixir and its standard modules can be read here , and on Erlang / OTP here .

Solving the Euler Horse Problem


When I was just starting to study C ++ and getting ready for entrance exams to the VMK magistracy (naively believing that they would learn how to code cool), I came across this task in one of the options for entrance exams. Then I could not solve it. For some reason, yesterday I remembered it again, and, having thrown the decision in an hour, I decided to write this article.

In general, the essence: “There is a square chessboard of arbitrary size, a horse is standing on it in an arbitrary cage, there are no more pieces on the board. It is necessary to go through a horse through all the cells of a chessboard, having visited each one exactly once, or to prove that it is impossible to do this. ”

Since there are no specific conditions determining the size of the board and the initial position of the horse, it is rather difficult to make abstract mathematical conclusions, tedious and not rational, so the most obvious solution is brute force.

To begin with, we will determine the data structures that we will operate in our functions. This will achieve a higher level of abstraction and greatly simplify the solution. In addition, the structures defined in this way make the code more deterministic.

# structs of data
defmodule Position do
	defstruct	first: 1, second: 1
end
defmodule GameState do
	defstruct 	current_pos: %Position{}, path: []
end


Position - the position of the knight on the board at any given time. Here we consider the two-dimensional case, but as will be seen later, the functional code is arranged in such a way that this solution can be very easily generalized for a space of any dimension.
GameState - the current state of the game, is uniquely determined by the current position and the path traveled.
As you can see, we are defining default values ​​for the structure fields, so we get something like a class constructor. The structures in Elixir are based on the map data type, and are very similar to them in use / syntax.

defmodule Some do
	defstruct	a: 1, b: nil
end
res = %Some{} # => %Some{a: 1, b: nil}
is_map res # => true
Map.keys res # => [:__struct__, :a, :b]
Map.values res # => [Some, 1, nil]


Next, we write the solution in general form. The init / 1 function takes as an argument the size of the edge (in this case the side of the square) of the board, randomly determines the initial position of the horse (and therefore the state of the game), informs the user about this using the inform_user_about_beginning / 1 function, then calls the game / 2 function, which returns the many possible workarounds, and then the show_game_results / 2 function, which tells the user about the results. Pay attention to the operator "|>". It simply passes the expression on the left as the first argument to the function on the right. The problem is solved, it remains to determine the functions that are not yet defined.

def init(limit) when (is_integer(limit) and (limit > 0)) do
	:random.seed(:erlang.now)
	[
		%GameState{	current_pos: %Position{
						first: :random.uniform(limit),
						second: :random.uniform(limit)}
							|> inform_user_about_beginning   }
	]
		|> game(limit)
			|> show_game_results(limit)
end


For the inform_user_about_beginning function, I think everything is clear - it accepts the argument, displays it on the screen and returns it.

defp inform_user_about_beginning info do
	IO.puts "Hello, user, we begin from #{inspect info}"
	info
end


The show_game_results function is a bit more complicated. As a result of our algorithm, we should get a list of possible workarounds. Naturally, we want to see different messages for an empty and non-empty list. Instead of if-else or case expressions inside one function, in this case it is better to write two separate clauses of the show_game_results / 2 function. This simplifies the code, makes it more visual and readable. The general rule is this: when a function is called, clauses for a given function begin to move over in the order in which they are written out in the code. In this case, pattern matching of all the arguments of the function in this clause and the corresponding arguments transferred from the outside are performed. If pattern matching succeeds, the function returns the expression of this clause; if not, the next clause is taken. If no clause comes up, an exception is thrown.

defp show_game_results([], limit) do
	IO.puts "FAIL. This is no any way to go through desk #{limit}x#{limit} from this position."
end
defp show_game_results([%GameState{current_pos: current_pos, path: path} | rest_way], limit) do
	"""
	SUCCESS! There are #{length(rest_way)+1} ways to go through desk #{limit}x#{limit} from this position.
	Here one of them: 
	"""
		|> IO.puts 
	Enum.each( path++[current_pos] , &(IO.puts "\t#{inspect &1}") )
end


Pay attention to the second clause, it uses the splitting of the list into the head and tail, which is typical for FP. In this case, the purpose of such a partition is to get the first traversal path from the list of traversal paths found directly in the function argument, eliminating the need to do this somewhere in the function body. In Elixir, both in and in Erlang, a list can either be empty ([]) or be broken down into a head and tail, where tail is a list.

lst = [1,2,3] # => [1, 2, 3]
[a | rest] = lst # => [1, 2, 3]
a # => 1
rest # => [2, 3]
lst2 = [0 | lst] # => [0, 1, 2, 3]
[first|rest] = [0] # => [0]
first # => 0
rest # => []


Also at the end of the second clause there is a higher order function. In fact, the Enum.each / 2 function here goes through all the elements of the list and applies to each element a function that it itself takes as the second argument (in this case, it simply displays). Further in the text there will be several more functions from the Enum module so that there are no questions about this I will immediately briefly describe how they work:

Enum.map( lst, func/1 ) # возвращает спискок, состоящий из элементов func(el), где el - элемент списка lst
Enum.filter(lst, func/1) # возвращает список из элементов списка lst, для которых func(el) == true
Enum.reduce( lst, res, func/2 ) # возвращает значение Enum.reduce(rest, func(el, res), func/2), где [el | rest] = lst, причём Enum.reduce([], some_res, func/2) == some_res


Now define the missing function game / 2. If we get an empty list of possible game states (and therefore bypasses) - we have nothing left to do with it except to return it. If the list is not empty, we check to see if the end of the crawl is reached, and depending on this, we either return the list of crawl paths or continue the crawl.

defp game([], _limit) do [] end
defp game(lst, limit) do
  case game_over?(lst, limit) do
    true -> lst
    false -> Enum.map(lst,
          &(generate_new_list_and_game_next(&1, limit)))
            |> List.flatten
  end
end
defp game_over?([%GameState{path: path}| _rest], limit) do
  length(path) == (limit*limit - 1)
end 


In the second clause of the game / 2 function there is a case - expression. At first glance, it resembles a switch, but in reality, by its nature, case is almost the same as a regular function in Elixir. The bottom line is:

case (выражение_0) do
	клауза_1 -> выражение_1
	клауза_2 -> выражение_2
	...
	клауза_n -> выражение_n
end


Sequential pattern matching of each clause is performed starting with the first c resulting from the execution of expression 0, and if it succeeds, case - the construct returns the expression corresponding to this clause. If no clause matches, an exception follows.

Next, we need to define the function generate_new_list_and_game_next / 2, which will take the state of the game in step n, convert it into a list of game states in step n + 1 (because from any cell the horse can make a move to a certain number of cells from 0 to 8, depending on the state in step n), and then pass this list to the game / 2 function. To write this function, you first need to know how the horse walks. Regardless of the initial conditions, all possible movements of the knight are known to us even before the algorithm starts working (for the queen, for example, this is not true - in this case, many possible movements are related to the size of the board). Therefore, the work of calculating all theoretically possible moves of the knight can (and should) be placed in compile-time. To do this, we write the make_permutations / 4 function in a separate module.

defmodule Permutations do
	def make_permutations( input_set, perm_size, condition, result \\ [])
	def make_permutations( _input_set, perm_size, condition, result ) when (length(result) == perm_size) do
		case condition.(result) do
			true -> List.to_tuple(result)
			false -> :failed
		end
	end
	def make_permutations( input_set, perm_size, condition, result ) when (length(input_set)+length(result) >= perm_size) do
		Enum.map( input_set, 
			fn(input_el) ->
				make_permutations( 	input_set--[input_el],
									perm_size,
									condition,
									result++[input_el] )
			end )
				|> List.flatten
					|> Enum.filter(&(&1 != :failed))
	end
end

In the make_permutations / 4 function, we simply get all permutations of elements from the set input_set with perm_size length that satisfy the condition condition.
And in the module in which we want to use the result of specific calculations, we simply write:

@horse_ways Permutations.make_permutations([-1, -2, 1, 2], 2, fn(lst) -> Enum.reduce(lst, 0, &(abs(&1)+&2)) == 3 end )


@ - designation of the module attribute. The expression accepted by the module attribute is computed when this module is compiled.
Now we are ready to write the missing code. Everything is completely trivial here, and the names of functions and arguments speak for themselves.

	defp generate_new_list_and_game_next(game_state = %GameState{current_pos: current_pos}, limit) do
		@horse_ways
			|> Enum.map( &(generate_new_position(current_pos, &1)) )
				|> Enum.filter(&( can_go_here?(game_state, &1, limit) ))
					|> Enum.map(&( go_here(game_state, &1) ))
						|> game(limit)
	end
	defp generate_new_position(	%Position{first: first, second: second},
								{delta1, delta2}  ) do
		%Position{first: (first+delta1), second: (second+delta2)}
	end
	defp can_go_here?(	%GameState{current_pos: current_pos, path: path},
						prompt = %Position{first: first, second: second},
						limit   ) do
		not(prompt in [current_pos | path]) and Enum.all?([first, second], &( (&1 <= limit) and (&1 > 0) ))
	end
	defp go_here( %GameState{current_pos: current_pos, path: path}, prompt ) do
		%GameState{current_pos: prompt, path: path++[current_pos]}
	end

Full listing:
full listing
defmodule Permutations do
	def make_permutations( input_set, perm_size, condition, result \\ [])
	def make_permutations( _input_set, perm_size, condition, result ) when (length(result) == perm_size) do
		case condition.(result) do
			true -> List.to_tuple(result)
			false -> :failed
		end
	end
	def make_permutations( input_set, perm_size, condition, result ) when (length(input_set)+length(result) >= perm_size) do
		Enum.map( input_set, 
			fn(input_el) ->
				make_permutations( 	input_set--[input_el],
									perm_size,
									condition,
									result++[input_el] )
			end )
				|> List.flatten
					|> Enum.filter(&(&1 != :failed))
	end
end
defmodule Horse.Solution do
	#########################
	### compile-time work ###
	#########################
	@horse_ways Permutations.make_permutations([-1, -2, 1, 2], 2, fn(lst) -> Enum.reduce(lst, 0, &(abs(&1)+&2)) == 3 end )
	# structs of data
	defmodule Position do
		defstruct	first: 1, second: 1
	end
	defmodule GameState do
		defstruct 	current_pos: %Position{}, path: []
	end
	####################
	### runtime work ###
	####################
	def init(limit) when (is_integer(limit) and (limit > 0)) do
		:random.seed(:erlang.now)
		[
			%GameState{current_pos: %Position{	first: :random.uniform(limit),
												second: :random.uniform(limit)}
													|> inform_user_about_beginning   }
		]
			|> game(limit)
				|> show_game_results(limit)
	end
	defp inform_user_about_beginning info do
		IO.puts "Hello, user, we begin from #{inspect info}"
		info
	end
	defp game([], _limit) do [] end
	defp game(lst, limit) do
		case game_over?(lst, limit) do
			true -> lst
			false -> Enum.map(lst,
						&(generate_new_list_and_game_next(&1, limit)))
							|> List.flatten
		end
	end
	defp game_over?([%GameState{path: path}| _rest], limit) do
		length(path) == (limit*limit - 1)
	end 
	defp generate_new_list_and_game_next(game_state = %GameState{current_pos: current_pos}, limit) do
		@horse_ways
			|> Enum.map( &(generate_new_position(current_pos, &1)) )
				|> Enum.filter(&( can_go_here?(game_state, &1, limit) ))
					|> Enum.map(&( go_here(game_state, &1) ))
						|> game(limit)
	end
	defp generate_new_position(	%Position{first: first, second: second},
								{delta1, delta2}  ) do
		%Position{first: (first+delta1), second: (second+delta2)}
	end
	defp can_go_here?(	%GameState{current_pos: current_pos, path: path},
						prompt = %Position{first: first, second: second},
						limit   ) do
		not(prompt in [current_pos | path]) and Enum.all?([first, second], &( (&1 <= limit) and (&1 > 0) ))
	end
	defp go_here( %GameState{current_pos: current_pos, path: path}, prompt ) do
		%GameState{current_pos: prompt, path: path++[current_pos]}
	end
	defp show_game_results([], limit) do
		IO.puts "FAIL. This is no any way to go through desk #{limit}x#{limit} from this position."
	end
	defp show_game_results([%GameState{current_pos: current_pos, path: path} | rest_way], limit) do
		"""
		SUCCESS! There are #{length(rest_way)+1} ways to go through desk #{limit}x#{limit} from this position.
		Here one of them: 
		"""
			|> IO.puts 
		Enum.each( path++[current_pos] , &(IO.puts "\t#{inspect &1}") )
	end
end



Let's try to run. Something like this should turn out:

image

Or this, if you're unlucky with the initial conditions:

image

How quickly did you get the result for the 5x5 board? What about 6x6? Not very fast. As top shows us, Erlang VM loads only one core.

image

Time to parallelize the calculations.

Parallel task solution optimization



Making a new process in Erlang VM is easy. The spawn and spawn_link functions start a function in the new process, which is taken as an argument and returns the PID of the child process. The process ends after this function returns a value. Using spawn_link is generally more preferable, since in this case, if there was an exception in the child process, it will be forwarded to the parent process, and vice versa, which makes the program execution more deterministic.

spawn_link fn() -> IO.puts "hello from #{inspect self}" end # => #PID<0.80.0>
spawn_link fn() -> 109 / 0 end # => ** (EXIT from #PID<0.76.0>) an exception was raised
spawn fn() -> 109 / 0 end # => #PID<0.85.0>


The obvious place to optimize is the Enum.map/2 function anywhere in our code - all you need to do is process each element of the list in a separate process, and then collect a new list from the values ​​received. Why is this not implemented directly in the core of the language?
The first possible reason is that in the general case no one guarantees that a pure function will be passed to Enum.map. Alas, it sometimes matters in what order to make the calculations. Such "dirty" functions, the outcome of which (in the global sense) depends not only on the arguments - should be avoided, and if it cannot be avoided, at least somehow localized.
The second possible reason is the limitation of the number of processes. If we assume that such a hypothetical parallel running Enum.map is somehow called recursively, then the number of processes will begin to grow like an avalanche. The Erlang virtual machine is a very stable thing in this regard, and the processes themselves are very cheap. But everything in this world has a limit.
Nevertheless, right now we will write our own, in parallel (and at the same time correctly) working Enum.map (although the purity of the functions transferred to Enum.map will remain on the conscience of the one who will use it).

Formally, processes in Erlang VM do not have shared data, they are completely isolated, and can only send messages to each other asynchronously. The message can be any Erlang term. Messages are sent by the send / 2 function, and are received using receive expressions that are very similar to case expressions. The difference is that if there is no suitable clause for the receive expression (that is, there are no messages of expected types in the mailbox) - the exception is not thrown, and the expression “hangs” until the appropriate message arrives (it is also possible to set some timeout )

defmodule Some do
  def receiver do
    receive do
      "hello" ->  IO.puts "hello from receiver"
                  receiver
      "please, die" -> IO.puts "OK ... "
    end
  end
end
child = spawn_link &Some.receiver/0 # => #PID<0.182.0>
send child, "hello" # => на экране hello from receiver
send child, "some message" # => на экран ничего не вывелось
send child, "hello" # => на экране hello from receiver
send child, "please, die" # => на экране OK ...


As you can see, everything is very simple. But there is one “but” about which we have already spoken. Erlang VM can support thousands, tens and even hundreds of thousands of processes simultaneously. But this number is still finite, and this must be taken into account. For such an account, we need one counter-process for the entire Erlang VM. It is arranged very simply - accepting corresponding messages from other processes, it must be able to increase by 1, decrease by 1, or send its value to the process that requested this value. How to store the state of an abstract object in functional languages ​​where there is no shared memory and global variables? The correct answer is recursion.

	def parallel_enum_control_system number \\ 1 do
		receive do
			%{ from: sender, query: :get_number} -> 
						send sender, number
						parallel_enum_control_system number
			:increment -> parallel_enum_control_system number+1
			:decrement -> parallel_enum_control_system number-1
			some -> IO.puts "WARNING! Unexpected message in parallel_enum_control_system: #{inspect some}"
					parallel_enum_control_system number
		end
	end


But passing the PID of the counter process to each process that wants to send a message to the counter process is inconvenient. Especially considering that ParallelEnum.map can (and in our case it will) indirectly call itself recursively. We register its PID under a certain name (alias) and will send messages using an alias. The listing below shows what will happen when ParallelEnum.map is called - if the process under the name of the counter process is not registered, start it and register it. I use if instead of case to emphasize that the result that this expression returns is not important in this case, and the expression is executed solely for the side-effect. Note also that spawn is used here instead of spawn_link. This is no coincidence. The thing is, that initially we made no assumptions about where, when, and by whom the ParallelEnum.map/2 function will be used. If somewhere in Erlang VM two ParallelEnum.map/2 functions are simultaneously executed, and one of them throws an exception for some reason, then the counter process will also fall, creating obvious prerequisites for unpredictable behavior and for “healthy” a process that just wasn’t fortunate enough to perform the function ParallelEnum.map/2 at the moment. That is why the counter process should not be linked to any other process. Having created clear prerequisites for unpredictable behavior and for a “healthy” process, which simply was not lucky enough to perform the function ParallelEnum.map/2 at the moment. That is why the counter process should not be linked to any other process. Having created clear prerequisites for unpredictable behavior and for a “healthy” process, which simply was not lucky enough to perform the function ParallelEnum.map/2 at the moment. That is why the counter process should not be linked to any other process.

	def map lst, func, limit \\ 2 do
		if (:erlang.whereis(@controller) == :undefined ) do
			:erlang.register( @controller,
			spawn(ParallelEnum, :parallel_enum_control_system, [1]) )
		end
		Enum.map(lst, &(try_make_child(&1, func, limit)))
			|> Enum.map( &collect_results/1 )
	end

After the if-expression in the body of the ParallelEnum.map/2 function, there is a classic map-reduce (for some irony, formally, map-map is here, but do not rush to conclusions). So, according to Wikipedia, this pattern consists of two steps.

Map Step


At the Map step, we check the number of running processes related to ParallelEnum according to the counter process. If the specified limit of the number of processes is not exceeded, we create a child process, pass it our PID (so that it can return the results to us), as well as a function with arguments that the workflow should execute. If the limit is exceeded, the parent process executes the expression on its own.

A few words about why we use the IntermediateResult structure. If there were no limit on the number of processes, we could simply collect a list from the PID of the child processes, and then wait in turn for answers with the results from them. But due to the restriction, in some cases the parent process will have to do the work itself, and this structure will help us in the reduce step to understand whether to expect results from the child process.

	defmodule IntermediateResult do
		defstruct child_pid: nil, my_own_result: nil
	end
	defp try_make_child(arg, func, limit) do
		case  (get_number_of_processes < limit) do
			false ->
				%IntermediateResult{child_pid: nil,
									my_own_result: func.(arg)} # in this case do work yourself haha 
			true -> 
				%IntermediateResult{child_pid: spawn_link(ParallelEnum, :worker, [self, func, arg]),
									my_own_result: nil} 
		end
	end
	defp get_number_of_processes do
		send @controller, %{ from: self, query: :get_number }
		receive do
			num when is_integer(num) -> num
		end
	end


The working process


There is absolutely nothing complicated: immediately after starting, we send the increment signal to the counter, we perform the function, sending the results to the spawned process, and before we finish, we send the decrement signal to the counter.

	def worker(daddy, func, arg) do
		send @controller, :increment
		send daddy, %{ from: self, result: func.(arg)}
		send @controller, :decrement
	end


Reduce Step


Here, too, everything is pretty transparent. The IntermediateResult structure obtained after the map step unambiguously shows what needs to be done in the reduce step - take the finished result (in case the parent process did the work itself), or wait for the message with the result from the child process.

	defp collect_results( %IntermediateResult{child_pid: nil, my_own_result: result}) do
		result
	end
	defp collect_results( %IntermediateResult{child_pid: pid, my_own_result: nil}) do
		receive do
			%{ from: incoming_pid, result: result} when (incoming_pid == pid) -> result
		end
	end


Now it remains to replace the Enum.map function with the ParallelEnum.map function, for example, in the game function, and the job is done. The final version of the code can be seen here .

Performance tests


So, the “Euler horse” problem is solved and the solution is optimized. Now everything works quickly and loads all processor cores to the fullest.

image

Time for tests. During the discussion of parallel optimization, almost nothing was said about exactly what should be the limitation of the number of processes for a given task. We will slightly modify our functions from the Horse.Solution module in order to be able to uniquely set the required number of processes and the initial position of the horse (for definiteness). And we will test the execution time of the Horse.Solution.init function for a 5x5 board, an initial position of 1.1 and different values ​​of the maximum number of processes using this function:

	def test_of_performance do
		Enum.each( 1..25, fn(num) -> test_of_performance_process(num) end )
		Enum.each( [50, 75, 100, 150, 200, 250, 500, 1000], 
			fn(num) -> test_of_performance_process(num) end )
		# to test this, add +P 100000000 flag when starting iex
		Enum.each( [10000, 50000, 100000, 500000, 1000000, 5000000, 10000000], 
			fn(num) -> test_of_performance_process(num) end )
	end
	defp test_of_performance_process(num) do
		{res, _} = :timer.tc( fn() -> init(5, num, %Position{}) end )
		File.write "./test_results", "#{num} #{res}\n", [:append]
	end


Measurements showed a minimum of time (maximum productivity) on the number of work processes 24.

image

Why so much


After all, there are much fewer cores on our local machine. Because Erlang VM processes are not OS processes in the usual sense of the word. It is not even threads. The vitrutual machine fully encapsulates them in itself, and evenly distributes the load across the processor cores (if possible).

Why so few


Erlang VM processes cost very few resources, but they do. With an increase in the number of processes, the total overhead costs also increase, moreover, evenly distributing the load on the processor cores at around 24 processes, the virtual machine cannot "distribute the load even more evenly" - here it rests on the physical limitations of the real processor.

In our particular case, it is still worth remembering about the counter process. When the parent process decides whether to create a child process or do the work itself, it asks the counting process the number of already running processes. Here he needs to not only send a message to the counter, but also wait for an answer from him. The process is one counter. Hundreds of thousands of work processes. I think everything is clear here.
Why productivity started to rise again after marking 1,000,000 processes is a mystery to me.

Conclusion


Erlang is a unique phenomenon in the world of multi-threaded programming. In 1987, when there was not even Java yet, and I could only dream about simple multi-threaded programming in C ++, Ericsson developers already wrote fault-tolerant programs for use in the telecommunications industry. Erlang language and its virtual machine were created for exclusively utilitarian purposes - to solve specific telecom tasks; over the years of its existence, the language has evolved on real tasks (unlike, for example, Haskell). In the process of development, it has “grown” with many well-debugged and documented libraries, the OTP (Open Telecom Platform) framework has appeared. OTP for Erlang is something more than, say, Qt for C ++. Remember the send and receive expressions? Erlang VM actually only has asynchronous messaging between processes. It is not very convenient to write such a low-level code in large projects, OTP has tools that encapsulate low-level details and provide a very simple, convenient and intuitive interface - there is not only asynchronous exchange, but for example synchronous communication, error handling tools / falls and much more. In this article, I did not use OTP just because it is a topic for a separate large article. Erlang VM is unmatched in stability and fault tolerance - remember, when we tested performance for a different number of processes, the last value was 10,000,000! At the same time, performance, of course, fell compared to 24, but in a completely non-fatal way. Yes, the arithmetic in Erlang VM is "a bit tight", but as they say, if you want fast arithmetic - Fortran is in your hands. With this figure I just wanted to say that for Erlang VM you can write programs in which you need to simultaneously maintainreally a lot of processes. As an example, a web server or something similar immediately comes to mind. In addition, the performance of Erlang VM is not bad, in principle it is soft-realtime. In general, Erlang / Elixir + OTP can become your indispensable assistant for writing stable, distributed and very reliable programs.

UPD: Lisp version



A couple of days ago I decided to join Lisp and JVM at the same time, and rewrote this task in Clojure. Actually, one can argue endlessly about the elegance / readability of the code, but the fact that the speed of work here is also quite acceptable.



The code is here .
For those who still want to understand where Elixir actually grows their legs - I advise you to get acquainted with some dialect of Lisp, really a lot falls into place.

Also popular now: