Experiments with generators

[Matt Bauman]

I've been playing around with an implementation of a Generator.  It was surprisingly easy to add the required syntax and just a few methods to get lots of cool functionality.  But I'm probably not the one who should be adding this kind of core functionality to Julia.

Some cool results:

julia> Dict(("$i*$j", i*j) for i in 1:3, j in 9:10)

["2*9"=>18,"3*10"=>30,"1*10"=>10,"3*9"=>27,"2*10"=>20,"1*9"=>9]

julia> typeof(ans)

Dict{Union(UTF8String,ASCIIString),Int64} (constructor with 3 methods)

julia> g = (i*j for i = 2:2:10, j=1:2:10)

5x5 Generator{Int64,2}: (i * j for i = 2:2:10, j = 1:2:10)

julia> sum(g)

750

julia> full(g)

5x5 Array{Int64,2}:

  2   6  10  14  18

  4  12  20  28  36

  6  18  30  42  54

  8  24  40  56  72

 10  30  50  70  90

julia> ntuple(i*2 for i = -5:5)

(-10,-8,-6,-4,-2,0,2,4,6,8,10)

Some thoughts:

I think it makes sense to have generators be abstract arrays to work with the multidimensional comprehension syntax.  The python-esque way would be to use a Task that's just a one-shot, but that's not compatible with multiple dimensions.  I suppose generators could be restricted to just a one-dimensional iterable task, but that seems like a sliver of what they could be.

It's awesome to be able to specify generators without extra parentheses in function calls.  But then there's a disconnect in my simple implementation: the commas get parsed as part of the generator, not as an argument seperator  (so sum(i for i in 1:2, 1) is an invalid iteration specification).  Should we require parens for multiple args or multiple iterables in the generator?  I'm leaning towards the latter, but it'll take a bit of work.

The implementation:

I changed the scheme syntax to simply emit a macrocall upon finding the generator syntax. Within that macro, I used @simonster's wonderful return_types PR to simplify grabbing the element type and it worked just as prescribed.  An anonymous function created by the macro grabs the closure and defers evaluation.

Performance:

Well, that's why this isn't a PR.  Calling the anonymous function and the multiple indexing required (without help from @inbounds) means that this is about 10-20x slower than just creating the array… and there's lots of small allocations (I think in the field and iterable indexing).  And array accesses are just so darn fast in Julia.  E.g., 

julia> sum(i for i=1:1); @time sum(i for i=1:100000000)

elapsed time: 7.959239089 seconds (3199996408 bytes allocated)

5000000050000000

julia> sum([i for i=1:1]); @time sum([i for i=1:100000000])

elapsed time: 0.816201815 seconds (800000048 bytes allocated)

5000000050000000

Anyhow, this was a fun weekend project.  I'm excited to see Generators become a part of Julia, but I'm not sure how one might improve the performance here.  Here's the branch: https://github.com/mbauman/julia/compare/JuliaLang:master...mbauman:generators

[Kevin Squire]

Hi Matt, 

I plan to take a look, but I probably don't know enough about the Julia back end to add anything constructive.  I would like to say that 1) I'm impressed that you got this up and running, and 2) I would love to see this functionality in Julia. 

See also:

http://stackoverflow.com/questions/17516250/is-there-a-way-to-avoid-creating-an-array-in-this-julia-expression

https://github.com/JuliaLang/julia/issues/550

Cheers,

  Kevin

[Matt Bauman]

On Sunday, May 4, 2014 10:12:34 PM UTC-4, Kevin Squire wrote:

Hi Matt, 

I plan to take a look, but I probably don't know enough about the Julia back end to add anything constructive.  I would like to say that 1) I'm impressed that you got this up and running, and 2) I would love to see this functionality in Julia. 

The best part about this is that the "back end" changes are so minimal (it's just 15 lines of code).  It's just a handful of lines that punt to a real Julia macro — which can be trivially changed to test out different implementations.

I hadn't seen Stefan's SO answer before — it's great. The task idea is so much simpler but loses the multidimensional information.  We can test it very easily it on my branch (with only support for one dimension for now):

julia> macro generator(thunk, assgn)
         esc(quote
           @task for $(assgn.args[1]) = $(assgn.args[2]); produce(($thunk)); end;
         end)
       end

julia> sum(i for i=1:1); @time sum(i for i=1:100000000)

elapsed time: 72.190015069 seconds (3200067900 bytes allocated)
5000000050000000

Of course, this has the semantics and control flow that may be more desirable.  Perhaps it can be made to run faster, too.

(One thing that I failed to note in my original post: The {base,test}/generator.jl files aren't aggregated with the rest of {base,test}.  You must include them manually, which allows for rapid iteration without rebuilding the sysimg).

[Jeff Bezanson]

This is very good. I certainly want to add this feature. We should be
able to get much better performance with the following approach:

1. The function part should look like (x::T)->(...), where T is the
element type of the iterable (considering only the 1d case for now)
2. Use static_typeof on the body of the function to provide the type
parameter for the Generator. This is the secret feature used by
comprehensions.

This will be a bit tricky and could certainly use better language
support. One thing that would work is to add function types (e.g.
`Int-->Int`) for anonymous functions, or generally for functions with
a single definition. The single definition part is key; I don't
believe there is a really nice way to make this work with generic
functions. This is because generic functions multiply-inherit many
function signatures, so almost any dispatch you try to do with them is
ambiguous.

[Steven G. Johnson]

See also

    https://github.com/JuliaLang/julia/issues/4470

[Matt Bauman]

On Monday, May 5, 2014 4:39:20 PM UTC-4, Jeff Bezanson wrote:

This is very good. I certainly want to add this feature. We should be
able to get much better performance with the following approach:

1. The function part should look like (x::T)->(...), where T is the
element type of the iterable (considering only the 1d case for now)
2. Use static_typeof on the body of the function to provide the type
parameter for the Generator. This is the secret feature used by
comprehensions.

Thanks for the feedback, Jeff.  I figured I was effectively doing static_typeof by using the return_type function from https://github.com/JuliaLang/julia/pull/6692 (I quickly learned the basics of femtolisp, but the Julia-interaction syntax is still a bit above my head).  But I had a type-instability before in the return from the anonymous function. Adding type asserts to the result fixed that and led to a 2x speed increase (and a corresponding 2x decrease in allocations).  So it's doing better now, but there's still ~16 bytes getting allocated on each loop.  Might this be boxing between the anonymous function call and the type assertion?  Here's a simple test case (with very similar performance):

julia> f(v,n) = (z = 0; for i=1:n; z+=v(i)::Int; end; z)
f (generic function with 1 method)

julia> f(i->i, 1); @time f(i->i, 100_000_000)
elapsed time: 3.585196659 seconds (1599992896 bytes allocated)
5000000050000000

Unfortunately, typing the arguments in the anonymous function as you suggested makes the performance and allocations worse again (but there's something more complicated going on here, as it has no effect in the above testcase):

julia> macro generator(thunk, assignment)
         arg = assignment.args[1]
         itr = assignment.args[2]
         esc(quote
           Generator("",($arg::eltype($itr)) -> ($thunk), ($itr,))
         end)
       end

julia> sum(i for i=1:1); @time sum(i for i=1:100_000_000)
elapsed time: 12.632105811 seconds (4000010452 bytes allocated)
5000000050000000

Matt

[Jeff Bezanson]

The type declaration will probably need to be something easier to
statically evaluate than `eltype(x)`. Or better still we should try to
improve the compiler to deal with this.

[Gustavo Lacerda]

Are we planning to add generators (lazy list comprehensions)? Matt
Bauman's results look cool.

Gustavo

On Tue, May 6, 2014 at 4:09 PM, Matt Bauman <mba...@gmail.com> wrote:

[Stefan Karpinski]

Yes, that's a desired feature. The idea would be that e.g. sum(x^2 for x in v) would be the equivalent of sum([x^2 for x in v]) but without having to materialize the array.

[Gustavo Lacerda]

methods(sum) tells me that sum is not defined for iterators yet.

It would be nice if reduce functions (like sum) can be implemented
only once. Is there a type that generalizes lists and iterators?
Iterable?

[Matt Bauman]

The catch-all method `sum(a) at reduce.jl:234` is effectively the iterator implementation. It simply expects that its arguments will have start, next and done methods defined.  Since there's no formal interfaces, and so there's no way of specifying that an argument must support the (currently informal) iteration protocol.

I think one of the big things holding back efficient generators (as I had implemented it) is the overhead of anonymous functions. See: https://github.com/JuliaLang/julia/issues/1864

[Steven G. Johnson]

On Wednesday, July 9, 2014 2:21:22 PM UTC-4, Stefan Karpinski wrote:

Yes, that's a desired feature. The idea would be that e.g. sum(x^2 for x in v) would be the equivalent of sum([x^2 for x in v]) but without having to materialize the array.

Note that this is issue #4470: https://github.com/JuliaLang/julia/issues/4470 

[Steven G. Johnson]

(Whoops, I just noticed I posted the issue link twice.)

[Ivar Nesje]

It would be nice if reduce functions (like sum) can be implemented only once. 

Unfortunately that is not a good idea, because in some cases we want to use better algorithms than the general iterator version. For example; addition of floating point numbers accumulates error, and for containers that support fast random access, we use an algorithm that reduces the numeric noise. For performance we might decide to use multiple threads or special processor instructions, that does not work with general iterables. The great thing about Julia is that that we can have different implementations that specialize for the argument type and you should be able to trust that we have had a discussion and picked the best algorithm for your case with regards to performance and accuracy. If you really need high performance or accuracy, you can see that we have sum_kbn for high accuracy, or profile different solutions to find the most optimal performance for your specific case.

Ivar

[Jeff Bezanson]

Just bumping this thread since I'd like to get this in 0.4. It's added
to the milestone.

[Matt Bauman]

That's great.  I rebased my branch (no conflicts!) and re-ran those same tests I did back in May.  It's magically 2x faster and has half the allocations on the simple test I did:

julia> include("base/generator.jl");

julia> sum(i for i=1:1); @time sum(i for i=1:100000000)
elapsed time: 3.550339048 seconds (1599997360 bytes allocated, 48.60% gc time)

5000000050000000

julia> sum([i for i=1:1]); @time sum([i for i=1:100000000])

elapsed time: 0.66174807 seconds (800000048 bytes allocated)
5000000050000000

[Rafael Fourquet]

I took a crack at this: generate code for each new comprehension (for inlining), and now the perfs are similar to array comprehensions :)

At least in one dimension (one variable), and if the code is correct (I will link to my commit in the issue page, in case of interest).