Re: can multi-core improve single funciton?

On Tue, Feb 10, 2009 at 12:45 AM, Steven D'Aprano
<steven@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
On Tue, 10 Feb 2009 18:18:23 +1000, Gerhard Weis wrote:

Once I have seen Haskell code, that ran fibonacci on a 4 core system.

The algorithm itself basically used an extra granularity paramet until
which new threads will be sparked. e.g. fib(40, 36) means, calculate
fib(40) and spark threads until n=36. 1. divide: fib(n-1), fib(n-2)
2. divide: fib(n-2), fib(n-3)
3. divide: fib(n-3), fib(n-4)

We tried this code on a 4 core machine using only 1 core and all 4
cores. 1 core wallclock: ~10s
4 core wallclock: ~3s

Three seconds to calculate fib(40) is terrible. Well, it's a great saving
over ten seconds, but it's still horribly, horribly slow.

Check this out, on a two-core 2.2 GHz system:


import timeit
timeit.Timer('fib(40)', 'from __main__ import fib').timeit(1)
7.2956085205078125e-05

That's five orders of magnitude faster. How did I do it? I used a better
algorithm.


def fib(n, a=1, b=1):
if n==0:
return a
elif n==1:
return b
return fib(n-1, b, a+b)


And for the record:

fib(500)
225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626L
timeit.Timer('fib(500)', 'from __main__ import fib').timeit(1)
0.00083398818969726562

Less than a millisecond, versus millions of years for the OP's algorithm.
I know which I would choose. Faster hardware can only go so far in hiding
the effect of poor algorithms.

Indeed. And apparently memoization can hide it also:

$ #memoization added to OP's code
$ python -m timeit -s 'from memoized_naive_recursive_version import
fib' 'fib(40)'
1000000 loops, best of 3: 0.639 usec per loop
$ #your code
$ python -m timeit -s 'from your_version import fib' 'fib(40)'
100000 loops, best of 3: 15.4 usec per loop
$ cat memoized_naive_recursive_version.py
def memoize(func):
cache = {}
def memoized(*args):
if args in cache:
return cache[args]
else:
result = func(*args)
cache[args] = result
return result
return memoized

@memoize
def fib(n):
if n <= 1:
return 1
else:
return fib(n-1) + fib(n-2)

However, the naive recursive version fails by exceeding the maximum
recursion depth if N is too large, whereas your version continues to
succeed for a much higher limit of N.

Cheers,
Chris

--
Follow the path of the Iguana...
http://rebertia.com
.

Relevant Pages

  • Re: A Symbol- Abstracted Al
    ... What did the algorithm you used look like. ... Except the loops must be optimized ... I was making a DES cracker example and had Visual C6.0 default to ... The basic code is the correct and functional code, ...
    (sci.crypt)
  • Re: Spatial Optimization Algorithm Help
    ... > Are you using a formal pseudocode or your own notation? ... > which you correctly addressed in your algorithm). ... subset" loops, which enumerate combinations. ... an algorithm with your favourite search engine (search for something like ...
    (comp.programming)
  • Re: text compare takes very long...
    ... b1 = StrConv(String1, vbFromUnicode) ... In the earlier versions (where the loops in the main algorithm were equal to the product of the two string lengths) it would be best to do it two the two Integer arrays themselves, making sure that you revert the contents of those arrays back to their original condition at the end of the routine to avoid altering the String data in the calling procedure. ...
    (microsoft.public.vb.general.discussion)
  • Re: Parallel Scientific Computing
    ... spare time. ... you profile your algorithm, you can spot the performance bottleneck, ... My main loops are while loops, that checks on an Incrementmethod, ...
    (comp.programming.threads)
  • Re: First Attempt at Forth
    ... UM/MOD, in other words. ... and it is the core of the algorithm. ... you must have some idea of an arbitrary-precision ...
    (comp.lang.forth)