Subject: [clisp-list] About speed, and regexp&FFI in particular (was: A general query o n the virtual machine)

From: "Hoehle, Joerg-Cyril" <[email-masked]>
Date: Wed Apr 17 01:28:16 2002

Hi,

Raymond Toy writes:
> There will always be something that needs the speed.

Except for strict number crunching (wheather forecasts etc.) I see
the need mostly induced by broken software design. This consumes
tons and tons of cycles, making even today's machines look slow.

E.g. GUI: on slow machines, you can see how many applications refresh
their windows 2 to 3 times. Do you think the designers and programmers
solved the problems? No, they (and the users) moved to faster machines
where multiple refresh doesn't blink on the eye anymore.

E.g. CLISP regexp: I've yet to post the figures (at home). But in short:
CLISP modules/regexp performance is abysmal in certain situations.
This is not due to regex.c, somewhat due to the FFI, not due to CLISP
strictly speaking (as opposed to native code compilers like CMUCL).

It's due to the API that the regexp module and FFI provide and makes
things impossible or dreadfully slow.

Yet, nobody ever complained here that CLISP's regexp may become slow beyond any belief! (Who uses it? please raise hands :)

 + On my machine, it takes 0.203 seconds to find the 3 occurrences
   of "Extracts" in the 1MB large file impnotes.html
 - It takes 50 seconds(!!) to find the 2839 occurrences of "lisp"
   using the following code.

The reason is IMHO due to regexp' use of the CLISP FFI and its
property to copy everything on the stack. As a result, subparts
of the 1MB impnotes text are repeatedly copied on the stack.
An O(n) algorithm (n length of text) becomes O(n*m) (m number
of matches), and it shows :-(

The search "speed" is brought down to reasonable values (< 1 second
IIRC, figure at home), when, using my work-in-progress FFI, I allocate
the impnotes buffer *once* and pass a reference to it (using the
:start keyword), like anybody would do in C, instead of copying the
huge FFI:C-STRING type argument on every match. The current CLISP
FFI doesn't provide an interface for doing this.

Of course, there's some tradition in the last decade to buy
machines 50 times faster instead of working on software design,
so search time also stays within one second for up-to-date users (buyers).

Regards,
	Jorg Hohle.
Why buy faster machines instead of doing homework?
Maybe my fault is that I grew up in times when people still counted
machine cycles and knew the number of cycles most processor
instructions required?

(defun test1 (&optional (text *huge-buffer*))
  (ext:space
   (loop for pos = 0 then (regexp:match-end m)
	 for m = (regexp:match "lisp" text :start pos
			       :case-sensitive t)
	 while m
	 collect (regexp:match-start m))))

;(defvar *regexp-testfile* ".../src/clisp-2.28/src/impnotes.html")

(defun read-file (&optional (name *regexp-testfile*))
  (with-open-file (f name :direction :input
		     :external-format
		     (ext:make-encoding :charset 'charset:iso-8859-1
					:line-terminator :unix))
    (let ((buffer (make-string (file-length f))))
      ;;TODO test length = read
      (values
       buffer
       (read-char-sequence buffer f)))))

;(multiple-value-bind (buf l) (read-file) (list (length buf) l))
;(defvar *huge-buffer* (read-file))

---

From: Raymond Toy <[email-masked]>
Date: Wed Apr 17 06:30:13 2002

>>>>> "Joerg" == Hoehle, Joerg-Cyril <[email-masked]> writes:

    Joerg> Hi,
    >> There will always be something that needs the speed.

    Joerg> Except for strict number crunching (wheather forecasts etc.) I see
    Joerg> the need mostly induced by broken software design. This consumes
    Joerg> tons and tons of cycles, making even today's machines look slow.

I'm biased.  I do number crunching with Lisp (mostly CMUCL).

    Joerg> E.g. GUI: on slow machines, you can see how many applications refresh
    Joerg> their windows 2 to 3 times. Do you think the designers and programmers
    Joerg> solved the problems? No, they (and the users) moved to faster machines
    Joerg> where multiple refresh doesn't blink on the eye anymore.

This is also one of my pet peeves.  I think developers should develop
on the fastest machine they can find, but run the GUI on the slowest
machine they can find.  While I run Mozilla everywhere and all the
time, I think it's one of the worst offenders.  A simple dialog box
takes forever to come up.  It's almost to slow to use on a 300 MHz
Ultra 30.

    Joerg> E.g. CLISP regexp: I've yet to post the figures (at home). But in short:
    Joerg> CLISP modules/regexp performance is abysmal in certain situations.
    Joerg> This is not due to regex.c, somewhat due to the FFI, not due to CLISP
    Joerg> strictly speaking (as opposed to native code compilers like CMUCL).

Have you tried one of the pure Lisp implementations of regex routines?
I tried 2 different ones for Maxima: nregex from the CMU AI archives,
and regex by Shenoy.  regex was abysmally slow with Clisp, but very
fast with CMUCL.  nregex was very fast on Clisp and just fast enough
with CMUCL.  I think nregex was only slightly slower then Clisp's
regexp module for looking up info documention for maxima.

But this no longer really has anything to do with clisp....

Ray