On Mon, Sep 01, 2008 at 05:52:28PM +0200, TSa wrote: > HaloO, > > John M. Dlugosz wrote: >> Perhaps the supplier of the CPAN module for the nth function could >> also include, besides the actual function, an optimization pattern >> plug-in that locates the idiom in the parse tree and replaces the >> expression with a call to nth. > > Wouldn't a dispatch target postcircumfix:<[ ]>:(LazySortedList,Int) > suffice when the sort would return such a thing?
I suspect that warping the semantics of sort to support lazy readout will tend to adversely affect the performance of a normal sort (in an O(n²) kind of way), so I would rather optimize for sorting the entire list (the common case) and leave the top-n kinds of cases to a more specialized algorithm. (I would consider the problem posed in the OP to be somewhat artificial in any case.) All that being said, it's possible that, once we've written a sort routine without taking laziness into account (using, say, quicksort), the normal laziness of lists will kick in and essentially turn all of the partition calls into a kind of unbalanced heap algorithm. In any case, the sort algoritm may choose to eagerly evaluate as many elements as it likes in a batch in order to stay in the cache. In the limit, the algorithm may eagerly sort the entire list if it feels like it doesnt want to share the cache with anyone else. More generally, Perl 6 programs are not allowed to depend on strict laziness because strict laziness assumes a uniform memory access model that is unrealistic both in the current world of caching and the future world of NUMA. Strict laziness makes it much more difficult to do speculative execution on some of your spare multicores if other parts of your program are depending on whether something has been evaluated yet or not, and parts of your program disagree on that subject. Maybe quantum computers will allow such superposed entanglements, but Dr Von Neumann doesn't seem to like 'em. Yeah, I know, FP thinks it has the Correct Answer to that, but until someone invents a quantum computer that can lift monads, we have to worry about side effects sooner or later... :) Larry
