Re: map: chaining vs. nesting

When I see those constructs, I wonder whether Perl is doing anything clever to avoid unnecessary copying

No, a list is generated at the end of each map. So the ST, for example:

my @sorted_data = 
    map   { $_->[1] }
    sort  { $a->[0] <=> $b->[0] }
    map   {[ do_something($_), $_ ]} 
    @unsorted_data;
[download]

Takes about 3 times as much memory as @unsorted_data orginally used. It also happens to be efficient because of an optimized sort step. CPU/memory tradeoffs generally favor the CPU--in fact, Perl itself is one gigantic CPU/memory tradeoff.

Further meditiation: LISP and other old interpreted languages were not well received when they were still young. Its detractors claimed it took too much computing power to handle the virtual machine it required. Today, a lot of very popular languages run under VMs (Perl, Java, Python, C#/.NET, etc.), and often run without significantly cutting into the resources available on a modern system. So the old reasoning should be considered moot.

However, there is a second reason why LISP and other functional langauges are inefficient--that being the memory requirements to handle the massively-chained operations that functional programming styles encourage. With significant ammounts of data, it could easily overwhelm the RAM of even modern systems.

----
send money to your kernel via the boot loader.. This and more wisdom available from Markov Hardburn.

Comment on Re: map: chaining vs. nesting Select or Download Code

Replies are listed 'Best First'.
Re^2: map: chaining vs. nesting by diotalevi (Canon) on Jun 18, 2004 at 14:35 UTC
Not quite. There's a check in map to see whether the input is a TEMP or not and if so, it is re-used for the output. The list assignment operator also notices that the input is stealable and steals the scalars away to be the kept-for-real copies in @sorted_data. So one copy is made. I'd have written this one as a GRT or tye's fast, flexible, stable sort, though instead.	[reply]
Re^2: map: chaining vs. nesting by danderson (Beadle) on Jun 18, 2004 at 18:42 UTC
They are only inefficient to a point. If, in Lisp\|Perl\|C\|whatever, you write a recursive function that runs a few thousand times, then you're going to suck up some RAM and the stack-push/pop CPU time. LISP, Scheme, ML, and their compadres are pretty well designed to minimize this. But, if you write a tail-recursive function, you're fine; overhead is exactly the same as for iteration. So it's all about how you implement your algorithms. Any language can be inefficient - `m/(a\|b+)*/` being a simple example I can remember being horrible in Perl. Besides, though most style guides for functional languages don't encourage it, they almost all have iteration constructs, even if they're not popular. I know LISP does; I think Scheme and ML do.	[reply] [d/l]
Re^3: map: chaining vs. nesting by Errto (Vicar) on Jun 19, 2004 at 01:17 UTC
Indeed. I spent a year working rather intensively on both ML and Haskell (which are structurally similar but have some crucial differences) and one of the first things I learned is that while it's tempting to implement a factorial like this: `fact 0 = 1 fact 1 = 1 fact n \| n < 0 = error "Negative factorial!" \| otherwise = n * fact (n - 1)` [download] your life will be vastly improved if you implement it like this: `fact 0 = 1 fact 1 = 1 fact n \| n < 0 = error "Negative factorial!" \| otherwise = g 1 n where g x 1 = x g x n' = g (x * n') (n' - 1)` [download] because the latter uses tail recursion and the former doesn't.	[reply] [d/l] [select]
Re^3: map: chaining vs. nesting by FoxtrotUniform (Prior) on Jun 18, 2004 at 18:54 UTC
If, in Lisp\|Perl\|C\|whatever, you write a recursive function that runs a few thousand times, then you're going to suck up some RAM and the stack-push/pop CPU time. LISP, Scheme, ML, and their compadres are pretty well designed to minimize this. But, if you write a tail-recursive function, you're fine; overhead is exactly the same as for iteration. Tail recursion can be converted directly into iteration; this is part of the Scheme standard, I believe, and most implementations of other functional languages support it. If you're unlucky enough to have an implementation that doesn't, though, tail recursion will still suck up stack space for function calls. `-- F o x t r o t U n i f o r m Found a typo in this node? /msg me % man 3 strfry`	[reply]