Skip to content

RFC: clean up map and collect with iterator traits#15123

Closed
JeffBezanson wants to merge 27 commits intojb/generatorsfrom
jb/itertraits
Closed

RFC: clean up map and collect with iterator traits#15123
JeffBezanson wants to merge 27 commits intojb/generatorsfrom
jb/itertraits

Conversation

@JeffBezanson
Copy link
Copy Markdown
Member

@JeffBezanson JeffBezanson commented Feb 17, 2016

This is a proposal for cleaning up our iteration, mapping, and collecting. Between copy[!], collect, map, and comprehensions we had subtly different behaviors for similar operations. We also had some repeated code and inefficient generic fallbacks.

This change replaces all that with collect of various iterators. There are four core algorithms for this, based on whether an iterator has a known length/shape and whether it has a known element type. To select the right algorithm, I added some HolyTraits for iterators. I seem to recall iterator traits being discussed before, but I can't find a reference.

The biggest immediate benefit is that generic map is faster and better-typed.
Before:

julia> @time map(tuple, 11:2000000, enumerate(11:2000000));
  2.745751 seconds (18.00 M allocations: 505.257 MB, 29.04% gc time)

giving a Vector{Any}.
After:

julia> @time map(tuple, 11:2000000, enumerate(11:2000000));
  0.570696 seconds (6.00 M allocations: 198.356 MB, 11.51% gc time)

giving a Vector{Tuple{Int64,Tuple{Int64,Int64}}}.
This is achieved with the following glorious definition(s):

spread(f) = (args)->f(args...)
map(f, iters...) = collect(Generator(spread(f),zip(iters...)))

This definition is almost as fast as existing array functions:

julia> A = rand(1000,1000);

julia> @time A+A;
  0.001964 seconds (9 allocations: 7.630 MB)

julia> @time map(+,A,A);
  0.004792 seconds (11 allocations: 7.630 MB)

Hopefully this gap can be closed.

A major issue here is iterator shape preservation. Some iterators just wrap others and so should obviously preserve their shape, like Generator. Others are less obvious. Since zipped iteration is so common when working with arrays, I made zip shape-preserving. product is currently 1d only, but could for example concatenate the shapes of its component iterators.

@JeffBezanson JeffBezanson changed the title RFC: clean up map and collect RFC: clean up map and collect with iterator traits Feb 17, 2016
@tbreloff
Copy link
Copy Markdown

tbreloff commented Feb 18, 2016

+1. Does this mean we could have a correctly typed unzip as well?

On Wednesday, February 17, 2016, Jeff Bezanson notifications@github.com
wrote:

This is a proposal for cleaning up our iteration, mapping, and collecting.
Between copy[!], collect, map, and comprehensions we had subtly different
behaviors for similar operations. We also had some repeated code and
inefficient generic fallbacks.

This change replaces all that with collect of various iterators. There
are four core algorithms for this, based on whether an iterator has a known
length/shape and whether it has a known element type. To select the right
algorithm, I added some HolyTraits for iterators. I seem to recall iterator
traits being discussed before, but I can't find a reference.

The biggest immediate benefit is that generic map is faster and
better-typed.
Before:

julia> @time map(tuple, 11:2000000, enumerate(11:2000000));
2.745751 seconds (18.00 M allocations: 505.257 MB, 29.04% gc time)

giving a Vector{Any}.
After:

julia> @time map(tuple, 11:2000000, enumerate(11:2000000));
0.570696 seconds (6.00 M allocations: 198.356 MB, 11.51% gc time)

giving a Vector{Tuple{Int64,Tuple{Int64,Int64}}}.
This is achieved with the following glorious definition(s):

spread(f) = (args)->f(args...)
map(f, iters...) = collect(Generator(spread(f),zip(iters...)))

This definition is almost as fast as existing array functions:

julia> A = rand(1000,1000);

julia> @time A+A;
0.001964 seconds (9 allocations: 7.630 MB)

julia> @time map(+,A,A);
0.004792 seconds (11 allocations: 7.630 MB)

Hopefully this gap can be closed.

A major issue here is iterator shape preservation. Some iterators just
wrap others and so should obviously preserve their shape, like Generator.
Others are less obvious. Since zipped iteration is so common when working
with arrays, I made zip shape-preserving. product is currently 1d only,

but could for example concatenate the shapes of its component iterators.

You can view, comment on, or merge this pull request online at:

#15123
Commit Summary

  • make map and collect more general and uniform by adding iterator
    traits

File Changes

Patch Links:

—
Reply to this email directly or view it on GitHub
#15123.

StefanKarpinski and others added 10 commits February 17, 2016 19:22
@StefanKarpinski
Merge pull request #15122 from JuliaLang/sk/envtweaks
73950bf 
some tweaks to code for the EnvHash type
@andreasnoack
Reenable test of condition number estimates of sparse matrices
8536c88 
and adjurst the tolerance. Fixes #14778
@JeffBezanson
Merge pull request #15124 from JuliaLang/jb/parsefaster2
ba8e972 
a few more micro-optimizations to parsing
@tkelman
Merge pull request #15125 from Cody-G/cjg/fix_mmap_win
fabec7b 
patches #13682 to fix memory mapping of large files on Windows
@helgee
Clarify section about Base.convert fall-back.
8a02b3f
@helgee
Remove trailing whitespace.
200fcdf
@mbauman
Merge pull request #15104 from KristofferC/kc/sparse_copy
84e0a18 
add specialized copy! for sparse matrices
added os_only documentation
0b9041a
@StefanKarpinski
mmap: remove unnecessary use of utf16
008cf23
@JeffBezanson
Merge pull request #15132 from helgee/master
fc799c3 
[WIP] Clarify section about Base.convert fall-back.
@JeffBezanson JeffBezanson mentioned this pull request Feb 18, 2016
Merged
@justbur
julia-mode: Fix prompt regexp
400710c 
Fixes #14002

The primary problem was the lack of a space at the end of the regexp,
which didn't match the output of the shell process (does have a space).
This meant that emacs sometimes placed the point one character before
the end of the buffer, which prevented M-p from working.

This new regexp also allows for other prompts, such as "shell> "
yuyichao and others added 3 commits February 18, 2016 13:00
@yuyichao
Merge pull request #15135 from justbur/julia-mode-fix-prompt
7220389 
julia-mode: Add space to prompt regexp
@tkelman
Merge pull request #15108 from morris25/add_os_only_documentation
279586b 
RFC: added os_only documentation
@andreasnoack
Merge pull request #15113 from JuliaLang/anj/cond
04f208f 
Reenable test of condition number estimates of sparse matrices
@JeffBezanson JeffBezanson mentioned this pull request Feb 19, 2016
Merged
@JeffBezanson JeffBezanson mentioned this pull request Mar 1, 2016
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.