[plt-scheme] Statistics for Sequences

From: Matthew Flatt (mflatt at cs.utah.edu)
Date: Thu Sep 10 11:39:56 EDT 2009

At Thu, 10 Sep 2009 09:29:02 -0600, Doug Williams wrote:
> What I was hoping was that in the case of a generic sequence, the extracted
> procedures would be specific to the underlying sequence. For example, the
> procedures returned from sequence-generate for a vector would be (highly)
> optimized for vectors. 

Maybe the issue of when "just in time" is. The JIT currently compiles
at the granularity of `lambda', and it compiles each `lambda' only
once.

So, although `sequence-generate' may produce vector-specific operations
for a given invocation of the `for' loop, the JIT produces a generic
function call to the vector-specific operation (which might not be
vector-specific next time around).

One possibility for improvement, then, is to change the JIT strategy to
generate code later and more frequently.


> On Thu, Sep 10, 2009 at 9:18 AM, Matthew Flatt <mflatt at cs.utah.edu> wrote:
> 
> > When you use `in-vector', the expansion of `for' uses `vector-ref' etc.
> > directly, so those operations can be inlined by the JIT.
> >
> > When you use a generic sequence, the expansion of `for' extracts a set
> > of procedures from the sequence. The compiler can't tell that the
> > extracted procedures will sometimes be `vector-ref' etc.
> >
> > At Thu, 10 Sep 2009 09:03:24 -0600, Doug Williams wrote:
> > > Actually, I'd like to dig into the sequence code (specifically,
> > > sequence-generate) that should give you the sequencing function
> > dynamically.
> > > I'm not sure why it isn't as efficient as anything the for macro can
> > > generate for vectors.
> > >
> > > On Thu, Sep 10, 2009 at 8:47 AM, Jakub Piotr Cłapa <jpc-ml at zenburn.net
> > >wrote:
> > >
> > > > On 09-09-10 16:30, Doug Williams wrote:
> > > >
> > > >> It's interesting that if I use (in-vector ...) in the for/fold
> > > >> statements, the times for the for/fold version are about the same as
> > for
> > > >> the (uglier) do version (with vector-refs). [This one probably would
> > > >> benefit from Matthew's performance improvements.] Actually using it
> > > >> would mean giving up the flexibility in going to sequences in the
> > first
> > > >> place, but it means there is some hope of eventually getting the same
> > > >> performance for the sequence versions (at least for vectors).
> > > >>
> > > >> using in-vector in the for
> > > >> cpu time: 266 real time: 265 gc time: 0
> > > >> cpu time: 250 real time: 250 gc time: 47
> > > >>
> > > >> current science collection routines
> > > >> cpu time: 250 real time: 249 gc time: 0
> > > >> cpu time: 218 real time: 218 gc time: 16
> > > >>
> > > >> It would be nice if (for ((x some-vector)) ...) and (for ((x
> > (in-vector
> > > >> some-vector))) ...) had similar performance. I realize that at
> > expansion
> > > >> time the latter knows to expect a vector while the former does not and
> > > >> can generate code accordingly. But, I can dream.
> > > >>
> > > >
> > > > AFAIU you could special case vectors (duplicating the code) if you
> > expect
> > > > them to be used frequently. Probably a for-like macro expanding into
> > > > shortcuts for specified fast iterators would be nice to have. Something
> > like
> > > >
> > > > (for ([x (in (list vector string) lst)])
> > > >  x)
> > > >
> > > > would expand to
> > > >
> > > > (cond
> > > >  [(list? x) (for ([x (in-list lst)]) x)]
> > > >  ...
> > > >  [else (for ([x lst]) x)])
> > > >
> > > > PS. And what about generating such special cases by evaling a
> > dynamically
> > > > generated lambda at runtime? I guess it would make really long
> > iterations
> > > > faster but the eval overhead would kill the performance for short ones?
> > > >
> > > > --
> > > > regards,
> > > > Jakub Piotr Cłapa
> > > >
> > > > _________________________________________________
> > > >  For list-related administrative tasks:
> > > >  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> > > >
> > > _________________________________________________
> > >   For list-related administrative tasks:
> > >   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> >
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme


Posted on the users mailing list.