Fastest way to find a string delimited by two words

Question

Motivated by this question, I created a simple benchmark for investigating what is the fastest way to extract a substring given two delimiting words:

#! /usr/bin/env perl
use feature qw(say);
use strict;
use warnings;

use Benchmark qw(cmpthese);
use Inline C => './find_c.c';

my %methods = (
    find_quick   => \&find_quick,
    find_substr  => \&find_substr,
    find_index   => \&find_index,
    find_regex1  => \&find_regex,
    find_regex2  => \&find_regex,
    find_c       => \&find_c,
);

my %test_types = (
    short  => 2,
    medium => 20,
    long   => 200,
);

my $num_tests = ( scalar keys %test_types ) ** 3;
my $i = 1;
for my $delim_type (qw( short medium long )) {
    for my $substr_type (qw( short medium long )) {
        for my $prefix_type (qw( short medium long )) {
            run_test( $delim_type, $substr_type, $prefix_type, $i++, $num_tests );
        }
    }
}

sub run_test {
    my ( $delim_type, $substr_type, $prefix_type, $i, $N ) = @_;

    my $delim_len = $test_types{$delim_type};
    my $substr_len = $test_types{$substr_type};
    my $prefix_len = $test_types{$prefix_type};
    say "";
    say "----------------------------------";
    say "Running case: ($i/$N) delim=$delim_type,"
      . " substr=$substr_type, prefix=$prefix_type";
    say "----------------------------------";
    say "";
    my $delim1 = '<' x $delim_len;
    my $delim2 = '>' x $delim_len;
    my $substr = '1' x $substr_len;
    my $prefix = '2' x $prefix_len;
    my $postfix = '3' x 12; # some arbitrary trailing string

    my $regex1 = qr/\Q$delim1\E((?:(?!\Q$delim2\E).)*+)\Q$delim2\E/;
    my $regex2 = qr/\Q$delim1\E(.*?)\Q$delim2\E/;

    my $str = $prefix . $delim1 . $substr . $delim2 . $postfix;


    my %cmphash;
    # Before running the benchmark, check that all methods give correct output..
    for my $key (keys %methods) {
        my $method;
        if ( $key =~ /regex1/ ) {
            $method = sub { return $methods{$key}->( $str, $regex1 ) };
        }
        elsif ( $key =~ /regex2/ ) {
            $method = sub { return $methods{$key}->( $str, $regex2 ) };
        }
        elsif ( $key =~ /quick/ ) {
            $method = sub { return $methods{$key}->( $str, $substr ) };
        }
        else {
            $method = sub { return $methods{$key}->( $str, $delim1, $delim2 ) };
        }
        my $chk = $method->();
        if ( $chk ne $substr ) {
            die "Method: '$key' did not return correct result.\n";
        }
        $cmphash{$key} = $method;
    }
    cmpthese( -1, \%cmphash );
}

# Dummy method, to provide an lower limit on the run time
sub find_quick {
    my ($str, $substr) = @_;

    return $substr;
}

sub find_regex {
    my ($str, $regex) = @_;

    if ( $str =~ $regex) {
        return $1;
    }
    else {
        return "";
    }
}

sub find_index {
    my ($str, $delim1, $delim2) = @_;

    my $offset = (index $str, $delim1) + length $delim1;
    my $len = (index $str, $delim2, $offset) - $offset;
    return substr $str, $offset, $len; 
}

sub find_substr {
    my ($str, $delim1, $delim2) = @_;

    my $tmp = substr $str,
      (index $str, $delim1) + length $delim1;
    return substr $tmp, 0, index $tmp, $delim2;
}

And the C source file find_c.c is:

/* checks if the current position in str matches string delim
 *
 * Input arguments:
 *   i    : current position in str,
 *   len1 : length of str
 *   len2 : length of delim
 */ 
int check_delim( char *str, int i, char *delim, STRLEN len1, STRLEN len2 ) {
    int j = 0;
    while ( i < len1 ) {
        if ( str[i++] != delim[j++] ) {
            break;
        }
        if ( j >= len2 ) return 1;
    }
    return 0;
}

/* finds a substring of str delimited by strings delim1 at the left,
 * and delim2 at the right. 
 * Assumes neither of str, delim1, or delim2 are empty.
 */
SV *find_c(SV* str_sv, SV *delim1_sv, SV *delim2_sv) {
    STRLEN len, len1, len2;
    char *str = SvPVbyte(str_sv, len);
    char *delim1 = SvPVbyte(delim1_sv, len1);
    char *delim2 = SvPVbyte(delim2_sv, len2);
    if (len == 0 || len1 == 0 || len2 == 0) {
        croak( "Illegal input. Strings cannot be empty." );
    }
    SV* result = newSV(len);
    char *buf = SvPVX(result);
    int start = -1;
    int end = -1;
    // scan str from left for delim1
    for (int i = 0; i < (len - len1); i++) {
        if ( str[i] == delim1[0] ) {
            if ( check_delim( str, i, delim1, len, len1 ) ) {
                start = i + len1;
                break;
            }
        }
    }
    int j = 0; // index into result buffer
    // did we find delim1, if so continue scan for delim2
    if (start >= 0) {
        for (int i = start; i < (len - len2 + 1); i++) {
            if ( str[i] == delim2[0] ) {
                if ( check_delim( str, i, delim2, len, len2 ) ) {
                    end = i;
                    break;
                }
            }
            buf[j++] = str[i]; // copy to result buffer
        }
    }
    if ( end < 0 ) { // we did not find delim2..
        j = 0; // reset result index (meaning: erase everything, and put empty string)
    }
    buf[j] = '\0';  // null terminate result string
    SvPOK_on(result); // Make the result SV a string (i.e. a PV)
    SvCUR_set(result, j); // Set the length of the string in the result SV.
    return result;
}

Observations:

Based on running the 27 test cases on my laptop (see output), I can see that:

• regex1 is always slower than regex2
• index and substr is approximately the same speed for all cases
• substr/index is usually faster than regex2, but not for some of the cases where the delimiters are long, see cases 19, 21, 25
• find_c is usually faster than the other methods, but not for case 9 where the the delimiter is short and the substr is long.
• In some of the simpler cases the find_c is faster than the upper limit provided find_quick, see cases 1 and 2.

Answer 1

Fastest way to find a string delimited by two words

check_delim() can be linearly made faster by taking advantage that a string ends with the first null character.

No need for 2 checks of lengths on each iteration of the loop. Code can get by with 1 check and often 0 length checks.

Use const to allow additional optimizations.

Change names for clarity.

int check_delim(const char *str, int i, const char *delim, 
    STRLEN len_str, STRLEN len_delim ) {
  if (i >= len_str) {  // This test might be able to be omitted.
    return 0;
  }    
  len_str -= i;
  str += i;
  if (len_str == len_delim) {
    // same length - check offset and look for any mis-match
    while (--len_str > 0 && str[len_str] == delim[len_str]) {
      ;
    }
    return str[len_str] == delim[len_str];
  }
  i = 0;
  // Different lengths - look for any mis-match - no need to check `i`.
  // Null character of one string will not match the non-null character of the other.
  while (str[i] == delim[i]) {
    i++;
  }
  // Did str[] match all the delimiter?
  return delim[i] == '\0';
}

Note: I'd expect int i to be the same type as STRLEN len_str.