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

[Emmanuel Oga <emmanueloga@...>]

Sean,

       subsequence.subsequenceMatch("banunus","as")

should return 1, I checked it out and  it works as intended (the
subsequence comes first, the string comes next).


I modified the algorithm to use some pointer arithmetic based on the
code of David, check it out:

https://gist.github.com/938457#file_subsequence.c

the modifications where just aesthetic:, both programs produce aprox
the same performance.

it got from ~8x to ~11x!! (luajit2)

Probably I wont be able to squeeze any further speed here w/o
preindexing somehow the strings, but it is good enough for now.

Txs!
--------------------------------------------------------------
EmmanuelOga.com - Software Developer



On Sat, Apr 23, 2011 at 2:36 PM, David Favro <lua@meta-dynamic.com> wrote:
> 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
>
>