[HN Gopher] Fibs, Lies, and Benchmarks (2019)
       ___________________________________________________________________
        
       Fibs, Lies, and Benchmarks (2019)
        
       Author : kgwxd
       Score  : 14 points
       Date   : 2020-03-04 14:55 UTC (8 hours ago)
        
 (HTM) web link (wingolog.org)
 (TXT) w3m dump (wingolog.org)
        
       | jxy wrote:
       | Somebody should update this R7RS benchmark,
       | https://ecraven.github.io/r7rs-benchmarks/
       | 
       | Though even if it is currently 3 times better than version 2.2.6
       | on that benchmark, guile is still far away from the top tier.
        
       | AtlasBarfed wrote:
       | "The microbenchmark is no longer measuring call performance,
       | because GCC managed to reduce the number of calls. If I had to
       | guess, I would say this optimization doesn't have a wide
       | applicability and is just to game benchmarks. In that case, well
       | played, GCC, well played."
       | 
       | Loop unrolling and/or equivalent in recursion is a very basic
       | optimization.
       | 
       | It's weird that an optimizing compiler optimizes away something
       | that he is somewhat arbitrarily benchmarking, and he declares it
       | something specifically targeted at only improving artificial
       | benchmarks.
       | 
       | "In Guile you can recurse however much you want."
       | 
       | Sooo... if your recursion depends on accumulated stack data,
       | which is what most non-tail-recursive recursions want to do...
       | can you recurse however much you want? This seems like a
       | disingenuous statement. Every recursion algorithm cannot be
       | magically refactored to perfectly tail recursion.
       | 
       | When I was a wee CS student, I heard that any recursion algorithm
       | can be converted to a loop. With puzzlement I asked the prof who
       | said that about something that pretty clearly needed stack-state,
       | and he further qualified it with "well, if you have a stack
       | datastructure in the loop."
       | 
       | There seems to be pervasive overclaims here, and narcissistic
       | self-focus. Doesn't inspire confidence in the language.
        
       | nemo1618 wrote:
       | >Friends, it's not entirely clear to me why this is, but I
       | instrumented a copy of fib, and I found that the number of calls
       | in fib(n) was a more or less constant factor of the result of
       | calling fib. That ratio converges to twice the golden ratio,
       | which means that since fib(n+1) ~= ph * fib(n), then the number
       | of calls in fib(n) is approximately 2 * fib(n+1). I scratched my
       | head for a bit as to why this is and I gave up; the Lord works in
       | mysterious ways.
       | 
       | We can model the number of calls with a doubly-recursive
       | function, much like fib itself:                 calls 0 = 1
       | calls 1 = 1       calls n = 1 + calls(n-1) + calls(n-2)
       | 
       | However, it's easier to work with this if we split into three
       | parts: the base case of fib that adds 0, the base case that adds
       | 1, and the recursive case. If you examine the number of each type
       | of call, you get the following table:                 add 0:   1,
       | 0, 1, 1, 2, 3,  5 ... = fib(n-1)       add 1:   0, 1, 1, 2, 3, 5,
       | 8 ... = fib(n)       recurse: 0, 0, 1, 2, 4, 7, 12 ... =
       | fib(n+1)-1
       | 
       | So the total number of calls is fib(n-1) + fib(n) + fib(n+1) - 1.
       | Since fib(n+1) = fib(n) + fib(n-1), we can express the sum as 2 x
       | fib(n+1)-1.
       | 
       | And of course, there's an OEIS entry for this sequence:
       | http://oeis.org/A001595. I notice that one of the definitions
       | given there is "odd numbers whose index is a Fibonacci number,"
       | which matches our definition nicely, since you can define the set
       | of odd numbers as 2*(n+1)-1.
        
       ___________________________________________________________________
       (page generated 2020-03-04 23:00 UTC)