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

Suboptimal performance of captured small unions #31909

Closed
bramtayl opened this issue May 3, 2019 · 3 comments · Fixed by #56617 · May be fixed by #56532
Closed

Suboptimal performance of captured small unions #31909

bramtayl opened this issue May 3, 2019 · 3 comments · Fixed by #56617 · May be fixed by #56532
Labels
performance Must go faster

Comments

@bramtayl
Copy link
Contributor

bramtayl commented May 3, 2019 

function test(ys)
    x = if rand(Bool)
        1
    else
        missing
    end
    map(y -> x + y, ys)
end
@code_warntype test((1, 2))
@Keno
Copy link
Member

Keno commented May 3, 2019

This corresponds to a TODO in the apply_type tfunc: https://github.com/JuliaLang/julia/blob/master/base/compiler/tfuncs.jl#L998. However, I think there is a larger question of whether putting the union on the outside of the closure is really the right thing to do. Perhaps there is a lowering that would allow small unions as the field type for closures.

@bramtayl
Copy link
Contributor Author

bramtayl commented May 3, 2019

I used this to get around it:

partial_map(f, fixed, variables::Tuple{}) = ()
partial_map(f, fixed, variables::Tuple) =
    f(fixed, variables[1]), partial_map(f, fixed, tail(variables))...
partial_map(f, fixed, ::Tuple{}, ::Tuple{}) = ()
partial_map(f, fixed, variables1::Tuple, variables2::Tuple) =
    f(fixed, variables1[1], variables2[1]),
    partial_map(f, fixed, tail(variables1), tail(variables2))...

@bramtayl bramtayl mentioned this issue Sep 19, 2019
Closed
@bramtayl bramtayl mentioned this issue Jul 17, 2020
Closed
@bramtayl bramtayl mentioned this issue Sep 8, 2020
Open
@bramtayl
Copy link
Contributor Author

I watched the JuliaCon talk where @StefanKarpinski mentioned prioritizing making Julia faster for tabular data and I think solving this would be an important step

@brenhinkeller brenhinkeller added the performance Must go faster label Nov 21, 2022
aviatesk added a commit that referenced this issue Nov 12, 2024
@aviatesk
inference: (slightly) improve type stability of capturing closures
27ea06e 
As an idea to improve type stability for capturing closures, such as in
#31909, I tried this idea of propagating the closure
object as a `PartialStruct` whose `fields` include captured variables
of which types are (partially) known. By performing const-prop on this
`closure::PartialStruct`, we can achieve a certain level of type
stability.
Specifically, I made some modifications to `abstract_eval_new` to allow
creating `PartialStruct` even for `:new` objects that are
`!isconcretedispatch` (since `PartialStruct` can now represent abstract
elements). I also adjusted `const_prop_argument_heuristic` to perform
aggressive constant propagation using such `closure::PartialStruct`.

As a result, the following code now achieves type stability:
```julia
julia> Base.infer_return_type((Bool,Int,)) do b, y
           x = b ? 1 : missing
           inner = y -> x + y
           return inner(y)
       end
Any                   # master
Union{Missing, Int64} # this commit
```

However, this alone was not enough to fully resolve #31909.
The call graph of `map` is extremely complex, and simply applying
constant propagation everywhere does not achieve the type safety
requested in the issue.

Nevertheless this commit alone would still improve type stability for
some cases, so I will go ahead and submit it as a PR.
@aviatesk aviatesk mentioned this issue Nov 12, 2024
Open
aviatesk added a commit that referenced this issue Nov 13, 2024
@aviatesk
inference: (slightly) improve type stability of capturing closures
72be4a1 
As an idea to improve type stability for capturing closures, such as in
#31909, I tried this idea of propagating the closure
object as a `PartialStruct` whose `fields` include captured variables
of which types are (partially) known. By performing const-prop on this
`closure::PartialStruct`, we can achieve a certain level of type
stability.
Specifically, I made some modifications to `abstract_eval_new` to allow
creating `PartialStruct` even for `:new` objects that are
`!isconcretedispatch` (since `PartialStruct` can now represent abstract
elements). I also adjusted `const_prop_argument_heuristic` to perform
aggressive constant propagation using such `closure::PartialStruct`.

As a result, the following code now achieves type stability:
```julia
julia> Base.infer_return_type((Bool,Int,)) do b, y
           x = b ? 1 : missing
           inner = y -> x + y
           return inner(y)
       end
Any                   # master
Union{Missing, Int64} # this commit
```

However, this alone was not enough to fully resolve #31909.
The call graph of `map` is extremely complex, and simply applying
constant propagation everywhere does not achieve the type safety
requested in the issue.

Nevertheless this commit alone would still improve type stability for
some cases, so I will go ahead and submit it as a PR.
aviatesk added a commit that referenced this issue Nov 13, 2024
@aviatesk
inference: (slightly) improve type stability of capturing closures
56de49c 
As an idea to improve type stability for capturing closures, such as in
#31909, I tried this idea of propagating the closure
object as a `PartialStruct` whose `fields` include captured variables
of which types are (partially) known. By performing const-prop on this
`closure::PartialStruct`, we can achieve a certain level of type
stability.
Specifically, I made some modifications to `abstract_eval_new` to allow
creating `PartialStruct` even for `:new` objects that are
`!isconcretedispatch` (since `PartialStruct` can now represent abstract
elements). I also adjusted `const_prop_argument_heuristic` to perform
aggressive constant propagation using such `closure::PartialStruct`.

As a result, the following code now achieves type stability:
```julia
julia> Base.infer_return_type((Bool,Int,)) do b, y
           x = b ? 1 : missing
           inner = y -> x + y
           return inner(y)
       end
Any                   # master
Union{Missing, Int64} # this commit
```

However, this alone was not enough to fully resolve #31909.
The call graph of `map` is extremely complex, and simply applying
constant propagation everywhere does not achieve the type safety
requested in the issue.

Nevertheless this commit alone would still improve type stability for
some cases, so I will go ahead and submit it as a PR.
aviatesk added a commit that referenced this issue Nov 20, 2024
@aviatesk
allow apply_type_tfunc to handle argtypes with Union
dcd8170 
This is an alternative to #56532 and can resolve #31909.
Currently `apply_type_tfunc` is unable to handle `Union`-argtypes with
any precision. With this change, `apply_type_tfunc` now performs
union-splitting on `Union`-argtypes and returns the merged result of
the splits.
While this can improve inference precision, we might need to be cautious
about potential inference time bloat.
@aviatesk aviatesk mentioned this issue Nov 20, 2024
Merged
aviatesk added a commit that referenced this issue Nov 20, 2024
@aviatesk
allow apply_type_tfunc to handle argtypes with Union
c6fde6d 
This is an alternative to #56532 and can resolve #31909.
Currently `apply_type_tfunc` is unable to handle `Union`-argtypes with
any precision. With this change, `apply_type_tfunc` now performs
union-splitting on `Union`-argtypes and returns the merged result of
the splits.
While this can improve inference precision, we might need to be cautious
about potential inference time bloat.
aviatesk added a commit that referenced this issue Nov 21, 2024
@aviatesk
allow apply_type_tfunc to handle argtypes with Union
4644565 
This is an alternative to #56532 and can resolve #31909.
Currently `apply_type_tfunc` is unable to handle `Union`-argtypes with
any precision. With this change, `apply_type_tfunc` now performs
union-splitting on `Union`-argtypes and returns the merged result of
the splits.
While this can improve inference precision, we might need to be cautious
about potential inference time bloat.
aviatesk added a commit that referenced this issue Nov 21, 2024
@aviatesk
allow apply_type_tfunc to handle argtypes with Union
77065b5 
This is an alternative to #56532 and can resolve #31909.
Currently `apply_type_tfunc` is unable to handle `Union`-argtypes with
any precision. With this change, `apply_type_tfunc` now performs
union-splitting on `Union`-argtypes and returns the merged result of
the splits.
While this can improve inference precision, we might need to be cautious
about potential inference time bloat.
aviatesk added a commit that referenced this issue Nov 21, 2024
@aviatesk
allow apply_type_tfunc to handle argtypes with Union
a28ada4 
This is an alternative to #56532 and can resolve #31909.
Currently `apply_type_tfunc` is unable to handle `Union`-argtypes with
any precision. With this change, `apply_type_tfunc` now performs
union-splitting on `Union`-argtypes and returns the merged result of
the splits.
While this can improve inference precision, we might need to be cautious
about potential inference time bloat.
aviatesk added a commit that referenced this issue Nov 22, 2024
@aviatesk
allow apply_type_tfunc to handle argtypes with Union
d42712b 
This is an alternative to #56532 and can resolve #31909.
Currently `apply_type_tfunc` is unable to handle `Union`-argtypes with
any precision. With this change, `apply_type_tfunc` now performs
union-splitting on `Union`-argtypes and returns the merged result of
the splits.
While this can improve inference precision, we might need to be cautious
about potential inference time bloat.
aviatesk added a commit that referenced this issue Nov 22, 2024
@aviatesk
inference: (slightly) improve type stability of capturing closures
fb76bfe 
As an idea to improve type stability for capturing closures, such as in
#31909, I tried this idea of propagating the closure
object as a `PartialStruct` whose `fields` include captured variables
of which types are (partially) known. By performing const-prop on this
`closure::PartialStruct`, we can achieve a certain level of type
stability.
Specifically, I made some modifications to `abstract_eval_new` to allow
creating `PartialStruct` even for `:new` objects that are
`!isconcretedispatch` (since `PartialStruct` can now represent abstract
elements). I also adjusted `const_prop_argument_heuristic` to perform
aggressive constant propagation using such `closure::PartialStruct`.

As a result, the following code now achieves type stability:
```julia
julia> Base.infer_return_type((Bool,Int,)) do b, y
           x = b ? 1 : missing
           inner = y -> x + y
           return inner(y)
       end
Any                   # master
Union{Missing, Int64} # this commit
```

However, this alone was not enough to fully resolve #31909.
The call graph of `map` is extremely complex, and simply applying
constant propagation everywhere does not achieve the type safety
requested in the issue.

Nevertheless this commit alone would still improve type stability for
some cases, so I will go ahead and submit it as a PR.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
performance Must go faster
Projects
None yet
Milestone
No milestone
3 participants
@Keno @brenhinkeller @bramtayl