4 ms·

I guess I'm surprised at the speed of lazy streams then - usually I just pre-generate the fib sequence if I need it and then filter/aggregate as you mention. Pr

by exdsq 5y ago

I guess I'm surprised at the speed of lazy streams then - usually I just pre-generate the fib sequence if I need it and then filter/aggregate as you mention. Probably slightly embarrassing I've only just discovered their power after several years working in software development :)

Jtsummers 5y ago
This is basically the way that Haskell and other lazy languages work, but also generators in Python and other languages. They're often implemented using something like coroutines or closures in languages that aren't lazy (by default), or perhaps with classes and objects. For instance, in Common Lisp you might do something like this (I'm too rusty on Racket to write it up properly) as a kind of poor man's generator/iterator/stream: (defun new-fib-sequence () (let ((a 0) (b 1)) (lambda () (shiftf a b (+ a b))))) ;; CL detail, permits parallel assignment and returns the value of the first item *before* assignment (untested, should work) and then you can repeatedly use apply or funcall (so not as clean as Scheme or Racket as lisp-1s) to generate the sequence) > (let ((fib (new-fib-sequence)) (loop repeat 3 do (print (funcall fib)))) 0 1 1 racket/stream just gives you all this without the manual elements that I'm doing here. There are libraries in CL that give you all of this, too, but I figured an illustration of what's happening behind the scenes would be useful.
- exdsq 5y ago
  I appreciate it, thanks!
  - Jtsummers 5y ago
    NP. By the way, for grins I altered my program to generate only even Fibonacci numbers. I was seeing approximately 30% improvements, though I think you will see bigger improvements as you get to much larger numbers than I was testing on (on a cheap VPS box with 1 core and 4GB of RAM so I didn't really feel like stressing it too much because it was slow enough already). The changed recurrence relation is: EF(N) = Nth Even Fibonacci Numbers EF(N) = 4 * EF(N-1) + EF(N) EF(0) = 0, EF(1) = 2 This skips the generation of odd Fibonacci numbers and removes the need for the filtering step (if even then add to accumulator), but it adds in the multiplication which seems to reduce some of the potential performance gains. Once you get to the point that you're dealing with big numbers, addition becomes very expensive and, depending on how multiplication is implemented, you ought to get a larger performance boost as you get to very large numbers.
    - exdsq 5y ago
      Multiplication is more efficient than addition? That’s surprising! I assumed multiplication would be built at least partially from addition when you’re at the lowest levels of the stack
      - Jtsummers 5y ago
        Well, in this case because we also eliminate several additions. For each even Fibonacci number you have to perform multiple additions in the naive approach (generate all, filter): F(0) = 0 F(1) = 1 F(2) = 1 + 0 F(3) = 1 + 1 = 2 (2 additions to get here) F(4) = 2 + 1 = 3 F(5) = 3 + 2 = 5 F(6) = 5 + 3 = 8 (3 more additions to get here, and 3 for each subsequent one) With the faster version you have one multiplication and one addition (2 operations) versus 3 additions. The 3 additions naive version also has a branch that has been eliminated by just generating the even elements. EF(0) = 0 EF(1) = 2 EF(2) = 4 * 2 + 0 = 8 (1 mul, 1 add) EF(3) = 4 * 8 + 2 = 34 (1 mul, 1 add) This is why I was getting about a 30% improvement in performance, it's performing one less op (the branch itself isn't too expensive in comparison so with large numbers it's a minor cost).
        exdsq 5y ago
        Gotcha! Thanks for all your informed answers.

by exdsq 5y ago

Jtsummers 5y ago

This is basically the way that Haskell and other lazy languages work, but also generators in Python and other languages. They're often implemented using something like coroutines or closures in languages that aren't lazy (by default), or perhaps with classes and objects. For instance, in Common Lisp you might do something like this (I'm too rusty on Racket to write it up properly) as a kind of poor man's generator/iterator/stream: (defun new-fib-sequence () (let ((a 0) (b 1)) (lambda () (shiftf a b (+ a b))))) ;; CL detail, permits parallel assignment and returns the value of the first item *before* assignment (untested, should work) and then you can repeatedly use apply or funcall (so not as clean as Scheme or Racket as lisp-1s) to generate the sequence) > (let ((fib (new-fib-sequence)) (loop repeat 3 do (print (funcall fib)))) 0 1 1 racket/stream just gives you all this without the manual elements that I'm doing here. There are libraries in CL that give you all of this, too, but I figured an illustration of what's happening behind the scenes would be useful.

exdsq 5y ago
I appreciate it, thanks!
- Jtsummers 5y ago
  NP. By the way, for grins I altered my program to generate only even Fibonacci numbers. I was seeing approximately 30% improvements, though I think you will see bigger improvements as you get to much larger numbers than I was testing on (on a cheap VPS box with 1 core and 4GB of RAM so I didn't really feel like stressing it too much because it was slow enough already). The changed recurrence relation is: EF(N) = Nth Even Fibonacci Numbers EF(N) = 4 * EF(N-1) + EF(N) EF(0) = 0, EF(1) = 2 This skips the generation of odd Fibonacci numbers and removes the need for the filtering step (if even then add to accumulator), but it adds in the multiplication which seems to reduce some of the potential performance gains. Once you get to the point that you're dealing with big numbers, addition becomes very expensive and, depending on how multiplication is implemented, you ought to get a larger performance boost as you get to very large numbers.
  - exdsq 5y ago
    Multiplication is more efficient than addition? That’s surprising! I assumed multiplication would be built at least partially from addition when you’re at the lowest levels of the stack
    - Jtsummers 5y ago
      Well, in this case because we also eliminate several additions. For each even Fibonacci number you have to perform multiple additions in the naive approach (generate all, filter): F(0) = 0 F(1) = 1 F(2) = 1 + 0 F(3) = 1 + 1 = 2 (2 additions to get here) F(4) = 2 + 1 = 3 F(5) = 3 + 2 = 5 F(6) = 5 + 3 = 8 (3 more additions to get here, and 3 for each subsequent one) With the faster version you have one multiplication and one addition (2 operations) versus 3 additions. The 3 additions naive version also has a branch that has been eliminated by just generating the even elements. EF(0) = 0 EF(1) = 2 EF(2) = 4 * 2 + 0 = 8 (1 mul, 1 add) EF(3) = 4 * 8 + 2 = 34 (1 mul, 1 add) This is why I was getting about a 30% improvement in performance, it's performing one less op (the branch itself isn't too expensive in comparison so with large numbers it's a minor cost).
      - exdsq 5y ago
        Gotcha! Thanks for all your informed answers.