Skip to content

More robust iteration over Vectors#27079

Merged
mbauman merged 3 commits intomasterfrom
mb/iterableresize
May 15, 2018
Merged

More robust iteration over Vectors#27079
mbauman merged 3 commits intomasterfrom
mb/iterableresize

Conversation

@mbauman
Copy link
Copy Markdown
Member

@mbauman mbauman commented May 11, 2018

Currently, if a vector is resized in the midst of iteration, then done might "miss" the end of iteration. This trivially changes the definition to catch such a case. I am not sure what guarantees we make about mutating iterables during iteration, but this seems simple and easy to support. Note, though, that it is somewhat tricky: until #13866 we used i > length(a), but that foils vectorization due to the typemax case. This definition seems to get the best of both worlds. For a definition like f below, this new definition just requires one extra add i64 operation in the preamble (before the loop). Everything else is identical to master.

function f(A)
    r = 0
    @inbounds for x in A
        r += x
    end
    r
end

Motivated by https://stackoverflow.com/questions/50297791/julia-boundserror-when-deleting-items-of-a-list-while-iterating-over-it

@mbauman
Copy link
Copy Markdown
Member Author

mbauman commented May 11, 2018

Of course:

@nanosoldier runbenchmarks(ALL, vs = ":master")

@mbauman mbauman added the arrays [a, r, r, a, y, s] label May 11, 2018
@nanosoldier
Copy link
Copy Markdown
Collaborator

nanosoldier commented May 12, 2018

Your benchmark job has completed - possible performance regressions were detected. A full report can be found here. cc @ararslan

@mbauman
Copy link
Copy Markdown
Member Author

mbauman commented May 14, 2018 •
edited
Loading

The regressions in any/all that Nanosoldier flagged are indeed real and I can reproduce them locally. The only difference within the loop of the generated LLVM is using an icmp sgt i64 instead of a icmp eq i64 — as I'd expect (side-by-side with most lineloc comments removed). It appears as though that's significantly more expensive operation? These cases are definitely the absolute worst case since their loops do nothing but iteration and a test. Anything more trivial and it'll get optimized away. If the loop doesn't have a break and you throw an @inbounds on it, then it'll get vectorized and see the same performance as the current setup on master.

That said, all and any are still 4x slower than mapreduce(f, &, …) in the cases where they don't short-circuit due to SIMD-ificability without the breaks. Could we use VecElement here to do the breaks in groups of 4?

In any case, I still think think this is worth doing as it adds a layer of protection if we decide to go in on the unsafe-iteration-by-default-when-guaranteed-by-lowering.

@mbauman
Copy link
Copy Markdown
Member Author

mbauman commented May 14, 2018

Oh, of course, I cannot test for vectorization on CI because of --check-bounds=yes.

mbauman added 3 commits May 14, 2018 18:26
@mbauman
More robust iteration over Vectors
e2098ac 
Currently, if a vector is resized in the midst of iteration, then `done` might "miss" the end of iteration. This trivially changes the definition to catch such a case. I am not sure what guarantees we make about mutating iterables during iteration, but this seems simple and easy to support.  Note, though, that it is somewhat tricky: until #13866 we used `i > length(a)`, but that foils vectorization due to the `typemax` case. This definition seems to get the best of both worlds. For a definition like `f` below, this new definition just requires one extra `add i64` operation in the preamble (before the loop). Everything else is identical to master.

```julia
function f(A)
    r = 0
    @inbounds for x in A
        r += x
    end
    r
end
```
@mbauman
Add InteractiveUtils to arrayops to allow testing code_llvm
b880403
@mbauman
Move vectorizability test to boundscheck_exec.jl
bfd8462
@mbauman mbauman force-pushed the mb/iterableresize branch from d13c26f to bfd8462 Compare May 14, 2018 22:42
@mbauman
Copy link
Copy Markdown
Member Author

mbauman commented May 15, 2018

FreeBSD failed with a

Error in testset LibGit2/libgit2:
Error During Test at /usr/home/julia/julia-fbsd-buildbot/worker/11rel-amd64/build/usr/share/julia/stdlib/v0.7/LibGit2/test/libgit2.jl:2344
  Got exception ErrorException(...) outside of a @test
  Could not locate challenge: "Private key location for 'git@github.com':". Process output found:

And macOS was #26725.

@mbauman mbauman merged commit eebeaa9 into master May 15, 2018
@mbauman mbauman deleted the mb/iterableresize branch May 15, 2018 15:24
This was referenced Jun 2, 2018
Closed
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@StefanKarpinski StefanKarpinski StefanKarpinski approved these changes

@Keno Keno Keno approved these changes

Assignees

No one assigned

Labels

arrays [a, r, r, a, y, s]

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@mbauman @nanosoldier @StefanKarpinski @Keno