Re: Re: Reply to Chen regarding Porting the Black Hole Solver to C

Hi all,

On Saturday 28 August 2010 22:21:10 Shlomi Fish wrote:
> Resending because YahooGroups rejected my message (silently).
> 
> On Thursday 26 August 2010 21:40:37 Gwen Shapira wrote:
> > > So here is my reply: my code is not slow as Perl code goes, but it
> > > still often takes many seconds to solve a given deal of Black Hole
> > > Solitaire. As I'd like to run the solver on a range of deals in order
> > > to collect some statistics, I expect the Perl code to be too slow for
> > > that. The code is algorithmic and I'd expect that executing the
> > > bytecode by the Perl 5 backend to incur a large amount of overhead.
> > 
> > So your code is CPU bound and you are counting on the C optimizer to
> > reduce the CPU usage?
> 
> I believe that is the case. I have very little I/O there - mostly just
> parsing the input, and outputting the solution to the STDOUT.
> 
> > The reason I'm drilling down into the details is that I've been
> > interested in the question of "In what conditions can a program be
> > made faster by switching to a different language?" and you seem to
> > have a perfect test case :)
> 
> Heh, yes.
> 
> > In my world code is usually made faster by making it do less physical
> > IO or less logical IO (aka use less memory) or by resolving
> > concurrency issues. All those problems are rarely solved by switching
> > to a different language - although some folks seem to solve
> > concurrency problems by using Erlang.
> 
> Memory (RAM/Swap/etc.) access may be a huge factor in the run-time of the
> program, but it is also something that C is much better at.
> 
> > I'm curious how it works in other areas that I'm less familiar with.
> > Could you post benchmarks?
> 

Now that I've converted the program to C here is a Perl 5-vs.-C benchmark:

{{{
shlomif[black-hole]:$trunk/black-hole-solitaire$ sudo_renice time bash 
benchmark-perl.bash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
127.13user 1.44system 2:07.96elapsed 100%CPU (0avgtext+0avgdata 
3785616maxresident)k

0inputs+216outputs (0major+519908minor)pagefaults 0swaps
shlomif[black-hole]:$trunk/black-hole-solitaire$ sudo_renice time bash 
benchmark-c.bash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
4.98user 0.31system 0:05.30elapsed 99%CPU (0avgtext+0avgdata 
454512maxresident)k
0inputs+320outputs (0major+113825minor)pagefaults 0swaps
shlomif[black-hole]:$trunk/black-hole-solitaire$ 
}}}

So, the C solver runs at 5.3 seconds while the Perl solver takes 2:07.96 
minutes (~24 times slower).

Just for the record, here are the benchmarking scripts I've used:

[benchmark-perl.bash]
#!/bin/bash
export PATH="$HOME/apps/perl/modules/local/bin:$PATH"
export PERL5LIB="$HOME/apps/perl/modules/lib/perl5/site_perl/5.10.1/"
    (
        seq 1 20
    ) |
    (
        while read T ; do
            echo "$T"
            make_pysol_freecell_board.py -F -t "$T" black_hole |
            black-hole-solve - > "$T".results.txt
        done
    ) 2>&1 | tee -a black_hole_range_LOG
[/]

[benchmark-c.bash]
#!/bin/bash
export PATH="/home/shlomif/apps/test/bhs/bin/:$PATH"
    (
        seq 1 20
    ) |
    (
        while read T ; do
            echo "$T"
            make_pysol_freecell_board.py -F -t "$T" black_hole |
            black-hole-solve - > "$T".results.txt
        done
    ) 2>&1 | tee -a black_hole_range_LOG
[/]

On one occasion I was told that perl 5 was 100 times slower than C, and on a 
different one that it was 1,000 times slower, and 24 times slower is still a 
very dramatic difference.

Regards,

	Shlomi Fish

-- 
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
My Public Domain Photos - http://www.flickr.com/photos/shlomif/

<rindolf> She's a hot chick. But she smokes.
<go|dfish> She can smoke as long as she's smokin'.

Please reply to list if it's a mailing list post - http://shlom.in/reply .


------------------------------------

Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/hackers-il/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/hackers-il/join
    (Yahoo! ID required)

<*> To change settings via email:
    [email protected] 
    [email protected]

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/