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.

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

RFC: lower x^literal as x^Val{literal} for integer literals #20530

Merged
merged 8 commits into from
Feb 16, 2017

Conversation

stevengj
Copy link
Member

@stevengj stevengj commented Feb 8, 2017

As discussed in #20527.

This PR doesn't change any behaviors or implement any optimizations for small powers yet — it just falls through to the generic ^ for now — but there are a number of improvements that would be easy to add (in separate PRs, probably) if this is merged.

@stevengj stevengj added needs decision A decision on this change is needed maths Mathematical functions needs docs Documentation for this change is required parser Language parsing and surface syntax labels Feb 8, 2017
@stevengj stevengj changed the title lower x^literal as x^Val{literal} for small integer literals RFC: lower x^literal as x^Val{literal} for small integer literals Feb 8, 2017
src/ast.c Outdated
return fl_ctx->T;
else if (iscvalue(args[0]) && fl_ctx->jl_sym == cv_type((cvalue_t*)ptr(args[0]))) {
jl_value_t *v = *(jl_value_t**)cptr(args[0]);
if (jl_is_long(v) && jl_unbox_long(v) < 32 && jl_unbox_long(v) > -32)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I believe small julia Ints get mapped to fixnums, so this should not be necessary.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I was thinking about metaprogramming where someone splices a value into an expression

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The representation should be the same in that case. It would be an issue for splicing other integer types, though, but that's difficult to handle in general.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Oh, right, julia_to_scm does that transformation automatically. Great, this PR will get shorter!

@stevengj stevengj changed the title RFC: lower x^literal as x^Val{literal} for small integer literals RFC: lower x^literal as x^Val{literal} for integer literals Feb 8, 2017
@JeffBezanson
Copy link
Member

With this, we might be able to remove the custom inlining code for ^, which is pretty nasty. cc @vtjnash

@stevengj stevengj removed the needs docs Documentation for this change is required label Feb 9, 2017
@@ -253,6 +253,11 @@ end

Exponentiation operator. If `x` is a matrix, computes matrix exponentiation.

If `y` is an `Int` literal (e.g. `x^2` or `x^-3`), the Julia code
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

"(e.g. 2 in x^2 or -3 in x^-3)," ?

@andyferris
Copy link
Member

Could this be made more powerful/useful as a step in inference? That is, have the transformation made for any constant exponent, rather than just literal?

Yes, it would be a bit more magical, but it would also be a bit more powerful/generic.

@stevengj
Copy link
Member Author

stevengj commented Feb 10, 2017

@andyferris, seems like a lot of effort for little payoff. How often does one do const two = 2 and then use x^two instead of x^2? Moreover, I'm skeptical that we want to do this for non-integer exponents.

Right now, this is merely syntactic sugar. Making it something "more magical" that occurs later in compilation would be a more invasive change in the language.

@andyferris
Copy link
Member

That's fair enough (I would only ask it to do this for constant integers). The thought for me was you might have dimensionful packages call exponentiation programmatically with type parameter constants as exponents e.g. when converting metric to imperial, etc. But it's not a big deal if these are a bit slower, and I can't estimate if inference transformations are harder to implement than lisp ones, and more magical = bad, for sure.

@stevengj
Copy link
Member Author

stevengj commented Feb 10, 2017

@andyferris, that's a good point, but they can still use this PR as-is for type parameters via generated functions. Note also that if you do miles_to_km(x::Miles{n}) = Kilometers{n}(x.val * kmpermile^Val{n}} it will work too. (Though in that application you can use e.g. a generated function and avoid the runtime exponentiation completely.)

@StefanKarpinski
Copy link
Member

StefanKarpinski commented Feb 10, 2017

To me the fact that this is only for literal exponents is a feature – it keeps the rule simple: exponentiation by an integer literal means one thing; exponentiation by anything else (constant, variable, expression, whatever) means something else. The fact that this fairly simple distinction addresses the vast majority of the pain we've encountered over the years from ^ is the appeal.

@andyferris
Copy link
Member

Simple rules are always best.

Does this expand out automatically for v.^5 and so on? Seems like that would present a similar performance and inferability bottleneck.

@stevengj
Copy link
Member Author

stevengj commented Feb 13, 2017

@andyferris, yes, see the test.

What happens is that literal arguments are already inlined in dot calls, so v.^5 was getting converted to broadcast(x -> x^5, v) during lowering. As a result, the x^5 in the anonymous function now gets converted to x^Val{5} without requiring any special case for .^.

@andyferris
Copy link
Member

Awesome, thanks for the clarification.

@stevengj stevengj added this to the 0.6.0 milestone Feb 13, 2017
@stevengj
Copy link
Member Author

Can we get a decision on this for 0.6?

@tkelman
Copy link
Contributor

tkelman commented Feb 13, 2017

I share @vtjnash's reservations on this (it may conflict with #19890), and dislike giving literals special treatment.

@stevengj
Copy link
Member Author

stevengj commented Feb 13, 2017

(I don't see any conflict with #19890 ... whether to do anything special for float^literal is entirely orthogonal to this PR. We could still decide to call powf unless @fastmath is enabled, for example. And we could still inline cases that are currently calling power_by_squaring, like complex^literal or int^literal. And there is still the inference benefit for Unitful, and the ability to do integer^-1 etc.)

@tkelman
Copy link
Contributor

tkelman commented Feb 13, 2017

Having x^(-2) work dramatically better than p=-2; x^p and give potentially different behavior in some package would be rather surprising. There's a semantic red flag this is raising to me (would you call this referential transparency?)

@ajkeller34
Copy link
Contributor

@tkelman I share your concerns about referential transparency, but I think the pros outweigh the cons here. @stevengj has listed several tangible benefits of this PR and I think the disadvantages you point out could be mitigated in documentation.

Could PackageEvaluator be run to see if any packages are impacted by the changes in this PR? If few or none of them are, then that seems like useful data to have before making a final decision.

@stevengj
Copy link
Member Author

@ajkeller34, this particular PR shouldn't affect any package, because x^Val{p} simply calls x^p in all cases at the moment.

@vtjnash
Copy link
Member

vtjnash commented Feb 13, 2017

I think the disadvantages you point out could be mitigated in documentation

Stefan mentioned this too. To me, this sounds like a significant con (that the behavior is sufficiently surprising it requires extra documentation on pow). And it also makes understanding how to call/overload pow take more effort.

There's a substantial amount a language can do by pattern matching input rather than doing dispatch. But I don't think we should go down that route.

@martinholters
Copy link
Member

What if we don't do any special parsing but still go ahead and do something useful for x^Val{n}? Yes, writing out x^Val{-2} is longer than just x^-2, but it's absolutely non-magic (and that's supposed to be a pro in this context).

@KristofferC
Copy link
Member

KristofferC commented Feb 15, 2017

@valify x^2 + x^-3

@stevengj
Copy link
Member Author

stevengj commented Feb 15, 2017

@martinholters, explaining to users that they have to use x^Val{-2} or @valify x^-2 to do what they want would be a huge wart on the language, in my opinion.

Explaining about x^Val{p} to the tiny minority of users who want to override ^ for new numeric types (which tend to be defined by only the most sophisticated developers) seems like not such a huge deal. (Overriding ^ for non-numeric types will still be able to just override ^(x, p), since in those cases ^(x, Val{p}) will probably call the fallback.)

@StefanKarpinski
Copy link
Member

@stevengj: since this has passed CI, you could just merge it and add text in NEWS saying that it's an experimental feature in a separate PR, or add a [ci skip] commit to this PR – your call.

@vtjnash
Copy link
Member

vtjnash commented Feb 17, 2017

It looks like this hurt performance of several benchmarks (I'm guessing, but this seems to be the only commit that changed code). I suspect that this may be blocking inlining now in some cases. I suspect it will also will be hiding x^2 from inlining as x*x right now.

@tkelman
Copy link
Contributor

tkelman commented Feb 17, 2017

probably shouldn't have assumed this wouldn't cost anything without verifying as much. 3x slowdown on several of the benchmarls is a substantial argument against doing this.

@stevengj
Copy link
Member Author

Would it fix it just to put @inline in front of the fallback definition?

@stevengj
Copy link
Member Author

@tkelman, it's not really a "substantial argument" if it is easily fixed, as I'm sure that it is. (On the contrary, this approach allows us to easily do more inlining if we want.)

@tkelman
Copy link
Contributor

tkelman commented Feb 17, 2017

until it's fixed it's a noticeable performance regression. if simple, fine, but the existing logic in inference isn't simple and this shouldn't break it without a more general replacement

@stevengj
Copy link
Member Author

The existing logic isn't simple, but the new logic in terms of Val should simple; it shouldn't require me to touch inference.jl at all, I think. I'll push a PR.

@stevengj
Copy link
Member Author

I've pushed a PR with a "more general replacement" as requested.

@tkelman
Copy link
Contributor

tkelman commented Feb 17, 2017

it's less general if inference can currently handle non-literal constants

@stevengj
Copy link
Member Author

stevengj commented Feb 17, 2017

That case is still handled by inference.jl, since non-literal constants are not lowered to x^Val{p}.

# x^p for any literal integer p is lowered to x^Val{p},
# to enable compile-time optimizations specialized to p.
# However, we still need a fallback that calls the general ^:
^{p}(x, ::Type{Val{p}}) = x^p
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

How about we rewrite this as ^(x, p) = internal_pow(x, p) and then dispatch on Val in internal_pow? I ask because this is going to be a magnet for ambiguities since packages are likely to specialize on the first argument. E.g., PainterQubits/Unitful.jl#54

Copy link
Member Author

@stevengj stevengj Feb 17, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Unitful will maybe want to write its own ^(x, Val{p}) methods that are type-stable anyway, however, so in this case the ambiguity warning is helpful.

Copy link
Member Author

@stevengj stevengj Feb 17, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

But I guess it doesn't hurt to do this, and it may be helpful in other cases?

Copy link
Member Author

@stevengj stevengj Feb 17, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I dunno, the more I think about it the more I think that the ambiguity warning is actually helpful here. Particularly if we start inlining x^Val{p}, anyone specializing purely on the first argument (and not restricting to p::Number, as most types would) will want to explicitly decide what to do for the Val{p} case.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

these won't be warnings any more, they'll be errors the first time someone happens to call the ambiguous signature, unless you're going out of your way to check for ambiguities

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Unitful wasn't even getting through precompilation, because some of these run at build time and the ambiguity error kicks in. These are fixable errors, as witnessed by that PR, but I don't personally see much downside to engineering the dispatch chain to avoid breakage.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The downside is that packages that really should be thinking about doing something different for Val{p} will get no warning of the change.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

But I don't feel strongly about this; I've updated #20648 to use internal_pow as you suggest.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
maths Mathematical functions needs decision A decision on this change is needed parser Language parsing and surface syntax
Projects
None yet
Development

Successfully merging this pull request may close these issues.