making Lisp faster by giving it 40 more bits (was: Wasting Time)

From: André Thieme (address.good.until.2004.jun.05_at_justmail.de)
Date: 05/29/04

  • Next message: André Thieme: "Re: making Lisp faster by giving it 40 more bits" 
    Date: Sat, 29 May 2004 02:47:21 +0200

    David Steuber wrote:
    > I wrote a simple little function to simulate a web page request taking
    > several seconds to calculate before beginning to return a result. As
    > strange as it may sound, I got side tracked because I was disappointed
    > in the efficiency of my time wasting function. I actually learned a
    > few things along the way.
    >
    > ;;; Time waster
    >
    > ;; the declarations in this function make no noticable difference
    > (defun waste-time ()
    > (do ((tim (+ 2 (get-universal-time)))
    > (i 0 (the fixnum (1+ i))))
    > ((< tim (get-universal-time)) i)
    > (declare (fixnum i))))
    >
    > ;; the declerations in this function improved speed by about x10
    > (defun count-to-n (n)
    > (do ((i 0 (the fixnum (1+ i))))
    > ((<= n i) i)
    > (declare (fixnum i n))))
    >
    > ;; self explanatory
    > (defun time-waste-time ()
    > (let ((tim (time (waste-time))))
    > (time (count-to-n tim))))
    >
    > (time-waste-time)
    >
    > (let ((res nil))
    > (dotimes (i 10 res)
    > (push (time-waste-time) res)))
    >
    > ;; this shows that (get-universal-time) is NOT where the time is spent
    > (time (dotimes (i 10000000) (get-universal-time)))
    >
    > ;; shis shows lots of work being done just by bignum assignment
    > (time (let ((tim))
    > (dotimes (i 10000000 tim)
    > (setf tim (get-universal-time)))))
    >
    > ;; this shows bignum compares being fairly fast
    > (time (let ((tim (+ 2 (get-universal-time))))
    > (dotimes (i 10000000 tim)
    > (< tim (get-universal-time)))))
    >
    > My expectation was for larger values from waste-time. I can't tell
    > from the above what is making waste-time so 'slow'. I expect the do
    > to loop much faster than it does. waste-time also conses a lot. It
    > is comparable to bignum assignment rather than to the bignum compare.
    >
    > If waste-time was doing useful work to return a dynamicly generated
    > file in a single threaded HTTP server, how would it be made to work
    > concurrently with other requests that require the same sort of
    > processing? It seems to me that some sort of yield function would
    > have to be thrown in. This is why I operate under the belief that a
    > thread per request is the better model. I'm not sure how you set up a
    > Lisp process to run with smaller stacks for threads. On my Mac, I
    > have 'ulimit -s 8192' in my .profile for SBCL. Stacks may not need to
    > be larger than that depending on the app.
    >

    You just found out what I stumbled over some weeks ago. I probably
    forgot to post about it...

    please do this:
    CL-USER 2 > (defun bignum-counter ()
                   (dotimes (i 25000000)))
    BIGNUM-COUNTER

    CL-USER 3 > (compile 'bignum-counter)

    and then time it and then come back and compare with my results:

    CL-USER 7 > (time (bignum-counter))
    Timing the evaluation of (BIGNUM-COUNTER)

    user time = 21.931
    system time = 0.070
    Elapsed time = 0:00:53
    Allocation = 265783960 bytes standard / 3652 bytes conses
    0 Page faults
    Calls to %EVAL 33
    NIL

    If you try this in Java you will get an execution speed which is 50-80
    times higher. This thing is done in less than one second!

    I think the problem lies in the implementation of bignum.

    After these disappointing results try now this:

    CL-USER 16 > (defun clever-counter ()
                   (dotimes (o 1000)
                     (dotimes (i 25000))))
    CLEVER-COUNTER

    CL-USER 17 > (compile 'clever-counter)

    And see what happens:
    CL-USER 21 > (time (clever-counter))
    Timing the evaluation of (CLEVER-COUNTER)

    user time = 0.180
    system time = 0.010
    Elapsed time = 0:00:00
    Allocation = 1672 bytes standard / 3542 bytes conses
    0 Page faults
    Calls to %EVAL 33
    NIL

    We now have the expected, Lisp worthy speed.
    Tested in LW 4.3.6 on Windows.

    I hope this helps a bit.
    I don't know why the implementors of Lisps don't give us a "real" 64-bit
    datatype, like the one in Java or at least a 32-bit type. In real world
    apps it happens from time to time to use numbers over 100 million.
    In LW I see

    CL-USER 80 > (bignump 8388608)
    T

    CL-USER 81 > (bignump 8388607)
    NIL

    8388608 is 2^23-1

    In Clisp I get 2^24-1

    [63]> (type-of 16777216)
    BIGNUM
    [64]> (type-of 16777215)
    FIXNUM

    The problem starts when we run over these numbers. So in LW 2^23 or
    more. In Java (for example) I can go up to 2^63-1 before I need to start
    with bignum calculations. Of course, then also in Java the process of
    working with these numbers slows down greatly.

    What are the problems for the implementors to give us some more bits for
    faster calculations?
    In my programs I must play the human compiler/optimizer and try to split
    up numbers.. if possible (which usually isn't).

    André 

    --
  • Next message: André Thieme: "Re: making Lisp faster by giving it 40 more bits"

    Relevant Pages

    • Wasting Time
      ... I wrote a simple little function to simulate a web page request taking ... ;; this shows bignum compares being fairly fast ... My expectation was for larger values from waste-time. ... is comparable to bignum assignment rather than to the bignum compare. ...
      (comp.lang.lisp)
    • Re: jsp client for axis2 webservice
      ... Read the Java EE tutorial on the Sun web site. ... to call logic from a JSP. ... all the JSP does is POST an HTTP request to the application ... calling one of the stub methods that you have. ...
      (comp.lang.java.programmer)
    • Re: Servlet To Java Application Communication
      ... I would like to write a Java servlet that it will be able to ... way to communicate with a servlet. ... probably know you should encode the request XML in the body part of a POST ... and expect the response XML in the response content. ...
      (comp.lang.java.databases)
    • Re: Connecting to Analysis Services with Java XML
      ... Most likely your element isn't in the correct namespace. ... Compare your Java request to the VB request and see the difference... ... public static void main(String[] args) throws Exception { ...
      (microsoft.public.data.xmlanalysis)
    • Re: jsp client for axis2 webservice
      ... Read the Java EE tutorial on the Sun web site. ... It talks generally about how to call logic from a JSP. ... A servlet on the app server receives the request, parses out the request parameters, and passes them along to an instance of a regular Java class, usually a Bean. ... That object in turn will perform some processing, say, calling one of the stub methods that you have. ...
      (comp.lang.java.programmer)