Hi!
I'm in a situation where I want to find a (short) substring of another
(long) string and I want it to be fast. My initial approach was to use
SEARCH but I wasn't really happy with the performance and thus wrote
my own little toy implementation which benefits from the fact that I
don't have to be as general as SEARCH is - I don't deal with
sequences, just (simple) strings - and I don't have to take into
account all the key parameters because I know in advance how long my
strings will be and where in the string I want to search.
It turned out that my own approach was indeed much faster:
(defun foo ()
(declare (optimize (speed 3) (safety 0) (space 0) (debug 0)))
(let ((s1 (concatenate 'string
(make-string 1000000 :initial-element #\a)
"b"))
(s2 "ab"))
(declare (type simple-string s1 s2))
(time (dotimes (i 100)
(search s2 s1 :test #'char=)))))
(defun bar ()
(declare (optimize (speed 3) (safety 0) (space 0) (debug 0)))
(let ((s1 (concatenate 'string
(make-string 1000000 :initial-element #\a)
"b"))
(s2 "ab"))
(declare (type simple-string s1 s2))
(time (dotimes (i 100)
(loop for index1 of-type fixnum from 0 to 1000000
thereis (loop for index2 of-type fixnum from 0 to 1
always (char= (char s1 (+ index1 index2))
(char s2 index2))
finally (return index1)))))))
* (foo)
Evaluation took:
13.35 seconds of real time
13.28418 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
NIL
* (bar)
Evaluation took:
1.7 seconds of real time
1.699219 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
NIL
(The functions are of course compiled and I take it that CMUCL won't
be able to optimize further because I got no notes when compiling
them.)
While this is a significant speed bump I still see that some, cough,
cough, inferior languages are faster. See this example:
edi@bird:~ > time perl -e '$s1 = "a" x 1000000 . "b"; $s2 = "ab"; for ($i = 0; $i <
100; $i++) { index $s1, $s2; }'
real 0m0.618s
user 0m0.611s
sys 0m0.004s
Ooops! I've seen enough occasions where CMUCL was faster or just as
fast as good C code so I was pretty surprised to see Perl (i.e. Perl's
C implementation of its find function) to beat CMUCL by a factor of
almost 3.
Why is this? Is my algorithm too dumb and/or did I miss something? Or
are there some reasons inherent in CMUCL's or rather CL's
string/sequence handling that prevent it from being as fast as C?
(I suppose that simple strings in CMUCL are just sequences of octets
in memory as in C so maybe what's lacking is a Lisp idiom[1] to just
advance a pointer to the current character?)
I might add that I'm mainly interested in portable solutions. I use
CMUCL as my reference implementation and it wouldn't hurt if CMUCL
were much faster than the rest of the crowd but I want the code to run
on other CL implementations as well.
Thanks in advance for your comments.
Edi.
[1] I tried 'LOOP FOR ... ACROSS' which didn't buy me
anything. Looking at the macroexpansion this doesn't surprise me
because obviously it basically uses the method shown in BAR above
but has to compute the LENGTH of both strings before starting the
iteration. Also, it seems[2] to use AREF instead of CHAR which
might be another factor.
[2] I'm writing "it seems" because I don't know what the compiler
might do with the AREF I saw. Maybe it's able to replace it with
CHAR given my declarations.
