Re: Fibonacci recursion incredibly slow
Jeremy Tregunna <[email protected]> Mon, 07 Jan 2013 16:54:50 -0600
| Newsgroups | gmane.comp.lang.io |
|---|---|
| Message-ID | <[email protected]> |
--Boundary_(ID_5OAnw6I0khM+1BJfwVexTw)
Content-type: text/plain; charset=utf-8
Content-transfer-encoding: quoted-printable
Content-disposition: inline
Io doesn't have tail call elimination or many other facilities to help you =
out here. Io is inherently an imperative language, and not designed for eff=
icient recursion. That said, Io takes the design decision that running out =
of stack space at a fixed low level, is not a good idea, and we'd prefer to=
be a little slower but allow you to recurse much longer. By this effect, w=
hat slows down recursion in Io is when we're about to run out of stack spac=
e, we create another object to act as part of the composite "call frame" an=
d chain it together with the previous. Thus when you do exhaust stack space=
, we have another object of unlimited extent waiting there to catch your ov=
erflow. In this respect, it puts much more pressure on the allocator and th=
e garbage collector, which is what makes recursion slower in Io. Fun fact, =
the more you recurse, the worse the effect is, as I'm sure is understandabl=
e based on my description above.
While you can recurse into infinity*, that doesn't mean you should. As with=
in languages like C and otherwise, you should probably find an iterative a=
lgorithm if possible than a heavily recursive algorithm.
* - Assuming you have an infinite amount of addressable RAM, and a backing =
store of infinite size=20=20
Regards,
Jeremy Tregunna
On Monday, 7 January, 2013 at 4:53 PM, Jeremy Tregunna wrote:
> Io doesn't have tail call elimination or many other facilities to help yo=
u out here. Io is inherently an imperative language, and not designed for e=
fficient recursion. That said, Io takes the design decision that running ou=
t of stack space at a fixed low level, is not a good idea, and we'd prefer =
to be a little slower but allow you to recurse much longer. By this effect,=
what slows down recursion in Io is when we're about to run out of stack sp=
ace, we create another object to act as part of the composite "call frame" =
and chain it together with the previous. Thus when you do exhaust stack spa=
ce, we have another object of unlimited extent waiting there to catch your =
overflow. In this respect, it puts much more pressure on the allocator and =
the garbage collector, which is what makes recursion slower in Io. Fun fact=
, the more you recurse, the worse the effect is, as I'm sure is understanda=
ble based on my description above.
>=20=20
> While you can recurse into infinity*, that doesn't mean you should. As wi=
th in languages like C and otherwise, you should probably find an iterative=
algorithm if possible than a heavily recursive algorithm.
>=20=20
> * - Assuming you have an infinite amount of addressable RAM, and a backin=
g store of infinite size=20=20
>=20=20
> Regards,
>=20=20
> Jeremy Tregunna
>=20=20
>=20=20
> On Sunday, 6 January, 2013 at 3:23 PM, trevor_landau wrote:
>=20=20
> >=20=20=20=20
> > I'm running through the 7 langs 7 weeks book and am working on the 1st =
question self study question concerning writing a fibonacci sequence.
> >=20=20
> > I've written one using a for loop which is quite fast and another using=
recursion which is super slow after I try to use the sequence on a number =
passed say 20. If i try 42, it won't ever print or at least I don't wait lo=
ng enough to let it print.
> >=20=20
> > Am I doing something wrong?
> >=20=20
> > fibRec :=3D method(num,
> > if(num < 2,
> > return num,
> > return fibRec(num - 1) + fibRec(num - 2)
> > )
> > )
> >=20=20
> > fibRec(1) println
> > fibRec(4) println
> > fibRec(17) println=20=20
> > fibRec(42) println # Pretty much never executes
> >=20=20
> > Thanks.
> >=20=20
> >=20=20=20
>=20=20
--Boundary_(ID_5OAnw6I0khM+1BJfwVexTw)
Content-Type: text/html; charset=UTF-8
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>
<div>
Io doesn't have tail call elimination or many other facilities to help you out here. Io is inherently an imperative language, and not designed for efficient recursion. That said, Io takes the design decision that running out of stack space at a fixed low level, is not a good idea, and we'd prefer to be a little slower but allow you to recurse much longer. By this effect, what slows down recursion in Io is when we're about to run out of stack space, we create another object to act as part of the composite "call frame" and chain it together with the previous. Thus when you do exhaust stack space, we have another object of unlimited extent waiting there to catch your overflow. In this respect, it puts much more pressure on the allocator and the garbage collector, which is
what makes recursion slower in Io. Fun fact, the more you recurse, the worse the effect is, as I'm sure is understandable based on my description above.<br><font color="#002162"><br></font>While you can recurse into infinity*, that doesn't mean you should. As with in languages like C and otherwise, you should probably find an iterative algorithm if possible than a heavily recursive algorithm.<br><font color="#002162"><br></font><div><div>* - Assuming you have an infinite amount of addressable RAM, and a backing store of infinite size</div></div>
</div>
<div><div><br></div><div>Regards,</div><div><br></div><div>Jeremy Tregunna</div><div><br></div></div>
<p style="color: #A0A0A8;">On Monday, 7 January, 2013 at 4:53 PM, Jeremy Tregunna wrote:</p>
<blockquote type="cite" style="border-left-style:solid;border-width:1px;">
<span><div><div>
<div style="font-family: Helvetica;font-size: 13px;">Io doesn't have tail call elimination or many other facilities to help you out here. Io is inherently an imperative language, and not designed for efficient recursion. That said, Io takes the design decision that running out of stack space at a fixed low level, is not a good idea, and we'd prefer to be a little slower but allow you to recurse much longer. By this effect, what slows down recursion in Io is when we're about to run out of stack space, we create another object to act as part of the composite "call frame" and chain it together with the previous. Thus when you do exhaust stack space, we have another object of unlimited extent waiting there to catch your overflow. In this respect, it puts much more pressure on t
he allocator and the garbage collector, which is what makes recursion slower in Io. Fun fact, the more you recurse, the worse the effect is, as I'm sure is understandable based on my description above.<div><br></div><div>While you can recurse into infinity*, that doesn't mean you should. As with in languages like C and otherwise, you should probably find an iterative algorithm if possible than a heavily recursive algorithm.</div><div><br></div><div>* - Assuming you have an infinite amount of addressable RAM, and a backing store of infinite size</div></div>
<div><div><br></div><div>Regards,</div><div><br></div><div>Jeremy Tregunna</div><div><br></div></div>
<p style="color: #A0A0A8;">On Sunday, 6 January, 2013 at 3:23 PM, trevor_landau wrote:</p><blockquote type="cite"><div>
<span><div><div>
<span> </span>
<div>
<p>I'm running through the 7 langs 7 weeks book and am working on the 1st question self study question concerning writing a fibonacci sequence.<br>
<br>
I've written one using a for loop which is quite fast and another using recursion which is super slow after I try to use the sequence on a number passed say 20. If i try 42, it won't ever print or at least I don't wait long enough to let it print.<br>
<br>
Am I doing something wrong?<br>
<br>
fibRec := method(num,<br>
if(num < 2,<br>
return num,<br>
return fibRec(num - 1) + fibRec(num - 2)<br>
)<br>
)<br>
<br>
fibRec(1) println<br>
fibRec(4) println<br>
fibRec(17) println <br>
fibRec(42) println # Pretty much never executes<br>
<br>
Thanks.<br>
<br>
</p>
</div>
<!-- end group email -->
</div></div></span>
</div></blockquote><div>
<br>
</div>
</div></div></span>
</blockquote>
<div>
<br>
</div>
</p>
</div>
<!--~-|**|PrettyHtmlStart|**|-~-->
<div style="color: #fff; height: 0;">__._,_.___</div>
<table cellspacing=4px style="margin-top: 20px; margin-bottom: 10px;">
<tbody>
<tr>
<td style="font-size: 12px; font-family: arial; font-weight: bold; padding: 7px 5px 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA " >
<a style="text-decoration: none; color: #2D50FD" href="http://groups.yahoo.com/group/iolanguage/post;_ylc=X3oDMTJxbWlzamx2BF9TAzk3MzU5NzE0BGdycElkAzY2Nzc0NzYEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzEzMzA4BHNlYwNmdHIEc2xrA3JwbHkEc3RpbWUDMTM1NzU5OTI5NA--?act=reply&messageNum=13308">Reply via web post</a>
</td>
<td style="font-size: 12px; font-family: arial; padding: 7px 5px 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA; " >
<a href="mailto:[email protected]?subject=Re%3A%20%5BIo%5D%20Fibonacci%20recursion%20incredibly%20slow" style="text-decoration: none; color: #2D50FD;">
Reply to sender </a>
</td>
<td style="font-size: 12px; font-family: arial; padding: 7px 5px 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA; ">
<a href="mailto:[email protected]?subject=Re%3A%20%5BIo%5D%20Fibonacci%20recursion%20incredibly%20slow" style="text-decoration: none; color: #2D50FD">
Reply to group </a>
</td>
<td style="font-size: 12px; font-family: arial; padding: 7px 5px 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA; " >
<a href="http://groups.yahoo.com/group/iolanguage/post;_ylc=X3oDMTJlYjZqbHI3BF9TAzk3MzU5NzE0BGdycElkAzY2Nzc0NzYEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTM1NzU5OTI5NA--" style="text-decoration: none; color: #2D50FD">Start a New Topic</a>
</td>
<td style="font-size: 12px; font-family: arial; padding: 7px 5px 5px; color: #2D50FD; background-color: #F2F2F2; border: 1px solid #EAEAEA; " >
<a href="http://groups.yahoo.com/group/iolanguage/message/13307;_ylc=X3oDMTM2OHEwZGJyBF9TAzk3MzU5NzE0BGdycElkAzY2Nzc0NzYEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzEzMzA4BHNlYwNmdHIEc2xrA3Z0cGMEc3RpbWUDMTM1NzU5OTI5NAR0cGNJZAMxMzMwNw--" style="text-decoration: none; color: #2D50FD;">Messages in this topic</a>
(2)
</td>
</tr>
</tbody>
</table>
<!------- Start Nav Bar ------>
<!-- |**|begin egp html banner|**| -->
<!-- |**|end egp html banner|**| -->
<!-- |**|begin egp html banner|**| -->
<div id="ygrp-vital" style="background-color: #f2f2f2; 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;">
<li style="border-right: 1px solid #000; font-weight: 700; display: inline; padding: 0 5px; margin-left: 0;">
<span class="cat"><a href="http://groups.yahoo.com/group/iolanguage/members;_ylc=X3oDMTJmNmg4NHJiBF9TAzk3MzU5NzE0BGdycElkAzY2Nzc0NzYEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZtYnJzBHN0aW1lAzEzNTc1OTkyOTQ-?o=6" style="text-decoration: none;">New Members</a></span>
<span class="ct" style="color: #ff7900;">4</span>
</li>
</ul>
<div style="clear: both; padding-top: 2px; color: #1e66ae;">
<a href="http://groups.yahoo.com/group/iolanguage;_ylc=X3oDMTJlM2V1NXRzBF9TAzk3MzU5NzE0BGdycElkAzY2Nzc0NzYEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTM1NzU5OTI5NA--" 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=X3oDMTJkNmg5cDNqBF9TAzk3NDc2NTkwBGdycElkAzY2Nzc0NzYEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxMzU3NTk5Mjk0" 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> • <a href="mailto:[email protected]?subject=Feedback on the redesigned individual mail v1" style="text-decoration: none;">Send us Feedback </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=6677476/grpspId=1705006764/msgId=13308/stime=1357599294/nc1=3848644/nc2=4507179/nc3=5522125" 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;
}
#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-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 -->
--Boundary_(ID_5OAnw6I0khM+1BJfwVexTw)--