Re^3: Performance, Abstraction and HOP

[Dominus]

Said demerphq:

I mean, yes, if slow function calls are a problem then yes it is a language issue that really long term aught to be handled by fixing the implementation. But on the other hand we are engineers and problem solvers that have to work with the tools we have.

Sure. But if Perl's function calls are "too slow", where does that leave you with Perl? You can't do functional-style programming, because that would use too many function calls. And you can't do object-oriented style programming, because that would also use too many function calls, and method calls are slower than regular function calls. And you can't write any big or complex programs, because big complex programs are full of functions and then they must be too slow.

So where does that leave you? I think it leaves you with "Perl is just a scripting language, only good for throwaway scripts, but nothing big or important." Which some people do believe, but I do not.

Basically, my argument is this: Some language features can be avoided, but functions are not one of those features. Some implementation deficiencies can be worked around, but if function calls are too slow, there is no workaround. Every nontrivial program must contain lots of function calls. So if Perl's function calls are "too slow" (whatever that means, and nobody in this thread has suggested any relevant meaning) then you have only two choices. One is to fix Perl. The other, as you said, is to be a problem-solving engineer, to recognize that you are in a hopeless situation, and to obtain a tool that is not hopelessly defective. I have recently been informed that Java's function calls are faster than Perl's; perhaps that would be a better choice.

But it seems to me that you cannot reasonably hold the opinion that Perl is worth using for nontrivial programs and also that Perl's function calls are too slow to use.

I found your description of "constructing tailored code..." etc. above really interesting, but I can't imagine what it looks like, or what you could be doing that the function-call overhead is the bottleneck. I can only imagine that what you are doing does not really make sense, or that it is such a weird special situation that it has little applicability to general discussions like this one. I suppose this is just a failure of my imagination, but I certainly would like to see it.

Anyway, I was hoping that HOP had stuff along this line...

Wouldn't it better if it had something in it that you hadn't already thought of?

[demerphq]

Wouldn't it better if it had something in it that you hadn't already thought of?

No, I figure you are smarter than I am, and I know you are a better writer, so I figured if you covered the subject of dynamically generated code it would be well worth reading. :-)

But it seems to me that you cannot reasonably hold the opinion that Perl is worth using for nontrivial programs and also that Perl's function calls are too slow to use.

Of course that would be an unreasonable position. And Its not the position I hold. The position that I hold is that there are some task where Perls function call overhead starts to become unreasonable, and thus for those tasks I do what I can to avoid function calls. Eliminating them entirely is usually not feasable, but with a bit of cacheing (not ala Memoize.pm which is too slow -- yes ive benchmarked it) you can often minimize their impact.

I can only imagine that what you are doing does not really make sense, or that it is such a weird special situation that it has little applicability to general discussions like this one.

Well I'm talking about processing tens to hundreds of millions of records per program run. For instance every day a program I have has to apply a set of rules stipluated in an ini file to all of the records that we have recieved from the previous day. Exactly which rules apply to a record are determined based on criteria like the the type of file that is being processed.

A naive implementation of code like this would have a single main loop and then a lot of conditional logic, checking to see which rules apply. In addition it would probably have the rule handling logic factored out into method calls and subroutines. The naive implementation will take a big speed hit just for the method calls.

When I realized how large the speed hit was from the method calls i started looking into how I could unroll them, and dynamically generate the loop so that once it started all lookups were statically resolved. Thus each method knows how to represent itself as a snippet. Each rule object knows how to represent itself as an if statement, etc. The result is a considerably faster record processing engine. IOW, instead of writing a generic record processing tool, I wrote an engine that would produce a tailored record processing tool that would then do the processing.

Ive used this technique quite succesfully a number of times, and normally I find that it provides a perfect compromise. In most parts of the code function all overhead is negligable. DB calls, file operations accross the network, etc are the bottlenecks, not the function call overhead. But inside of a tight loop that has to process millions of records per day, doing what I can to avoid unnecessary method and function calls has proved to be a powerful optimization technique.

The other, as you said, is to be a problem-solving engineer, to recognize that you are in a hopeless situation, and to obtain a tool that is not hopelessly defective. I have recently been informed that Java's function calls are faster than Perl's; perhaps that would be a better choice.

well, personally I never considered changing language, just squeezing more performance out of the one I have. If it seemed to me that I could not reach acceptable performance levels with Perl regardless of the techniques I used then I probably would have done so. But the truth is that Perl is pretty fast at a alot of things, and is flexible too. I usually am able to fairly easily avoid method and function calls when I need to, so I dont worry about it too much.

And actually its amusing that you say to use Java, as thats one of the few languages that I actually havent seen used for any serious systems in my field. Apparently its just too slow. :-)

[Dominus]

Says demerphq:

I figured if you covered the subject of dynamically generated code it would be well worth reading.

Thanks. I wish that were true. One of the technical reviewers for the book asked why I didn't discuss dynamically-generated code. The real reason is that I was not aware of any examples where it was worth doing in Perl. That's why I find your example so intriguing.

[Anonymous Monk]

Basically, my argument is this: Some language features can be avoided, but functions are not one of those features. Some implementation deficiencies can be worked around, but if function calls are too slow, there is no workaround. Every nontrivial program must contain lots of function calls. So if Perl's function calls are "too slow" (whatever that means, and nobody in this thread has suggested any relevant meaning) then you have only two choices. One is to fix Perl. The other, as you said, is to be a problem-solving engineer, to recognize that you are in a hopeless situation, and to obtain a tool that is not hopelessly defective.

Maybe I'm not reading that right, but that sounds like a huge failure of imagination. Here's my recipe for writing programs. First, you should try make sure you're using a low complexity algorithm if there's one available (i.e. no exponentials or O(n**2), O(n**3), etc.). Then you code up the problem in a functional manner, in high level language like Perl. The test and debug it on small amounts of data. Then you try running it. If its not fast enough, profile it to identify the "inner loop", which might only be 5% of your code. If the "inner loop" is a recursive function, rewrite it in tail recursive form (using a manual stack if necessary) and implement it with a while loop, eliminating the function calls. Or maybe the problem calls for some manual inlining (also called fusion or deforestation). If its still not fast enough, write the inner loop in C. If that's not fast enough, then you need a faster machine. But in any case, you've still got the (debugged, tested) Perl version to test your other programs against. Here's some fine further reading to keep you motivated.

[Anonymous Monk]

So if Perl's function calls are "too slow" (whatever that means, and nobody in this thread has suggested any relevant meaning)

~/perl$ cat func_test.pl 
#!/usr/bin/perl 

#sum of number between 1 and 1,000,000
$n = 1_000_000;

print addup($n, 0);

sub addup
{
    return $_[1] if !$_[0];
    return addup($_[0]-1,$_[1]+$_[0]);
}

~/perl$ cat loop_test.pl 
#!/usr/bin/perl 

#sum of number between 1 and 1,000,000
$n = 1_000_000;
$sum = 0;

$sum += $n-- while($n);


~/perl$ time ./func_test.pl 
500000500000
real    0m4.025s
user    0m3.568s
sys     0m0.455s

~/perl$ time loop_test.pl  

real    0m0.390s
user    0m0.388s
sys     0m0.001s

[runrig]

I'm not sure that a memory hogging recursive function makes for a fair benchmark of function calling speed (even if the tail recursion could be optimized away in another language -- and if the tail recursion could be optimized away, you wouldn't be calling the function anymore, you'd just be doing a goto). I think this version of func_test.pl is more fair (which attempts to test the speed of function calling rather than memory allocation):

#!/usr/bin/perl

#sum of number between 1 and 1,000,000
$n = 1_000_000;

my $t = 0;

$t = addup( $t, $n-- ) while $n;
print "$t\n";

sub addup
{
    $_[0] + $_[1];
}

and then the two come out closer:

$ time ./func_tst.pl
500000500000

real    0m5.68s
user    0m5.48s
sys     0m0.02s
$ time ./loop_test.pl
500000500000

real    0m1.48s
user    0m1.47s
sys     0m0.01s