Skip to content

Simple recursive functions can hang in inference #57873

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

Closed
KristofferC opened this issue Mar 24, 2025 · 4 comments · Fixed by #58273
Closed

Simple recursive functions can hang in inference #57873

KristofferC opened this issue Mar 24, 2025 · 4 comments · Fixed by #58273
Assignees
Labels
compiler:inference Type inference
Milestone

Comments

@KristofferC
Copy link
Member

KristofferC commented Mar 24, 2025

Edit: See comment #57873 (comment) for most up to date info.

The following code takes a second or so to run on 1.11

julia> using NCDatasets

julia> @time NCDataset(["a", "b"])
ERROR: NetCDF error: Opening path a: No such file or directory (NetCDF error code: 2)

On 1.12 it gets stuck in inference for at least more than a minute.

    30.57%  julia    libjulia-internal.so.1.13.0  [.] egal_types
     4.41%  julia    libjulia-internal.so.1.13.0  [.] gc_mark_loop_serial_
     2.14%  julia    libjulia-internal.so.1.13.0  [.] ijl_gc_small_alloc
     2.09%  julia    sys.so                       [.] julia_is_derived_type_55869.2
     1.96%  julia    libjulia-internal.so.1.13.0  [.] jl_gc_alloc_
     1.92%  julia    libjulia-internal.so.1.13.0  [.] ijl_apply_generic
     1.83%  julia    libjulia-internal.so.1.13.0  [.] gc_sweep_page.isra.0
@KristofferC KristofferC added the compiler:inference Type inference label Mar 24, 2025
@KristofferC KristofferC added this to the 1.12 milestone Mar 24, 2025
@KristofferC
Copy link
Member Author

KristofferC commented Mar 24, 2025

Introduced in #56880. cc @vtjnash.

FWIW, the types involved seem to look something like

x = NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{NCDatasets.NCDataset{Nothing, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}, Base.Missing}

Even though the type above looks horrible, the returned type from the function is normal:

julia> fnames
3-element Vector{String}:
 "/var/folders/tp/2p4x9ygx48sgsdl1ccg1mp_40000gn/T/jl_Y36H2N6PMv"
 "/var/folders/tp/2p4x9ygx48sgsdl1ccg1mp_40000gn/T/jl_MzArgrmRYp"
 "/var/folders/tp/2p4x9ygx48sgsdl1ccg1mp_40000gn/T/jl_E3EpCFMD01"

julia> dataset = NCDataset(fnames);

julia> typeof(dataset)
CommonDataModel.MFDataset{DeferDataset{NCDataset}, 1, String}

So I don't know if inference is going on a wild goose chase or something...

@KristofferC
Copy link
Member Author

KristofferC commented Mar 24, 2025

The following code reduced from a package that hits the time-limit also gets bisected to #56880 so it seems that PR is somewhat problematic:

function tt(TY::Type, pref=("",))
    println("I am now running...")
    ret = String[]
    ST = subtypes(TY)
    for i in 1:length(ST)
        append!(ret, tt(ST[i], (pref..., "")))
    end
    ret
end

tt(Int)
    21.28%  julia    libjulia-internal.so.1.13.0  [.] obvious_subtype.part.0
    19.33%  julia    libjulia-internal.so.1.13.0  [.] has_concrete_supertype
    17.79%  julia    libjulia-internal.so.1.13.0  [.] obviously_unequal
    10.06%  julia    libjulia-internal.so.1.13.0  [.] has_free_typevars
     2.87%  julia    libjulia-internal.so.1.13.0  [.] gc_mark_loop_serial_
     1.36%  julia    libjulia-internal.so.1.13.0  [.] egal_types

Removing the ::Type makes it infer quickly.

1.11 has no problem with it:

julia> @time tt(Int)
I am now running...
  0.001929 seconds (5.71 k allocations: 318.789 KiB, 95.32% compilation time)

It seems even here as in the first full package example some big types are "imagined" by inference:

Tuple{String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, String, Vararg{String}}
String[]

@KristofferC
Copy link
Member Author

KristofferC commented Mar 24, 2025

This might be a dup of #57098 but the MWE in the comment above might still be useful.

@KristofferC KristofferC changed the title Running a constructor in NCDatasets hangs in type inference Simple recursive functions can hang in inference Mar 24, 2025
@vtjnash vtjnash self-assigned this Mar 28, 2025
@KristofferC
Copy link
Member Author

Any update on this? Still many packages that time out in PkgEval.

vtjnash added a commit that referenced this issue Apr 29, 2025
Prevent infinite inference when dealing with LimitedAccuracy by
declining to cache them. Presence in the cache triggers further
compilation to resolve it, so removing infinite work from the cache also
prevents infinite work at pre-compile/jit compile time.

Fix #57098
Fix #57873
vtjnash added a commit that referenced this issue May 1, 2025
Prevent infinite inference when dealing with LimitedAccuracy by
declining to cache them. Presence in the cache triggers further
compilation to resolve it, so removing infinite work from the cache also
prevents infinite work at pre-compile/jit compile time.

Fix #57098
Fix #57873
@vtjnash vtjnash closed this as completed in 48bd673 May 2, 2025
KristofferC pushed a commit that referenced this issue May 5, 2025
Prevent infinite inference when dealing with LimitedAccuracy by
declining to cache them. Presence in the cache triggers further
compilation to resolve it, so removing infinite work from the cache also
prevents infinite work at pre-compile/jit compile time.

Fix #57098
Fix #57873

(cherry picked from commit 48bd673)
charleskawczynski pushed a commit to charleskawczynski/julia that referenced this issue May 12, 2025
)

Prevent infinite inference when dealing with LimitedAccuracy by
declining to cache them. Presence in the cache triggers further
compilation to resolve it, so removing infinite work from the cache also
prevents infinite work at pre-compile/jit compile time.

Fix JuliaLang#57098
Fix JuliaLang#57873
charleskawczynski pushed a commit to charleskawczynski/julia that referenced this issue May 12, 2025
)

Prevent infinite inference when dealing with LimitedAccuracy by
declining to cache them. Presence in the cache triggers further
compilation to resolve it, so removing infinite work from the cache also
prevents infinite work at pre-compile/jit compile time.

Fix JuliaLang#57098
Fix JuliaLang#57873
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler:inference Type inference
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants