Type system abuse, advisability of

New to Julia
, ,
1

Part of my learning process with Julia has been to abuse the type system in various fun ways to see what’s possible. My latest monstrosity uses type parameters for partial application of functions:

module TypeAbuse
struct Fix{Fn,Args,KW}
  Fix{Fn}() where {Fn} = new{Fn,(),(;)}()
  Fix{Fn,Args}() where {Fn,Args} = new{Fn,Args,(;)}()
  Fix{Fn,Args,KW}() where {Fn,Args,KW} = new{Fn,Args,KW}()
end

function (::Fix{Fn,Args,KW})(moreargs...) where {Fn,Args,KW} 
  Fn(_cat(Args, moreargs)...; KW...)
end

_cat(a, b) = (a..., b...)
end

let c = TypeAbuse.Fix{+,1}()
  @show c
  @show c(2) == 3
end

let c = TypeAbuse.Fix{digits,(),(; base = 2)}()
  println()
  @show c
  @show c(5) == [1, 0, 1]
end

c = Main.TypeAbuse.Fix{+, 1, NamedTuple()}()
c(2) == 3 = true

c = Main.TypeAbuse.Fix{digits, (), (base = 2,)}()
c(5) == [1, 0, 1] = true

I benchmarked calling TypeAbuse.Fix{log,5}() with rand() against the equivalent Base.Fix1 call, and on my system calling both log(5, rand()) and the TypeAbuse.Fix takes ~24ns, where Base.Fix1 takes ~33ns, so it’s basically zero overhead at least in that particular case. I assume this is due to it being a singleton type and having both the function and its partially applied arguments available statically, meaning no construction of a new Fix instance and no field lookups?

Now, this benchmark result got me curious about how inadvisable this is, exactly. I know it will create a new type for every new Fn, Args and KW, increase compilation time at least to some extent, and only work with Argss / KWs that are isbitstypes (I think?), but considering those caveats is this actually as much of a crime against the type system as it originally seemed to me? As a beginner it feels like it could also actually be a useful optimization to shave off some nanoseconds from calling partially applied functions, assuming a case where those nanoseconds actually matter and the number of different type parameters doesn’t get out of hand.

7 Likes
2

This just hurts. I need a ritual bath.

4 Likes
3

Truly sublime.

It’s got me wondering if you could use a Tuple of Val{Int}s to mark the position of the partially applied arguments so that you could Fix arbitrary arguments and then some recursion to insert new arguments in the empty slots…

1 Like
4

image
image1036×1027 30.9 KB

1 Like
5

If you’re comparing the log computations, the efficiency comes from doing a log call on the fixed base value at compile time. See, a logarithm with an arbitrary base is actually done by dividing two logarithms: logab = log(b)/log(a). With Base.Fix1, the base value a is not known at compile-time, so every run it has to retrieve the field, convert it to floating point, compute the denominator logarithm, then divide the numerator logarithm by it. With your TypeAbuse.Fix, the value a is known at compile-time, so everything except the numerator logarithm and division can be done at compile-time. You could narrow the gap by fixing a floating point base a so conversion doesn’t happen, but that’s about it.

3 Likes
6

Ha, I love it that the reactions range from “why god why” to a “truly sublime” :smile:

@mrufsvold, I think you could maybe use a Tuple of Some / nothing for that. Partially applied args like (1, _, 2) (_ is just a stand-in for “not bound” here, not intended as a syntax example) could be encoded as (Some(1), nothing, Some(2)).

I highly encourage further development of this silliness, although I really am curious whether it’s as silly as it seems on the surface. There’s no denying that it’s not exactly something that you’d want to file under “best practices” in the Julia docs, but how bad is it when keeping in mind the caveats I listed?

1 Like
7

About the same as using Val, it’s not bad so much as niche. For the example in particular, I’d prefer doing a more direct @eval function log5(b) log2(b)/$(log2(5)) end however few times I need to make one (as you said, it’s not worth compiling for too many of these types).

1 Like
8

A-ha, so my gut feeling was right in that it’s actually not so much a “anybody caught doing this should be reprimanded and shot” deal as it is “you probably won’t need this, but it might be useful in some very specific cases if you know what you’re doing”.

3 Likes
9

This isn’t abuse of the type system, sometimes it’s useful to put data into the type domain.

Some stylistic notes:

  1. usually the constructors would be organized in such a manner that there’s at most a single explicit inner constructor:
struct Fix{Fn,Args,KW}
  Fix{Fn,Args,KW}() where {Fn,Args,KW} = new{Fn,Args,KW}()
end
Fix{Fn,Args}() where {Fn,Args} = Fix{Fn,Args,(;)}()
Fix{Fn}() where {Fn} = Fix{Fn,()}()
  1. The definition of the inner constructor in the above definition of Fix is actually redundant: leaving out the definition of the inner constructor would be preferable in this case because Julia will do the right thing by creating the default constructor. An inner constructor is most useful for checking the arguments given to the constructor and similar, which isn’t necessary here.
julia> struct Fix{Fn,Args,KW} end

julia> methods(Fix)
# 0 methods for type constructor

julia> methods(Fix{rand})
# 0 methods for type constructor

julia> methods(Fix{rand, (), (;)})
# 1 method for type constructor:
 [1] (var"#ctor-self#"::Type{Fix{Fn, Args, KW}} where {Fn, Args, KW})()
     @ REPL[1]:1
  1. The intention behind a constructor like Fix{Fn}() where {Fn} = Fix{Fn,()}() is to provide a default value for a type parameter. This makes sense and works, but may be problematic in some cases, because it is, in a sense, ambiguous, because it may not be clear whether an expression like Fix{some_function} should refer to the UnionAll type (see here and here) or to the constructor method. This wouldn’t be an issue in practice for Fix, but it doesn’t seem like good style. It may be better to have the user-facing interface be a function that would wrap the Fix type, which would have only the inner constructor.
2 Likes
10

I’m curious how you benchmarked this, can you share the code?

11

Two remarks:

  1. I don’t see this kind of code as type system abuse at all. This is pretty much run-of-the-mill stuff, you see lot more complex manipulations in type space in Base and the standard libraries.

  2. That said, I don’t understand why you think it optimizes anything. Fn will get called, maybe if it is super-simple then you gain something from constant folding, but that is not generally guaranteed. You may want to read the discussion that lead to Base.Fix2 (Base.Fix1 was introduced after to make it symmetric) for motivation, it does not generally lead to any runtime saving.

12

Sure! I actually hadn’t thought about whether I might be benchmarking this wrong, but this is what I used:

let bset = @benchmarkset "perf" begin
    let c = TypeAbuse.Fix{log,5}()
      @case "$c" $c(rand()) evals = 1000 samples = 10000
    end
    let c = Base.Fix1(log, 5)
      @case "$c" $c(rand()) evals = 1000 samples = 10000
    end

    @case "log(5,rand())" log(5, rand()) evals = 1000 samples = 10000
  end

  for (_, set) in BenchmarkTools.run(bset)
    for (name, trial) in set
      display(name)
      display(trial)
    end
  end

On my M1 Mac those give log(5,rand()) median ~25ns, Base.Fix1{typeof(log), Int64}(log, 5) ~34ns, Main.TypeAbuse.Fix{log, 5, NamedTuple()}() ~25ns.

@Tamas_Papp, :point_up: that is what I was referring to when I said that (at least at face value and to a beginner) it looks like TypeAbuse.Fix can have less overhead compared to Base.Fix1 in some cases.

13

Ah, thank you for the “best practices” note. I’m honestly still a bit puzzled about how types (especially UnionAlls) and constructor function naming play together.

As an example, would the Fix in Fix() = Fix{identity}() be referring to the (UnionAll) type Fix or is it just a method that happens to be named Fix? And how does that compare to eg. (::Type{Fix})() = Fix{identity}()?

Fix{Fn}() where {Fn} = # … seems like it’s definitely referring to the type, so is that the same as (::Type{Fix{Fn}})() where {Fn} = # …?

You also mentioned potential ambiguity between constructor methods and types, and I’m fairly sure I’ve run into that in some tomfoolery but I can’t quite remember what it was. It was related to providing default type parameters though, possibly in a constructor with no type parameters

1 Like
14

It’s definitely machine dependent then - on my machine, I see these:

"log(5,rand())"
BenchmarkTools.Trial: 10000 samples with 1000 evaluations.
 Range (min … max):  14.840 ns … 23.990 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     15.060 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   15.104 ns ±  0.407 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

      ▂▅██▇▃                                                   
  ▂▃▄▆███████▅▃▃▂▂▂▂▁▁▂▂▂▂▂▂▂▁▂▁▁▁▁▁▁▂▁▂▂▁▁▂▁▁▁▁▁▁▁▁▁▁▁▂▁▁▁▁▂ ▃
  14.8 ns         Histogram: frequency by time        16.6 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.
"Base.Fix1{typeof(log), Int64}(log, 5)"
BenchmarkTools.Trial: 10000 samples with 1000 evaluations.
 Range (min … max):  8.230 ns … 19.890 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     8.430 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   8.455 ns ±  0.329 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

                 █▁▁▁  ▁                                      
  ▂▁▂▂▂▂▃▃▃▃█▆▇███████▇█▅▄▃▃▃▂▂▂▂▂▁▁▁▁▁▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▂▂ ▃
  8.23 ns        Histogram: frequency by time        8.92 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.
"Main.TypeAbuse.Fix{log, 5, NamedTuple()}()"
BenchmarkTools.Trial: 10000 samples with 1000 evaluations.
 Range (min … max):  14.850 ns … 25.340 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     15.080 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   15.114 ns ±  0.391 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

        ▁▃▆███▇▅▃▁                                             
  ▂▂▃▃▅▆██████████▇▅▄▃▃▂▂▂▂▂▂▁▁▂▁▁▂▂▂▁▂▂▂▂▂▂▂▂▁▁▁▁▁▁▁▁▂▁▁▁▂▁▂ ▃
  14.8 ns         Histogram: frequency by time          16 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

So Fix1 is actually fastest here:

julia> versioninfo()
Julia Version 1.11.0-DEV.269
Commit f8d46800c6c (2023-08-12 15:16 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: 24 × AMD Ryzen 9 7900X 12-Core Processor
  WORD_SIZE: 64
  LLVM: libLLVM-15.0.7 (ORCJIT, znver3)
  Threads: 34 on 24 virtual cores
Environment:
  JULIA_PKG_USE_CLI_GIT = true

Generally speaking, any possible advantage of your TyepAbuse version of Fix1 is only possible with isbits values, due to being able to use them as type parameters. This means that you’re more or less forcing the compiler to propagate these constants (or risk type instability if it can’t). There can be cases where this is faster at runtime, but don’t overdo it - the additional constant propagation can come with an increase in compilation time, if done excessively.

2 Likes
15

This REPL session should be illustrative. Start Julia with --warn-overwrite=yes (a good idea anyway) to get the “method overwritten” warning:

julia> struct S{x} end

julia> S() = S{3}()
S

julia> methods(S)
# 1 method for type constructor:
 [1] S()
     @ REPL[2]:1

julia> (::Type{S})() = S{2}()
WARNING: Method definition (::Type{Main.S{x} where x})() in module Main at REPL[2]:1 overwritten at REPL[4]:1.

Conclusion: S() = S{3}() is syntax sugar for (::Type{S})() = S{3}(). So this is a method defined on the UnionAll type.

One place where this may matter in particular is when calling functions like map with arguments that are types. map currently (it may not necessarily be a set matter) assumes that when it is given a type as the first argument, that type will be the element type of the collection. This is usually problematic when it is given an UnionAll type, because the final result ends up not being concrete.

3 Likes
16

Interesting that it’s machine-dependent! I wonder what’s going on under the hood; I somehow intuitively didn’t expect TypeAbuse.Fix could be slower than Base.Fix1, and assumed that it would at worst break even.

Generally speaking, any possible advantage of your TyepAbuse version of Fix1 is only possible with isbits values, due to being able to use them as type parameters. This means that you’re more or less forcing the compiler to propagate these constants (or risk type instability if it can’t). There can be cases where this is faster at runtime, but don’t overdo it - the additional constant propagation can come with an increase in compilation time, if done excessively.

Oh yeah, this was purely a thought exercise that I did “because it’s there” :grin: Those were the caveats I was more or less assuming it’d have, I just wasn’t sure if there would be something more (“this will summon nasal demons”). Sort of assumed not, because – as others have also pointed out here – using type parameters for storing static values is a common practice in Julia and it’s fairly visible in many packages.

Edit: I did the benchmarks without low power mode and the plain function call and the TypeAbuse.Fix call still take more or less exactly the same time, ~6ns, where Base.Fix1 is ~10ns

17

Very cool idea. Here’s one possible explanation:

julia> const f = Base.Fix1(log, 5.0)
(::Base.Fix1{typeof(log), Float64}) (generic function with 1 method)

julia> const g = TypeAbuse.Fix{log, 5.0}()
Main.TypeAbuse.Fix{log, 5.0, NamedTuple()}()

julia> @code_typed optimize=true f(0.2)
CodeInfo(
1 ─ %1 = Base.getfield(f, :x)::Float64
│   %2 = invoke Base.Math._log(y::Float64, $(QuoteNode(Val{:ℯ}()))::Val{:ℯ}, :log::Symbol)::Float64
│   %3 = invoke Base.Math._log(%1::Float64, $(QuoteNode(Val{:ℯ}()))::Val{:ℯ}, :log::Symbol)::Float64
│   %4 = Base.div_float(%2, %3)::Float64
└──      return %4
) => Float64

julia> @code_typed optimize=true g(0.2)
CodeInfo(
1 ─ %1 = Core.getfield(moreargs, 1)::Float64
│   %2 = invoke Base.Math._log(%1::Float64, $(QuoteNode(Val{:ℯ}()))::Val{:ℯ}, :log::Symbol)::Float64
│   %3 = Base.div_float(%2, 1.6094379124341003)::Float64
└──      return %3
) => Float64

In g, 5.0 is at the type level, which guarantees it’s known statically. That’s not the case in f.

This is basically pitting type-level programming against constant propagation. As I understand, this can be hard to benchmark, since the compiler is stateful. Maybe someone with a deeper understanding of the compiler can add more detail about this.

I’ve used the type-level approach before and kind of enjoy it, but there can be some problems:

  1. The compiler is not at all optimized for dealing with large numbers of types. If you had lots of different Base.Fix calls you’d probably be fine, but lots of different TypeAbuse.Fix instances would (I think) bog down the compiler.
  2. The core dev team has put lots of effort into constant propagation. As I understand, this is also ongoing work, so I think we can expect even more progress on this front. Maybe not so for type inference, at least not in the short term.

FWIW, you can get the same benefits (and potential issues) as your approach like this:

julia> using Static
[ Info: Precompiling Static [aedffcd0-7271-4cad-89d0-dc628f76c6d3]

julia> const h = Base.Fix1(log, static(5.0))
(::Base.Fix1{typeof(log), StaticFloat64{5.0}}) (generic function with 1 method)

julia> @code_typed optimize=true h(0.2)
CodeInfo(
1 ─ %1 = invoke Base.Math._log(y::Float64, $(QuoteNode(Val{:ℯ}()))::Val{:ℯ}, :log::Symbol)::Float64
│   %2 = Base.div_float(%1, 1.6094379124341003)::Float64
└──      return %2
) => Float64
4 Likes
18

Yeah I also looked at the lowered code after Benny’s earlier comment and noted the same thing, which is why it’s so surprising that on @Sukera system TypeAbuse.Fix{log, 5, NamedTuple()}() was slower than the equivalent Base.Fix1 (see benchmark code above if you want to try it out). I assumed that at worst these simple TypeAbuse.Fix uses would lower to something that’s more or less equivalent to their Base.Fix1 counterparts and have comparable performance.

My versioninfo() is:

Julia Version 1.9.3
Commit bed2cd540a (2023-08-24 14:43 UTC)
Build Info:
  Built by Homebrew (v1.9.3)

    Note: This is an unofficial build, please report bugs to the project
    responsible for this build and not to the Julia project unless you can
    reproduce the issue using official builds available at https://julialang.org/downloads

Platform Info:
  OS: macOS (arm64-apple-darwin22.4.0)
  CPU: 10 × Apple M1 Pro
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, apple-m1)
  Threads: 8 on 8 virtual cores
1 Like