Reply to Chen regarding Porting the Black Hole Solver to C
Shlomi Fish <shlomif-ik1l9ssToec+JF/[email protected]> Wed, 25 Aug 2010 13:10:24 +0300
| Newsgroups | gmane.culture.hackers.israel |
|---|---|
| Message-ID | <[email protected]> |
--ORv85lsAna-40rSs1MGHttgyreP89UZvdLEG9Pq
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Hi all,
on Twitter I mentioned that I've started porting my Black Hole Solitaire
solver from Perl to C and that it will hopefully make it faster:
http://twitter.com/shlomif/status/22027561541
Chen replied thusly:
http://twitter.com/gwenshap/status/22031112275
{{{
Why go to all the effort without knowing what causes your code to be slow and
how C can help? Don't guess when you can measure!
}}}
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.
My code is very minimal as it is, and it's not very complicated or
sophisticated so I expect a conversion to C to yield great speed (and possibly
also memory consumption) benefits.
For more information see my:
* http://en.wikibooks.org/wiki/Optimizing_Code_for_Speed
I've replied to it here instead of on Twitter, because I didn't have enough
character quota to express myself properly. (Also I thought it may be of
interest to the list.).
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
List of Portability Libraries - http://shlom.in/port-libs
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 .
--ORv85lsAna-40rSs1MGHttgyreP89UZvdLEG9Pq
Content-Type: text/html; charset=US-ASCII
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>Hi all,<br>
<br>
on Twitter I mentioned that I've started porting my Black Hole Solitaire <br>
solver from Perl to C and that it will hopefully make it faster:<br>
<br>
<a href="http://twitter.com/shlomif/status/22027561541">http://twitter.com/shlomif/status/22027561541</a><br>
<br>
Chen replied thusly:<br>
<br>
<a href="http://twitter.com/gwenshap/status/22031112275">http://twitter.com/gwenshap/status/22031112275</a><br>
<br>
{{{<br>
Why go to all the effort without knowing what causes your code to be slow and <br>
how C can help? Don't guess when you can measure!<br>
}}}<br>
<br>
So here is my reply: my code is not slow as Perl code goes, but it still often <br>
takes many seconds to solve a given deal of Black Hole Solitaire. As I'd like <br>
to run the solver on a range of deals in order to collect some statistics, I <br>
expect the Perl code to be too slow for that. The code is algorithmic and I'd <br>
expect that executing the bytecode by the Perl 5 backend to incur a large <br>
amount of overhead.<br>
<br>
My code is very minimal as it is, and it's not very complicated or <br>
sophisticated so I expect a conversion to C to yield great speed (and possibly <br>
also memory consumption) benefits.<br>
<br>
For more information see my:<br>
<br>
* <a href="http://en.wikibooks.org/wiki/Optimizing_Code_for_Speed">http://en.wikibooks.org/wiki/Optimizing_Code_for_Speed</a><br>
<br>
I've replied to it here instead of on Twitter, because I didn't have enough <br>
character quota to express myself properly. (Also I thought it may be of <br>
interest to the list.).<br>
<br>
Regards,<br>
<br>
Shlomi Fish<br>
<br>
-- <br>
----------------------------------------------------------<br>
Shlomi Fish <a href="http://www.shlomifish.org/">http://www.shlomifish.org/</a><br>
List of Portability Libraries - <a href="http://shlom.in/port-libs">http://shlom.in/port-libs</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=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=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=X3oDMTJwNzlpanY0BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzUxMzAEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMjgyNzMxMTI5?act=reply&messageNum=5130">Reply <span style="font-weight: 700;">via web post</span></a> |
<a href="http://groups.yahoo.com/group/hackers-il/post;_ylc=X3oDMTJlcXZ0bGcyBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTI4MjczMTEyOQ--" style="font-weight: 700;">Start a New Topic</a>
</div>
<a href="http://groups.yahoo.com/group/hackers-il/message/5130;_ylc=X3oDMTM0amUwb2xvBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzUxMzAEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQMxMjgyNzMxMTI5BHRwY0lkAzUxMzA-">Messages in this topic</a>
(<span style="font-weight: 700;">1</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=X3oDMTJlb3E5Y2h2BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTI4MjczMTEyOQ--" style="text-decoration: none;">Visit Your Group</a>
</div>
</div>
<div id="ygrp-mkp" style="border: 1px solid #d8d8d8; clear: both; float: left; font-family: Arial; margin: 5px 0 10px 0; padding: 0 10px;">
<div id="hd" style="color: #628c2a; font-size: 85%; font-weight: 700; line-height: 122%; margin: 10px 0;">MARKETPLACE</div>
<div id="ads" style="margin-bottom: 10px;">
<div class="ad" style="color: #628C2A; font-family: Arial; font-weight: 700; padding: 0 0;">
<p><a href="http://us.ard.yahoo.com/SIG=15o6up4ig/M=493064.13983314.14041046.13298430/D=groups/S=1705006764:MKP1/Y=YAHOO/EXP=1282738329/L=38776c6c-b031-11df-a8ae-a7b9eda2320e/B=rMhmJ2KJiVY-/J=1282731129176348/K=oNRWP.49WeJL3r_Nah8afw/A=6060255/R=0/SIG=1194m4keh/*http://us.toolbar.yahoo.com/?.cpdl=grpj">Stay on top of your group activity without leaving the page you're on - Get the Yahoo! Toolbar now.</a></p> <script language=javascript>
if(window.yzq_d==null)window.yzq_d=new Object();
window.yzq_d['rMhmJ2KJiVY-']='&U=13cghp5hs%2fN%3drMhmJ2KJiVY-%2fC%3d493064.13983314.14041046.13298430%2fD%3dMKP1%2fB%3d6060255%2fV%3d1';
</script><noscript><img width=1 height=1 alt="" src="http://us.bc.yahoo.com/b?P=38776c6c-b031-11df-a8ae-a7b9eda2320e&T=1d9c49o9l%2fX%3d1282731129%2fE%3d1705006764%2fR%3dgroups%2fK%3d5%2fV%3d2.1%2fW%3dH%2fY%3dYAHOO%2fF%3d1802806143%2fH%3dY29udGVudD0iR287UG9kY2FzdHM7V2Vic2l0ZV9TZXJ2aWNlcztXaWRnZXRzO1lhaG9vX1NlYXJjaF9NYXJrZXRpbmc7RmxpY2tyO0JyaWVmY2FzZTtGaW5hbmNlO0Jvb2ttYXJrO01vYmlsZTsiIGRpc2FibGVzaHVmZmxpbmc9IjEiIHNlcnZlSWQ9IjM4Nzc2YzZjLWIwMzEtMTFkZi1hOGFlLWE3YjllZGEyMzIwZSIgc2l0ZUlkPSI0NDUyNTUxIiB0U3RtcD0iMTI4MjczMTEyOTE2NDI2MCIg%2fQ%3d-1%2fS%3d1%2fJ%3d27228962&U=13cghp5hs%2fN%3drMhmJ2KJiVY-%2fC%3d493064.13983314.14041046.13298430%2fD%3dMKP1%2fB%3d6060255%2fV%3d1"></noscript> </div>
<div class="ad" style="color: #628C2A; font-family: Arial; font-weight: 700; padding: 0 0;">
<hr style="border: 1px solid #d8d8d8;">
<p><a href="http://us.ard.yahoo.com/SIG=15o69un0c/M=493064.14012770.13963757.13298430/D=groups/S=1705006764:MKP1/Y=YAHOO/EXP=1282738329/L=38776c6c-b031-11df-a8ae-a7b9eda2320e/B=rshmJ2KJiVY-/J=1282731129176348/K=oNRWP.49WeJL3r_Nah8afw/A=6015306/R=0/SIG=11vlkvigg/*http://advision.webevents.yahoo.com/hobbiesandactivitieszone/">Hobbies & Activities Zone: Find others who share your passions! Explore new interests.</a></p><script language=javascript>
if(window.yzq_d==null)window.yzq_d=new Object();
window.yzq_d['rshmJ2KJiVY-']='&U=13cnhj0l9%2fN%3drshmJ2KJiVY-%2fC%3d493064.14012770.13963757.13298430%2fD%3dMKP1%2fB%3d6015306%2fV%3d1';
</script><noscript><img width=1 height=1 alt="" src="http://us.bc.yahoo.com/b?P=38776c6c-b031-11df-a8ae-a7b9eda2320e&T=1d8j1854t%2fX%3d1282731129%2fE%3d1705006764%2fR%3dgroups%2fK%3d5%2fV%3d2.1%2fW%3dH%2fY%3dYAHOO%2fF%3d545879289%2fH%3dY29udGVudD0iR287UG9kY2FzdHM7V2Vic2l0ZV9TZXJ2aWNlcztXaWRnZXRzO1lhaG9vX1NlYXJjaF9NYXJrZXRpbmc7RmxpY2tyO0JyaWVmY2FzZTtGaW5hbmNlO0Jvb2ttYXJrO01vYmlsZTsiIGRpc2FibGVzaHVmZmxpbmc9IjEiIHNlcnZlSWQ9IjM4Nzc2YzZjLWIwMzEtMTFkZi1hOGFlLWE3YjllZGEyMzIwZSIgc2l0ZUlkPSI0NDUyNTUxIiB0U3RtcD0iMTI4MjczMTEyOTE2NDI2MCIg%2fQ%3d-1%2fS%3d1%2fJ%3d27228962&U=13cnhj0l9%2fN%3drshmJ2KJiVY-%2fC%3d493064.14012770.13963757.13298430%2fD%3dMKP1%2fB%3d6015306%2fV%3d1"></noscript> </div>
<div class="ad" style="color: #628C2A; font-family: Arial; font-weight: 700; padding: 0 0;">
<hr style="border: 1px solid #d8d8d8;">
<p><a href="http://us.ard.yahoo.com/SIG=15of7633q/M=493064.13814537.14041040.10835568/D=groups/S=1705006764:MKP1/Y=YAHOO/EXP=1282738329/L=38776c6c-b031-11df-a8ae-a7b9eda2320e/B=rchmJ2KJiVY-/J=1282731129176348/K=oNRWP.49WeJL3r_Nah8afw/A=6078812/R=0/SIG=114ae4ln1/*http://dogandcatanswers.yahoo.com/">Get great advice about dogs and cats. Visit the Dog & Cat Answers Center.</a></p><script language=javascript>
if(window.yzq_d==null)window.yzq_d=new Object();
window.yzq_d['rchmJ2KJiVY-']='&U=13clbb72l%2fN%3drchmJ2KJiVY-%2fC%3d493064.13814537.14041040.10835568%2fD%3dMKP1%2fB%3d6078812%2fV%3d1';
</script><noscript><img width=1 height=1 alt="" src="http://us.bc.yahoo.com/b?P=38776c6c-b031-11df-a8ae-a7b9eda2320e&T=1d9e0mb6c%2fX%3d1282731129%2fE%3d1705006764%2fR%3dgroups%2fK%3d5%2fV%3d2.1%2fW%3dH%2fY%3dYAHOO%2fF%3d2804465870%2fH%3dY29udGVudD0iR287UG9kY2FzdHM7V2Vic2l0ZV9TZXJ2aWNlcztXaWRnZXRzO1lhaG9vX1NlYXJjaF9NYXJrZXRpbmc7RmxpY2tyO0JyaWVmY2FzZTtGaW5hbmNlO0Jvb2ttYXJrO01vYmlsZTsiIGRpc2FibGVzaHVmZmxpbmc9IjEiIHNlcnZlSWQ9IjM4Nzc2YzZjLWIwMzEtMTFkZi1hOGFlLWE3YjllZGEyMzIwZSIgc2l0ZUlkPSI0NDUyNTUxIiB0U3RtcD0iMTI4MjczMTEyOTE2NDI2MCIg%2fQ%3d-1%2fS%3d1%2fJ%3d27228962&U=13clbb72l%2fN%3drchmJ2KJiVY-%2fC%3d493064.13814537.14041040.10835568%2fD%3dMKP1%2fB%3d6078812%2fV%3d1"></noscript> </div>
</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=X3oDMTJkdGVpcHFkBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxMjgyNzMxMTI5" 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=5130/stime=1282731129/nc1=3848643/nc2=4507179/nc3=6083913" 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 -->
--ORv85lsAna-40rSs1MGHttgyreP89UZvdLEG9Pq--