I was able to reproduce the O(n^2)-behavior here. For the general implementation, the O(n^2) behavior persists even when I remove support for "forcing-extent", i.e. when I remove the parameterization of "current-forcing-extent".


Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de> schrieb am Fr., 6. Okt. 2017 um 14:36 Uhr:

thank you very much for your helpful comment. I think you analysis is correct. The current implementation (of the optional procedure "forcing-extent") yields a blow-up of the dynamic extents involved, which is not acceptable.

I am currently investigating how the sample implementation can be repaired. This should be resolved before SRFI 154 and SRFI 155 are finalized.


Shiro Kawai <xxxxxx@gmail.com> schrieb am So., 1. Okt. 2017 um 16:20 Uhr:
I've ported srfi-154 and srfi-155 reference implementations to Gauche and played with it to see performance implications, and noticed a peculiar behavior.  It might be something I'm doing wrong.

I use these infinite stream of integers and taking first n elements from it:

(define srfi-155-integers
  (let next ((n 0))
    (delay (cons n (next (+ n 1))))))

(define (xtake stream n)
  (let loop ((s stream) (r '()) (n n))
    (if (= n 0)
      (reverse r)
      (loop (cdr (force s))
            (cons (car (force s)) r)
            (- n 1)))))

While running with various n with fresh streams, I noticed it was taking O(n^2) time.

After some digging, I see the cause.

(delay (cons n (next (+ n 1))))

is expanded to:

(let ((dynamic-extent (current-dynamic-extent)))
     (let ((forcing-extent (current-dynamic-extent)))
       (with-dynamic-extent dynamic-extent
          (lambda ()
             (parameterize ((current-forcing-extent forcing-extent))
                 (cons n (next (+ n 1)))))))))

When it is forced, the inner expression (cons n (next (+ n 1))) is evaluated with the dynamic extent
which is the extent 'delay' is evaluated *plus* the extent added by parameterizing current-forcing-extent.  The call to next calls delay again, which captures this enhanced dynamic extent.

When the new promise is evaluated, the dynamic extent is further extended by yet another parameterization of current-forcing-extent, and so on.

Since the calls of force in xtake happens outside of those extended dynamic extent, every force executes before and after thunks of parameterization of current-forcing-extent, which gets longer as the stream unfolded.

To unsubscribe from this list please go to http://www.simplelists.com/confirm.php?u=3gmIi49Ouh6YpCluDZXWeokz7NgY9f9r