Thanks for the hints.
Updated cpop code:
Code: Select all
;; best in functionality
(context 'cpop)
(define-macro (cpop:cpop l (ix 0))
(if (eval l)
(pop (eval l) (eval ix)))) ; returns empty list, if empty list
(context MAIN)
;; this has limitations, but should be faster
(macro (em-cpop L (Ix 0)) ; emacro: expansion macro
(if L
(pop L Ix))) ; returns empty list, if empty list
Some performance measures
First
push and
pop for getting a lower bound (using a filled list, so that (
pop l -1) never fails).
Short queue:
Code: Select all
> (set 'lt (sequence 1 10) 'num 1000000)
1000000
> ;;
> ;; Note: (pop l -1) would fail for an empty list (l always contains elemennts here).
> ;; LIFO standard
> (begin (set 'l lt) (time (begin (push 0 l) (pop l) ) num))
61.152
> (begin (set 'l lt) (time (begin (pop l) (push 0 l) ) num))
58.211
> ;; LIFO non-standard
> (begin (set 'l lt) (time (begin (push 22 l -1) (pop l -1) ) num))
87.94
> (begin (set 'l lt) (time (begin (pop l -1) (push 22 l -1) ) num))
87.211
> ;; FIFO by push
> (begin (set 'l lt) (time (begin (push 22 l -1) (pop l) ) num))
60.188
> (begin (set 'l lt) (time (begin (pop l) (push 22 l -1) ) num))
60.357
> ;; FIFO by pop
> (begin (set 'l lt) (time (begin (push 0 l) (pop l -1) ) num))
80.66
> (begin (set 'l lt) (time (begin (pop l -1) (push 0 l) ) num))
78.233
> ;;
Long queue:
Code: Select all
> ;;
> (set 'lt (sequence 1 1000) 'num 1000000)
1000000
> ;;
> ;; Note: (pop l -1) would fail for an empty list (l always contains elemennts here).
> ;; LIFO standard
> (begin (set 'l lt) (time (begin (push 0 l) (pop l) ) num))
56.846
> (begin (set 'l lt) (time (begin (pop l) (push 0 l) ) num))
59.729
> ;; LIFO non-standard
> (begin (set 'l lt) (time (begin (push 22 l -1) (pop l -1) ) num))
3855.777
> (begin (set 'l lt) (time (begin (pop l -1) (push 22 l -1) ) num))
3892.905
> ;; FIFO by push
> (begin (set 'l lt) (time (begin (push 22 l -1) (pop l) ) num))
60.436
> (begin (set 'l lt) (time (begin (pop l) (push 22 l -1) ) num))
60.664
> ;; FIFO by pop
> (begin (set 'l lt) (time (begin (push 0 l) (pop l -1) ) num))
2533.831
> (begin (set 'l lt) (time (begin (pop l -1) (push 0 l) ) num))
2538.82
>
Result of comparison between LIFO standard versus non-standard, and comparison between FIFO by
push versus
pop (optimized versus unoptimized cases):
- short queue (about 10 elements): small difference,
- long queue (about 1000 elements): huge difference!
Let's stay with the long list, since it is the more critical case, and continue with
em-cpop:
Code: Select all
> (set 'lt (sequence 1 1000) 'num 1000000)
1000000
> ;;
> ;; Note: (em-cpop l -1) would also work for an empty list.
> ;; LIFO standard
> (begin (set 'l lt) (time (begin (push 0 l) (em-cpop l) ) num))
93.721
> (begin (set 'l lt) (time (begin (em-cpop l) (push 0 l) ) num))
82.858
> ;; LIFO non-standard
> (begin (set 'l lt) (time (begin (push 22 l -1) (em-cpop l -1) ) num))
4329.809
> (begin (set 'l lt) (time (begin (em-cpop l -1) (push 22 l -1) ) num))
3945.459
> ;; FIFO by push
> (begin (set 'l lt) (time (begin (push 22 l -1) (em-cpop l) ) num))
1616.678
> (begin (set 'l lt) (time (begin (em-cpop l) (push 22 l -1) ) num))
1471.864
> ;; FIFO by em-cpop
> (begin (set 'l lt) (time (begin (push 0 l) (em-cpop l -1) ) num))
2854.785
> (begin (set 'l lt) (time (begin (em-cpop l -1) (push 0 l) ) num))
2578.798
>
Wired observation
Interesting in comparison between
pop and
em-cpop is the difference between
Code: Select all
> ;; FIFO by push
> (begin (set 'l lt) (time (begin (push 22 l -1) (pop l) ) num))
60.436
and
Code: Select all
> ;; FIFO by push
> (begin (set 'l lt) (time (begin (push 22 l -1) (em-cpop l) ) num))
1616.678
This is wired, because LIFO standard for
em-cpop has been fast:
Code: Select all
> ;; LIFO standard
> (begin (set 'l lt) (time (begin (push 0 l) (em-cpop l) ) num))
93.721
Digging deeper back to
push'n'
pop; compare cases with or without explicitely given (unneeded and failing for empty lists)
pop ix 0 (which will be used by
em-cpop):
Code: Select all
> ;; FIFO by push
> (begin (set 'l lt) (time (begin (push 22 l -1) (pop l) ) num))
73.90600000000001
> ;; FIFO by push (with explicit pop ix)
> (begin (set 'l lt) (time (begin (push 22 l -1) (pop l 0) ) num))
1463.805
>
-> here the explicit ix makes it slow,
but:
Code: Select all
> ;; LIFO standard
> (begin (set 'l lt) (time (begin (push 0 l) (pop l) ) num))
71.03100000000001
> ;; LIFO standard (with explicit pop ix)
> (begin (set 'l lt) (time (begin (push 0 l) (pop l 0) ) num))
66.854
>
-> here it doesn't hurt!
Why this difference?