Re: substring match like "strstr"

[Gerd Stolpmann <gerd@gerd-stolpmann.de>]

On Mon, 11 Dec 2000, Chris Hecker wrote:
>Any ideas why strstr blows the others away?  

It's the type of brain-dead loop for which C compilers are written.

>Have you tried a purely imperative version?  I'd say I'd do the tests myself,
>but I don't have a bunch of gene sequences laying around.  :)   

It's not always the imperative version which is better. The difference in the
generated code of a functional and an imperative version is often minimal.

>Looking at the asm output from strstr_imp, there's not that much you could do
>to make it better.  Maybe there are a few peephole things, and there are
>probably 30% more instructions than you need in this specific case because the
>code to compare characters goes to the trouble of keeping the ints in the caml
>format even in registers inside the loop (so they're shifted back and forth),
>and it converts the chars from the unsafe_gets to full caml ints, which is
>useless since they just get compared to each other and then dumped.  It might
>be interesting to write a peephole optimizer aimed at peepholing camlopt code,
>and looking for things like this. 
> 
>Can anybody optimize the caml src for strstr_imp? 

let strstr_imp2 pat str =
  let strlen = String.length str in
  let patlen = String.length pat and
    i = ref 0 and
    f = ref strlen in
  let i_limit = strlen - patlen in
  while !i < i_limit do
    let pati = ref 0 and
      j = ref !i in
    while !pati < patlen &&
      String.unsafe_get str !j == String.unsafe_get pat !pati do
	pati := succ !pati;
	j := succ !j;
    done;
    if !pati = patlen then
      begin f := !i; i := strlen end
    else
      i := succ !i
  done;
  !f
;;

Perhaps !pati < patlen can also be removed by introducing a "guard" (modifying
the last character of pat such that the loop runs always into an inequality).
However, this would require extra code managing the temporary modification of
pat, and I guess it is not worth-while for short pats.

Gerd
--
----------------------------------------------------------------------------
Gerd Stolpmann      Telefon: +49 6151 997705 (privat)
Viktoriastr. 100             
64293 Darmstadt     EMail:   gerd@gerd-stolpmann.de
Germany                     
----------------------------------------------------------------------------