Faster Perl, Good and Bad News

[abitkin]

Let me first say, I'm writing this Meditation as guide when you have to make a perl script that works on a big set of data.

So, to start out with, I've found, the sooner you decide to use inline c, the better. If you have a complex data structure, you may want to use inline c++ and classes to represent it. Not only will you get a speed boost (most of the time), but also the memory footprint should be smaller.

The next thing you should look at is using direct memory calls rather than function calls. Functions have a lot of CPU overhead, so store data where you can, and use direct access for that data.

Be very careful for recursion. Remember, what may work with 10 records in a reasonable amount of time; may not at 90,000 records. So if you are getting something from recursion, store it rather than calling that function again. I’m sure right now you’re saying, well duh, I knew that, but here’s where you may forget it:

.....
if($object->some_recursive_call > $value){
    $value = $object->some_recursive_call;
}
.....

It is better to do this:

.....
my $temp = $object->some_recursive_call;
if($temp > $value){
    $value = temp;
}
.....

Or this:

.....
my $temp = $object->some_recursive_call;
$value = $temp if $temp > $value;
.....

Do not use Class::Struct to create your objects, it will not give you the performance that you require. Instead use real Perl classes, they aren’t hard to write, and nothing to fear.

Change your Perl objects (if you find out too late to change to c objects) to use arrays rather than hashes. Hashes cost you some in speed, and quite a bit in memory. If you have hashes right now; create some constants to represent the values in your hash. So depth becomes $node::depth. This makes it easier to change; all you have to edit is the brackets and the prefix to the string you were using before.

Use c wherever you can to increase speed and memory usage. A c function call takes less CPU then a Perl call. Recursive calls on your Perl data structure is possible, but takes some real voodoo c programming (through XS.) Here is an example of using XS and recursion on a Perl data structure that is already arrays:

# perl
# node:
sub countLeaves{
    my $self = shift;
    my $ret = 0;
    foreach my $item (@{$self->[$node::child]}){
        next if ! defined($item);
        $ret += $item->countLeaves;
    }
    $self->[$node::leaves]=$ret;
    return $ret;
}
#leaf:
sub countLeaves{
    return 1;
}

# calling the Perl function:
$tree->countLeaves;

# C code:
I32 getLeavesInt( SV* root, I32 childPlace, I32 numKeys,
        I32 lPlace, I32 wPlace){
    I32 i, n, curr;
    AV* arr1;
    AV* arr2;
    SV* child;
    if( !SvROK(root)){
        return 0;
    }
    arr1 = (AV*)SvRV(root);
    n = av_len(arr1);
    curr = 0;
    if(n>1){
        if(!SvROK(*av_fetch (arr1,childPlace,0))){
            return 0;
        }
        arr2 = (AV*)SvRV(*av_fetch (arr1,childPlace,0));
        for(i = 0; i <= numKeys; i++){
            if(!(av_fetch(arr2,i,0) == NULL)){
                child = (*av_fetch(arr2,i,0));
                if(SvROK(child)){
                    curr += getLeavesInt(child,childPlace,numKeys,lPla
+ce,wPlace);
                }
            }
        }
        av_store(arr1,lPlace,(SV*) newSViv(curr));
        root=((SV*)arr1);
    }else{
        if(SvIV(*av_fetch(arr1,wPlace,0))!=0){
            curr = 1;
        }
    }
    return curr;
}

SV* getLeaves( SV* root, SV* childPlace, SV* numKeys,
        SV* lPlace, SV* wPlace){
    I32 ret;
    ret = getLeavesInt(root,SvIV(childPlace),SvIV(numKeys),
            SvIV(lPlace),SvIV(wPlace));
    return newSViv(ret);    
}

# calling the c function is:
getLeaves($tree,$node::child,$numKeys,$node::leaves,$leaf::weight);

Though there may be more lines of c, the c runs considerably faster than the Perl version. By using recursion such as this (not only in this function, but others as well) I have halved both my running time and memory usage.

One final note: optimize everything you can. No reason add extra variables that aren’t needed in your data structure (as defined by some command line options for example.)

[MrNobo1024]

"Premature optimization is the root of all evil" - Donald Knuth

You shouldn't go through contortions to make your program run a bit faster if it's not needed in the first place. It's just wasted effort, and will make your program harder to read and maintain.

I'm not saying you should never optimize, if a part of a program really *is* running significantly slowly, then by all means it should be sped up. But if you don't even check if it's needed, you could be wasting time optimizing, and making it more obfuscated in the process.

For example, check out these two ways to swap two variables: (Actually they're not exactly the same, for the first one to work they must be integers or same-length strings)

$x ^= $y ^= $x ^= $y;
($x, $y) = ($y, $x);

The first one is a bit faster, but if I didn't just say what it did (or if you had already seen it before) it would probably take a while to figure it out. The second one, it's obvious (if you know Perl) what it's doing, and unless it's going to be called 1000s of times it won't make any noticible speed difference.

--MrNobo1024
s]]HrLfbfe|EbBibmv]e|s}w}ciZx^RYhL}e^print

[sauoq]

For example, check out these two ways to swap two variables:

$x ^= $y ^= $x ^= $y;
($x, $y) = ($y, $x);

It might surprise you to learn that these aren't even equivalent. The XORs won't work with references.

-sauoq
"My two cents aren't worth a dime.";

[demerphq]

Er by far faster and easier to read to someone inexperienced in perl is

my $tmp=$x;
$x=$y;
$y=$tmp;

Premature optimization is evil, but then again so is false lazyness

Yves / DeMerphq
---
Software Engineering is Programming when you can't. -- E. W. Dijkstra (RIP)

[MrNobo1024]

I benchmarked them, there was no significant difference between list assignment and using a temp var, and IMO the list assignment is more readable. Still, TMTOWTDI, and the temp var isn't really *that* obfuscated...

--MrNobo1024
s]]HrLfbfe|EbBibmv]e|s}w}ciZx^RYhL}e^print

[dws]

Functions have a lot of CPU overhead, so store data where you can, and use direct access for that data.

This is entirely too simplistic a view.

Optimization is often about making a trade-off between space and time. Which way to go depends on the characteristics of your (working) application. To prejudge what you'll need optimize and how is a grand mistake. Unless you have a lot of experience. Then, it's merely a mistake.

If you're running up against the edge of your available memory, pushing stuff into memory risks causing virtual memory thrashing, which can be enormously expensive.

Here's an example from your earlier Possible Memory Usage Issues post: You're representing a Tree in memory. You have Node and Leaf objects. During a tree traversal, you need to distinguish between (internal) Nodes and Leafs. How do you do this?

One way to to store a type indicator in each object, and to either provide an common accessor for this field, or allow clients to peek into the object directly, so that the type can be queried. Let's assume you're doing pedal-to-the-metal optimization, and have made the dubious choice^* to let clients peek into the objects directly. This approach trades away time for space (the extra slot in each object. Each time you create a Node or a Leaf, you're taking on the (slight) extra overhead of setting up an additional slot or association, and each object carries around the extra space.

Another approach is to dispense with a common type field in favor of a predicate function, which might be implemented as follows:

  package Node;
  ...
  sub isLeaf { 0 }
  ...
  package Leaf;
  ...
  sub isLeaf { 1 }

This approach trades away space for time. Because of method lookup, it's a bit more expensive to do   if ( $o->isLeaf() ) { ... than it is to do   if ( $o->[$Node::isLeaf] ) { ... but which is better?

And the answer is: It Depends!

And this is only a simple example. There are a range of space-for-time tradeoffs possible in many applications, including caching (or not caching) frequently calculating intermediate results.

Unless you measure a working application on real data, you won't know for sure. To paraphrase Sherlock Holmes, "It is a capital crime to optimize before one has collected data."


^*Allowing clients to peek directly into objects increases "coupling", which makes an application harder to maintain and modify. Much of the flexibily of objects is that they hide their internal representation from clients, allowing implementations to be easily replaced.

[abitkin]

dws

I think you are saying something similar to what has been said, but in a more complete way. These are things to do for performance tuning; to get your script to run in a "sweet spot" of memory/cpu usage.

The only reason I even put in the bit about starting with a c data structure is for those who re-write all their code to help them tune it to run the best that it can.

You have to put work in to get these performance savings to happen, so I don't expect people to use it pass the point at which things run the best for them. Now I'm having to tune this for two machines, one with 128 megs of ram and 700 mhz pIII processor, and a pII 300 mhz with 212 megs of ram. With those limits, I stopped trying to optimize after I got under the requirements of both systems (running in a reasonable time on one, and not using the swap disk on the other.) Perhaps this would have been better titled as tips and tricks for perfomance.

Personally, I think the real gem is the recursive calls in c, mainly becuase I didn't find any good examples of recursing a perl data structure in c, until I asked here.

Now then, I'm going to sit in the corner and put my thumb in my mouth, to try to keep my foot out of it.

[dws]

Now I'm having to tune this for two machines, one with 128 megs of ram and 700 mhz pIII processor, and a pII 300 mhz with 212 megs of ram.

Something else to consider when optimizing: What is the cost , compared with the cost of implementing various solutions. Multiply the time it takes you to develop an XS-based solution times the cost of your time, and compare this to the cost of adding memory to these machines. You can add a 128Mb stick to a box for < 75 USD right now.(Granted, once you factor in overhead in including purchasing and labor, it costs an organization more this.)

It may well be that capital budget is difficult where you work, and that throwing your time at the problem is less expensive. But this is still a calculation that you and your management (or management equivalent) need to make.

[mirod]

Perlmonks is sometimes a funny place! The original post started by stating explicitely that it addressed the problem of optimizing code for big sets of data. In other words: how to optimize when you NEED to.

Why all the bashing and the warnings and the "premature optimization is the root..." routine? If you don't need to optimize then don't. If you need to then read this post and learn. Or discuss. But there is only one reply in this all thread that actually discusses optimization techniques, all the others redundantly chant the "don't optimize" mantra.

Please people, let Perlmonks be a place where such topics can be discussed, not one where they are stiffled by the official party line.

The original post made usefull suggestions, and you will be a better programer if you know the techniques it describes. So please, try being constructive and giving other techniques you used, not adding yet another "thou shalt not optimize" post to the thread. After all I don't see people answering golf posts, with "please do not write code like this", "build a test suite first" and "documentation, documentation, documentation!". There is a place for golf on Perlmonks and there should be a place for discussing optimization techniques too. They ARE useful.

Thank you for your attention, and I can now go back to chastisizing people who parse XML with regular expression ;--)

[ichimunki]

Mirod is right. Move along. Nothing interesting here. I somehow missed the opening remark, or glossed over it. I would not have written anything had I been more careful to observe it.

If CPU and RAM usage are major concerns, then Perl may be the wrong tool for the job, or for that part of the job. Well written, your algorithms will be fairly isolated in code, which means that if you find one is slowing you down, then (and only then) you go and write a C version which is hopefully more efficient.

Or perhaps you prototype with Perl and a smaller data set, then write the final application in C. This way you can "prove" the general theory and have problems whack you in Perl, where development time is short and testing is easy. But to go mixing C into your Perl too early is certain to make development a major headache, since each testing cycle will now include compiling the C code and then running the Perl script. And I don't know about others, but I like to build and run tests for every new piece of functionality (sometimes the tests come before the functionality). So the longer it takes to test is just longer it takes me to finish.

As to optimization: yes, optimize everything you can, especially your use of your time, since that is precious. Don't put in extra variable that aren't needed because this will take up your valuable time, both in generating the code, but also in maintaining it.

[derby]

About the only things to add from the other "evils of early optimization" comments,

A c function call takes less CPU then a Perl call.

After 15+ years of C coding, I wouldn't take that as gospel. I've seen too many poorly implemented c functions. If your c function is finely crafted then maybe its true for certain cases.

And the other addition ... optimization of my coding time is key nowadays and perl definetly has the one up there.

-derby

[theorbtwo]

BTW, as far as not calling recursive (or otherwise very expensive) functions more then neccessary, if you do this a lot, consider Memoize, which is designed for exactly that. It's not quite as transparent with objects as it is with, say, factorial, but if your code has a lot of redundant calls it's certianly worth the effort.

You might want to read The Perl Hardware Store section on Memoization and Quantitative Analysis of Memoization, both talks by Mark-Jason Dominous, the author of Memoize. (For that matter, his entire site is full of mind-bending perl stuff.)

Update:Memoize, not Memonize, thanks mirod.

---

Confession: It does an Immortal Body good.

[simon.proctor]

I think I've said it here before but I'll say it again. There's fast and there's fast enough. Knowing the difference is what makes the difference between finishing early and keeping it simple and wasting time optimising something that will change once your line manager finally gets their requirements sorted.

Flippancy aside, if you're having to re-write massive chunks in inline::C then surely you should just treat your Perl app as the prototype and build the production app in C or C++.

Of course you've probably gone and then doubled the cost of your project but at least it runs faster now :)

[petral]

Not to ignore mirod's statement above, but if we are stifling this useful post, at least "the official party line" should mention using > perl -d:DProf prog.plto help determine where optimization would be most fruitful ( > perldoc Devel::DProf).

  p

[Abigail-II]

You forget that a badly implemented efficient algorithm beats an efficiently implemented bad algorithm most of the time.

Before you go switching to C and doing direct access in the data, see whether you can optimize the datastructure. Perhaps a different structure is much smaller, or needs far less access.

Abigail