From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA08754 for caml-red; Tue, 12 Dec 2000 10:22:32 +0100 (MET) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id XAA26804 for ; Mon, 11 Dec 2000 23:41:35 +0100 (MET) Received: from moutvdom00.kundenserver.de (moutvdom00.kundenserver.de [195.20.224.149]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id eBBMfYv17333 for ; Mon, 11 Dec 2000 23:41:34 +0100 (MET) Received: from [195.20.224.219] (helo=mrvdom03.kundenserver.de) by moutvdom00.kundenserver.de with esmtp (Exim 2.12 #2) id 145bdQ-0007Qw-00; Mon, 11 Dec 2000 23:41:28 +0100 Received: from drms-3e364b82.pool.mediaways.net ([62.54.75.130] helo=ice.gerd-stolpmann.de) by mrvdom03.kundenserver.de with esmtp (Exim 2.12 #2) id 145bdL-0004iJ-00; Mon, 11 Dec 2000 23:41:24 +0100 Received: from localhost (localhost [[UNIX: localhost]]) by ice.gerd-stolpmann.de (8.9.3/8.9.3) id XAA02997; Mon, 11 Dec 2000 23:41:15 +0100 From: Gerd Stolpmann Reply-To: gerd@gerd-stolpmann.de Organization: privat To: Chris Hecker , eijiro_sumii@anet.ne.jp, caml-list@inria.fr Subject: Re: substring match like "strstr" Date: Mon, 11 Dec 2000 23:22:08 +0100 X-Mailer: KMail [version 1.0.28] Content-Type: text/plain Cc: gerd@gerd-stolpmann.de, sumii@venus.is.s.u-tokyo.ac.jp References: <00120814135508.00625@ice> <4.3.2.7.2.20001211103237.00c12100@shell16.ba.best.com> In-Reply-To: <4.3.2.7.2.20001211103237.00c12100@shell16.ba.best.com> MIME-Version: 1.0 Message-Id: <0012112341150J.00625@ice> Content-Transfer-Encoding: 8bit Sender: weis@pauillac.inria.fr 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 ----------------------------------------------------------------------------