gen-wrapper + questions for Lutz

[itistoday]

So I was messing around and came up with a function called 'gen-wrapper':

Code: Select all

(define (gen-wrapper:gen-wrapper x)
    (letn (obj-sym (sym (string "genobj#" (inc gen-wrapper:i)))
           obj-val (sym obj-sym obj-sym))
        (when x (set obj-val x))
        (context obj-sym)
    )
)

gen-wrapper is a lot like gensym, except it creates an "anonymous" context to wrap around some possibly large data (which is stored in the default function).

I did some benchmarks with it though and was surprised to find, that even for very large lists, this did not seem to improve performance much:

Code: Select all

(define (how-many-0s lst , (num-zeros 0) break)
    (dolist (item lst break)
        (if (zero? item)
            (inc num-zeros)
            (setf break true)
        )
    )
    (push num-zeros lst)
)

(define-macro (eval-print what)
	(println what " => " (eval what))
)

(setf obj '(0 0 0 1 2 5 3)) ; 22.376 vs 1943.697
; (setf obj (append (dup 0 50 true) (dup 1 10000 true))) ; 5043.505 vs 5306.893
; (setf obj (append (dup 0 50 true) (dup 1 20000 true))) ; 9808.213 vs 8523.749

(eval-print (time (dotimes (_ 10000) (how-many-0s obj))))
(eval-print (setf obj (gen-wrapper obj)))
(eval-print (time (dotimes (_ 10000) (how-many-0s obj))))

The comments after the (setf obj ... ) lines indicate the times it took (direct value passing vs. wrapper).

As you can see even with extremely large lists of numbers (10050 elements), the direct value passing was faster. Only when 20050 elements were being passed did it seem to matter. And for small lists the performance was much much worse for the wrapper.

So I have three questions:

1) Why is this? I'm assuming it's because accessing the default function in 'dolist' still copies the list?
2) Can this be improved? I.e. Can 'dolist' or whatever it is reference the list instead of copying it?
3) Can we get a library function that takes a symbol and returns the context that symbol belongs to? Take a look at my gen-wrapper function, I end up having to "hack" this through the use of the 'context' function which is normally used to change contexts, and only because newLISP can't do that within a function call can I get away with it. I've found myself wishing for a dedicated function to retrieve the context of a symbol many times.

[Lutz]

Basically its this::

Code: Select all

(set 'foo '(a b c d e f g))
(set 'bar:bar '(a b c d e f g))

(time (foo 0) 1000000) ;=> 72.831
(time (bar:bar 0) 1000000) ;=> 72.43
(time (bar 0) 1000000) ;=> 128.92

The transformation of a context symbol 'bar' to default symbol 'bar:bar' involves a symbol tree lookup. Raw lookup time will be anywhere between 50 nano seconds for small symbols trees to 1 micro second for symbol trees with millions of symbols on a 1.8 GHz Intel Core 2 Duo. This is as fast as it can get with current RB-tree-algorithm technology.

[itistoday]

The transformation of a context symbol 'bar' to default symbol 'bar:bar' involves a symbol tree lookup. Raw lookup time will be anywhere between 50 nano seconds for small symbols trees to 1 micro second for symbol trees with millions of symbols on a 1.8 GHz Intel Core 2 Duo. This is as fast as it can get with current RB-tree-algorithm technology.

Why doesn't the context have a direct pointer to its default function? This way the lookup can be avoided.

newLISP needs a fast way of passing data by reference anonymously, otherwise it will always be handicapped at certain tasks, and this very point will prevent its wider adoption.

[Kazimir Majorinc]

It doesn't look obvious, but Lutz is - from practical point of view - right here.

Newlisp copy large amounts of memory so fast that there is little advantage in passing *anonymous* lists as reference. Why? Because, if you pass anonymous list, that means that you just created it. And if you created it, you have already spent so much time on creation that one copy more or less is not essential. Look at this code:

Code: Select all

(set 'last-by-value (lambda(X)(last X)))
(set 'last-by-reference (lambda-macro(X)(last (eval X))))
(set 'last-by-references (lambda-macro(Y)(last-by-reference (eval Y))))

(set 'N 10000000)
(println "N=" N)
(println 'empty ": " (time '(sequence 1 N 1) N))
(println 'sequence ": " (time (sequence 1 N 1) 1))
(println 'begin ": " (time (begin (sequence 1 N 1)) 1))
(println 'copy ": " (time (copy (sequence 1 N 1)) 1))
(println 'last  ": " (time (last (sequence 1 N 1)) 1))
(println 'last-by-value ": " (time (last-by-value (sequence 1 N 1)) 1))
(println 'last-by-reference ": " (time (last-by-reference (sequence 1 N 1)) 1))
(println 'last-by-references ": " (time (last-by-references (sequence 1 N 1)) 1))

N=10000000
empty: 177
sequence: 772
begin: 1074
copy: 845
last: 618
last-by-value: 833
last-by-reference: 834
last-by-references: 1132

Well, times are of same order of value for all of these operations! Also, note that sequence is very simple built in operation, that means, it is much, much faster than anything we can do to construct list "manually". So, passing anonymous lists by values is really not time inefficient. We really need passing by reference for non-anonymous lists - something that is passed many times back and forth. That is - your wrapper is good solution. The time is linear. But - it is slow for small lists, constant factor is big - as one can expect. But - I guess that in practice, even small lists require so much job that time spent by your wrapper is neglectable.

In the discussion we recently had on reddit, first-rest dispatch, the example our opponent gave was good one. In his case, really, Newlisp requires quadratic time, and CL requires linear time. Fortunately, his example is artificial, made to suit CL lists (and ignores space complexity.)[/color]

[itistoday]

Kazimir, I think you misunderstood what I meant when I said "anonymous". I'm not referring to anonymous lists, but to a method of passing them by reference anonymously (i.e. "anonymous" context, as opposed to named contexts. gen-wrapper creates a pseudo-anonymous context).

gen-wrapper should be fast but for some reason it's not. Lutz says that the performance hit is from a symbol lookup in a red-black tree, but I wouldn't be surprised if there was extra copying going on too. Either way, it means we're stuck with no way to do this quickly, which is a real shame because it means newLISP shouldn't be used in situations where you're dealing with a lot of data.

Wait, it's late and Lutz is right and I'm wrong. :-p It is just the symbol-lookup overhead that's the issue, there's no extra copying. More reason to ask for a direct pointer. :-D

[Kazimir Majorinc]

I see. OK. I did few experiments, and it appears that gen-wrapper is fast, so if you only pass "referenced" object around, with little work, it will be lightning fast, but if function works extensively on the object, it will be less advantage.

No work in called function - 1000 times faster

Code: Select all

(define (gen-wrapper:gen-wrapper x)
    (letn (obj-sym (sym (string "genobj#" (inc gen-wrapper:i)))
           obj-val (sym obj-sym obj-sym))
        (when x (set obj-val x))
        (context obj-sym)
    )
)

(define (how-many-0s lst , (num-zeros 0) break)
    '(dolist (item lst break)
        (if (zero? item)
            (inc num-zeros)
            (setf break true)
        )
    )
    '(push num-zeros lst)
)

(define-macro (eval-print what)
   (println what " => " (eval what))
)


(setf obj (append (dup 0 50 true) (dup 1 20000 true))) 

(eval-print (time (dotimes (_ 10000) (how-many-0s obj)))) ;=>4414 
(eval-print (setf obj (gen-wrapper obj)))
(eval-print (time (dotimes (_ 10000) (how-many-0s obj)))) ;=>5

Lot of work in called function - 20% faster

Code: Select all

(define (gen-wrapper:gen-wrapper x)
    (letn (obj-sym (sym (string "genobj#" (inc gen-wrapper:i)))
           obj-val (sym obj-sym obj-sym))
        (when x (set obj-val x))
        (context obj-sym)
    )
)

(define (how-many-0s lst , (num-zeros 0) break)
    (dolist (item lst break)
        (if (zero? item)
            (inc num-zeros)
            (setf break true)
        )
    )
    (push num-zeros lst)
)

(define-macro (eval-print what)
   (println what " => " (eval what))
)


(setf obj (append (dup 0 50 true) (dup 1 20000 true))) 

(eval-print (time (dotimes (_ 10000) (how-many-0s obj)))) ;=>13467
(eval-print (setf obj (gen-wrapper obj)))
(eval-print (time (dotimes (_ 10000) (how-many-0s obj)))) ;=>11380 
(exit)

Some work in called function - 200% faster

Code: Select all

(define (gen-wrapper:gen-wrapper x)
    (letn (obj-sym (sym (string "genobj#" (inc gen-wrapper:i)))
           obj-val (sym obj-sym obj-sym))
        (when x (set obj-val x))
        (context obj-sym)
    )
)

(define (how-many-0s lst , (num-zeros 0) break)
    (dolist (item lst break)
        (if (zero? item)
            (inc num-zeros)
            (setf break true)
        )
    )
    '(push num-zeros lst)
    lst
)

(define-macro (eval-print what)
   (println what " => " (eval what))
)


(setf obj (append (dup 0 50 true) (dup 1 20000 true))) 

(eval-print (time (dotimes (_ 10000) (how-many-0s obj)))) ;=>14630
(eval-print (setf obj (gen-wrapper obj)))
(eval-print (time (dotimes (_ 10000) (how-many-0s obj)))) ;=>5325  

Little work in called function - 2000 times faster

Code: Select all

(define (gen-wrapper:gen-wrapper x)
    (letn (obj-sym (sym (string "genobj#" (inc gen-wrapper:i)))
           obj-val (sym obj-sym obj-sym))
        (when x (set obj-val x))
        (context obj-sym)
    )
)

(define (how-many-0s lst , (num-zeros 0) break)
    '(dolist (item lst break)
        (if (zero? item)
            (inc num-zeros)
            (setf break true)
        )
    )
    (push num-zeros lst)
    lst
)

(define-macro (eval-print what)
   (println what " => " (eval what))
)


(setf obj (append (dup 0 50 true) (dup 1 20000 true))) ; 

(eval-print (time (dotimes (_ 10000) (how-many-0s obj)))) ;=>13991
(eval-print (setf obj (gen-wrapper obj)))
(eval-print (time (dotimes (_ 10000) (how-many-0s obj)))) ;=>6        Thats what you want!!

(exit)

Now, that last is something you can be proud on.

And, if you speak about

Code: Select all

(time (foo 0) 1000000) ;=> 72.831
(time (bar:bar 0) 1000000) ;=> 72.43
(time (bar 0) 1000000) ;=> 128.92

It looks quite satisfying to me.

[itistoday]

Thanks Kazimir, for some reason this didn't sink previously, but now I see that the original benchmark wasn't very good for testing gen-wrapper.

I modified this example to see what happens if the data is simply passed around several times between user functions:

Code: Select all

(define (pass-to-myself lst times)
	(if (not (zero? times))
		(pass-to-myself lst (dec times))
		(= (sequence 1000 1) lst)
	)
)

(setf obj (sequence 1 10000))
(eval-print (time (pass-to-myself obj 500) 100)) ;=>12220.615
(eval-print (setf obj (gen-wrapper obj)))
(eval-print (time (pass-to-myself obj 500) 100)) ;=>25.445

(setf obj (sequence 1 10000))
(eval-print (time (pass-to-myself obj 5) 100)) ;=>109.034
(eval-print (setf obj (gen-wrapper obj)))
(eval-print (time (pass-to-myself obj 5) 100)) ;=>1.912
(exit)

The function pass-to-myself calls itself a specified number of times to simulate passing large data through multiple functions, and on the last time it accesses the data.

So now I am a bit happier, because this shows that gen-wrapper results in a significant performance increase if your large data is being passed around even a small number of times. If it's passed around 500 times then it's 480.276 times faster, and if it's being passed just 5 times it's 57.0262 times faster.

So, gen-wrapper is a nice function to have around, but I think it would be even nicer if the access to the default function were optimized to O(1). :-)