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.

Sign up for GitHub

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

Jump to bottom

New stack overflow in type inference on old package. #53585

Closed
KristofferC opened this issue Mar 4, 2024 · 1 comment · Fixed by #53665
Closed

New stack overflow in type inference on old package. #53585

KristofferC opened this issue Mar 4, 2024 · 1 comment · Fixed by #53665
Assignees
@vtjnash
Labels
compiler:inference Type inference regression Regression in behavior compared to a previous version
Milestone
1.11

Comments

@KristofferC
Copy link
Member

Copy pasting the following into the REPL:

using Elliptic, Test

@testset "Table 17.9: Π(n; φ, m)" begin
    #                       Abramowitz & Stegun, Table 17.9, p625-6
    #                                  Π(n;phi\alpha)
    #    n   α\φ  0     15       30       45       60       75       90
    table17p9 = [
        0.0    0  0  0.26180  0.52360  0.78540  1.04720  1.30900  1.57080;
        0.0   15  0  0.26200  0.52513  0.79025  1.05774  1.32733  1.59814;
        0.0   30  0  0.26254  0.52943  0.80437  1.08955  1.38457  1.68575;
        0.0   45  0  0.26330  0.53562  0.82602  1.14243  1.48788  1.85407;
        0.0   60  0  0.26406  0.54223  0.85122  1.21260  1.64918  2.15651;
        0.0   75  0  0.26463  0.54736  0.87270  1.28371  1.87145  2.76806;
        0.0   90  0  0.26484  0.54931  0.88137  1.31696  2.02759      Inf;
        0.1    0  0  0.26239  0.52820  0.80013  1.07949  1.36560  1.65576;
        0.1   15  0  0.26259  0.52975  0.80514  1.09058  1.38520  1.68536;
        0.1   30  0  0.26314  0.53412  0.81972  1.12405  1.44649  1.78030;
        0.1   45  0  0.26390  0.54041  0.84210  1.17980  1.55739  1.96326;
        0.1   60  0  0.26467  0.54712  0.86817  1.25393  1.73121  2.29355;
        0.1   75  0  0.26524  0.55234  0.89040  1.32926  1.97204  2.96601;
        0.1   90  0  0.26545  0.55431  0.89939  1.36454  2.14201      Inf;
        0.2    0  0  0.26299  0.53294  0.81586  1.11534  1.43078  1.75620;
        0.2   15  0  0.26319  0.53452  0.82104  1.12705  1.45187  1.78850;
        0.2   30  0  0.26374  0.53896  0.83612  1.16241  1.51792  1.89229;
        0.2   45  0  0.26450  0.54535  0.85928  1.22139  1.63775  2.09296;
        0.2   60  0  0.26527  0.55217  0.88629  1.30003  1.82643  2.45715;
        0.2   75  0  0.26585  0.55747  0.90934  1.38016  2.08942  3.20448;
        0.2   90  0  0.26606  0.55948  0.91867  1.41777  2.27604      Inf;
        0.3    0  0  0.26359  0.53784  0.83271  1.15551  1.50701  1.87746;
        0.3   15  0  0.26379  0.53945  0.83808  1.16791  1.52988  1.91309;
        0.3   30  0  0.26434  0.54396  0.85370  1.20543  1.60161  2.02779;
        0.3   45  0  0.26511  0.55046  0.87771  1.26812  1.73217  2.25038;
        0.3   60  0  0.26588  0.55739  0.90574  1.35193  1.93879  2.65684;
        0.3   75  0  0.26646  0.56278  0.92969  1.43759  2.22876  3.49853;
        0.3   90  0  0.26667  0.56483  0.93938  1.47789  2.43581      Inf;
        0.4    0  0  0.26420  0.54291  0.85084  1.20098  1.59794  2.02789;
        0.4   15  0  0.26440  0.54454  0.85641  1.21419  1.62298  2.06774;
        0.4   30  0  0.26495  0.54912  0.87262  1.25419  1.70165  2.19629;
        0.4   45  0  0.26572  0.55573  0.89756  1.32117  1.84537  2.44683;
        0.4   60  0  0.26650  0.56278  0.92670  1.41098  2.07413  2.90761;
        0.4   75  0  0.26708  0.56827  0.95162  1.50309  2.39775  3.87214;
        0.4   90  0  0.26729  0.57035  0.96171  1.54653  2.63052      Inf;
        0.5    0  0  0.26481  0.54814  0.87042  1.25310  1.70919  2.22144;
        0.5   15  0  0.26501  0.54980  0.87621  1.26726  1.73695  2.26685;
        0.5   30  0  0.26557  0.55447  0.89307  1.31017  1.82433  2.41367;
        0.5   45  0  0.26634  0.56119  0.91902  1.38218  1.98464  2.70129;
        0.5   60  0  0.26712  0.56837  0.94939  1.47906  2.24155  3.23477;
        0.5   75  0  0.26770  0.57394  0.97538  1.57881  2.60846  4.36620;
        0.5   90  0  0.26792  0.57606  0.98591  1.62599  2.87468      Inf;
        0.6    0  0  0.26543  0.55357  0.89167  1.31379  1.85002  2.48365;
        0.6   15  0  0.26563  0.55525  0.89770  1.32907  1.88131  2.53677;
        0.6   30  0  0.26619  0.56000  0.91527  1.37544  1.98005  2.70905;
        0.6   45  0  0.26696  0.56684  0.94235  1.45347  2.16210  3.04862;
        0.6   60  0  0.26775  0.57414  0.97406  1.55884  2.45623  3.68509;
        0.6   75  0  0.26833  0.57982  1.00123  1.66780  2.88113  5.05734;
        0.6   90  0  0.26855  0.58198  1.01225  1.71951  3.19278      Inf;
        0.7    0  0  0.26605  0.55918  0.91487  1.38587  2.03720  2.86787;
        0.7   15  0  0.26625  0.56090  0.92116  1.40251  2.07333  2.93263;
        0.7   30  0  0.26681  0.56573  0.93952  1.45309  2.18765  3.14339;
        0.7   45  0  0.26759  0.57270  0.96784  1.53846  2.39973  3.56210;
        0.7   60  0  0.26838  0.58014  1.00104  1.65425  2.74586  4.35751;
        0.7   75  0  0.26897  0.58592  1.02954  1.77459  3.25315  6.11030;
        0.7   90  0  0.26918  0.58812  1.04110  1.83192  3.63042      Inf;
        0.8    0  0  0.26668  0.56501  0.94034  1.47370  2.30538  3.51240;
        0.8   15  0  0.26688  0.56676  0.94694  1.49205  2.34868  3.59733;
        0.8   30  0  0.26745  0.57168  0.96618  1.54790  2.48618  3.87507;
        0.8   45  0  0.26823  0.57877  0.99588  1.64250  2.74328  4.43274;
        0.8   60  0  0.26902  0.58635  1.03076  1.77145  3.16844  5.51206;
        0.8   75  0  0.26961  0.59225  1.06073  1.90629  3.80370  7.96669;
        0.8   90  0  0.26982  0.59449  1.07290  1.97080  4.28518      Inf;
        0.9    0  0  0.26731  0.57106  0.96853  1.58459  2.74439  4.96729;
        0.9   15  0  0.26752  0.57284  0.97547  1.60515  2.79990  5.09958;
        0.9   30  0  0.26808  0.57785  0.99569  1.66788  2.97710  5.53551;
        0.9   45  0  0.26887  0.58508  1.02695  1.77453  3.31210  6.42557;
        0.9   60  0  0.26966  0.59281  1.06372  1.92081  3.87661  8.20086;
        0.9   75  0  0.27025  0.59882  1.09535  2.07487  4.74432 12.46407;
        0.9   90  0  0.27047  0.60110  1.10821  2.14899  5.42125      Inf;
        1.0    0  0  0.26795  0.57735  1.00000  1.73205  3.73205      Inf;
        1.0   15  0  0.26816  0.57916  1.00731  1.75565  3.81655      Inf;
        1.0   30  0  0.26872  0.58428  1.02866  1.82781  4.08864      Inf;
        1.0   45  0  0.26951  0.59165  1.06170  1.95114  4.61280      Inf;
        1.0   60  0  0.27031  0.59953  1.10060  2.12160  5.52554      Inf;
        1.0   75  0  0.27090  0.60566  1.13414  2.30276  7.00372      Inf;
        1.0   90  0  0.27112  0.60799  1.14779  2.39053  8.22356      Inf;
    ]

    for i = 1:size(table17p9,1)
        n = table17p9[i,1]
        alpha = table17p9[i,2]
        m = sind(alpha)^2
        for j = 3:size(table17p9,2)
            phi = 15.0*(j-3)
            x = table17p9[i,j]
            y = Pi(n, deg2rad(phi), m)
            if x == Inf
                @test x == y
            else
                @test x ≈ y atol=1e-5*max(x,1.)
            end
        end
    end
end

kills julia with

Internal error: during type inference of
Tuple{}
Encountered stack overflow.
This might be caused by recursion over very long tuples or argument lists.

[65717] signal 6: Abort trap: 6
in expression starting at REPL[2]:1
__pthread_kill at /usr/lib/system/libsystem_kernel.dylib (unknown line)
pthread_kill at /usr/lib/system/libsystem_pthread.dylib (unknown line)
abort at /usr/lib/system/libsystem_c.dylib (unknown line)
jl_type_infer at /Users/kristoffercarlsson/julia1.11/src/gf.c:409
jl_toplevel_eval_flex at /Users/kristoffercarlsson/julia1.11/src/toplevel.c:932
jl_toplevel_eval_flex at /Users/kristoffercarlsson/julia1.11/src/toplevel.c:886
ijl_toplevel_eval at /Users/kristoffercarlsson/julia1.11/src/toplevel.c:952 [inlined]
ijl_toplevel_eval_in at /Users/kristoffercarlsson/julia1.11/src/toplevel.c:994
eval at ./boot.jl:428 [inlined]
eval_user_input at /Users/kristoffercarlsson/julia1.11/usr/share/julia/stdlib/v1.11/REPL/src/REPL.jl:224
repl_backend_loop at /Users/kristoffercarlsson/julia1.11/usr/share/julia/stdlib/v1.11/REPL/src/REPL.jl:320
#start_repl_backend#59 at /Users/kristoffercarlsson/julia1.11/usr/share/julia/stdlib/v1.11/REPL/src/REPL.jl:305

Seen on PkgEval https://s3.amazonaws.com/julialang-reports/nanosoldier/pkgeval/by_hash/0520b80_vs_997b49f/Elliptic.primary.log.

I don't think this code is very weird and the package is quite old so I would say this is a regression
@KristofferC KristofferC added regression Regression in behavior compared to a previous version compiler:inference Type inference labels Mar 4, 2024
@KristofferC KristofferC added this to the 1.11 milestone Mar 4, 2024
@vtjnash
Copy link
Member

vtjnash commented Mar 8, 2024

MWE

julia> let t = ntuple(i -> i % 8 == 1 ? Int64 : Float64, 4000) # fails somewhere around 700 for me -- the literal above has 693 elements
              Base.return_types(Base.promote_typeof, t) # or Base.return_types(vcat, t)
       end

vtjnash added a commit that referenced this issue Mar 8, 2024
@vtjnash
use afoldl instead of tail recursion for tuples
a85fc89 
It is easy to accidentally call these functions (they are used by vcat,
which is syntax) with very long lists of values, causing inference to
crash and take a long time. The `afoldl` function can handle that very
well however, while naive recursion did not.

Fixes #53585
@vtjnash vtjnash mentioned this issue Mar 8, 2024
Merged
@vtjnash vtjnash self-assigned this Mar 8, 2024
vtjnash added a commit that referenced this issue Mar 12, 2024
@vtjnash
use afoldl instead of tail recursion for tuples
9f2bd92 
It is easy to accidentally call these functions (they are used by vcat,
which is syntax) with very long lists of values, causing inference to
crash and take a long time. The `afoldl` function can handle that very
well however, while naive recursion did not.

Fixes #53585
vtjnash added a commit that referenced this issue Mar 12, 2024
@vtjnash
use afoldl instead of tail recursion for tuples
53de0c9 
It is easy to accidentally call these functions (they are used by vcat,
which is syntax) with very long lists of values, causing inference to
crash and take a long time. The `afoldl` function can handle that very
well however, while naive recursion did not.

Fixes #53585
vtjnash added a commit that referenced this issue Mar 12, 2024
@vtjnash
use afoldl instead of tail recursion for tuples (#53665)
df28bf7 
It is easy to accidentally call these functions (they are used by vcat,
which is syntax) with very long lists of values, causing inference to
crash and take a long time. The `afoldl` function can handle that very
well however, while naive recursion did not.

Fixes #53585
KristofferC pushed a commit that referenced this issue Apr 18, 2024
@vtjnash @KristofferC
use afoldl instead of tail recursion for tuples (#53665)
30c6e25 
It is easy to accidentally call these functions (they are used by vcat,
which is syntax) with very long lists of values, causing inference to
crash and take a long time. The `afoldl` function can handle that very
well however, while naive recursion did not.

Fixes #53585

(cherry picked from commit df28bf7)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@vtjnash vtjnash

Labels
compiler:inference Type inference regression Regression in behavior compared to a previous version
Projects
None yet
Milestone
1.11
Development

Successfully merging a pull request may close this issue.

use afoldl instead of tail recursion for tuples JuliaLang/julia
2 participants
@vtjnash @KristofferC