[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)