Benchmark scalar products for all our tables

[fingolfin]

@SoongNoonien maybe you can compute timings for all our tables for ...

1. computing a single scalar product of two "random" character types,
2. computing all scalar products (i.e. $n^2$ if there are $n$ character types).

What are the slowest ones, and how long do they need?

Once we have that, we can perhaps try to see how long the Maple version takes for this to get a rough idea of where we are, performance wise, at least in this particular computation.

[SoongNoonien]

Ok, so here are some results for computing all scalar products:

GU3:   8.298026 seconds (25.19 M allocations: 3.086 GiB, 13.21% gc time, 2.87% compilation time)
PGU3.2:  10.119181 seconds (35.85 M allocations: 3.140 GiB, 12.50% gc time, 1.93% compilation time)
PGU3.n2:   3.886293 seconds (14.55 M allocations: 1.190 GiB, 14.41% gc time, 3.53% compilation time)
PSU3.2:  17.323727 seconds (64.42 M allocations: 5.543 GiB, 13.09% gc time, 1.54% compilation time)
PSU3.n2:   3.751353 seconds (14.55 M allocations: 1.190 GiB, 10.74% gc time, 3.60% compilation time)
SU3.2:  28.732406 seconds (98.44 M allocations: 8.346 GiB, 12.27% gc time, 0.91% compilation time)
SU3.n2:   4.275720 seconds (14.55 M allocations: 1.190 GiB, 15.06% gc time, 3.42% compilation time)
2B2:   1.159450 seconds (3.74 M allocations: 392.136 MiB, 12.15% gc time, 6.30% compilation time)
Sz:   1.261504 seconds (3.74 M allocations: 392.136 MiB, 16.90% gc time, 6.15% compilation time)
uni2D4.0:   0.013009 seconds (45.22 k allocations: 4.570 MiB)
uni2D4.1:   0.014082 seconds (52.61 k allocations: 5.309 MiB)
2G2:  22.078558 seconds (72.43 M allocations: 6.284 GiB, 11.78% gc time, 1.54% compilation time)
ree:  20.463347 seconds (72.26 M allocations: 6.275 GiB, 12.03% gc time, 1.06% compilation time)
3D4.0: 631.629873 seconds (2.00 G allocations: 184.452 GiB, 12.63% gc time, 0.15% compilation time)
3D4.11: 1191.190006 seconds (3.73 G allocations: 345.399 GiB, 12.41% gc time, 0.10% compilation time)
3D4.13: 1194.269016 seconds (3.73 G allocations: 345.410 GiB, 12.58% gc time, 0.10% compilation time)
GL2:   0.337142 seconds (1.29 M allocations: 106.508 MiB, 23.44% compilation time)
GU2:   0.328392 seconds (1.28 M allocations: 105.470 MiB, 22.71% compilation time)
PGL2.0:   1.033102 seconds (1.67 M allocations: 91.236 MiB, 86.62% compilation time)
PGL2.1:   1.138693 seconds (3.13 M allocations: 279.696 MiB, 26.40% gc time, 5.84% compilation time)
PSL2.0:   0.177913 seconds (1.11 M allocations: 63.271 MiB, 20.69% compilation time)
PSL2.1:   0.477209 seconds (3.27 M allocations: 188.400 MiB, 13.19% compilation time)
PSL2.3:   0.987999 seconds (4.21 M allocations: 244.832 MiB, 29.04% gc time, 6.12% compilation time)
SL2.0:   0.182207 seconds (1.11 M allocations: 63.271 MiB, 20.20% compilation time)
SL2.1:   1.381537 seconds (6.66 M allocations: 388.623 MiB, 20.44% gc time, 8.09% compilation time)
GL3:   8.296505 seconds (25.50 M allocations: 3.119 GiB, 13.14% gc time, 2.86% compilation time)
PGL3.1:   9.678230 seconds (35.75 M allocations: 3.125 GiB, 12.38% gc time, 1.88% compilation time)
PGL3.n1:   3.844796 seconds (14.65 M allocations: 1.197 GiB, 14.43% gc time, 3.48% compilation time)
PSL3.1:  17.484593 seconds (64.63 M allocations: 5.558 GiB, 13.62% gc time, 1.48% compilation time)
PSL3.n1:   3.806852 seconds (14.65 M allocations: 1.196 GiB, 15.13% gc time, 3.50% compilation time)
SL3.1:  25.385772 seconds (98.73 M allocations: 8.372 GiB, 12.77% gc time, 0.97% compilation time)
SL3.n1:   3.795213 seconds (14.65 M allocations: 1.196 GiB, 15.05% gc time, 3.48% compilation time)
Sp4.0:  70.847771 seconds (274.98 M allocations: 22.977 GiB, 13.74% gc time, 0.37% compilation time)
uniCSp4.1:   0.001775 seconds (6.75 k allocations: 412.273 KiB)
uniCSp6.1:   0.019676 seconds (87.09 k allocations: 7.300 MiB)
uniSp6.0:   0.012137 seconds (64.22 k allocations: 5.262 MiB)
uniCSpin8.1:   0.045702 seconds (225.99 k allocations: 22.495 MiB)
uniSpin8.0:   0.039011 seconds (186.08 k allocations: 17.945 MiB)
uniuniF4p2:  15.043472 seconds (105.09 M allocations: 4.525 GiB, 21.60% gc time, 4.39% compilation time)
G2.01: 324.035696 seconds (1.17 G allocations: 104.154 GiB, 13.14% gc time, 0.15% compilation time)
G2.02: 293.642652 seconds (1.05 G allocations: 92.589 GiB, 13.05% gc time, 0.17% compilation time)
G2.101: 344.228376 seconds (1.23 G allocations: 105.756 GiB, 13.32% gc time, 0.18% compilation time)
G2.103: 337.780120 seconds (1.23 G allocations: 105.758 GiB, 13.47% gc time, 0.19% compilation time)
G2.111: 429.898215 seconds (1.57 G allocations: 135.472 GiB, 13.49% gc time, 0.16% compilation time)
G2.113: 440.306751 seconds (1.59 G allocations: 137.515 GiB, 13.40% gc time, 0.16% compilation time)
G2.121: 437.184096 seconds (1.59 G allocations: 137.717 GiB, 13.40% gc time, 0.16% compilation time)
G2.123: 436.091760 seconds (1.58 G allocations: 135.670 GiB, 13.42% gc time, 0.16% compilation time)
uniGL2:   0.000741 seconds (174 allocations: 8.125 KiB)
uniGL3:   0.000157 seconds (651 allocations: 36.289 KiB)
uniGL4:   0.001073 seconds (4.34 k allocations: 308.234 KiB)
uniGL5:   0.003556 seconds (14.89 k allocations: 1.327 MiB)
uniGL6:   0.024259 seconds (92.29 k allocations: 10.522 MiB)
uniGL7:   0.100373 seconds (324.36 k allocations: 47.132 MiB)
uniGL8:   1.216119 seconds (1.63 M allocations: 293.449 MiB, 27.05% gc time)
uniGU2:   0.000057 seconds (171 allocations: 8.062 KiB)
uniGU3:   0.000158 seconds (651 allocations: 36.289 KiB)
uniGU4:   0.000950 seconds (4.34 k allocations: 308.250 KiB)
uniGU5:   0.003536 seconds (14.89 k allocations: 1.327 MiB)
uniGU6:   0.024480 seconds (92.29 k allocations: 10.523 MiB)
uniGU7:   0.094642 seconds (324.36 k allocations: 47.129 MiB)
uniGU8:   1.165741 seconds (1.63 M allocations: 293.437 MiB, 18.68% gc time)
2F4.1: 7994.423638 seconds (25.54 G allocations: 2.399 TiB, 13.70% gc time, 0.02% compilation time)

CSp6.1 takes very long so I skipped it for now. Also the 2F4 tables take quite some time so I ran them after I looked at all the other tables. I think the times for one "random" scalar product can be computed by dividing the total time by the number of computed scalar products. So for 2F4.1 this would give an average time of around 4.75 seconds for the scalar product of two random character types.

[SoongNoonien]

To get to these results I defined

function scalar_test(g)
   for c1 in g
       for c2 in g
           scalar_product(c1, c2)
       end
   end
end

and then ran

for name in generic_character_table()
   print(name,": ")
   g=generic_character_table(name)
   @time scalar_test(g)
end

to skip some tables I simply inserted a startswith(table, "TABELNAME") && continue.

[SoongNoonien]

I have a working CHEVIE environment again. Running Scalar on 3D4.0 takes 112 seconds and around 2 gigabytes of allocations. The Scalar function in CHEVIE computes every possibly scalar product just once and not twice as my original scalar_test function. So I reran the test for 3D4.0 with this scalar_test function:

function scalar_test(g)
  for c1 in 1:number_of_character_types(g)
      for c2 in 1:c1
          scalar_product(g[c1], g[c2])
      end
  end
end

This gives 487.636221 seconds (1.38 G allocations: 128.666 GiB, 11.59% gc time). So have a time factor of around 4.4.

[fingolfin]

... and a factor 64 for allocated memory which gives a good hint for potential optimizations

[SoongNoonien]

Now that I have Oscar 1.2.2 installed it seems like it's not so bad anymore.

julia> function scalar_test(g)
         for c1 in 1:number_of_character_types(g)
             for c2 in 1:c1
                 scalar_product(g[c1], g[c2])
             end
         end
       end
scalar_test (generic function with 1 method)

julia> g=generic_character_table("3D4.0")
Generic character table 3D4.0
  of order q^28 - q^26 + q^24 - 2*q^22 + 2*q^20 - 2*q^18 + q^16 - q^14 + q^12
  with 29 irreducible character types
  with 29 class types
  with parameters (a, b, k, l)

julia> @time scalar_test(g)
 74.464829 seconds (241.92 M allocations: 24.918 GiB, 12.96% gc time, 2.81% compilation time)

julia> @time scalar_test(g)
 67.418201 seconds (239.91 M allocations: 24.819 GiB, 12.32% gc time)

It seems like we are actually faster now. But still factor 12 for allocations. Keep in mind that the CHEVIE installation is inside a VM. So now that we are actually that close I'll set up Julia in the VM as well and see if anything changes.

[SoongNoonien]

Ok, it is indeed a bit slower inside the VM but still faster than CHEVIE:

julia> @time scalar_test(g)
112.907877 seconds (243.06 M allocations: 24.975 GiB, 12.65% gc time, 6.53% compilation time)

julia> @time scalar_test(g)
 95.166720 seconds (239.91 M allocations: 24.819 GiB, 13.33% gc time)

[fingolfin]

You can e.g. use PProf.jl to dig deeper into the causes for the slow downs

[fingolfin]

I looked a bit at the profiles. I did

using GenericCharacterTables, Profile

g=generic_character_table("3D4.0")
@profile for j in 1:10 x = [g[i] * g[29] for i in 1:29] end;

• about 22% of the time is in hash(UnivPoly{QQFieldElem}, ::UInt64)
• about 37% is spent in var_shift, most of it in evaluate

This is of course not necessarily mutually exclusive.