Vector and List Performance

Vector and List Performance

[Nordlöw]

I'm trying to figure the performance different between lists and
vectors. Here is my mockup:

  (defun bench (&rest forms)
    "Convenience wrapper for benchmark-run-compiled."
    (/ (nth 0 (benchmark-run 1024 forms)) 1024))

(let ((length 1000000))
  (cons
   (bench (aref (make-vector length 0) (/ length 2)))
   (bench (nth (/ length 2) (make-list length 0)))
   ))

Strangely I can't seem to find any significant different in
performance when accessing the middle element in a long vector and
long list. Shouldn't the random access performance be the big
difference between vectors and lists? What have I missed?

Thanks in advance,
Per Nordlöw

Re: Vector and List Performance

[Tassilo Horn]

Nordlöw <per.nordlow@gmail.com> writes:

Hi!

>   (defun bench (&rest forms)
>     "Convenience wrapper for benchmark-run-compiled."
>     (/ (nth 0 (benchmark-run 1024 forms)) 1024))
>
> (let ((length 1000000))
>   (cons
>    (bench (aref (make-vector length 0) (/ length 2)))
>    (bench (nth (/ length 2) (make-list length 0)))
>    ))
>
> Strangely I can't seem to find any significant different in
> performance when accessing the middle element in a long vector and
> long list. Shouldn't the random access performance be the big
> difference between vectors and lists? What have I missed?

I think that there's some optimization under the hood.  Actually, you
always access the same place in the list/vector.  With real random
access, you get the expected result:

--8<---------------cut here---------------start------------->8---
(defun bench ()
  (let* ((len 1000000)
         (vec (make-vector len 0))
         (lst (make-list   len 0))
         (times 50000))
    (cons
     (/ (car (benchmark-run times (aref vec (random len)))) times)
     (/ (car (benchmark-run times (nth (random len) lst)))  times))))

(bench)
==> (1.5999999999999999e-09 . 1.2723999999999999e-06)
--8<---------------cut here---------------end--------------->8---

So random access on a vector is about 1000 times faster.

Bye,
Tassilo

Re: Vector and List Performance

[Pascal J. Bourguignon]

Nordlöw <per.nordlow@gmail.com> writes:

> I'm trying to figure the performance different between lists and
> vectors. Here is my mockup:
>
>   (defun bench (&rest forms)
>     "Convenience wrapper for benchmark-run-compiled."
>     (/ (nth 0 (benchmark-run 1024 forms)) 1024))
>
> (let ((length 1000000))
>   (cons
>    (bench (aref (make-vector length 0) (/ length 2)))
>    (bench (nth (/ length 2) (make-list length 0)))
>    ))
>
> Strangely I can't seem to find any significant different in
> performance when accessing the middle element in a long vector and
> long list. Shouldn't the random access performance be the big
> difference between vectors and lists? 

Tyere is.


> What have I missed?

You have missed that functions receive their argument already evaluated.
The argument to each of the calls to bench is 0, in both case.

(require 'cl) ; as always
(loop 
    with length = 1000000
    with index  = (1- length)
    for seq in (list (make-vector length 0) (make-list length 0))
    do (insert (format "%8S %s" (type-of seq)
                       (time (loop repeat 100 do (elt seq index))))))

C-x C-e inserts:

  vector Time: 2.030000e+02 ms
    cons Time: 7.819890e+05 ms



Note however that adding or removing elements from the head, or even
in the middle of a list is much faster than doing the same to a
vector.


-- 
__Pascal Bourguignon__

Re: Vector and List Performance

[Nordlöw]

Aahh, we needed a macro instead:

(defmacro bench (&rest forms)
    "Convenience wrapper for benchmark-run-compiled."
    `(let ((n 10))
       (/ (nth 0 (benchmark-run n ,@forms)) n)))

This gives a reasonable difference in performance.

By the way, does elisp lists have extra pointers to the middle of the
list (a skip-list)?

/Per Nordlöw

Re: Vector and List Performance

[Pascal J. Bourguignon]

Nordlöw <per.nordlow@gmail.com> writes:

> Aahh, we needed a macro instead:
>
> (defmacro bench (&rest forms)
>     "Convenience wrapper for benchmark-run-compiled."
>     `(let ((n 10))
>        (/ (nth 0 (benchmark-run n ,@forms)) n)))
>
> This gives a reasonable difference in performance.
>
> By the way, does elisp lists have extra pointers to the middle of the
> list (a skip-list)?

No, because it wouldn't be efficient to have to maintain them.

(let* ((c (list 7 8 9))
       (b (list* 4 5 6 c))
       (a (list* 1 2 3 b)))
    (push -1 (cddr c))  (push -2 (cddr c))  ; you may have to update a big number of skip-lists!
    (list a b c))
-->
((1 2 3 . #1=(4 5 6 . #2=(7 8 -2 -1 9))) #1# #2#)


(deftype list () '(or null (cons t list))) ; nothing more.


-- 
__Pascal Bourguignon__

Re: Vector and List Performance

[Nordlöw]

On Jun 9, 2:51 pm, p...@informatimago.com (Pascal J. Bourguignon)
wrote:
> Nordlöw <per.nord...@gmail.com> writes:
> > Aahh, we needed a macro instead:
>
> > (defmacro bench (&rest forms)
> >     "Convenience wrapper for benchmark-run-compiled."
> >     `(let ((n 10))
> >        (/ (nth 0 (benchmark-run n ,@forms)) n)))
>
> > This gives a reasonable difference in performance.
>
> > By the way, does elisp lists have extra pointers to the middle of the
> > list (a skip-list)?
>
> No, because it wouldn't be efficient to have to maintain them.
>
> (let* ((c (list 7 8 9))
>        (b (list* 4 5 6 c))
>        (a (list* 1 2 3 b)))
>     (push -1 (cddr c))  (push -2 (cddr c))  ; you may have to update a big number of skip-lists!
>     (list a b c))
> -->
> ((1 2 3 . #1=(4 5 6 . #2=(7 8 -2 -1 9))) #1# #2#)
>
> (deftype list () '(or null (cons t list))) ; nothing more.
>
> --
> __Pascal Bourguignon__

I tested the performance difference and strangely the vector version
of my benchmarking is only faster when the number of elements exceeds
roughy 1000. Why is this? Shouldn' aref() always be faster than nth
regardless of the size of the sequence?

/Per Nordlöw

Re: Vector and List Performance

[Pascal J. Bourguignon]

Nordlöw <per.nordlow@gmail.com> writes:

> On Jun 9, 2:51 pm, p...@informatimago.com (Pascal J. Bourguignon)
> wrote:
>> Nordlöw <per.nord...@gmail.com> writes:
>> > Aahh, we needed a macro instead:
>>
>> > (defmacro bench (&rest forms)
>> >     "Convenience wrapper for benchmark-run-compiled."
>> >     `(let ((n 10))
>> >        (/ (nth 0 (benchmark-run n ,@forms)) n)))
>>
>> > This gives a reasonable difference in performance.
>>
>> > By the way, does elisp lists have extra pointers to the middle of the
>> > list (a skip-list)?
>>
>> No, because it wouldn't be efficient to have to maintain them.
>>
>> (let* ((c (list 7 8 9))
>>        (b (list* 4 5 6 c))
>>        (a (list* 1 2 3 b)))
>>     (push -1 (cddr c))  (push -2 (cddr c))  ; you may have to update a big number of skip-lists!
>>     (list a b c))
>> -->
>> ((1 2 3 . #1=(4 5 6 . #2=(7 8 -2 -1 9))) #1# #2#)
>>
>> (deftype list () '(or null (cons t list))) ; nothing more.
>>
>> --
>> __Pascal Bourguignon__
>
> I tested the performance difference and strangely the vector version
> of my benchmarking is only faster when the number of elements exceeds
> roughy 1000. Why is this? Shouldn' aref() always be faster than nth
> regardless of the size of the sequence?

How could we say?  You don't provide the full source of what you tested.

Check my other post in this thread, and see how faster the vector
accesses are.  Try the same form in your CL implementation, and report
the results here.

-- 
__Pascal Bourguignon__

Re: Vector and List Performance

[Pascal J. Bourguignon]

pjb@informatimago.com (Pascal J. Bourguignon) writes:

> Nordlöw <per.nordlow@gmail.com> writes:
>
>> I tested the performance difference and strangely the vector version
>> of my benchmarking is only faster when the number of elements exceeds
>> roughy 1000. Why is this? Shouldn' aref() always be faster than nth
>> regardless of the size of the sequence?
>
> How could we say?  You don't provide the full source of what you tested.
>
> Check my other post in this thread, and see how faster the vector
> accesses are.  Try the same form in your CL implementation, and report
> the results here.

Sorry, I was in my comp.lang.lisp gears.  

Just try the same form in emacs and tell us what you get.


In the meanwhile, a guess: you tested the creation of a big list
vs. the creation of a big vector (plus one access).  Study closely my
form, and see what sub-expression is timed.

-- 
__Pascal Bourguignon__