Re: Reply to Chen regarding Porting the Black Hole Solver to C
Shlomi Fish <shlomif-ik1l9ssToec+JF/[email protected]> Sat, 28 Aug 2010 22:21:10 +0300
| Newsgroups | gmane.culture.hackers.israel |
|---|---|
| Message-ID | <[email protected]> |
--kRK-b9g3hmEiOzorv485thA-HT0mOYcXK8NKvNP
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 7bit
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 .
--kRK-b9g3hmEiOzorv485thA-HT0mOYcXK8NKvNP
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
</head>
<body style="background-color: #fff;">
<span style="display:none"> </span>
<!--~-|**|PrettyHtmlStartT|**|-~-->
<div id="ygrp-mlmsg" style="position:relative;">
<div id="ygrp-msg" style="z-index: 1;">
<!--~-|**|PrettyHtmlEndT|**|-~-->
<div id="ygrp-text" >
<p>Resending because YahooGroups rejected my message (silently).<br>
<br>
On Thursday 26 August 2010 21:40:37 Gwen Shapira wrote:<br>
> > So here is my reply: my code is not slow as Perl code goes, but it still<br>
> > often takes many seconds to solve a given deal of Black Hole Solitaire.<br>
> > As I'd like to run the solver on a range of deals in order to collect<br>
> > some statistics, I expect the Perl code to be too slow for that. The<br>
> > code is algorithmic and I'd expect that executing the bytecode by the<br>
> > Perl 5 backend to incur a large amount of overhead.<br>
> <br>
> So your code is CPU bound and you are counting on the C optimizer to<br>
> reduce the CPU usage?<br>
<br>
I believe that is the case. I have very little I/O there - mostly just parsing <br>
the input, and outputting the solution to the STDOUT.<br>
<br>
> <br>
> The reason I'm drilling down into the details is that I've been<br>
> interested in the question of "In what conditions can a program be<br>
> made faster by switching to a different language?" and you seem to<br>
> have a perfect test case :)<br>
<br>
Heh, yes.<br>
<br>
> <br>
> In my world code is usually made faster by making it do less physical<br>
> IO or less logical IO (aka use less memory) or by resolving<br>
> concurrency issues. All those problems are rarely solved by switching<br>
> to a different language - although some folks seem to solve<br>
> concurrency problems by using Erlang.<br>
<br>
Memory (RAM/Swap/etc.) access may be a huge factor in the run-time of the <br>
program, but it is also something that C is much better at.<br>
<br>
> <br>
> I'm curious how it works in other areas that I'm less familiar with.<br>
> Could you post benchmarks? <br>
<br>
Yes. Here you go:<br>
<br>
1. For PySolFC board No. 26464608654870335080 (which takes a very short time):<br>
<br>
{{{<br>
shlomif:$module$ time perl -Ilib ./scripts/black-hole-solve <br>
t/data/26464608654870335080.bh.board.txt <br>
Solved!<br>
2D<br>
3H<br>
2S<br>
3C<br>
4H<br>
5S<br>
6D<br>
7C<br>
8C<br>
9H<br>
TH<br>
9S<br>
8S<br>
9D<br>
TC<br>
JS<br>
QC<br>
KS<br>
QH<br>
JC<br>
TS<br>
JH<br>
QS<br>
KH<br>
AC<br>
2C<br>
3D<br>
4S<br>
5D<br>
6S<br>
7D<br>
6H<br>
5C<br>
4C<br>
3S<br>
2H<br>
AD<br>
KC<br>
AH<br>
KD<br>
QD<br>
JD<br>
TD<br>
9C<br>
8D<br>
7S<br>
8H<br>
7H<br>
6C<br>
5H<br>
4D<br>
<br>
real 0m0.568s<br>
user 0m0.538s<br>
sys 0m0.028s<br>
}}}<br>
<br>
2. For PySol FC board No. 2:<br>
<br>
{{{<br>
shlomif:$module$ make_pysol_freecell_board.py -F -t 2 black_hole | time perl <br>
-Ilib ./scripts/black-hole-solve -<br>
Solved!<br>
KH<br>
AD<br>
2H<br>
3D<br>
2S<br>
3S<br>
4H<br>
5S<br>
6C<br>
7D<br>
8H<br>
7H<br>
8D<br>
9D<br>
TH<br>
JH<br>
TS<br>
9S<br>
8S<br>
9H<br>
TC<br>
JC<br>
QS<br>
KS<br>
AH<br>
2D<br>
3H<br>
4D<br>
5H<br>
4S<br>
5D<br>
6S<br>
7C<br>
6H<br>
7S<br>
8C<br>
9C<br>
TD<br>
JS<br>
QH<br>
JD<br>
QC<br>
KD<br>
QD<br>
KC<br>
AC<br>
2C<br>
3C<br>
4C<br>
5C<br>
6D<br>
8.79user 0.07system 0:08.92elapsed 99%CPU (0avgtext+0avgdata <br>
131120maxresident)k<br>
0inputs+0outputs (0major+8266minor)pagefaults 0swaps<br>
}}}<br>
<br>
As you can see it takes much longer.<br>
<br>
> Do you have profiler output for your<br>
> program (i.e. where time is spent before and after)?<br>
><br>
<br>
Well, I haven't converted my program to C yet. I'm attaching the <br>
Devel::NYTProf output of:<br>
<br>
$ perl -d:NYTProf -Ilib ./scripts/black-hole-solve 2.bh.board.txt<br>
<br>
As one can see from it, most of the time is spent in the loop, with one <br>
statement taking over 1 second in the total run (as they are run many times). <br>
The amount of code spent on reading the board or outputting the solution is <br>
very small.<br>
<br>
Regards,<br>
<br>
Shlomi Fish<br>
<br>
> Chen<br>
<br>
-- <br>
----------------------------------------------------------<br>
Shlomi Fish <a href="http://www.shlomifish.org/">http://www.shlomifish.org/</a><br>
"The Human Hacking Field Guide" - <a href="http://shlom.in/hhfg">http://shlom.in/hhfg</a><br>
<br>
God considered inflicting XSLT as the tenth plague of Egypt, but then<br>
decided against it because he thought it would be too evil.<br>
<br>
Please reply to list if it's a mailing list post - <a href="http://shlom.in/reply">http://shlom.in/reply</a> .<br>
</p>
</div>
<!--~-|**|PrettyHtmlStart|**|-~-->
<div style="color: #fff; height: 0;">__._,_.___</div>
<div id="ygrp-actbar" style="clear: both; margin-bottom: 10px; white-space: nowrap; color: #666; padding-top: 15px;">
<div>
<a href="mailto:shlomif-ik1l9ssToec+JF/[email protected]?subject=Re: Reply to Chen regarding Porting the Black Hole Solver to C" style="margin-right: 0; padding-right: 0;">
Reply to <span style="font-weight: 700;">sender</span></a> |
<a href="mailto:[email protected]?subject=Re: Reply to Chen regarding Porting the Black Hole Solver to C">
Reply to <span style="font-weight: 700;">group</span></a> |
<a href="http://groups.yahoo.com/group/hackers-il/post;_ylc=X3oDMTJwYnB2ZjVvBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzUxMzIEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMjgzMDIzMzg1?act=reply&messageNum=5132">Reply <span style="font-weight: 700;">via web post</span></a> |
<a href="http://groups.yahoo.com/group/hackers-il/post;_ylc=X3oDMTJlMnNpNGxiBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTI4MzAyMzM4NQ--" style="font-weight: 700;">Start a New Topic</a>
</div>
<a href="http://groups.yahoo.com/group/hackers-il/message/5130;_ylc=X3oDMTM0NzhsdGdzBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzUxMzIEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQMxMjgzMDIzMzg1BHRwY0lkAzUxMzA-">Messages in this topic</a>
(<span style="font-weight: 700;">3</span>)
</div>
<!------- Start Nav Bar ------>
<!-- |**|begin egp html banner|**| -->
<div id="ygrp-vital" style="background-color: #e0ecee; font-family: Verdana; font-size: 10px; margin-bottom: 10px; padding: 10px;">
<span id="vithd" style="font-weight: bold; color: #333; text-transform: uppercase; ">Recent Activity:</span>
<ul style="list-style-type: none; margin: 0; padding: 0; display: inline;">
</ul>
<div style="clear: both; padding-top: 2px; color: #1e66ae;">
<a href="http://groups.yahoo.com/group/hackers-il;_ylc=X3oDMTJlN2NlMW4zBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTI4MzAyMzM4NQ--" style="text-decoration: none;">Visit Your Group</a>
</div>
</div>
<div id="ft" style="font-family: Arial; font-size: 11px; margin-top: 5px; padding: 0 2px 0 0; clear: both;">
<a href="http://groups.yahoo.com/;_ylc=X3oDMTJkbDZyOWp1BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxMjgzMDIzMzg1" style="float: left;"><img src="http://l.yimg.com/a/i/us/yg/logo/us.gif" height="15" width="137" alt="Yahoo! Groups" style="border: 0;"/></a>
<div style="color: #747575; float: right;">Switch to: <a href="mailto:[email protected]?subject=Change Delivery Format: Traditional" style="text-decoration: none;">Text-Only</a>, <a href="mailto:[email protected]?subject=Email Delivery: Digest" class="margin-rt" style="text-decoration: none;">Daily Digest</a> • <a href="mailto:[email protected]?subject=Unsubscribe" style="text-decoration: none;">Unsubscribe</a> • <a href="http://docs.yahoo.com/info/terms/" style="text-decoration: none;">Terms of Use</a></div>
</div>
<!-- |**|end egp html banner|**| -->
</div> <!-- ygrp-msg -->
<!-- Sponsor -->
<!-- |**|begin egp html banner|**| -->
<div id="ygrp-sponsor" style="width:160px; float:right; clear:none; margin:0 0 25px 0; background: #fff;">
<!-- Start Recommendations -->
<div id="ygrp-reco">
</div>
<!-- End Recommendations -->
</div> <!-- |**|end egp html banner|**| -->
<div style="clear:both; color: #FFF; font-size:1px;">.</div>
</div>
<img src="http://geo.yahoo.com/serv?s=97359714/grpId=1857332/grpspId=1705006764/msgId=5132/stime=1283023385/nc1=1/nc2=2/nc3=3" width="1" height="1"> <br>
<div style="color: #fff; height: 0;">__,_._,___</div>
<!--~-|**|PrettyHtmlEnd|**|-~-->
</body>
<!--~-|**|PrettyHtmlStart|**|-~-->
<head>
<style type="text/css">
<!--
#ygrp-mkp {
border: 1px solid #d8d8d8;
font-family: Arial;
margin: 10px 0;
padding: 0 10px;
}
#ygrp-mkp hr {
border: 1px solid #d8d8d8;
}
#ygrp-mkp #hd {
color: #628c2a;
font-size: 85%;
font-weight: 700;
line-height: 122%;
margin: 10px 0;
}
#ygrp-mkp #ads {
margin-bottom: 10px;
}
#ygrp-mkp .ad {
padding: 0 0;
}
#ygrp-mkp .ad p {
margin: 0;
}
#ygrp-mkp .ad a {
color: #0000ff;
text-decoration: none;
}
#ygrp-sponsor #ygrp-lc {
font-family: Arial;
}
#ygrp-sponsor #ygrp-lc #hd {
margin: 10px 0px;
font-weight: 700;
font-size: 78%;
line-height: 122%;
}
#ygrp-sponsor #ygrp-lc .ad {
margin-bottom: 10px;
padding: 0 0;
}
a {
color: #1e66ae;
}
#actions {
font-family: Verdana;
font-size: 11px;
padding: 10px 0;
}
#activity {
background-color: #e0ecee;
float: left;
font-family: Verdana;
font-size: 10px;
padding: 10px;
}
#activity span {
font-weight: 700;
}
#activity span:first-child {
text-transform: uppercase;
}
#activity span a {
color: #5085b6;
text-decoration: none;
}
#activity span span {
color: #ff7900;
}
#activity span .underline {
text-decoration: underline;
}
.attach {
clear: both;
display: table;
font-family: Arial;
font-size: 12px;
padding: 10px 0;
width: 400px;
}
.attach div a {
text-decoration: none;
}
.attach img {
border: none;
padding-right: 5px;
}
.attach label {
display: block;
margin-bottom: 5px;
}
.attach label a {
text-decoration: none;
}
blockquote {
margin: 0 0 0 4px;
}
.bold {
font-family: Arial;
font-size: 13px;
font-weight: 700;
}
.bold a {
text-decoration: none;
}
dd.last p a {
font-family: Verdana;
font-weight: 700;
}
dd.last p span {
margin-right: 10px;
font-family: Verdana;
font-weight: 700;
}
dd.last p span.yshortcuts {
margin-right: 0;
}
div.attach-table div div a {
text-decoration: none;
}
div.attach-table {
width: 400px;
}
div.file-title a, div.file-title a:active, div.file-title a:hover, div.file-title a:visited {
text-decoration: none;
}
div.photo-title a, div.photo-title a:active, div.photo-title a:hover, div.photo-title a:visited {
text-decoration: none;
}
div#ygrp-mlmsg #ygrp-msg p a span.yshortcuts {
font-family: Verdana;
font-size: 10px;
font-weight: normal;
}
.green {
color: #628c2a;
}
.MsoNormal {
margin: 0 0 0 0;
}
o {
font-size: 0;
}
#photos div {
float: left;
width: 72px;
}
#photos div div {
border: 1px solid #666666;
height: 62px;
overflow: hidden;
width: 62px;
}
#photos div label {
color: #666666;
font-size: 10px;
overflow: hidden;
text-align: center;
white-space: nowrap;
width: 64px;
}
#reco-category {
font-size: 77%;
}
#reco-desc {
font-size: 77%;
}
.replbq {
margin: 4px;
}
#ygrp-actbar div a:first-child {
/* border-right: 0px solid #000;*/
margin-right: 2px;
padding-right: 5px;
}
#ygrp-mlmsg {
font-size: 13px;
font-family: Arial, helvetica,clean, sans-serif;
*font-size: small;
*font: x-small;
}
#ygrp-mlmsg table {
font-size: inherit;
font: 100%;
}
#ygrp-mlmsg select, input, textarea {
font: 99% Arial, Helvetica, clean, sans-serif;
}
#ygrp-mlmsg pre, code {
font:115% monospace;
*font-size:100%;
}
#ygrp-mlmsg * {
line-height: 1.22em;
}
#ygrp-mlmsg #logo {
padding-bottom: 10px;
}
#ygrp-mlmsg a {
color: #1E66AE;
}
#ygrp-msg p a {
font-family: Verdana;
}
#ygrp-msg p#attach-count span {
color: #1E66AE;
font-weight: 700;
}
#ygrp-reco #reco-head {
color: #ff7900;
font-weight: 700;
}
#ygrp-reco {
margin-bottom: 20px;
padding: 0px;
}
#ygrp-sponsor #ov li a {
font-size: 130%;
text-decoration: none;
}
#ygrp-sponsor #ov li {
font-size: 77%;
list-style-type: square;
padding: 6px 0;
}
#ygrp-sponsor #ov ul {
margin: 0;
padding: 0 0 0 8px;
}
#ygrp-text {
font-family: Georgia;
}
#ygrp-text p {
margin: 0 0 1em 0;
}
#ygrp-text tt {
font-size: 120%;
}
#ygrp-vital ul li:last-child {
border-right: none !important;
}
-->
</style>
</head>
<!--~-|**|PrettyHtmlEnd|**|-~-->
</html>
<!-- end group email -->
--kRK-b9g3hmEiOzorv485thA-HT0mOYcXK8NKvNP--