Evaluation of Large Expressions in Newlisp.

; This time I'll try different eval benchmark; instead of
; evaluating simple expressions many time, I'll write the program
; that construct large s-expression and measures the time of its
; evaluation

(setq large-s-expression 1)


(setq counter 1)
(do-while (< counter 1000000)
    (setq counter (+ counter 1))
    (setq large-s-expression
          (list 'eval
                (list 'quote
                      (list '+ counter large-s-expression))))
    (when (= (% counter 100) 0)
          (println counter
                   " > "
                   (time (eval large-s-expression)))))

; This is how those z that are evaluated
; look like for counter=2,3,...

;(eval (quote (+ 2 1)))
;(eval (quote (+ 3 (eval (quote (+ 2 1))))))
;(eval (quote (+ 4 (eval (quote (+ 3 (eval (quote (+ 2 1)))))))))

; 100 > 0
; 200 > 15
; 300 > 15
; 400 > 31
; 500 > 46
; 600 > 78
; 700 > 109
; 800 > 140
; 900 > 234
; 1000 > 281
; 1100 >

; ERR: call stack overflow in function eval : quote
;
; Newlisp returns to REPL after that stack overflow. The speed
; is satisfactory, although it seems it is not stable, in some
; executions I got numbers like 900 ms for evaluation of the
; expression with 1000 evals.  

; Also, stack overflow happens earlier than in other Scheme
; or Lisp implementations. Clisp and PLT stack overflow
; happens for counter = about 4000, Lispworks and Allegro (free
; editons somewhere near 50 000, while Petit Chez Scheme works
; happily for counter > 10 000 000 and more. Stack overflow
; results in crash of PLT IDE and Chez Scheme interpreter
; respectively.

; However, that stack overflow in Newlisp is not the result of
; eval and quote, because it happens even earlier if eval and
; quote are replaced with sin and cos.

; Conclusion: for evaluation of very large expressions, Newlisp
; is satisfactory, but there is a lot of room for improvement.

2 comments:

  1. you could always change the stack size:

    newlisp -s 100000
    newLISP v.9.3.11 on OSX IPv4 UTF-8, execute 'newlisp -h' for more info.

    >
    ... your code

    1
    1
    100 > 2
    200 > 10
    300 > 21
    400 > 37
    500 > 59
    600 > 87
    700 > 120
    800 > 160
    900 > 206
    1000 > 258
    1100 > 316
    1200 > 381
    1300 > 460
    1400 > 534
    1500 > 620
    1600 > 710
    1700 > 807
    1800 > 906
    1900 > 1017
    2000 > 1271
    2100 > 5031
    2200 > 2891
    2300 > 3135
    2400 > 1711
    2500 > 3319
    2600 > 4231
    2700 > 9140
    2800 > 4333
    2900 > 3216
    3000 > 6424
    3100 > 3831
    3200 > 4892
    3300 > 6247
    3400 > 5205
    3500 > 6683
    3600 > 6150
    3700 > 22911
    3800 > 113175

    it gets very slow though... :)

    ReplyDelete
  2. Thanks, now I know for stack. This 3600 limit will require some rethinking once, it is not really big list for modern computers ...

    ReplyDelete