inline perl and recursion

[abitkin]

I am looking to save some time when going through a large data structure, mainly I would like to have the recursive call go through c, rather than perl.

Here is an example sub that I'm using:

# object1:
sub depth{
    my $self = shift;
    my $max = 0;
    foreach my $item (0 .. 15){
        if(defined($self->{child}->[$item])){
            my $temp = $self->{child}->[$item]->depth; 
            if($temp > $max){
                $max = $temp;
            }
        }
    }
    $self->{myDepth} = $max+1;
    return $max+1;
}

# object2
sub depth{1}

Now there is a base case, a child can be an object 1 or 2, but an object 2 has no children.

My question is how would this best be impmented through inline c, if it is possible. Nothing I've read on inline c has the complexity of recursion, and I do not know what $self looks like in c (do the refs to the same type of object become pointers, or what?)

[dws]

I am looking to save some time when going through a large data structure, mainly I would like to have the recursive call go through c, rather than perl.

I don't know about recurion in XS (C), but you can save a little bit of time by recoding your traversal algorithm to avoid array dereferencing. Something like the following (untested):

# object1:
sub depth{
    my $self = shift;
    my $max = 0;
    foreach my $item ( @{$self->{child}} ) {
        next if ! defined ($item);
        my $depth = $item->depth();
        $max = $depth if $depth > $max;
    }
    $self->{myDepth} = $max+1;
    return $max+1;
}

[jackdied]

Inline::C would likely be more complicated that it is worth. You may be able to squeeze some more uumph out of the perl version, as the poster above pointed out.

If you are recalculating this more than once (it doesn't look like you are) you could have the children notify the parent when their own depth changes. This way you wouldn't have to recalc the whole tree if just a couple changed.

If you are only doing this once, you could try some other optimizations. Keep two lists of children in the parent, one for object type #1's (which have variable depth) and the main list which has all objects. If the max depth of the #1s list is greater than one, just use that. If there are alot of #2 nodes, you save the function call overhead. Not great OO, but if you need the speed ...

You could try something like

sub depth {
my $self = shift;
return $self->{myDepth} = shift(sort map{ $_->depth(); } @{$self->{chi
+ld}}[0:14]) + 1;
}

To speed up the inner loop as well. That might have a touch of python syntax in it, but it is close to what you want.

[derby]

While not directly answering your question (I really don't see any recursion in the example). Recursion is possible with Inline::C. $self can look like almost anything, it depends on how you set up your code. Here's a very contrived example borrowing from K&R's "Self-referential Structures" paragraph (chapter 6.5 from K&R 1). First is a simplistic pure-perl approach (not that I recommend doing trees this way in perl).

#!/usr/bin/perl -w

package Tnode;

sub new {
   my( $class, $word, $count ) = @_;
   my $self = {};
   $self->{word}  = $word;
   $self->{count} = $count;
   $self->{left}  = undef;
   $self->{right} = undef;

   return bless $self, $class;
}

package main;

die unless @ARGV;

my $root = undef;

while(<>) {
   chomp;
   $word = $_;
   $root = tree( $root, $word );
}

treeprint( $root );

sub tree {
   my( $node, $word ) = @_;

   if( ! $node ) {
      $node = Tnode->new( $word, 1 );
      $node->{left} = undef;
      $node->{right} = undef;
   } elsif( $node->{word} eq $word ) {
      $node->{count}++;
   } elsif( $word lt $node->{word} ) {
      $node->{left} = tree( $node->{left}, $word );
   } else {
      $node->{right} = tree( $node->{right}, $word );
   }

   return $node;
}

sub treeprint {
   my( $root ) = shift;

   if( $root ) {
      treeprint( $root->{left} );
      printf( "%4d %s\n", $root->{count}, $root->{word} );
      treeprint( $root->{right} );
   }
}

given a file with a list of words, this script will output the ascii ordered words with their counts.

Now here's the sample example with the treeprint function done via inline. Now a couple notes about this example, my brain could not make the hv_fetch function work correctly, so this example rather ineffeciently uses a for loop to walk the hash entries. And speaking of hashes, we just assume the reference is a hash and blithely cast it as such (not good coding but the attempt here is to show recursion).

#!/usr/bin/perl -w

use Inline C;

package Tnode;

sub new {
   my( $class, $word, $count ) = @_;
   my $self = {};
   $self->{word}  = $word;
   $self->{count} = $count;
   $self->{left}  = undef;
   $self->{right} = undef;

   return bless $self, $class;
}

package main;

die unless @ARGV;

my $root = undef;

while(<>) {
   chomp;
   $word = $_;
   $root = tree( $root, $word );
}

treeprint( $root );

sub tree {
   my( $node, $word ) = @_;

   if( ! $node ) {
      $node = Tnode->new( $word, 1 );
      $node->{left} = undef;
      $node->{right} = undef;
   } elsif( $node->{word} eq $word ) {
      $node->{count}++;
   } elsif( $word lt $node->{word} ) {
      $node->{left} = tree( $node->{left}, $word );
   } else {
      $node->{right} = tree( $node->{right}, $word );
   }

   return $node;
}
__END__
__C__

void treeprint( SV *root ) {

   HV* hash;
   HE* hash_entry;
   SV* node;
   SV* word;
   SV* count;

   if( !SvROK(root) )
      return;

   hash = (HV*)SvRV(root);

   node = get_child( hash, "left" );
   if( node != NULL ) {
      treeprint( node );
   }

   output( hash );

   node = get_child( hash, "right" );
   if( node != NULL ) {
      treeprint( node );
   }
}

SV *get_child( HV *hash, char *key ) {
   int num_keys, i;
   HE *hash_entry;
   SV *sv_key;
   SV *sv_val;

   num_keys = hv_iterinit(hash);
   for (i = 0; i < num_keys; i++) {
      hash_entry = hv_iternext(hash);
      sv_key = hv_iterkeysv(hash_entry);
      sv_val = hv_iterval(hash, hash_entry);
      if( strcmp( SvPV( sv_key, PL_na), key ) == 0 ) {
         return( sv_val );
      }
   }

   sv_val = NULL;
   return sv_val;
}

void output( HV *hash ) {
   int num_keys, i;
   HE *hash_entry;
   SV *sv_key;
   SV *sv_val;
   int count;
   char *word = NULL;

   num_keys = hv_iterinit(hash);
   for(i = 0; i < num_keys; i++) {
      hash_entry = hv_iternext(hash);
      sv_key = hv_iterkeysv(hash_entry);
      sv_val = hv_iterval(hash, hash_entry);
      if( strcmp( SvPV( sv_key, PL_na), "word" ) == 0 ) {
         word = SvPV( sv_val, PL_na);
      }
      if( strcmp( SvPV( sv_key, PL_na), "count" ) == 0 ) {
         count = SvIV( sv_val );
      }
   }

   if( word ) {
      printf( "%4d %s\n", count, word );
   }
}

Now that all being said, a benchmark of the two approaches shows very little difference

Benchmark: timing 50000 iterations of inline, perl...
   inline: 13 wallclock secs (12.42 usr +  0.00 sys = 12.42 CPU) @ 
      4025.76/s (n=50000)
   perl: 12 wallclock secs (12.27 usr +  0.00 sys = 12.27 CPU) @ 
      4074.98/s (n=50000)

but maybe if I could get hv_fetch to work properly, there would be a noticeable diff.

-derby