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

From: Shlomi Fish <[email-masked]>
Date: Sat, 28 Aug 2010 22:21:10 +0300

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? 

Yes. Here you go:

1. For PySolFC board No. 26464608654870335080 (which takes a very short time):

{{{
shlomif:$module$ time perl -Ilib ./scripts/black-hole-solve 
t/data/26464608654870335080.bh.board.txt 
Solved!
2D
3H
2S
3C
4H
5S
6D
7C
8C
9H
TH
9S
8S
9D
TC
JS
QC
KS
QH
JC
TS
JH
QS
KH
AC
2C
3D
4S
5D
6S
7D
6H
5C
4C
3S
2H
AD
KC
AH
KD
QD
JD
TD
9C
8D
7S
8H
7H
6C
5H
4D

real    0m0.568s
user    0m0.538s
sys     0m0.028s
}}}

2. For PySol FC board No. 2:

{{{
shlomif:$module$ make_pysol_freecell_board.py -F -t 2 black_hole | time perl 
-Ilib ./scripts/black-hole-solve -
Solved!
KH
AD
2H
3D
2S
3S
4H
5S
6C
7D
8H
7H
8D
9D
TH
JH
TS
9S
8S
9H
TC
JC
QS
KS
AH
2D
3H
4D
5H
4S
5D
6S
7C
6H
7S
8C
9C
TD
JS
QH
JD
QC
KD
QD
KC
AC
2C
3C
4C
5C
6D
8.79user 0.07system 0:08.92elapsed 99%CPU (0avgtext+0avgdata 
131120maxresident)k
0inputs+0outputs (0major+8266minor)pagefaults 0swaps
}}}

As you can see it takes much longer.

> Do you have profiler output for your
> program (i.e. where time is spent before and after)?
>

Well, I haven't converted my program to C yet. I'm attaching the 
Devel::NYTProf output of:

$ perl -d:NYTProf -Ilib ./scripts/black-hole-solve 2.bh.board.txt

As one can see from it, most of the time is spent in the loop, with one 
statement taking over 1 second in the total run (as they are run many times). 
The amount of code spent on reading the board or outputting the solution is 
very small.

Regards,

	Shlomi Fish

> Chen

-- 
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
"The Human Hacking Field Guide" - http://shlom.in/hhfg

God considered inflicting XSLT as the tenth plague of Egypt, but then
decided against it because he thought it would be too evil.

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

---

From: Shlomi Fish <[email-masked]>
Date: Thu, 16 Sep 2010 13:55:59 +0200

Hi all,

On Saturday 28 August 2010 22:21:10 Shlomi Fish 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.
> > 
> 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.
> 

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'.