6
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ SvPVbyte(), SvPVX() and others missing from this post. \$\endgroup\$ – chux - Reinstate Monica Feb 16 '18 at 17:47
  • \$\begingroup\$ If SvPVbyte() is a function, STRLEN len; char *str = SvPVbyte(str_sv, len); ... if (len == 0 ... is undefined behavior as len is never assigned \$\endgroup\$ – chux - Reinstate Monica Feb 16 '18 at 17:50
  • 1
    \$\begingroup\$ @chux The functions are defined by including perl.h. This header is included autmatically when Inline::C compiles the C source file. Also, the function SvPVbyte is actually a macro, so one should not use & in front of the len output parameter, see perlguts for more information.. \$\endgroup\$ – Håkon Hægland Feb 16 '18 at 18:00
  • \$\begingroup\$ FYI: Code is O(len * (len1 + len2)). With more work, code could be O(len + (len1 + len2)). Requires more details than I care to answer. \$\endgroup\$ – chux - Reinstate Monica Feb 16 '18 at 18:50
  • 1
    \$\begingroup\$ The key idea to to pre-process delim looking for repeated characters/pattern. So when a mis-match occurs, code may advance by more than 1 character in the string. E.g. With delim == "abcdef" and pattern match fails string "abcdX...", code can start again at X, rather than b. See String searching algorithm \$\endgroup\$ – chux - Reinstate Monica Feb 16 '18 at 19:45
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.