Re: help optimizing a small lua function implemented in a C module.

[David Favro <lua@...>]

Hi Emmanuel --

While I haven't profiled it, I think that it will be hard to get any
huge speed-up in your benchmark because it mostly uses short strings and
subsequences, so that much of the time will be consumed in the overhead
of the function-calls, lua-parameter-extraction, etc. rather than the
meat of the algorithm itself.  I got about a 15% speed-up in your
benchmark over your C-subsequence function by using the attached one,
the biggest change is using pointer comparison against an end-of-string
pointer rather than integer increment and comparison for the loops.  By
using longer strings, I was able to increase the speed-up of my version
from ~15% to a more dramatic 32% (inversely seen as a 46% slowdown of
your version over mine) by applying the included patch to your benchmark
to use mostly long strings, although profiling will help identify where
to best target optimisation.

-- David

/*
** gcc -fPIC -shared -I/usr/local/include/lua/5.1 -O3 -Wall -Wextra subsequence2.c -o subsequence.so
*/


#include "lua.h"
#include "lualib.h"
#include "lauxlib.h"


static int l_subsequenceMatch(lua_State *L) {
  size_t lstr;
  size_t lpat;
  int found = 0;
  const char *pattern = luaL_checklstring(L, 1, &lpat);
  const char *str     = luaL_checklstring(L, 2, &lstr);
  const char *pPtr;

  if (lpat == 0) {
    found = 1;
  } else {
    const int pidx = lua_tonumber(L, 3) - 1;
    pPtr = pattern + ((pidx < 0) ? 0 : pidx);
    const char * const pEnd = pattern + lpat;

    if (pPtr < pEnd) {
      const char * const sEnd = str + lstr;
      for ( ; str < sEnd ; ) {
        if ( (*str++ == *pPtr) && (++pPtr >= pEnd) ) {
          found = 1;
          break;
        }
      }
    } else {
      found = 1;
    }
  }

  if (found) {
    lua_pushboolean(L, 1);
  } else {
    lua_pushnumber( L, pPtr - pattern + 1 );
  };

  return 1;
}

static const struct luaL_Reg subsequence [] = {
  {"subsequenceMatch", l_subsequenceMatch},
  {NULL, NULL} /* sentinel */
};

int luaopen_subsequence(lua_State *L) {
  luaL_register(L, "subsequence", subsequence);
  return 1;
}

--- sseq_bench.lua	2011-04-24 00:31:44.096066001 +0700
+++ sseq_bench_longer.lua	2011-04-24 00:31:57.886066000 +0700
@@ -18,17 +18,18 @@
 local ssmC = require('subsequence').subsequenceMatch
 
 local LONG = string.rep("z", 100).."app/models/user.rb"
+local bananas = string.rep("h",9000).."bananas"
 function test(cbk)
-  cbk(""   , "bananas"     )
-  cbk("as" , "bananas"     )
-  cbk("bas", "bananas"     )
-  cbk("x"  , "bananas"     )
-  cbk("caf", "bananas"     )
-  cbk("bfa", "bananas"     )
+  cbk(""   , bananas       )
+  cbk("as" , bananas       )
+  cbk("bas", bananas       )
+  cbk("x"  , bananas       )
+  cbk("caf", bananas       )
+  cbk("bfa", bananas       )
   cbk("bfa", "fanatic"     )
   cbk("bfa", "fanatic"  , 2 )
   cbk("bax", "bananasx" , 3 )
-  cbk("bax", "bananas"  , 3 )
+  cbk("bax", bananas    , 3 )
   cbk(string.rep("a/m/user", 10), LONG)
   cbk("bfa123123123123123123123123123123", "bananas123123123123123123123123123123"     )
   cbk("b123123123123123123123123123123fa", "fa123123123123123123123123123123natic"     )
@@ -40,5 +41,5 @@
 
 local TIMES = 50000
 
-bench("lua",   TIMES, function() test(ssm) end)
+--bench("lua",   TIMES, function() test(ssm) end)
 bench("C ext", TIMES, function() test(ssmC) end)