Subject: [clisp-list] fastest (character) based io with CLISP? - unicode is fast, posit ion dead slow

From: "Hoehle, Joerg-Cyril" <[email-masked]>
Date: Tue Feb 18 01:20:09 2003

Hi,

Here's some data to support the claim that POSITION (and by deduction COUNT and all the other sequence functions) are dead slow.

Using a 50MB log file, causing 474832 calls to POSITION (code below), I obtain
Real time: 34.906 sec.
Run time: 34.53125 sec.
Space: 531_720 Bytes
GC: 2, GC time: 0.015625 sec.

Using my specialised VECTOR-POSITION, I obtain
Real time: 5.063 sec.
Run time: 4.6875 sec.
Space: 531_720 Bytes
GC: 2, GC time: 0.0 sec.

This difference is far from negligible in my current application.

The believed reason that the sequence functions are slow is that they are overly generic. Moving from one element to the next in the sequence causes plenty of calls. There's nothing like a tight loop.

I advocate that CLISP should recognize optimizable cases and handle them internally. The time to test internally at run-time for optimizable cases is negligible compared to the full-blown sequence and stepping overhead, especially for a byte-code VM like CLISP.

Optimizable cases are, at a glance
o vector instead sequence (possibly only string or unsigned-byte 8/16/32)
o and test EQ or EQL (or maybe CHAR= and = with corresponding array element-type)
o with KEY #'IDENTITY
o :from-end is optimizable as well (means almost duplicate code).

Specifically, I advocate that CLISP handles these cases transparently and does not expose something like EXT:VECTOR-POSITION. CLISP should encourage portable code and thus use of CL:POSITION etc., with guarantees that it will be fast where it can be. As a result, non CLISP-specific code will be fast as well, without the need to go look for places where VECTOR-POSITION may be applicable and add #+CLISP hacks.

This said, I'll post my preliminary hack of vector-position (so far really only string-position) to the patches section of sourceforge.
http://sourceforge.net/tracker/index.php?func=detail&aid=688545&group_id=1355&atid=301355

(defun test1 (&optional (logfile "50MB.log.txt"))
 (space
  (with-open-file (stream logfile :direction :input
			  #+CLISP :buffered #+CLISP T
			  :element-type 'character)
    (let ((vec (make-array (ash 2 17) :element-type 'character)))
      (loop
       for max = (ext:read-char-sequence vec stream)
       for block-count from 0
       while (= max (length vec))
       ;TODO handle lines at buffer boundary and rest portion
       do (loop
	   for start = 0 then (1+ stop)
	   for stop = (position #\newline vec :start start :end max)
	   while stop))))))
test2 is test1 with position replaced by
 (EXT::VECTOR-POSITION #\newline vec start max)

Maybe there are more restriction on optimizable cases: what does the standard say on fill-pointers w.r.t. changes while within POSITION (e.g. the KEY or TEST functions may change the fill-pointer) or is that too hairy?

Regards,
	Jorg Hohle.
And the next thing to be handled internally may well be (CONCATENATE 'STRING ...all-strings) (dog slow) -> EXT:STRING-CONCAT (fast). Timings I did many years ago showed a comparable slowdown. I don't know if anybody ever changed this since I noticed this.