Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Identify the performance bottleneck for G(1, 3) #11

Open
utensil opened this issue May 25, 2023 · 2 comments
Open

Identify the performance bottleneck for G(1, 3) #11

utensil opened this issue May 25, 2023 · 2 comments

Comments

@utensil
Copy link
Member

utensil commented May 25, 2023

I've just noticed that the test CI is slow due to G(1, 3) Graded identities, particularly for A4, which takes 32m44.7s for no good reason. Tested with branch https://github.com/pygae/GAlgebra.jl/tree/profile_11

  G(1, 3, 0)          |  467            467  34m24.2s
    definition        |   25             25      6.8s
    LA identities     |   12             12      0.0s
    GA identities     |   30             30      9.8s
    Graded identities |  400            400  34m06.2s
      r: 0            |   72             72      0.3s
      r: 1            |   79             79      1.4s
      r: 2            |   82             82      6.3s
      r: 3            |   83             83   1m13.5s
        ArBs s: 0     |   13             13      0.1s
        ArBs s: 1     |   13             13      0.2s
        ArBs s: 2     |   13             13      0.3s
        ArBs s: 3     |   12             12      0.2s
        ArBs s: 4     |   12             12      0.1s
      r: 4            |   84             84  32m44.7s
        ArBs s: 0     |   13             13      0.0s
        ArBs s: 1     |   13             13      0.0s
        ArBs s: 2     |   13             13      0.1s
        ArBs s: 3     |   13             13      0.1s
        ArBs s: 4     |   12             12      0.0s
@utensil
Copy link
Member Author

utensil commented May 25, 2023

The slow bit is the tests for A.4.32:

a = V.mv("a", "vector")
a₁₋ᵣ = [V.mv("a_$(i)", "vector") for i in 1:r]

wedge_a₁₋ᵣ = reduce(, a₁₋ᵣ)
prod_a₁₋ᵣ = reduce(*, a₁₋ᵣ)

@test wedge_a₁₋ᵣ == prod_a₁₋ᵣ[r]                                                  # A.4.12

A₁₋ᵣ = prod_a₁₋ᵣ

s = 3

Bs = B[s]
# 0.604375 seconds (5 allocations: 96 bytes)
@time AB1 = A₁₋ᵣ * Bs
# 0.976315 seconds (7.27 k allocations: 366.075 KiB, 1.75% compilation time)
@time AB2 = (A₁₋ᵣ)ǂ
# 60.840067 seconds (5 allocations: 96 bytes)
@time A_Bs_Aǂ = AB1 * AB2
# 283.460948 seconds (22 allocations: 704 bytes)
@time @test A_Bs_Aǂ == A_Bs_Aǂ[s]                                         # A.4.32

I've also tried G(4), almost the same time, which means it's not triggered by metric.

utensil added a commit that referenced this issue May 25, 2023
@utensil
Copy link
Member Author

utensil commented May 26, 2023

Complete stat by https://github.com/pygae/GAlgebra.jl/actions/runs/5081830873/jobs/9130739582 of 7ac49b0

  G(1, 3, 0)          |  467            467  35m01.8s
    definition        |   25             25      7.0s
    LA identities     |   12             12      0.0s
    GA identities     |   30             30      9.9s
    Graded identities |  400            400  34m43.5s
      r: 0            |   72             72      0.3s
        ArBs s: 0     |   12             12      0.0s
        ArBs s: 1     |   12             12      0.1s
        ArBs s: 2     |   12             12      0.1s
        ArBs s: 3     |   12             12      0.1s
        ArBs s: 4     |   12             12      0.0s
      r: 1            |   79             79      1.4s
        s: 1          |    1              1      0.0s
        s: 1          |    1              1      0.1s
        s: 1          |    1              1      0.2s
        s: 1          |    1              1      0.1s
        s: 1          |    1              1      0.0s
        ArBs s: 0     |   13             13      0.1s
        ArBs s: 1     |   12             12      0.2s
        ArBs s: 2     |   12             12      0.3s
        ArBs s: 3     |   12             12      0.2s
        ArBs s: 4     |   12             12      0.0s
      r: 2            |   82             82      6.4s
        s: 2          |    1              1      0.2s
        s: 2          |    1              1      1.2s
        s: 2          |    1              1      2.0s
        s: 2          |    1              1      1.3s
        s: 2          |    1              1      0.2s
        ArBs s: 0     |   13             13      0.1s
        ArBs s: 1     |   13             13      0.3s
        ArBs s: 2     |   12             12      0.5s
        ArBs s: 3     |   12             12      0.3s
        ArBs s: 4     |   12             12      0.1s
      r: 3            |   83             83   1m14.3s
        s: 3          |    1              1      2.2s
        s: 3          |    1              1     16.6s
        s: 3          |    1              1     35.3s
        s: 3          |    1              1     16.7s
        s: 3          |    1              1      2.2s
        ArBs s: 0     |   13             13      0.1s
        ArBs s: 1     |   13             13      0.2s
        ArBs s: 2     |   13             13      0.3s
        ArBs s: 3     |   12             12      0.2s
        ArBs s: 4     |   12             12      0.1s
      r: 4            |   84             84  33m21.1s
        s: 4          |    1              1     32.0s
        s: 4          |    1              1   6m05.0s
        s: 4          |    1              1  20m10.1s
        s: 4          |    1              1   6m01.0s
        s: 4          |    1              1     31.8s
        ArBs s: 0     |   13             13      0.0s
        ArBs s: 1     |   13             13      0.1s
        ArBs s: 2     |   13             13      0.1s
        ArBs s: 3     |   13             13      0.1s
        ArBs s: 4     |   12             12      0.0s

compared to G(3):

  G(3, 0, 0)          |  379       1    380     29.2s
    definition        |   34             34      3.1s
    LA identities     |   12             12      0.0s
    GA identities     |   52       1     53     17.1s
    Graded identities |  281            281      8.9s
      r: 0            |   64             64      0.3s
        ArBs s: 0     |   13             13      0.0s
        ArBs s: 1     |   13             13      0.1s
        ArBs s: 2     |   13             13      0.1s
        ArBs s: 3     |   13             13      0.0s
      r: 1            |   70             70      0.9s
        s: 1          |    1              1      0.0s
        s: 1          |    1              1      0.0s
        s: 1          |    1              1      0.0s
        s: 1          |    1              1      0.0s
        ArBs s: 0     |   14             14      0.1s
        ArBs s: 1     |   13             13      0.3s
        ArBs s: 2     |   13             13      0.3s
        ArBs s: 3     |   13             13      0.1s
      r: 2            |   73             73      1.5s
        s: 2          |    1              1      0.1s
        s: 2          |    1              1      0.3s
        s: 2          |    1              1      0.3s
        s: 2          |    1              1      0.1s
        ArBs s: 0     |   14             14      0.1s
        ArBs s: 1     |   14             14      0.3s
        ArBs s: 2     |   13             13      0.3s
        ArBs s: 3     |   13             13      0.1s
      r: 3            |   74             74      6.1s
        s: 3          |    1              1      0.4s
        s: 3          |    1              1      2.5s
        s: 3          |    1              1      2.5s
        s: 3          |    1              1      0.4s
        ArBs s: 0     |   14             14      0.0s
        ArBs s: 1     |   14             14      0.1s
        ArBs s: 2     |   14             14      0.1s
        ArBs s: 3     |   13             13      0.0s

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant