Hi Slava,
Thanks for the tips. Out of interest, how does the optimizer know to use
fixnum+fast as opposed to fixnum+? (i.e. that the iteration will stop
happening before it overflows the fixnum) - is it really that smart?!
I'm afraid I haven't done any more with the specialized carrays - the
compiles were taking a few minutes each go so I figured I'd delay until
the new compiler changes were finished. If there's anything I can do to
help in this area then please let me know.
Thanks again,
Phil
Slava Pestov wrote:
> Phil Dawes wrote:
>> Hi Slava, Hi Factor list,
>>
>> I'm sure this must have been discussed before, but I was wondering if
>> the sequence combinators would be better served by an underlying
>> iterator protocol in addition to the current random access one.
>
> This has been discussed before. I think Eduardo is a proponent of the
> idea. Dan has been experimenting with something different but along the
> same lines; a generic iteration combinator (to unify each, assoc-each, etc.)
>
>> I can
>> see a couple of advantages of this:
>>
>> - sequence combinators could be used with streams
>> - sequence combinators could be used with lazy lists
>>
> Yup. Here are a few more to think about:
>
> - assocs
> - database query results (see query-each, query-map in extra/db; they're
> already sitting on top of a db-specific iterator protocol)
> - file system path iterators -- look at extra/io/files/paths, its
> unfinished but it would be more useful with a generic protocol
>
> However right now lazy list operations don't compile with the optimizing
> compiler so if you used the same generic words for sequences and lazy
> lists any code using them wouldn't compile either.
>> - outsources iteration to sequence classes, affording opportunites for
>> optimization
>>
>> (By the latter I mean that e.g. a fixnum-length container could optimize
>> to fixnum+fast)
>>
> Right now if you have a fixnum-length sequence and you apply a
> combinator to it, the compiler optimizes + down to fixnum+fast, etc. Eg,
>
> ( scratchpad ) [ { 1 2 3 } [ . ] each ] f optimized-quot.
> [
> { 1 2 3 } dup 1 slot swap 0 -rot \ G:184278 [
> pick pick fixnum< [
> swap
> >r 2dup
> >r
> >r
> >r r>
> swap 2 fixnum+fast slot . r>
> r>
> r>
> swap
> >r
> >r 1 fixnum+fast r>
> r>
> G:184278
> ] [ 3drop ] if
> ] call
> ]
>
> Iterators would be slower than combinators because of the overhead of
> creating the iterator object (which is slight, but might bite if you're
> iterating over very short sequences repeatedly), and accessing the
> iterator state slots. The compiler could perform escape analysis though,
> and stack-allocate the iterator. That would eliminate the overhead, but
> would require some work.
>> I had a quick go at an iterator protocol by way of proof-of-concept.
>> (old tuple notation I'm afraid). This protocol is more like python's
>> than STL or java. The 'each' combinator was pretty easy:
>>
>> GENERIC: next ( iterator -- end? )
>> GENERIC: elem ( iterator -- element )
>> GENERIC: iter ( seq -- iterator )
>>
>> USING: math.private ;
>>
>> TUPLE: fixnum-iterator num end ;
>> C: <fixnum-iterator> fixnum-iterator
>>
>> M: fixnum iter ( seq -- iterator ) 0 swap <fixnum-iterator> ;
>>
> Here you have an opportunity to re-order the tuple slots 'end num'. Then
> you can omit the 'swap' here.
>
>> M: fixnum-iterator elem ( iterator -- element ) fixnum-iterator-num ;
>>
>> M: fixnum-iterator next ( iterator -- end? )
>> dup fixnum-iterator-num 1 fixnum+fast
>> dup pick fixnum-iterator-end fixnum<
>> [ swap set-fixnum-iterator-num t ] [ 2drop f ] if ;
>>
>>
>> : each-iter-loop ( iter quot -- )
>> 2dup [ elem ] dip call
>> over next [ each-iter-loop ] [ 2drop ] if ; inline
>>
>> : each-iter ( seq quot -- )
>> [ iter ] dip each-iter-loop ; inline
>>
> This won't work with empty sequences. You need to have an 'end?' word
> which just does a test, and a 'next' which bumps the counter.
>> ( scratchpad ) 3 [ . ] each-iter
>> 0
>> 1
>> 2
>>
>> What do you think?
>
> If you want to experiment further, I encourage you to whip up a library
> and submit it to extra/.
>
> Also let me know how your specialized C arrays are going -- those could
> be added too.
>
> Slava
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2008.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> _______________________________________________
> Factor-talk mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/factor-talk
>
-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
Factor-talk mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/factor-talk
