View Forum Topic

Forums
CS5035
Measuring performance

Author	Message
rabbott Posts: 1649	Posted 21:20 Feb 01, 2019 \| I added some information to the homework write-up about how to measure performance in Python and Haskell. My results: Haskell: about 0.1 milliseconds. Python (using the primes() function discussed in class and in the handouts): about 40 seconds It's possible to speed up the Python code by computing the primes only once. Can you figure out how to do that without computing the primes you need in advance? (Hint use the `itertools chain` function.) If you are new to Python, I wouldn't expect you to think of how to do it. In that case, just compute the primes up to 6,000 in advance. With that fix, my Python code took 1.1 seconds, a factor of 40 improvement but still much slower than Haskell. These times were an average of 10 executions for Python and 100 executions for Haskel. A simple way to do that in both languages is to run your code inside a list-comprehension 10 or 100 times. `[twoGoldbachExceptions() for _ in 10]` or `[twoGoldbachExceptions \| _ <- 100]` and divide the elapsed time by 10 or 100. Last edited by rabbott at 13:57 Feb 02, 2019.
rabbott Posts: 1649	Posted 10:09 Feb 02, 2019 \| I made a mistake in the previous entry on the Haskell time. The reported time (0.1 ms) was from a second or subsequent run. But by then GHCi had computed the needed primes and cached them away. On the first run, the time was more than an order of magnitude slower, about 5 ms, which is still much faster than even the optimized Python version. Last edited by rabbott at 10:11 Feb 02, 2019.
rabbott Posts: 1649	Posted 10:16 Feb 02, 2019 \| To be sure you are computing the right answer, and computing as many iterations of it as you think, you can print the final value. For `n` iterations: Python: `[twoGoldbachExceptions() for _ in n][-1]` Haskell: `last [twoGoldbachExceptions \| _ <- n]` Last edited by rabbott at 10:20 Feb 02, 2019.
rabbott Posts: 1649	Posted 10:57 Feb 02, 2019 \| Even my last Haskell timing estimate was too low. When the function is run multiple times, it computes the primes only on the first run. Running it once -- a number of times independently -- gives a timing estimate of about 0.5 sec, two orders of magnitude slower than 5 ms. (GHCi apparently discards its cache if you reload a changed file -- even if the change is just adding or removing a space.) With this adjustment, Haskell looks like it's twice as fast as the optimized Python. In both cases, the needed primes are computed once, but once only, on each run. Since the algorithms of the two versions are pretty much the same (at least in my versions), and since each version caches the primes as it computes them to avoid computing them again, this is probably a fair comparison. Last edited by rabbott at 13:56 Feb 02, 2019.
rabbott Posts: 1649	Posted 14:23 Feb 02, 2019 \| Another python optimization. My code uses a list comprehension to find the Goldbach factors of a number `n`, i.e., the prime `p` and constant `k` such that `n = p + 2kk`. Because Python does not support a `let` construct within list comprehensions, I took the square root of `(n-p)//2` twice. I eliminated the second square root; in addition I converted the list comprehension to a more brute-force `for`-loop. With those two changes, the Python time went down to 0.9 sec. (Either change by itself didn't make much of a difference.) Last edited by rabbott at 09:14 Feb 03, 2019.
rabbott Posts: 1649	Posted 21:31 Feb 03, 2019 \| Yet another Python optimization. Previously I had collected all the ways a number `n` could be represented as `n == p + 2kk`, where `p` is prime and `k` is some integer. But when I stopped at the first way (thereby determining that a number was not a counter-example), the code ran in 0.3 sec. Adding this optimization to the Haskell code didn't speed it up. That was presumably because the system automatically stopped at the first way since the logic only required one example. So now the Python version is faster than the Haskell version. Last edited by rabbott at 21:32 Feb 03, 2019.
rabbott Posts: 1649	Posted 21:47 Feb 03, 2019 \| If I test a number for Goldbach factors before testing for primarily, the Python version runs in 0.2 sec, and the Haskell version runs in 0.4 sec.