Matrax library - use :atomics as a matrix

preciz · October 21, 2019, 1:28pm

The main idea of this library is to use :atomics as a matrix with all its benefits preserved.

iex> matrax = Matrax.new(7, 4, seed_fun: fn _, {row, col} -> row + col end)
iex> matrax |> Matrax.put({0, 0}, 1989) # atomics are mutable
iex> matrax |> Matrax.to_list_of_lists()
[
    [1989, 1, 2, 3],
    [1, 2, 3, 4],
    [2, 3, 4, 5],
    [3, 4, 5, 6],
    [4, 5, 6, 7],
    [5, 6, 7, 8],
    [6, 7, 8, 9]
]

All :atomics functions are wrapped and a few matrix specific functions are provided:

API summary

See https://hexdocs.pm/matrax for full documentation.

Matrax.new/2 - Create new matrix.
Matrax.get/2 - Returns the integer at the given position.
Matrax.put/3 - Puts the given integer into the given position.
Matrax.add/3 - Adds the given increment to the value at given position atomically.
Matrax.add_get/3 - Adds the given increment to the value at given position atomically and returns result.
Matrax.sub/3 - Subtracts the given decrement to the value at given position atomically.
Matrax.sub_get/3 - Subtracts the given decrement to the value at given position atomically and returns result.
Matrax.exchange/3 - Exchanges the given integer at the given position atomically.
Matrax.compare_exchange/4 - Compares & exchanges the given integer at the given position atomically.
Matrax.index_to_position/2 - Converts the given atomics index to position tuple.
Matrax.position_to_index/2 - Converts the given position tuple to atomics index.
Matrax.min/1 - Returns smallest integer in matrix.
Matrax.max/1 - Returns largest integer in matrix.
Matrax.sum/1 - Returns sum of integers in matrix.
Matrax.member?/2 - Checks if value exists within matrix.
Matrax.apply/2 - Applies the given function to all elements of matrix.
Matrax.to_list/1 - Converts matrix to a flat list.
Matrax.to_list_of_lists/1 - Converts matrix to list of lists.
Matrax.row_to_list/2 - Converts row at given index of matrix to list.
Matrax.column_to_list/2 - Converts column at given index of matrix to list.
Matrax.transpose/1 - Transposes the given matrix. (access path modification only)
Matrax.copy/1 - Returns a copy of the matrix with a new atomics reference. Can be used to finish transpose.
Matrax.submatrix/3 - Returns a new submatrix. Creates new atomics and copies values over.

GitHub: https://github.com/preciz/matrax

What is the use case?
An example use case is when you need concurrent access to a matrix of integers / bitmasks.
(my use case was a constraint solving algorithm)

:atomics "utilizes only atomic hardware instructions without any software level locking, which makes it very efficient for concurrent access. " - Erlang :atomics documentation.

Feedback is welcome.

(I would like to also mention that I’m looking for employment, if you are an employer or your company is hiring I would be happy to talk with you. PM me. Thank you!)

axelson · October 21, 2019, 1:55pm

Looks like a neat library! Could you do a high-level comparison between Matrax and Matrex (https://hex.pm/packages/matrex)? Since the names are so similar I’m going to have a hard time keeping them straight! (and good luck on your job search!)

preciz · October 21, 2019, 2:16pm

I love Matrex that is why I gave a similar name
The A in MatrAx is for :atomics.

MatrEx uses 4 byte floats.
MatrAx uses 64 bit integers and a mutable data structure under the hood called :atomics.

MatrEx optionally(?) depends on native code (NIFs).
MatrAx only requires Elixir.

MatrEx is more feature rich.
MatrAx only implements features that makes sense with :atomics
(at least that is the goal now).

MatraAx and MatrEx serve a different purpose and are not really similar,
apart from the fact that they are matrix libraries.

MatrAx use case example:
Let’s say you have 10x10 board with 25 possible states represented as bitmasks.
You could manipulate the states of the board’s cells from multiple processes concurrently and
only ping the processes that have the reference to update a view based on that.
I’m not sure if I’m clear but I have actually done something like this and :atomics were of course
way faster than lists.

axelson · October 21, 2019, 2:19pm

Thanks, that’s very helpful!

ondrej-tucek · October 21, 2019, 2:19pm

and also this comparison could be for matrix_reloaded (https://hex.pm/packages/matrix_reloaded)

preciz · October 21, 2019, 7:40pm

The matrix_reloaded library explicitly says that “…if you need make fast operations on matrices, please use Matrex library.”

I have did a few benchmarks ignoring the above warning, and Matrax is faster.
Matrax is still missing a lot of matrix operations found in matrix_reloaded, however if it is this much faster I will implement them in the next days (the ones which makes sense with :atomics).

Keep in mind however that this is not the best benchmark.
One of the benefits of Matrax is concurrency which is not benchmarked here.
(transpose is 14k times faster because Matrax doesn’t move the data, only modifies the access path)

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

Benchmarking matrax_put...
Benchmarking mr_update_element...

Name                        ips        average  deviation         median         99th %
matrax_put              83.02 K      0.0120 ms   ±357.54%     0.00946 ms      0.0177 ms
mr_update_element      0.0858 K       11.65 ms     ±2.96%       11.55 ms       13.08 ms

Comparison: 
matrax_put              83.02 K
mr_update_element      0.0858 K - 967.11x slower +11.64 ms

Benchmarking matrax_get...
Benchmarking mr_get_element...

Name                     ips        average  deviation         median         99th %
matrax_get           74.23 K      0.0135 ms   ±287.15%      0.0113 ms      0.0195 ms
mr_get_element      0.0920 K       10.87 ms     ±2.56%       10.77 ms       11.96 ms

Comparison: 
matrax_get           74.23 K
mr_get_element      0.0920 K - 807.29x slower +10.86 ms

Benchmarking matrax_transpose...
Benchmarking mr_transpose...

Name                       ips        average  deviation         median         99th %
matrax_transpose        6.96 M     0.00014 ms ±23433.64%     0.00005 ms     0.00070 ms
mr_transpose         0.00049 M        2.05 ms     ±6.64%        2.03 ms        2.43 ms

Comparison: 
matrax_transpose        6.96 M
mr_transpose         0.00049 M - 14252.96x slower +2.05 ms

preciz · October 29, 2019, 9:05pm

I have greatly extended the functions:
https://hexdocs.pm/matrax/Matrax.html#functions

I have also greatly improved performance and fixed a few bugs.

For matrix transformations like transpose or submatrix I chose to do access path only modifications
(that you can finish by calling copy/1).
I believe this is superior to always creating a new :atomics and copying the values over. Also this way multiple transformations can be chained together without expensive copy like:

m = Matrax.new(5, 5) |> Matrax.submatrix(1..2, 1..2) |> Matrax.flip_ud()

One process can work with the same matrix that another process uses as a submatrix since :atomics are mutable.

iex(8)> (m = Matrax.new(5, 5)) |> Matrax.to_list_of_lists()
[
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0]
]
iex(9)> m |> Matrax.diagonal() |> Matrax.apply(fn _ -> 1 end)
:ok
iex(10)> m |> Matrax.to_list_of_lists()                       
[
  [1, 0, 0, 0, 0],
  [0, 1, 0, 0, 0],
  [0, 0, 1, 0, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 0, 1]
]

What do you think about this solution of access path only modification for shared mutable matrices based on atomics?

ondrej-tucek · October 31, 2019, 7:40am

Somehow I overlooked your post. Thanks for your comparison. Maybe it would be worthwhile to rewrite matrix_reloaded with Streams instead of Enum…

preciz · October 31, 2019, 9:41am

rewrite matrix_reloaded with Streams instead of Enum

I think that would actually hurt performance or wouldn’t make a huge difference.
Since Matrax is limited to 64 bit integers because of :atomics maybe
a better change would be to support things Matrax can’t because of this limitation.