Fix Constructor performance by removing runtime cost of applicable

[NHDaly]

So there's this problem, well described by @omus here:
#30

TLDR, constructing these is way slower than it needs to be. It should be the same speed as regular ints, but it isn't:

julia> function _test(max)
         FD_t = FixedPointDecimals.FixedDecimal{Int64, 0}
         sum(1:10)
         sum(FD_t(1):FD_t(10))
         @time X = collect(1:max)
         @time sum(X)
         @time Y = collect(FD_t(1) : FD_t(max))
         @time sum(Y)
         nothing
       end
>> _test (generic function with 1 method)

julia> _test(1)  # warmup
...

julia> _test(10_000_000)
  0.114792 seconds (2 allocations: 76.294 MiB, 60.54% gc time)
  0.006643 seconds
  4.474370 seconds (2 allocations: 76.294 MiB, 0.31% gc time)
  0.504544 seconds

I opened and closed a bunch of PRs here so I could discuss other alternatives we might consider, but I currently think this one is best:
#34

[NHDaly]

This PR shows that it is indeed applicable that's the problem. If we simply hard-cod this function to only work on types where we know typemax is defined, we can remove that check, and it works great, but of course it's not at all extensible:
#31

This one is the same as Curtis's: we just @eval a bunch of definitions for types that need it. But I don't like that users have to @eval more function definitions if they want to add a custom type. it feels hacky.
#32

After reading @oxinabox's awesome blog post here:
https://white.ucc.asn.au/2018/10/03/Dispatch,-Traits-and-Metaprogramming-Over-Reflection.html
I realized that Holy Traits are exactly what we want -- a declarative way to say "my type supports this thing!" So that's this PR:
#33

I think that's a good solution for this problem generally. But actually, in this case, i think we can get away with just removing applicable entirely:
#34

I think that PR is probably how we should move forward! :) What do you think?

[omus]

As @KristofferC pointed out we can't really rely on isbitstype as proposed in #34.

Traits would be a good solution here but without native support in Julia I think a cleaner solution would be to make a Base PR which defines:

typemax(::Type{BigInt}) = nothing
typemin(::Type{BigInt}) = nothing

Having these methods would allow us to call typemax without the risk of encountering a MethodError.

[NHDaly]

Ah yeah i think that's probably right unfortunately..

Having these methods would allow us to call typemax without the risk of encountering a MethodError.

Mmm yes i like that approach. That seems reasonable! And in the meantime, we could define those ourselves, in this package.

Crazy question: is there anything wrong with a MethodError? Does it even make sense to have an unbounded type in a "Fixed" Point Decimal?

[omus]

Mmm yes i like that approach. That seems reasonable! And in the meantime, we could define those ourselves, in this package.

If we define these methods in FixedPointDecimals we'll have a method redefinition warning when/if they get merged into Base. I'd rather keep things the way they are in #30 and once they're merged in base we can add those methods here but with an appropriate VERSION check.

[omus]

Crazy question: is there anything wrong with a MethodError? Does it even make sense to have an unbounded type in a "Fixed" Point Decimal?

The storage type used by FixedDecimal isn't the part that is fixed. You can use use whatever Integer type you want to store the underlying value. It's up to the user of this package to pick a efficient storage type. For example:

julia> FixedDecimal{Int128,2}(1.234567)
FixedDecimal{Int128,2}(1.23)

Having an unbounded type as the storage just allows you to make as high precision values if you want:

julia> parse(FixedDecimal{BigInt,100}, "0." * "9"^100)
FixedDecimal{BigInt,100}(0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999)

[NHDaly]

Okay i think that makes sense. Thanks.

I'd rather keep things the way they are in #30
Okay, i can see that it's better not to do the typemax definitions here until that's decided in Base.

That said, then, I actually still think I prefer the traits based solution in #33 to #30.
I have updated it to simplify the API a bit, would you mind taking another look?

My specific concerns with the @eval solution are two fold:

1. It seems weird to ask users to eval a new method on a function defined in the other module. I know that it's different than evaling into a Module, but at first glance it really looks like it, and that's something you're not supposed to do:

   @eval FixedPointDecimals.max_exp10(::Type{MyInt}) = $(FixedPointDecimals.max_exp10(MyInt))

2. I don't like that we're exposing max_exp10 as the interface for adding new types, and asking them to really understand its implementation when deciding whether to set its value to $(FixedPointDecimals.max_exp10(MyInt)) or -1.

   Arguably max_exp10 is part of the implementation, and now it's being exposed as a necessary part of the interface. Instead, in Fix constructor performance via Holy Traits. #33, I think there's a nice, easy to consume interface: int_type_doesnt_overflow (the name is open to bikeshedding).

I like that the traits solution adds a clear, and declarative interface for adding your custom type. I do agree that it's a bit verbose, but I think I've it a bit simpler by making the trait types simply Val{true} and Val{false}, so the user only needs to write int_type_doesnt_overflow(::Type{MyType}) = true.

[TotalVerb]

@NHDaly on an unrelated note to the substance of your post itself, why did you close your PR #33?

I prefer @omus's PR to base: https://github.com/JuliaLang/julia/pull/29815/files
which seems to me the most generic and easy-to-extend solution in the long run. The solution of #30 seems reasonable in the short run.

[NHDaly]

Yeah, i think the Base PR is good. I'm happy with how #30 turned out, so it's all fine. I didn't really like the @eval approach, but I think where we ended up is great. :)

@NHDaly on an unrelated note to the substance of your post itself, why did you close your PR #33?

Hmm, I meant to reopen it, and i thought I did... I originally closed it because I was advocating for #34 instead. But after Kristoffer explained why it doesn't work, I meant to reopen it when i made the above post.

I don't want to open a new one now, because i think i've made enough noise on this repo today (sorry about all that, btw), but here's the final version of the Traits changes I was proposing:
https://github.com/JuliaMath/FixedPointDecimals.jl/compare/master...NHDaly:traits?expand=1

But yeah, i'm happy with #30. Thanks again everyone! :)

[omus]

Looks like we'll be waiting for applicable to be fast for the long term solution.

[ghost]

Sounds great. Thanks again Curtis! :)

i'll close this for now. feel free to reopen if you were using it to track the future dependent change on applicable.