Nemo.gf2 methods vs current QuantumClifford.gf2 methods

[Fe-r-oz]

Nemo gf2 methods vs QuantumClifford gf2 methods

Methods considered:

1. Nemo: .is_invertible, .echelon_form, .rref
2. QuantumClifford: .gf2_isinvertible and .gf2_gausselim!

This small study aims to check the following:

QuantumClifford.jl/src/QuantumClifford.jl

Line 1019 in 10bb4b6

# TODO check whether Nemo is faster in doing this and other gf2 methods.

julia> using QuantumClifford.ECC: Gottesman, parity_checks

julia> using QuantumClifford: stab_to_gf2, gf2_gausselim!

julia> using Nemo

julia> using BenchmarkTools

julia> h10 = stab_to_gf2(parity_checks(Gottesman(12)))
14×8192 Matrix{Bool}:
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  …  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
 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  0     1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
 1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0     1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
 1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0     1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
 1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0     1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
 1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  …  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
 1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0     1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
 1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0     1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
 1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0     1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
 1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0     0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
 1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  0  1  0  1  0  1  0  1  0  1  …  0  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1
 1  0  1  0  1  0  1  0  0  1  0  1  0  1  0  1  1  0  1  0  1  0  1  0  0  1     1  0  0  0  0  1  1  1  1  0  0  0  0  1  1  1  1  0  0  0  0  1  1  1  1
 1  0  1  0  0  1  0  1  1  0  1  0  0  1  0  1  1  0  1  0  0  1  0  1  1  0     1  0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1
 1  0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1  0     1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1

julia> @benchmark is_invertible(matrix(GF(2), h10))
BenchmarkTools.Trial: 155 samples with 1 evaluation.
 Range (min … max):  14.129 ms … 74.570 ms  ┊ GC (min … max):  0.00% … 37.32%
 Time  (median):     14.909 ms              ┊ GC (median):     0.00%
 Time  (mean ± σ):   32.670 ms ± 24.542 ms  ┊ GC (mean ± σ):  26.90% ± 18.25%

  █▂                                                    ▄▄     
  ██▇▄▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄██▆▆▅ ▄
  14.1 ms      Histogram: log(frequency) by time      69.3 ms <

 Memory estimate: 15.75 MiB, allocs estimate: 458760.

julia> @benchmark gf2_isinvertible(h10)
BenchmarkTools.Trial: 5670 samples with 1 evaluation.
 Range (min … max):  799.970 μs …   4.015 ms  ┊ GC (min … max): 0.00% … 78.13%
 Time  (median):     822.635 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   879.655 μs ± 279.623 μs  ┊ GC (mean ± σ):  4.44% ±  9.67%

  █▇▅▃▂▁                                                        ▁
  ██████▇▅▄▁▁▃▃▃▁▁▃▃▁▁▁▃▁▁▁▁▁▁▃▃▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▆██ █
  800 μs        Histogram: log(frequency) by time       2.73 ms <

 Memory estimate: 941.30 KiB, allocs estimate: 4169.

julia> @benchmark echelon_form(matrix(GF(2), h10))
BenchmarkTools.Trial: 143 samples with 1 evaluation.
 Range (min … max):  17.679 ms … 66.786 ms  ┊ GC (min … max):  0.00% … 38.91%
 Time  (median):     18.401 ms              ┊ GC (median):     0.00%
 Time  (mean ± σ):   34.978 ms ± 21.980 ms  ┊ GC (mean ± σ):  25.14% ± 18.12%

  █                                                    ▄  ▃    
  ██▄▅▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄▄█▇▅█▄▆ ▄
  17.7 ms      Histogram: log(frequency) by time      66.7 ms <

 Memory estimate: 17.56 MiB, allocs estimate: 458773.

julia> @benchmark gf2_gausselim!(h10)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  225.321 μs …   2.314 ms  ┊ GC (min … max): 0.00% … 87.28%
 Time  (median):     229.019 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   244.413 μs ± 125.313 μs  ┊ GC (mean ± σ):  3.79% ±  6.50%

  ▆▇█▆▂    ▁▁          ▁▃▂▂                                     ▁
  █████▆▄▆▇███████▇▆▆▆██████▇▆▆▆▅▆▆▆▇▇▇▆▆▅▅▄▅▅▇▇▇▆▆▅▅▄▅▄▅▄▄▅▄▄▄ █
  225 μs        Histogram: log(frequency) by time        323 μs <

 Memory estimate: 256.06 KiB, allocs estimate: 4097.

julia> h = [1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1;
             1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0;
             1  1  1  1  0  0  0  0  1  1  1  1  0  0  0  0;
             1  1  0  0  1  1  0  0  1  1  0  0  1  1  0  0;
             1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0;
             1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0;
             1  1  0  0  1  1  0  0  0  0  0  0  0  0  0  0;
             1  0  1  0  1  0  1  0  0  0  0  0  0  0  0  0;
             1  1  0  0  0  0  0  0  1  1  0  0  0  0  0  0;
             1  0  1  0  0  0  0  0  1  0  1  0  0  0  0  0;
             1  0  0  0  1  0  0  0  1  0  0  0  1  0  0  0];

julia> @benchmark is_invertible(matrix(GF(2), h))
BenchmarkTools.Trial: 10000 samples with 4 evaluations.
 Range (min … max):   7.706 μs …  1.744 ms  ┊ GC (min … max):  0.00% … 75.04%
 Time  (median):      8.015 μs              ┊ GC (median):     0.00%
 Time  (mean ± σ):   10.980 μs ± 60.483 μs  ┊ GC (mean ± σ):  15.19% ±  2.74%

  ▅█▆▂▃▃▂▂                                  ▁▁▂               ▁
  █████████▆▇▇▇▆▇▆▆▆▆▆███▇▅▅▅▅▇▇▇▇▅▄▅▄▆▆▆▅▆▇████▆▅▅▆▇▄▄▄▄▅▃▄▄ █
  7.71 μs      Histogram: log(frequency) by time      17.5 μs <

 Memory estimate: 15.46 KiB, allocs estimate: 184.

julia> @benchmark gf2_isinvertible(Matrix{Bool}(h))
BenchmarkTools.Trial: 10000 samples with 4 evaluations.
 Range (min … max):  7.320 μs … 598.714 μs  ┊ GC (min … max): 0.00% … 97.34%
 Time  (median):     7.590 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   8.710 μs ±  16.422 μs  ┊ GC (mean ± σ):  5.57% ±  2.93%

  ▅█▇▄▂▁      ▃▃▁                  ▁▁  ▁▁                     ▁
  ███████▇▆▇▇████▇▆▆▅▆▆▇▅▆▇██▆▅██▆▅███▇██▇▆▆▇▆▆▅▆▅▅▅▅▄▄▅▄▅▃▃▃ █
  7.32 μs      Histogram: log(frequency) by time      15.5 μs <

 Memory estimate: 10.19 KiB, allocs estimate: 129.

julia> gf2_gausselim!(Matrix{Bool}(h))
11×16 Matrix{Bool}:
 1  0  0  0  0  0  0  1  0  0  0  1  0  1  1  1
 0  1  0  0  0  0  0  1  0  0  0  1  0  1  0  0
 0  0  1  0  0  0  0  1  0  0  0  1  0  0  1  0
 0  0  0  1  0  0  0  1  0  0  0  1  0  0  0  1
 0  0  0  0  1  0  0  1  0  0  0  0  0  1  1  0
 0  0  0  0  0  1  0  1  0  0  0  0  0  1  0  1
 0  0  0  0  0  0  1  1  0  0  0  0  0  0  1  1
 0  0  0  0  0  0  0  0  1  0  0  1  0  1  1  0
 0  0  0  0  0  0  0  0  0  1  0  1  0  1  0  1
 0  0  0  0  0  0  0  0  0  0  1  1  0  0  1  1
 0  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1

julia> echelon_form(matrix(GF(2), h))
[1   0   0   0   0   0   0   1   0   0   0   1   0   1   1   1]
[0   1   0   0   0   0   0   1   0   0   0   1   0   1   0   0]
[0   0   1   0   0   0   0   1   0   0   0   1   0   0   1   0]
[0   0   0   1   0   0   0   1   0   0   0   1   0   0   0   1]
[0   0   0   0   1   0   0   1   0   0   0   0   0   1   1   0]
[0   0   0   0   0   1   0   1   0   0   0   0   0   1   0   1]
[0   0   0   0   0   0   1   1   0   0   0   0   0   0   1   1]
[0   0   0   0   0   0   0   0   1   0   0   1   0   1   1   0]
[0   0   0   0   0   0   0   0   0   1   0   1   0   1   0   1]
[0   0   0   0   0   0   0   0   0   0   1   1   0   0   1   1]
[0   0   0   0   0   0   0   0   0   0   0   0   1   1   1   1]

julia> @benchmark echelon_form(matrix(GF(2), h))
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  11.483 μs …   6.888 ms  ┊ GC (min … max):  0.00% … 72.15%
 Time  (median):     12.124 μs               ┊ GC (median):     0.00%
 Time  (mean ± σ):   15.835 μs ± 128.008 μs  ┊ GC (mean ± σ):  11.58% ±  1.43%

  ▄█▇▅▄▂▁▁          ▁▂▂   ▁▂▂     ▁                            ▂
  █████████▇█▇▇▇▇▇▆▇████▆▇████▇▅▄▇██▆▇▅▅▃▁▆▇▇▅▄▅▁▅▃▁▃▃▁▅▅▄▁▄▄▇ █
  11.5 μs       Histogram: log(frequency) by time      30.3 μs <

 Memory estimate: 19.41 KiB, allocs estimate: 197.

julia> @benchmark gf2_gausselim!(Matrix{Bool}(h))
BenchmarkTools.Trial: 10000 samples with 4 evaluations.
 Range (min … max):  7.332 μs … 854.914 μs  ┊ GC (min … max): 0.00% … 98.36%
 Time  (median):     7.585 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   8.271 μs ±  16.629 μs  ┊ GC (mean ± σ):  5.55% ±  2.77%

  ▄▇█▇▄▁▁▁   ▁▁                                               ▂
  █████████████▇█▇▇▅▆▆▅▆▄▅▆▄▅▁▄▅▄▆▇▇█▇▆▅▅▅▄▄▃▄▅▆▇▇▆▇▆▆▄▄▅▅▅▆▆ █
  7.33 μs      Histogram: log(frequency) by time      13.4 μs <

 Memory estimate: 9.95 KiB, allocs estimate: 128.

julia> @benchmark echelon_form(matrix(GF(2), Matrix{Bool}(h)))

BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  25.584 μs … 47.041 ms  ┊ GC (min … max):  0.00% … 54.18%
 Time  (median):     27.273 μs              ┊ GC (median):     0.00%
 Time  (mean ± σ):   57.359 μs ±  1.121 ms  ┊ GC (mean ± σ):  25.68% ±  1.31%

   ▆█▃                                                         
  ▄███▅▃▃▃▂▂▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▁▁▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  25.6 μs         Histogram: frequency by time        53.9 μs <

 Memory estimate: 29.27 KiB, allocs estimate: 726.

julia> @benchmark echelon_form(matrix(GF(2), Matrix{Bool}(h)))
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  25.658 μs … 46.722 ms  ┊ GC (min … max):  0.00% … 54.86%
 Time  (median):     27.425 μs              ┊ GC (median):     0.00%
 Time  (mean ± σ):   57.852 μs ±  1.134 ms  ┊ GC (mean ± σ):  25.93% ±  1.32%

   ▅█▄                                                         
  ▄███▆▃▃▃▂▂▃▃▂▂▃▂▂▂▂▂▁▂▂▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  25.7 μs         Histogram: frequency by time        53.4 μs <

 Memory estimate: 29.27 KiB, allocs estimate: 726.

rref and echelon form have similar performances.

julia> @benchmark rref(matrix(GF(2), Matrix{Bool}(h)))

BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  25.707 μs … 49.377 ms  ┊ GC (min … max):  0.00% … 51.27%
 Time  (median):     27.668 μs              ┊ GC (median):     0.00%
 Time  (mean ± σ):   58.582 μs ±  1.157 ms  ┊ GC (mean ± σ):  25.15% ±  1.27%

   ██▁                                                         
  ▆███▆▆▅▄▃▃▄▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▂▂▂▂▂▂▂▂▂▂▂▂ ▃
  25.7 μs         Histogram: frequency by time        55.9 μs <

 Memory estimate: 29.30 KiB, allocs estimate: 727.


julia> @benchmark rref(matrix(GF(2), h))
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  11.609 μs …   6.374 ms  ┊ GC (min … max):  0.00% … 72.19%
 Time  (median):     12.226 μs               ┊ GC (median):     0.00%
 Time  (mean ± σ):   15.677 μs ± 126.268 μs  ┊ GC (mean ± σ):  11.45% ±  1.42%

  ▃██▆▄▃▁              ▁▁    ▁▂▁                               ▂
  ██████████▇▇▇▆█▇▇▇▆▅████▅▅▅█████▆▆▄▆▇█▇▆▄▄▃▄▄▆▇▇▆▆▅▁▄▁▁▁▁▁▄▄ █
  11.6 μs       Histogram: log(frequency) by time      28.5 μs <

 Memory estimate: 19.45 KiB, allocs estimate: 198.

Note: a small decrease in time is observed depending whether type is Int or Bool but regardless, overall, it seems that QC methods are faster than Nemos

In summary, this is somewhat surprising. Maybe this small study is not as comprehensive as it should be. In order to further validate this, maybe testing on further huge matrices of various types along with other gf2 methods could be helpful.

[Krastanov]

You have (matrix(GF(2), h). You are measuring times to convert from binary matrix to a nemo matix. I do not know if this is the main source of difference -- it is possible also that nemo needs to be much more general, given that it works with arbitrary fields.

[Fe-r-oz]

Thanks for pointing that out. Yes, Indeed, I have used GF(2) in the matrix, but it could be ZZ, QQ, etc. so it's more general.

[Krastanov]

also, at least some of the operations you are benchmarking are in-place operations. The benchmark runs the function many times, but only the first time the function does anything of interesting, so your results are extremely skewed. You should set evals=1 and use setup=(argument=copy(original_argument))

[Fe-r-oz]

Thanks. I will take this into account. I am not that familiar with BenchmarkTools and only some basic stuff about it.

[Fe-r-oz]

For larger matrices, it seems Nemo is much faster when using is_invertible! I was doing it wrong as correctly pointed out by _"You are measuring times to convert from binary matrix to a nemo matix."

In the larger context, as Nemo matrices are for arbitray fields, I am not fully sure whether these results are that much helpful when considering gaussion elimination methods. As for Nemo.is_invertible which is faster for larger values, maybe you will find it interesting.

I hope this is better and less skewed at least.

is_invertible results

julia> using QuantumClifford

julia> using QuantumClifford.ECC: Gottesman, parity_checks

julia> using QuantumClifford: stab_to_gf2, gf2_gausselim!

julia> using Nemo

julia> using BenchmarkTools

julia> h10 = stab_to_gf2(parity_checks(Gottesman(12)));

julia> h10_nemo = matrix(GF(2), h10);

julia> @benchmark gf2_isinvertible(h10_copy) evals=1 setup=(h10_copy=h10)
BenchmarkTools.Trial: 5653 samples with 1 evaluation.
 Range (min … max):  792.570 μs …   4.472 ms  ┊ GC (min … max): 0.00% … 76.90%
 Time  (median):     813.007 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   877.533 μs ± 275.435 μs  ┊ GC (mean ± σ):  4.14% ±  9.35%

  █▆▅▄▂▁       ▁                                                ▁
  ███████▇▇▇▆▅▆██▇▆▅▅▃▅▄▃▄▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▅▆▇█ █
  793 μs        Histogram: log(frequency) by time        2.5 ms <

 Memory estimate: 941.30 KiB, allocs estimate: 4169.

# There was no copy for `FqMatrix` in Nemo.
julia> @benchmark is_invertible($h10_nemo) evals=1 setup=(h10_nemo_copy=h10_nemo)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  51.000 ns …  18.050 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     70.000 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   68.130 ns ± 236.914 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

      ▂ ▇ ▅                              █ █ ▁                  
  ▂▁▃▁█▁█▁█▁█▁▅▁▃▁▃▁▂▁▂▁▂▁▂▁▂▁▂▁▁▂▁▂▁▂▁▇▁█▁█▁█▁▅▁▅▁▆▁▅▁▄▁▃▁▃▁▃ ▃
  51 ns           Histogram: frequency by time           80 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.


julia> h16 = stab_to_gf2(parity_checks(Gottesman(16)));

julia> h16_nemo = matrix(GF(2), h16);

julia> @benchmark gf2_isinvertible(h16_copy) evals=1 setup=(h16_copy=h16)
BenchmarkTools.Trial: 247 samples with 1 evaluation.
 Range (min … max):  17.897 ms … 29.688 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     19.670 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):   20.113 ms ±  1.765 ms  ┊ GC (mean ± σ):  2.67% ± 3.17%

   ▃█▅ ▂▇▇▄▁█▅▅▄█ ▁     ▃      ▂                               
  ▄███▅██████████▆█▅▅█▇▅██▇▇▄▅▃██▄▁▃▃▄▅▃▃▃▁▁▁▁▃▁▁▃▃▁▄▁▁▁▃▁▁▁▃ ▄
  17.9 ms         Histogram: frequency by time        26.1 ms <

 Memory estimate: 18.01 MiB, allocs estimate: 65727.

julia> @benchmark is_invertible($h16_nemo) evals=1 setup=(h16_nemo_copy=h16_nemo)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  53.000 ns …  1.242 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     60.000 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   63.215 ns ± 14.301 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

         ▃ █ ▆  ▂ ▅ ▃                              ▁           
  ▂▁▅▁█▁▁█▁█▁█▁▁█▁█▁█▁▁▅▁▂▁▂▁▁▂▁▂▁▁▂▁▂▁▃▁▁▃▁▅▁▆▁▁█▁█▁█▁▁▅▁▄▁▂ ▃
  53 ns           Histogram: frequency by time          78 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.


julia> h20 = stab_to_gf2(parity_checks(Gottesman(20)));

julia> h20_nemo = matrix(GF(2), h20);


julia> @benchmark gf2_isinvertible(h20_copy) evals=1 setup=(h20_copy=h20)
BenchmarkTools.Trial: 5 samples with 1 evaluation.
 Range (min … max):  812.376 ms … 967.500 ms  ┊ GC (min … max): 1.25% … 2.92%
 Time  (median):     854.201 ms               ┊ GC (median):    1.35%
 Time  (mean ± σ):   887.838 ms ±  67.710 ms  ┊ GC (mean ± σ):  1.88% ± 1.02%

  ▁               █                                     ▁     ▁  
  █▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁█ ▁
  812 ms           Histogram: frequency by time          967 ms <

 Memory estimate: 344.01 MiB, allocs estimate: 1048815.

julia> @benchmark is_invertible($h20_nemo) evals=1 setup=(h20_nemo_copy=h20_nemo)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  44.000 ns …  1.778 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     51.000 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   51.994 ns ± 17.766 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

            ▁ ▄  █ ▇  ▆  ▅ ▂                                   
  ▂▁▂▁▁▃▁▅▁▁█▁█▁▁█▁█▁▁█▁▁█▁█▁▁▅▁▃▁▁▂▁▂▁▁▂▁▁▂▁▂▁▁▂▁▃▁▁▃▁▂▁▁▂▁▂ ▃
  44 ns           Histogram: frequency by time          67 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.



julia> h = [1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1;
                    1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0;
                    1  1  1  1  0  0  0  0  1  1  1  1  0  0  0  0;
                    1  1  0  0  1  1  0  0  1  1  0  0  1  1  0  0;
                    1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0;
                    1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0;
                    1  1  0  0  1  1  0  0  0  0  0  0  0  0  0  0;
                    1  0  1  0  1  0  1  0  0  0  0  0  0  0  0  0;
                    1  1  0  0  0  0  0  0  1  1  0  0  0  0  0  0;
                    1  0  1  0  0  0  0  0  1  0  1  0  0  0  0  0;
                    1  0  0  0  1  0  0  0  1  0  0  0  1  0  0  0];

julia> h = Matrix{Bool}(h);

julia> h_nemo = matrix(GF(2), h);

julia> @benchmark gf2_isinvertible(h_copy) evals=1 setup=(h_copy=h)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):   6.750 μs … 145.538 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     10.640 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   10.973 μs ±   4.108 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

  ▂         ▆█                                                  
  █▇▄▂▂▂▂▂▂▂██▅▃▂▅█▇▄▃▂▂▃▄▃▂▂▂▂▂▂▂▂▂▂▁▁▁▂▂▁▂▁▁▁▁▂▂▂▂▂▂▂▂▂▂▂▂▂▂ ▃
  6.75 μs         Histogram: frequency by time         27.2 μs <

 Memory estimate: 9.95 KiB, allocs estimate: 128.

julia> @benchmark is_invertible($h_nemo) evals=1 setup=(h_nemo_copy=h_nemo)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  49.000 ns …  1.718 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     54.000 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   53.639 ns ± 16.922 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

               ▁     ▂      ▄     █      ▆                     
  ▃▁▁▁▁▁▇▁▁▁▁▁▁█▁▁▁▁▁█▁▁▁▁▁▁█▁▁▁▁▁█▁▁▁▁▁▁█▁▁▁▁▁▇▁▁▁▁▁▁▃▁▁▁▁▁▂ ▃
  49 ns           Histogram: frequency by time          58 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

gaussian elimination results

For larger matrices, it seems Nemo seems slower than gf2_gausselim!!.

julia> @benchmark gf2_gausselim!(h10_copy) evals=1 setup=(h10_copy=h10)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  223.424 μs … 50.118 ms  ┊ GC (min … max):  0.00% … 99.27%
 Time  (median):     353.022 μs              ┊ GC (median):     0.00%
 Time  (mean ± σ):   398.474 μs ±  1.557 ms  ┊ GC (mean ± σ):  12.94% ±  3.29%

  ▇ ▅▃▁▂▁            █▇▆▅▆▅▄▃▂▃▂▂▂▂▁▁▁▁▁                       ▂
  ████████████▇▇▇▇▅▅▆████████████████████▇█▇▇▇▇▇▇▆▆▇▆▆▆▆▄▃▅▅▆▅ █
  223 μs        Histogram: log(frequency) by time       610 μs <

 Memory estimate: 256.06 KiB, allocs estimate: 4097.

julia> @benchmark echelon_form(h10_copy) evals=1 setup=(h10_copy=h10_nemo)
BenchmarkTools.Trial: 1246 samples with 1 evaluation.
 Range (min … max):  3.468 ms …  10.219 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     3.865 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   3.984 ms ± 482.350 μs  ┊ GC (mean ± σ):  0.12% ± 1.33%

   ▂█▃▁   ▄▅▁▁  ▁                                              
  ▅████▅▆▇█████▇█▇▆▇▅▇▅▆▆▆▅▄▅▄▄▄▃▃▃▃▃▃▂▃▃▃▃▃▃▃▃▃▃▂▁▂▂▂▂▂▁▃▂▂▂ ▄
  3.47 ms         Histogram: frequency by time        5.48 ms <

 Memory estimate: 1.81 MiB, allocs estimate: 13.

julia> @benchmark rref(h10_copy) evals=1 setup=(h10_copy=h10_nemo)
BenchmarkTools.Trial: 1333 samples with 1 evaluation.
 Range (min … max):  3.455 ms …   5.900 ms  ┊ GC (min … max): 0.00% … 30.49%
 Time  (median):     3.600 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   3.723 ms ± 284.341 μs  ┊ GC (mean ± σ):  0.11% ±  1.28%

    ▄▆▇█▄▂                                                     
  ▃▆██████▇▆▅▅▅▅▄▃▂▃▄▄▃▃▃▄▄▄▃▃▃▃▃▂▂▃▂▃▂▂▂▂▃▂▃▃▃▂▃▂▂▁▂▂▂▂▂▂▂▁▂ ▃
  3.46 ms         Histogram: frequency by time        4.69 ms <

 Memory estimate: 1.81 MiB, allocs estimate: 14.

julia> @benchmark gf2_gausselim!(h16_copy) evals=1 setup=(h16_copy=h16)
BenchmarkTools.Trial: 699 samples with 1 evaluation.
 Range (min … max):  4.229 ms … 56.067 ms  ┊ GC (min … max):  0.00% … 88.24%
 Time  (median):     6.529 ms              ┊ GC (median):     0.00%
 Time  (mean ± σ):   7.106 ms ±  5.990 ms  ┊ GC (mean ± σ):  11.07% ± 11.57%

  ▂ █▄                                                        
  █▃██▅▃▂▂▂▂▁▁▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▂▂▂ ▂
  4.23 ms        Histogram: frequency by time        50.5 ms <

 Memory estimate: 4.00 MiB, allocs estimate: 65537.

julia> @benchmark echelon_form(h16_copy) evals=1 setup=(h16_copy=h16_nemo)
BenchmarkTools.Trial: 52 samples with 1 evaluation.
 Range (min … max):  83.870 ms … 111.575 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     94.088 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   95.079 ms ±   7.856 ms  ┊ GC (mean ± σ):  0.09% ± 0.31%

    ▁▁ ▁   ▄     ▁ ▁   ▁▁▁▁           ▁    █                 ▄  
  ▆▁██▆█▆▆▆█▆▁▁▆▆█▆█▁▆▁████▁▆▆▆▆▁▆▆▆▁▁█▁▁▁▆█▁▁▁▆▁▁▁▁▁▁▁▆▁▁▆▁▁█ ▁
  83.9 ms         Histogram: frequency by time          111 ms <

 Memory estimate: 37.00 MiB, allocs estimate: 13.

julia> @benchmark rref(h16_copy) evals=1 setup=(h16_copy=h16_nemo)
BenchmarkTools.Trial: 50 samples with 1 evaluation.
 Range (min … max):  85.857 ms … 116.830 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     97.418 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   97.525 ms ±   8.261 ms  ┊ GC (mean ± σ):  0.10% ± 0.39%

    █ ▃  ▃    ▃█         ▃ ▃     ▃  ▃   █                    ▃  
  ▇▇█▇█▇▇█▇▇▇▁██▇▇▁▇▇▁▁▇▁█▇█▁▇▇▇▇█▁▇█▇▇▁█▇▁▁▁▁▇▁▇▁▁▁▁▁▁▁▁▁▁▁▇█ ▁
  85.9 ms         Histogram: frequency by time          117 ms <

 Memory estimate: 37.00 MiB, allocs estimate: 14.

julia> @benchmark gf2_gausselim!(h20_copy) evals=1 setup=(h20_copy=h20)
BenchmarkTools.Trial: 23 samples with 1 evaluation.
 Range (min … max):  136.749 ms … 241.984 ms  ┊ GC (min … max): 0.00% … 20.32%
 Time  (median):     166.531 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   174.322 ms ±  24.708 ms  ┊ GC (mean ± σ):  7.55% ± 11.18%

                ▁ ▄█                  ▁                          
  ▆▁▆▁▁▁▁▆▆▁▁▁▆▁█▁██▁▁▆▁▁▁▆▁▁▆▁▁▁▁▆▁▁▁█▆▁▁▁▁▁▁▁▆▁▁▁▁▁▁▁▁▁▁▁▁▁▁▆ ▁
  137 ms           Histogram: frequency by time          242 ms <

 Memory estimate: 64.00 MiB, allocs estimate: 1048577.

julia> @benchmark echelon_form(h20_copy) evals=1 setup=(h20_copy=h20_nemo)
BenchmarkTools.Trial: 2 samples with 1 evaluation.
 Range (min … max):  2.433 s …  2.441 s  ┊ GC (min … max): 0.06% … 0.99%
 Time  (median):     2.437 s             ┊ GC (median):    0.52%
 Time  (mean ± σ):   2.437 s ± 5.636 ms  ┊ GC (mean ± σ):  0.52% ± 0.66%

  █                                                      █  
  █▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
  2.43 s        Histogram: frequency by time        2.44 s <

 Memory estimate: 720.00 MiB, allocs estimate: 13.

julia> @benchmark rref(h20_copy) evals=1 setup=(h20_copy=h20_nemo)
BenchmarkTools.Trial: 2 samples with 1 evaluation.
 Range (min … max):  2.303 s …   2.326 s  ┊ GC (min … max): 0.64% … 0.01%
 Time  (median):     2.314 s              ┊ GC (median):    0.32%
 Time  (mean ± σ):   2.314 s ± 15.863 ms  ┊ GC (mean ± σ):  0.32% ± 0.45%

  █                                                       █  
  █▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
  2.3 s          Histogram: frequency by time        2.33 s <

 Memory estimate: 720.00 MiB, allocs estimate: 14.


julia> @benchmark echelon_form(h_copy) evals=1 setup=(h_copy=h_nemo)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  3.683 μs … 34.596 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     3.900 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   4.723 μs ±  1.567 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%
  ▇█▆▄▂▁           ▄▆▆▅▃▁▁                ▂▂                 ▂
  ███████▅▄▄▁▃▁▁▁▁▃████████▇▆▆▆▅▅▁▃▇██▇▆▄████▆▆▅▄▄▅▃▁▁▁▄▁▁▅▅ █
  3.68 μs      Histogram: log(frequency) by time     9.98 μs <

 Memory estimate: 3.95 KiB, allocs estimate: 13.

julia> @benchmark rref(h_copy) evals=1 setup=(h_copy=h_nemo)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  3.565 μs … 40.789 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     3.882 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   4.147 μs ±  1.422 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

    ▅█▇▆▄▃▂                  ▁▂▂▁                            ▂
  ▄▅████████▇▅▄▄▃▁▃▃▁▃▁▁▁▁▁▄█████████▇▆▆▅▄▃▄▄▃▃▃▁▁▁▄▁▁▃▁▁▃▄▅ █
  3.56 μs      Histogram: log(frequency) by time     8.18 μs <

 Memory estimate: 3.98 KiB, allocs estimate: 14.


julia> @benchmark gf2_gausselim!(h_copy) evals=1 setup=(h_copy=h)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  920.000 ns …  58.186 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     973.000 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):     1.019 μs ± 879.487 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

           ▂▄█▄▂                                                 
  ▁▁▁▂▂▄▄▅███████▆▅▃▃▂▂▂▂▂▂▂▂▃▃▃▂▂▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  920 ns           Histogram: frequency by time         1.18 μs <

 Memory estimate: 832 bytes, allocs estimate: 13.

[Krastanov]

In a lot of these benchmarks you are testing on (and modifying) the original object, not the copied object, leading to the same issue that makes the benchmarks not trustworthy. E.g.

@benchmark is_invertible($h10_nemo) evals=1 setup=(h10_nemo_copy=h10_nemo)

[Fe-r-oz]

Thanks a lot. I will have to look which is the method to copy FqMatrix. When I used copy(nemo.matrix), I got error because copy as not defined.

[Fe-r-oz]

deepcopy works with FqMatrix!

[Fe-r-oz]

is_invertible results

Please have a look at these results.

julia> using QuantumClifford

julia> using QuantumClifford.ECC: Gottesman, parity_checks

julia> using QuantumClifford: stab_to_gf2, gf2_gausselim!

julia> using Nemo

julia> using BenchmarkTools

julia> h10 = stab_to_gf2(parity_checks(Gottesman(12)));

julia> h10_nemo = matrix(GF(2), h10);

julia> @benchmark gf2_isinvertible(h10_copy) evals=1 setup=(h10_copy=deepcopy(h10))
BenchmarkTools.Trial: 5244 samples with 1 evaluation.
 Range (min … max):  793.164 μs …   9.915 ms  ┊ GC (min … max): 0.00% … 90.83%
 Time  (median):     856.264 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   920.552 μs ± 332.492 μs  ┊ GC (mean ± σ):  1.87% ±  5.14%

  ▆█▅▅▆▇▆▅▅▄▄▃▃▂▂▂▂▁▁▁▁▁▁ ▁▁▁▁▁ ▁ ▁▃▁▁▁▁ ▁▁                     ▂
  █████████████████████████████████████████▇█▇▆▆▇▅▆▁▄▆▅▄▅▄▃▄▅▃▄ █
  793 μs        Histogram: log(frequency) by time       1.48 ms <

 Memory estimate: 941.30 KiB, allocs estimate: 4169.

julia> @benchmark is_invertible($h10_nemo) evals=1 setup=(h10_nemo_copy=deepcopy(h10_nemo))
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  106.000 ns … 159.789 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     223.000 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   360.776 ns ±   1.835 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

   ██▅▂                                                          
  ▆████▇▅▃▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  106 ns           Histogram: frequency by time         2.26 μs <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> h16 = stab_to_gf2(parity_checks(Gottesman(16)));

julia> h16_nemo = matrix(GF(2), h16);

julia> @benchmark gf2_isinvertible(h16_copy) evals=1 setup=(h16_copy=deepcopy(h16))
BenchmarkTools.Trial: 243 samples with 1 evaluation.
 Range (min … max):  17.977 ms … 36.936 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     19.551 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):   20.066 ms ±  2.309 ms  ┊ GC (mean ± σ):  0.78% ± 2.51%

  ▄█▄         ▃ ▁                                              
  ███▃▆▇▄▇▆▅▄▄█▆█▆▁▅▂▄▃▁▃▃▂▃▄▁▄▂▂▃▁▂▂▁▃▃▂▁▁▂▁▂▁▂▂▁▂▁▁▁▂▁▁▁▁▁▃ ▃
  18 ms           Histogram: frequency by time          28 ms <

 Memory estimate: 18.01 MiB, allocs estimate: 65727.

julia> @benchmark is_invertible($h16_nemo) evals=1 setup=(h16_nemo_copy=deepcopy(h16_nemo))
BenchmarkTools.Trial: 482 samples with 1 evaluation.
 Range (min … max):  791.000 ns … 19.614 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):       1.463 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):     1.899 μs ±  1.528 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

      ▆██▁  ▂▁                                                  
  ▂▃▅██████▇████▇▅▇▅▄▃▅▄▄▄▄▃▃▃▂▂▃▃▂▁▂▂▃▂▃▄▃▅▃▄▃▄▅▃▃▅▃▃▃▁▂▁▂▂▂▃ ▃
  791 ns          Histogram: frequency by time         4.22 μs <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> h20 = stab_to_gf2(parity_checks(Gottesman(20)));

julia> h20_nemo = matrix(GF(2), h20);

julia> @benchmark gf2_isinvertible(h20_copy) evals=1 setup=(h20_copy=deepcopy(h20))
BenchmarkTools.Trial: 6 samples with 1 evaluation.
 Range (min … max):  764.165 ms … 822.434 ms  ┊ GC (min … max): 0.92% … 1.31%
 Time  (median):     794.050 ms               ┊ GC (median):    0.89%
 Time  (mean ± σ):   793.051 ms ±  23.886 ms  ┊ GC (mean ± σ):  0.88% ± 0.49%

  █       █       █                            █   █          █  
  █▁▁▁▁▁▁▁█▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁█▁▁▁▁▁▁▁▁▁▁█ ▁
  764 ms           Histogram: frequency by time          822 ms <

 Memory estimate: 344.01 MiB, allocs estimate: 1048815.

julia> @benchmark is_invertible($h20_nemo) evals=1 setup=(h20_nemo_copy=deepcopy(h20_nemo))
BenchmarkTools.Trial: 18 samples with 1 evaluation.
 Range (min … max):  2.476 μs …   6.389 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     3.196 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   3.394 μs ± 826.424 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

  ▁    ▁▁█▁▁█▁▁█▁  █     ▁                                  ▁  
  █▁▁▁▁██████████▁▁█▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
  2.48 μs         Histogram: frequency by time        6.39 μs <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> h = [1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1;
                           1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0;
                           1  1  1  1  0  0  0  0  1  1  1  1  0  0  0  0;
                           1  1  0  0  1  1  0  0  1  1  0  0  1  1  0  0;
                           1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0;
                           1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0;
                           1  1  0  0  1  1  0  0  0  0  0  0  0  0  0  0;
                           1  0  1  0  1  0  1  0  0  0  0  0  0  0  0  0;
                           1  1  0  0  0  0  0  0  1  1  0  0  0  0  0  0;
                           1  0  1  0  0  0  0  0  1  0  1  0  0  0  0  0;
                           1  0  0  0  1  0  0  0  1  0  0  0  1  0  0  0];

julia> h = Matrix{Bool}(h);

julia> h_nemo = matrix(GF(2), h);

julia> @benchmark gf2_isinvertible(h_copy) evals=1 setup=(h_copy=deepcopy(h))
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):   6.765 μs … 49.564 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     10.728 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   11.491 μs ±  3.450 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

  ▆▄▁      ██▅▃▂▅▆▅▃▁▄▄▃▂▂ ▁▁                                 ▂
  ███▇▅▆▇▆████████████████▇████▇▄▄▇▇▇▄▄▁▄▁▃▄▆▆▅▄▁▅▆▄▁▅▇▆▄▄▃▆▆ █
  6.76 μs      Histogram: log(frequency) by time      29.1 μs <

 Memory estimate: 9.95 KiB, allocs estimate: 128.

julia> @benchmark is_invertible($h_nemo) evals=1 setup=(h_nemo_copy=deepcopy(h_nemo))
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  51.000 ns …  1.682 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     72.000 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   72.082 ns ± 16.885 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

                                   ▂ ▅ █ ▇ ▃▁                  
  ▂▂▁▂▁▂▁▂▃▁▃▁▃▁▃▁▃▃▁▂▁▂▁▂▁▂▃▁▄▁▆▁██▁█▁█▁█▁██▁▇▁▅▁▄▁▃▃▁▃▁▃▁▂▂ ▃
  51 ns           Histogram: frequency by time          84 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

gaussian elimination

julia> @benchmark gf2_gausselim!(h10_copy) evals=1 setup=(h10_copy=deepcopy(h10))
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  224.126 μs … 30.192 ms  ┊ GC (min … max):  0.00% … 98.91%
 Time  (median):     349.019 μs              ┊ GC (median):     0.00%
 Time  (mean ± σ):   360.677 μs ±  1.055 ms  ┊ GC (mean ± σ):  11.29% ±  3.82%

  ▇▇▁▁▃▁  ▁▁                   ██▅ ▂▃▃▁▄▄▃  ▁▂▁▁▁▁▁            ▂
  ███████████▇▆█▇▇▆▇▇▆▆▆▆▄▅▅▅▄█████████████████████▇▇▆▆▆▆▆▆▇▆▅ █
  224 μs        Histogram: log(frequency) by time       475 μs <

 Memory estimate: 256.06 KiB, allocs estimate: 4097.

julia> @benchmark echelon_form(h10_copy) evals=1 setup=(h10_copy=deepcopy(h10_nemo))
BenchmarkTools.Trial: 1290 samples with 1 evaluation.
 Range (min … max):  3.456 ms …   5.863 ms  ┊ GC (min … max): 0.00% … 32.41%
 Time  (median):     3.600 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   3.740 ms ± 342.036 μs  ┊ GC (mean ± σ):  0.14% ±  1.45%

    ▆█▇█▅▂                                                     
  ▅▅███████▇▅▆▅▅▄▃▃▃▃▃▃▂▃▃▂▂▃▂▂▁▂▂▂▁▁▂▁▁▂▁▃▂▄▃▄▄▃▄▃▃▃▃▂▃▂▂▂▃▂ ▃
  3.46 ms         Histogram: frequency by time        4.74 ms <

 Memory estimate: 1.81 MiB, allocs estimate: 13.

julia> @benchmark rref(h10_copy) evals=1 setup=(h10_copy=deepcopy(h10_nemo))
BenchmarkTools.Trial: 1251 samples with 1 evaluation.
 Range (min … max):  3.456 ms …  14.801 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     3.681 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   3.855 ms ± 506.289 μs  ┊ GC (mean ± σ):  0.15% ± 1.39%

   ▁▇▆█▅▂▁                                                     
  ▃███████▇▅▆▅▅▅▆▅▅▅▄▄▄▄▄▃▃▃▃▃▃▃▃▅▄▃▄▃▃▃▃▃▃▃▂▂▂▂▂▂▂▁▂▂▂▂▂▂▁▁▂ ▃
  3.46 ms         Histogram: frequency by time        5.19 ms <

 Memory estimate: 1.81 MiB, allocs estimate: 14.

julia> @benchmark gf2_gausselim!(h16_copy) evals=1 setup=(h16_copy=deepcopy(h16))
BenchmarkTools.Trial: 682 samples with 1 evaluation.
 Range (min … max):  4.261 ms … 37.854 ms  ┊ GC (min … max): 0.00% … 73.34%
 Time  (median):     6.500 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):   6.797 ms ±  3.992 ms  ┊ GC (mean ± σ):  7.99% ± 11.51%

  ▅   █▂                                                      
  █▇▄▄██▇▄▄▃▃▂▂▂▁▁▁▁▁▁▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▂▂▂▁▂ ▂
  4.26 ms        Histogram: frequency by time        31.9 ms <

 Memory estimate: 4.00 MiB, allocs estimate: 65537.

julia> @benchmark echelon_form(h16_copy) evals=1 setup=(h16_copy=deepcopy(h16_nemo))
BenchmarkTools.Trial: 44 samples with 1 evaluation.
 Range (min … max):   89.955 ms … 266.987 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):      98.267 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   108.065 ms ±  30.406 ms  ┊ GC (mean ± σ):  0.17% ± 0.57%

  █▅▅  ▂                                                         
  ███▇▇█▅▁▄▄▁▁▁▁▄▅▁▁▁▁▁▁▁▄▁▁▁▁▁▁▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄ ▁
  90 ms            Histogram: frequency by time          267 ms <

 Memory estimate: 37.00 MiB, allocs estimate: 13.

julia> @benchmark rref(h16_copy) evals=1 setup=(h16_copy=deepcopy(h16_nemo))
BenchmarkTools.Trial: 53 samples with 1 evaluation.
 Range (min … max):  83.878 ms … 123.476 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     86.739 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   89.947 ms ±   8.602 ms  ┊ GC (mean ± σ):  0.10% ± 0.36%

  ▃▆▄ █ ▁                                                       
  ███▇█▇█▆▆▄▁▁▄▁▆▄▁▁▁▆▁▁▁▁▁▁▁▁▁▁▆▁▁▁▁▁▁▁▄▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄ ▁
  83.9 ms         Histogram: frequency by time          121 ms <

 Memory estimate: 37.00 MiB, allocs estimate: 14.

julia> @benchmark gf2_gausselim!(h20_copy) evals=1 setup=(h20_copy=deepcopy(h20))
BenchmarkTools.Trial: 25 samples with 1 evaluation.
 Range (min … max):  127.912 ms … 203.983 ms  ┊ GC (min … max): 0.00% … 21.04%
 Time  (median):     157.780 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   157.817 ms ±  23.930 ms  ┊ GC (mean ± σ):  6.19% ±  9.37%

  ▂                      █ ▂                                     
  █▁▅█▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁█▅▁▅█▁▁▁▅▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁█ ▁
  128 ms           Histogram: frequency by time          204 ms <

 Memory estimate: 64.00 MiB, allocs estimate: 1048577.

julia> @benchmark echelon_form(h20_copy) evals=1 setup=(h20_copy=deepcopy(h20_nemo))
BenchmarkTools.Trial: 1 sample with 1 evaluation.
 Single result which took 2.412 s (0.67% GC) to evaluate,
 with a memory estimate of 720.00 MiB, over 13 allocations.

julia> @benchmark rref(h20_copy) evals=1 setup=(h20_copy=deepcopy(h20_nemo))
BenchmarkTools.Trial: 1 sample with 1 evaluation.
 Single result which took 2.386 s (0.71% GC) to evaluate,
 with a memory estimate of 720.00 MiB, over 14 allocations.

[Krastanov]

most of the first half of the benchmarks still do in-place operations on an object they reuse

[Fe-r-oz]

Thanks for your comments.

How about this? My apologies in advance if this is wrong.

julia> using QuantumClifford.ECC: Gottesman, parity_checks

julia> using QuantumClifford: stab_to_gf2, gf2_isinvertible

julia> using Nemo

julia> using BenchmarkTools

julia> function benchmark_gf2_isinvertible(h)
           h_nemo = matrix(GF(2), h)
           println("QC", @benchmark gf2_isinvertible($h) evals=1 setup=(h_copy=deepcopy($h)))
           println("Nemo", @benchmark is_invertible($h_nemo) evals=1 setup=(h_nemo_copy=deepcopy($h_nemo)))
       end
benchmark_gf2_isinvertible (generic function with 1 method)

julia> h10 = stab_to_gf2(parity_checks(Gottesman(12)));

julia> h10_nemo = matrix(GF(2), h10);

julia> benchmark_gf2_isinvertible(h10)
QCTrial(786.953 μs)
NemoTrial(52.000 ns)

julia> h16 = stab_to_gf2(parity_checks(Gottesman(16)));

julia> h16_nemo = matrix(GF(2), h16);

julia> benchmark_gf2_isinvertible(h16)
QCTrial(17.912 ms)
NemoTrial(380.000 ns)

julia> h20 = stab_to_gf2(parity_checks(Gottesman(20)));

julia> h20_nemo = matrix(GF(2), h20);

julia> benchmark_gf2_isinvertible(h20)
QCTrial(775.851 ms)
NemoTrial(1.355 μs)

[Krastanov]

This is going backwards. Now both benchmarks are misleading.

@benchmark gf2_isinvertible($h) evals=1 setup=(h_copy=deepcopy($h)))

In the above one you are benchmarking on object called h which is (potentially) modified the first time and then (potentially) reused, while you are making a copy h_copy that is never used for anything.

@benchmark is_invertible($h_nemo) evals=1 setup=(h_nemo_copy=deepcopy($h_nemo)))

Same problem in the above one. h_nemo_copy is never used for anything, while you work on h_nemo repeatedly.

Maybe all of this does not matter because these functions do not actually do any in-place operations or because they internally make copies. But this benchmark does not let me know if this is the case.

[Fe-r-oz]

Indeed. I am not using the copies...! 👀

[Fe-r-oz]

Maybe all of this does not matter because these functions do not actually do any in-place operations or because they internally make copies.

Just to add on, Tommy told me that there is no need for setup as the function(is_invertible) I am benchmark does not mutate the input.

[Fe-r-oz]

is_invertible results

julia> using QuantumClifford.ECC: Gottesman, parity_checks

julia> using QuantumClifford: stab_to_gf2, gf2_isinvertible

julia> using Nemo

julia> using BenchmarkTools

julia> function benchmark_gf2_isinvertible(h)
           h_nemo = matrix(GF(2), h)
           println("QC", @benchmark gf2_isinvertible(h_copy) setup=(h_copy=deepcopy($h)) evals=1)
           println("Nemo", @benchmark is_invertible(h_nemo_copy) setup=(h_nemo_copy=deepcopy($h_nemo)) evals=1)
       end
benchmark_gf2_isinvertible (generic function with 1 method)

julia> h10 = stab_to_gf2(parity_checks(Gottesman(12)));

julia> benchmark_gf2_isinvertible(h10)
QCTrial(789.489 μs)
NemoTrial(64.000 ns)

julia> h16 = stab_to_gf2(parity_checks(Gottesman(16)));

julia> benchmark_gf2_isinvertible(h16)
QCTrial(17.671 ms)
NemoTrial(270.000 ns)

julia> h20 = stab_to_gf2(parity_checks(Gottesman(20)));

julia> benchmark_gf2_isinvertible(h20)
QCTrial(733.538 ms)
NemoTrial(700.000 ns)