[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: LismMachine File Reading.

I've looked into READ and have found a way to speed it up by a factor of 4.

Say i open a file:

(setq f (open "dino:/usr/kanderson/baa/seis/ti/rt.det.shrink"))


When i do (read f) we go through the following functions:

   (SEND STREAM ':OPERATION-HANDLED-P ':READ)	; <- big win if stream handles this?
   (and presentation-type ...
     (SI:XR-XRTYI-WHITE-OUT STREAM T)		; Should be inlined.
      SI:XR-XRTYI				; How reader gets characters.
       :ANY-TYI method: SI:INPUT-STREAM default
                    whopper, SI:INDIRECT-INPUT-STREAM-MIXIN
          :TYI method: SI:BASIC-BUFFERED-INPUT-STREAM	; of an internal stream.
          ... Finally we get a character ...
       Check for mouse blips.
       Lookup in readtable finite state machine.
       Check for white space.

Ways to speed this up:

o When READ starts up, we go through 14 funcalls and 4 method
  dispatches to get to the first character, and lots of optional arg
  checking [a cost of flexibiliy].  Compiler optimizers should
  optimize some of this overhead away somehow.

o There are many things about the stream that READ checks over and
  over again.  For example, my stream never handles the :READ message,
  never deals with presentation types, and never sees escape
  characters or mouse blips.  Such things should be factored out of
  READ loops.

o The inner character reading loop has 6 funcalls in it, there should
  only be 1.  There are mixins that worry about ESCAPE-LOADING and
  INDIRECT-INPUT.  What i really want is the
  SI:BASIC-BUFFERED-INPUT-STREAM that is inside the stream given to me
  by open:

  "DINO:/usr/kanderson/baa/seis/ti/rt.det.shrink.~newest~" 326616042>

So, i did the following experiment [you can follow along in the 

o Using :element-type 'character (what you get if you do (OPEN file)
  causes most of the stream overhead.  So switching to :element-type
  'string-char which does only a :any-tyi and :tyi in the inner loop.

o To go one step further i overwrote :any-tyi for
  BUFFERED-INPUT-STREAM to do what :TYI does directly, saving 1
  function call.

o I then pulled things out of the read function i didn't need for non
  interactive I/O.  Basically, the new read is a rewrite of
  READ-INTERNAL-1 without optional arguments.

o I also modified XR-READ-THING to inline SI:XR-XRTYI-WHITE-OUT.

I used the following timing functions:

(defun try (N stream) ; old read.
  (si:without-interrupts (time (dotimes (i N) (read stream)))))

(defun %try (N stream) ; new read.
  (si:without-interrupts (time (dotimes (i N)
	(!read stream #'si:read-for-top-level 'si:NO-EOF-OPTION)))))

Here are the times for N = 2000 reading a file on a unix machine.

                       time    relative
function :element-type (sec)     time
read      character    20.1      1.0
read      string-char  11.02     0.55
!read     character     6.27     0.31
!read     string-char   4.71     0.23

So READ is about 4 times faster that what you get if you do 

  (read (open flile))

I'm sure we can do better.  For example, perhaps XR-XRTYI and
XR-XRUNTYI should be closures that inline the :ANY-TYI etc as they do
in C.  We should be able to write something like (MAKE-READER STREAM
READTABLE &REST ARGS) that makes as an efficient reader as possible
given the stream and other characteristics.

The flexiblity of READ lets us read other languages besides LISP,
simply by changing *readtable*.  This flexibility is the ultimate
performance limit of the current READ.