P vs P speed (was RE: Newbie question: files..)

[Tim Peters]

[Tim]
>> try-timing-a-program-with-bigints<wink>-ly y'rs  - tim

[Hrvoje Niksic]
> Huh?

Python's long ints; Perl's Math::BigInt.  I first saw Python when working
for a company trying to design a 64-bit supercomputer, using software on
32-bit workstations.  I had been using Perl, very painfully and slowly, and
the very first Python alpha already ran circles around Perl (I'm talking
factors of 10 - 100 here) for these tasks.  I kept Perl for text-crunching,
but dropped it for everything else.

[Tim again]
> It [Python] isn't slower than Perl in my experience (the contrary) --
> but then I use Perl for the little bit of serious text-crunching and
> regexp-slinging that comes up in my work.  Perl put extraordinary effort
> into implementing those efficiently; outside of them, I find that Python
> is typically faster.

[Hrvoje again]
> How do you measure that?

Speed excites me, so I just estimate my heartrate <wink -- but what do you
*think*?!>.

> So far I haven't seen an example of Python code that would be faster
> than its Perl equivalent.

I'll attach the first one I tried today -- and the last one I intend to try
ever again <0.1 wink>.  No bigints, just objects, recursion and simple
integer and floating-point math.  I did not work at optimizing either
version, but put considerable effort into fiddling the code so that:

a) Python and Perl print the same stuff.

b) Perl doesn't yield any warnings when run with -w (although, at the end,
it prints a bunch of "deep recursion" warnings when run as described next).

To be as fair as possible, I used the stock Python 1.5.2 without -O, and
downloaded the latest Win32 Perl (ActivePerl build 520).

OTOH, to be as unfair as possible (to compensate for the usual unfairness we
see in the other direction <0.5 wink>), I wrote this first in idiomatic
Python and then translated it straightforwardly into Perl.

Run it with command-line argument 5000.  It should print:

0 appeared 284 times
1 appeared 315 times
2 appeared 333 times
3 appeared 278 times
4 appeared 326 times
5 appeared 316 times
6 appeared 298 times
7 appeared 313 times
8 appeared 307 times
9 appeared 321 times
10 appeared 330 times
11 appeared 334 times
12 appeared 298 times
13 appeared 338 times
14 appeared 284 times
15 appeared 325 times
saw 5000 in all

On my home platform (P5-166, 32Mb RAM, Win95), it takes about 20 seconds in
Perl and about 14 in Python.  Which, applying the usual benchmarking
chicanery, means "Python is 43% faster than Perl".

More, this is *typical* in my experience.  All the convolution in Perl's
internals costs time to execute, and Python's much cleaner implementation
translates to faster runtime.  Python gets a bad rap here because of one
thing:  Guido doesn't put "extraordinary effort" into optimizing *anything*
(it's a personality flaw <wink>), while Larry et alia did put extraordinary
effort into optimizing some common things (mostly related to
text-crunching).  Outside of its areas of special competence, Perl is not
fast.

followups-ignored-ly y'rs  - tim

Python version:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, val):
        root = self.root
        lastdir = None
        while root:
            lastroot = root
            if val <= root.val:
                lastdir = 'left'
                root = root.left
            else:
                lastdir = 'right'
                root = root.right
        new = Node(val)
        if lastdir is None:
            self.root = new
        elif lastdir == 'left':
            lastroot.left = new
        else:
            lastroot.right = new

    def inorder(self):
        result = []
        self.__helper(self.root, result)
        return result

    def __helper(self, root, result):
        if root is not None:
            self.__helper(root.left, result)
            result.append(root.val)
            self.__helper(root.right, result)

class Random:
    def __init__(self, seed=(1,2,3)):
        self.x, self.y, self.z = seed

    def get(self):
        x, y, z = self.x, self.y, self.z
        x = (171 * x) % 30269
        y = (172 * y) % 30307
        z = (170 * z) % 30323
        self.x, self.y, self.z = x, y, z
        w = (x/30269.0 + y/30307.0 + z/30323.0) % 1.0
        return int(w * 16)

def _test(n):
    generator = Random().get
    tree = BinaryTree()
    for i in xrange(n):
        tree.insert(generator())
    all = tree.inorder()
    last = -1
    totalcount = count = 0
    for x in all:
        if x == last:
            count = count + 1
        else:
            if count:
                print last, "appeared", count, "times"
                totalcount = totalcount + count
            last = x
            count = 1
    if count:
        print last, "appeared", count, "times"
        totalcount = totalcount + count
    print "saw", totalcount, "in all"

if __name__ == "__main__":
    import sys
    _test(int(sys.argv[1]))

Perl version:

package Node;
sub new {
    my ($class, $val) = @_;
    return bless {"val" => $val, "left" => undef, "right" => undef}, $class;
}

package BinaryTree;
sub new {
    return bless {"root" => undef}, shift;
}

sub insert {
    my ($self, $val) = @_;
    my $root = $self->{root};
    my $lastdir = undef;
    while (defined $root) {
        $lastroot = $root;
        if ($val <= $root->{val}) {
            $lastdir = 'left';
            $root = $root->{left};
        }
        else {
            $lastdir = 'right';
            $root = $root->{right};
        }
    }
    my $newguy = new Node($val);
    if (!defined($lastdir)) {
        $self->{root} = $newguy;
    }
    elsif ($lastdir eq 'left') {
        $lastroot->{left} = $newguy;
    }
    else {
        $lastroot->{right} = $newguy;
    }
}

sub helper {
    my ($self, $root, $result) = @_;
    if (defined $root) {
        $self->helper($root->{left}, $result);
        push(@$result, $root->{val});
        $self->helper($root->{right}, $result);
    }
}

sub inorder {
    my $self = shift;
    my $result = [];
    $self->helper($self->{root}, $result);
    return $result;
}

package Random;
sub new {
    my $class = shift;
    return bless {"x" => 1, "y" => 2, "z" => 3}, $class;
}

sub get {
    my $self = shift;
    my ($x, $y, $z) = ($self->{x}, $self->{y}, $self->{z});
    $x = (171 * $x) % 30269;
    $y = (172 * $y) % 30307;
    $z = (170 * $z) % 30323;
    ($self->{x}, $self->{y}, $self->{z}) = ($x, $y, $z);
    # Perl doesn't do something sensible with float % float, so fake it by
    # hand.
    my $w = $x/30269.0 + $y/30307.0 + $z/30323.0;
    $w -= int $w;
    return int($w * 16);
}

package main;
sub _test {
    my $n = shift;
    my $generator = new Random;
    my $tree = new BinaryTree;
    foreach (1 .. $n) {
        $tree->insert($generator->get());
    }
    my $all = $tree->inorder();
    my $last = -1;
    my ($totalcount, $count) = (0, 0);
    foreach (@$all) {
        if ($_ == $last) {
            ++$count;
        }
        else {
            if ($count) {
                print "$last appeared $count times\n";
                $totalcount += $count;
            }
            $last = $_;
            $count = 1;
        }
    }
    if ($count) {
        print "$last appeared $count times\n";
        $totalcount += $count;
    }
    print "saw $totalcount in all\n";
}

_test($ARGV[0]);