why are references so slow ?

I have a script, with lots of deep recursion and noticed, that with the usage of references the whole programm becomes *much* slower (i noticed that in an earlier state, when i wanted to put something often used into a sub. The programm took at first less than 1 second, after i created the sub it took more than 5 seconds to complete.)
Now i am at a point where i want to use recursion, and perl says its even a deep recursion.
So, should i throw away all the parameters and just use global variables to get rid of referencing and dereferencing ?


--
Daniel Dünker

Re: why are references so slow ?

In article <20070926044919.3b257be3.dduenker@uni-koblenz.de>, Daniel
Dˆºnker wrote:

> I have a script, with lots of deep recursion and noticed, that with the usage
> of references the whole programm becomes *much* slower (i noticed that in an
> earlier state, when i wanted to put something often used into a sub. The
> programm took at first less than 1 second, after i created the sub it took
> more than 5 seconds to complete.)
> Now i am at a point where i want to use recursion, and perl says its even a
> deep recursion.
> So, should i throw away all the parameters and just use global variables to
> get rid of referencing and dereferencing ?

Well, before you do anything, profile the application to see where the
slow parts really are. I would be surprised if it's the references, and
surprised if you haven't coded something that's an inefficient
algorithm (especially since you noted a deep recursion warning).

I talk about profiling in chapter 5, "Profiling", of Mastering Perl:

http://www252.pair.com/comdog/mastering_perl/Chapters/

Good luck :)

Re: why are references so slow ?

On Sep 26, 3:49 am, Daniel Dünker wrote:
> I have a script, with lots of deep recursion and noticed, that with the u=
sage of
> references the whole programm becomes *much* slower (i noticed that in an
> earlier state, when i wanted to put something often used into a sub. The =
programm
> took at first less than 1 second, after i created the sub it took more th=
an 5 seconds to
> complete.)

I'm not sure what this has to do with references but subroutine
calling it expensive in Perl. As are constructing and unpacking
argument lists.

> Now i am at a point where i want to use recursion, and perl says its even=
a deep
> recursion.

If you want to use recursion I don't think you can do it without
subroutines. You'd have to refactor your code to be iterative.

> So, should i throw away all the parameters and just use global variables =
to get rid
> of referencing and dereferencing ?

I think it would have been clearer if you'd given us an example but if
I've understood correctly you effectively have a bunch of variables
that you are just passing unchanged down the recursion. Yes I'd
replace these by variables that are by some definition "globals". That
is to say they are used inside a subroutine but are not passed as
arguments. There are two obvious ways to go about this...

# Original

sub foo {
my ($this,$that,$other) =3D @_;
# stuff using $this,$that,$other...
# ...but not changing $this or $that
foo ($this, $that, whatever);
# stuff...
}
######################################

# With closure
sub foo {
my ($this,$that,$other) =3D @_;
my $r;
$r =3D sub{
my ($other) =3D @_;
# stuff using $this,$that,$other...
$r->(whatever);
# stuff...
};
$r->($other);
undef $r; # break circular reference
}
####################################

# With package variables and local()

our ($this,$that);

sub r {
my ($other) =3D @_;
# stuff using $this,$that,$other...
$r->(whatever);
# stuff...
}

sub foo {
(local($this,$that),my ($other)) =3D @_;
r($other);
}

Re: why are references so slow ?

On Wed, 26 Sep 2007 00:26:57 -0500
brian d foy wrote:

> In article <20070926044919.3b257be3.dduenker@uni-koblenz.de>, Daniel
> Dˆºnker wrote:
>
> > I have a script, with lots of deep recursion and noticed, that with the usage
> > of references the whole programm becomes *much* slower (i noticed that in an
> > earlier state, when i wanted to put something often used into a sub. The
> > programm took at first less than 1 second, after i created the sub it took
> > more than 5 seconds to complete.)
> > Now i am at a point where i want to use recursion, and perl says its even a
> > deep recursion.
> > So, should i throw away all the parameters and just use global variables to
> > get rid of referencing and dereferencing ?
>
> Well, before you do anything, profile the application to see where the
> slow parts really are. I would be surprised if it's the references, and
> surprised if you haven't coded something that's an inefficient
> algorithm (especially since you noted a deep recursion warning).
>
> I talk about profiling in chapter 5, "Profiling", of Mastering Perl:
>
> http://www252.pair.com/comdog/mastering_perl/Chapters/
>
> Good luck :)

Wow thanks, that's a very interesting tool, and of course you are right, there are still lot's of inefficient things in my script, but it seems that the slowest part's are actually really referencing and dereferencing, as for example:
4455 3.53946 3.40000 133: return \%pixels;
which is the part that takes the most time.

--
Daniel Dünker

Re: why are references so slow ?

On Wed, 26 Sep 2007 09:03:58 -0000, Brian McCauley
wrote:

>I'm not sure what this has to do with references but subroutine
>calling it expensive in Perl. As are constructing and unpacking
>argument lists.
>
>> Now i am at a point where i want to use recursion, and perl says its even=
> a deep
>> recursion.
>
>If you want to use recursion I don't think you can do it without
>subroutines. You'd have to refactor your code to be iterative.

(Mostly as an aside) if the recursion can be cast in the form of tail
recursion than much hassle can be eliminated, but existing perls
unfortunately don't handle it natively so one has to take care of that
"manually" with *magic* goto()s.


Michele
--
{$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
(($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^ ..'KYU;*EVH[.FHF2W+#"\Z*5TI/ER 256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,

Re: why are references so slow ?

Daniel =?UTF-8?B?RMO8bmtlcg==?= wrote:
>
> Wow thanks, that's a very interesting tool, and of course you are right,
> there are still lot's of inefficient things in my script, but it seems
> that the slowest part's are actually really referencing and
> dereferencing, as for example:
> 4455 3.53946 3.40000 133: return \%pixels;
> which is the part that takes the most time.

How do you know it is the reference, rather than the return, that is
taking the time? You could separate them into two different lines:

my $foo=\%pixels;
return $foo;

Also, I don't find Devel::SmallProf to be particularly reliable. Small
errors in its null compensation methods can lead to substantial spurious
timings.

Xho

--
-------------------- http://NewsReader.Com/ --------------------
The costs of publication of this article were defrayed in part by the
payment of page charges. This article must therefore be hereby marked
advertisement in accordance with 18 U.S.C. Section 1734 solely to indicate
this fact.

tail recursion (was: Re: why are references so slow ?)

Michele Dondi schreef:

> (Mostly as an aside) if the recursion can be cast in the form of tail
> recursion than much hassle can be eliminated, but existing perls
> unfortunately don't handle it natively so one has to take care of that
> "manually" with *magic* goto()s.

Can you show an example?

--
Affijn, Ruud

"Gewoon is een tijger."

Re: tail recursion (was: Re: why are references so slow ?)

On Wed, 26 Sep 2007 23:06:29 +0200, "Dr.Ruud"
wrote:

>Michele Dondi schreef:
>
>> (Mostly as an aside) if the recursion can be cast in the form of tail
>> recursion than much hassle can be eliminated, but existing perls
>> unfortunately don't handle it natively so one has to take care of that
>> "manually" with *magic* goto()s.
>
>Can you show an example?

It's surely discussed in HOP, but I don't know if it's online yet. No,
it isn't - see . Then there's a free
online book (ongoing work as of when I bookmarked it) available at
which talks about it, with examples, at
.


HTH,
Michele
--
{$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
(($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^ ..'KYU;*EVH[.FHF2W+#"\Z*5TI/ER 256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,

Re: tail recursion

Michele Dondi schreef:
> Dr.Ruud:
>> Michele Dondi:

>>> (Mostly as an aside) if the recursion can be cast in the form of
>>> tail recursion than much hassle can be eliminated, but existing
>>> perls unfortunately don't handle it natively so one has to take
>>> care of that "manually" with *magic* goto()s.
>>
>> Can you show an example?
>
> It's surely discussed in HOP, but I don't know if it's online yet. No,
> it isn't - see . Then there's a free
> online book (ongoing work as of when I bookmarked it) available at
> which talks about it, with examples, at
> .

Thanks.

--
Affijn, Ruud

"Gewoon is een tijger."

Re: why are references so slow ?

In article <20070926110818.0cb56f4f.dduenker@uni-koblenz.de>, Daniel
Dˆºnker wrote:


> Wow thanks, that's a very interesting tool, and of course you are right,
> there are still lot's of inefficient things in my script, but it seems that
> the slowest part's are actually really referencing and dereferencing, as for
> example:
> 4455 3.53946 3.40000 133: return \%pixels;
> which is the part that takes the most time.


remember that one line of a report like that doesn't mean much devoid
of the context of everything else going on. Feel free to post more of
the report :)

also, I don't know what is going on in that subroutine, but returning a
reference, which is just a scalar, shouldn't be talking up that much
time. Can you show the subroutine?

Re: tail recursion (was: Re: why are references so slow ?)

In article ,
Michele Dondi wrote:

: >Can you show an example?
:
: It's surely discussed in HOP, but I don't know if it's online yet.
: [...]

It's my recollection that Dominus had planned to include a
section on eliminating tail-calls with goto-&NAME but
abandoned the idea. (Seems like he couldn't make it work.)

Greg
--
Rightful liberty is unobstructed action according to our will within limits
drawn around us by the equal rights of others. I do not add 'within the limits
of the law,' because law is often but the tyrant's will, and always so when it
violates the rights of the individual. -- Thomas Jefferson

Re: tail recursion

>>>>> "GB" == Greg Bacon writes:

GB> In article ,
GB> Michele Dondi wrote:

GB> : >Can you show an example?
GB> :
GB> : It's surely discussed in HOP, but I don't know if it's online yet.
GB> : [...]

GB> It's my recollection that Dominus had planned to include a
GB> section on eliminating tail-calls with goto-&NAME but
GB> abandoned the idea. (Seems like he couldn't make it work.)

my guess is that the problem is setting up @_ is a pain. magic goto
leaves @_ to be passed to the called sub. many recursive calls will have
different @_ than they want to pass on so you have to mung @_ in some
wacky ways. surely it can be done but it will be fugly and maybe not
even efficient with the extra code needed.

for more speed i would rather unroll the recursion into a loop and use a
private stack. that is the classic way to speed up recursion which is
slow in perl due to all the sub calls. with this solution you don't have
tail recursion issues at all.

uri

--
Uri Guttman ------ uri@stemsystems.com -------- http://www.stemsystems.com
--Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
Search or Offer Perl Jobs ---------------------------- http://jobs.perl.org

Re: why are references so slow ?

On Wed, 26 Sep 2007 04:49:19 +0200, Daniel Dünker wrote:

>I have a script, with lots of deep recursion and noticed, that with the usage of references the whole programm becomes *much* slower (i noticed that in an earlier state, when i wanted to put something often used into a sub. The programm took at first less than 1 second, after i created the sub it took more than 5 seconds to complete.)
>Now i am at a point where i want to use recursion, and perl says its even a deep recursion.
>So, should i throw away all the parameters and just use global variables to get rid of referencing and dereferencing ?

Yes, you should throw away \@references or \$references, and pass by value always.

Should I get rid of pointers and go to dot net?

Re: why are references so slow ?

On Wed, 26 Sep 2007 04:49:19 +0200, Daniel Dünker wrote:

>I have a script, with lots of deep recursion and noticed, that with the usage of references the whole programm becomes *much* slower (i noticed that in an earlier state, when i wanted to put something often used into a sub. The programm took at first less than 1 second, after i created the sub it took more than 5 seconds to complete.)
>Now i am at a point where i want to use recursion, and perl says its even a deep recursion.
>So, should i throw away all the parameters and just use global variables to get rid of referencing and dereferencing ?

You should use nothing BUT global variables. Throw away subroutine parameters alltogether!

Re: why are references so slow ?

Post removed (X-No-Archive: yes)

Re: why are references so slow ?

On 28 Sep 2007 09:35:24 GMT all mail refused wrote:

amr> On 2007-09-28, sln@netherlands.co wrote:
>> On Wed, 26 Sep 2007 04:49:19 +0200, Daniel Dünker wrote:

>>> So, should i throw away all the parameters and just use global variables to get rid of referencing and dereferencing ?
>>
>> You should use nothing BUT global variables. Throw away subroutine parameters alltogether!

amr> Precompute all your programs and then for each situation run eithr /bin/true or /bin/false.

You might as well just write Quantum::Superpositions one-liners.

Ted

Re: why are references so slow ?

Quoth Ted Zlatanov :
> On 28 Sep 2007 09:35:24 GMT all mail refused
> wrote:
>
> amr> On 2007-09-28, sln@netherlands.co wrote:
> >> On Wed, 26 Sep 2007 04:49:19 +0200, Daniel Dünker
> wrote:
>
> >>> So, should i throw away all the parameters and just use global
> variables to get rid of referencing and dereferencing ?
> >>
> >> You should use nothing BUT global variables. Throw away subroutine
> parameters alltogether!
>
> amr> Precompute all your programs and then for each situation run eithr
> /bin/true or /bin/false.
>
> You might as well just write Quantum::Superpositions one-liners.

I'm not sure that would help... I'm fairly sure Acme::HaltingProblem
would be required as well :).

Ben