-
-
Notifications
You must be signed in to change notification settings - Fork 5.5k
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
Julep: Revised iteration protocol #18823
Comments
👍 I think your conditions in your lowering should be
|
Yes, you're right. Fixing. |
Needing to write the type of the state that would be returned is a slight problem. Returning |
Since the nullable is not really visible to users of the API, maybe the answer is no? |
Though if we're willing to go the type unstable way, we could just use the empty tuple to indicate the end and avoid having to declare type parameters entirely |
A small question/comment: I think As regards type stability, you can always declare the method's return type via Finally, @davidagold recently added an |
Corrections made. Yes, the return type annotation is a good point. But still, having to spell out that type is annoying. |
Upon further discussion, it seems that we may be ok with having That proposal would work especially nicely with the proposed syntax for a
As a side note, one interesting aspect of this proposal is that the state now is the index of the last access element rather than the state of the next element as it was with the old iteration protocol. |
Advantage: never having to return invalid state. |
Thanks for writing this up! Would we need |
Fast enough not to hinder vectorization? For example, things like this use SIMD instructions currently, and it would be too bad to lose this: function mysum(X::AbstractArray)
s = zero(eltype(X))
@inbounds for x in X
s += x
end
s
end |
FWIW another approach to avoid the need for explicit return-type declarations would be to have a function-wise declaration which would apply to all methods: function step{T}(itr, state::T)::Nullable{Tuple{eltype(itr), T}} end Cf. @StefanKarpinski's recent post. |
That doesn't work because the state may change type. |
cross-referencing the related #16878 |
Unlikely to happen by end-of-year feature freeze? |
I think sometime shortly after v0.6 is branched we can go ahead and implement this Julep:
Where the lowering of a for-loop would look like: let state = iterate(x)
while !(state === done)
body(state[1])
state = iterate(x, state[2])
end
end The codegen for this is already looking pretty good. |
That's awesome. I noted a couple of days ago that #9080 also seems less severe (but still not perfect), and specifically that the test case in #16035 (comment) seems fixed. (With recent PRs, the situation might be even better still.) |
Returning the |
This handles that case just fine (return values of |
Right, the terminal value is a state object, not a yielded object. So I guess this pattern would imply that the |
Why not just use |
|
To test this design I'd like to see implementations of the product, flatten, and filter iterators --- those being some of the trickiest and most important. Ideally we could get nicer code and better performance. |
And, looks like I just volunteered to do that :) |
I tried this, and ran into a current show-stopping optimization miss. It appears we will need some way to elide allocation of the tuple in types like: |
Sorry to reopen this issue: Could one of the core developers post the appropriate |
You can use |
We discussed at JuliaCon what to do about #8149. I'm opening this issue to capture the specific design proposed at JuliaCon (and so that others can make corrections about things I misremembered).
The new iteration protocol
In the new iteration protocol, there's only one function to be overloaded:
with for loops getting lowered as:
equivalent to
Implementation
This takes care of iterators that don't know whether they're done until trying (just return
Nullable{typeof(state}()
). One concern with this approach (and approaches like it) was whether there would be an extra allocation and branch, which would be an unacceptable performance regression. (Added in EDIT by @timholy: #16035 (comment) and #9080.) The conclusion we came to was that the compiler should be able to optimize this out. To make sure that this happens, we may want to use a slightly different lowering, such as:The motivation for structuring things that way, is that simple step functions where performance really matters probably look something like:
which after inlining, should make this a fairly straightforward jump threading optimization (if the optimization doesn't happen we should figure out why and fix that).
Migration
Another nice property of this proposal is that it's backwards compatible with the existing scheme. The fallback method is simply:
Now, the
Nullable{Any,}
in there is not ideal, but forced inlining together with allocation elision should be able to handle that just fine (otherwise we could also doNullable{eltype(it),...}
, which should work also, but has slightly greater risk of breaking).cc @timholy @JeffBezanson - Please add anything I missed
The text was updated successfully, but these errors were encountered: