unofficial mirror of help-gnu-emacs@gnu.org
 help / color / mirror / Atom feed
* Vector and List Performance
@ 2009-06-08 17:27 Nordlöw
  2009-06-08 19:57 ` Tassilo Horn
  2009-06-09  9:30 ` Pascal J. Bourguignon
  0 siblings, 2 replies; 8+ messages in thread
From: Nordlöw @ 2009-06-08 17:27 UTC (permalink / raw)
  To: help-gnu-emacs

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


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: Vector and List Performance
  2009-06-08 17:27 Vector and List Performance Nordlöw
@ 2009-06-08 19:57 ` Tassilo Horn
  2009-06-09  9:30 ` Pascal J. Bourguignon
  1 sibling, 0 replies; 8+ messages in thread
From: Tassilo Horn @ 2009-06-08 19:57 UTC (permalink / raw)
  To: help-gnu-emacs

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





^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: Vector and List Performance
  2009-06-08 17:27 Vector and List Performance Nordlöw
  2009-06-08 19:57 ` Tassilo Horn
@ 2009-06-09  9:30 ` Pascal J. Bourguignon
  2009-06-09 11:30   ` Nordlöw
  1 sibling, 1 reply; 8+ messages in thread
From: Pascal J. Bourguignon @ 2009-06-09  9:30 UTC (permalink / raw)
  To: help-gnu-emacs

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__


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: Vector and List Performance
  2009-06-09  9:30 ` Pascal J. Bourguignon
@ 2009-06-09 11:30   ` Nordlöw
  2009-06-09 12:51     ` Pascal J. Bourguignon
  0 siblings, 1 reply; 8+ messages in thread
From: Nordlöw @ 2009-06-09 11:30 UTC (permalink / raw)
  To: help-gnu-emacs

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


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: Vector and List Performance
  2009-06-09 11:30   ` Nordlöw
@ 2009-06-09 12:51     ` Pascal J. Bourguignon
  2009-06-09 18:13       ` Nordlöw
  0 siblings, 1 reply; 8+ messages in thread
From: Pascal J. Bourguignon @ 2009-06-09 12:51 UTC (permalink / raw)
  To: help-gnu-emacs

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__


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: Vector and List Performance
  2009-06-09 12:51     ` Pascal J. Bourguignon
@ 2009-06-09 18:13       ` Nordlöw
  2009-06-10  8:24         ` Pascal J. Bourguignon
       [not found]         ` <7c63f45we1.fsf@pbourguignon.informatimago.com>
  0 siblings, 2 replies; 8+ messages in thread
From: Nordlöw @ 2009-06-09 18:13 UTC (permalink / raw)
  To: help-gnu-emacs

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


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: Vector and List Performance
  2009-06-09 18:13       ` Nordlöw
@ 2009-06-10  8:24         ` Pascal J. Bourguignon
       [not found]         ` <7c63f45we1.fsf@pbourguignon.informatimago.com>
  1 sibling, 0 replies; 8+ messages in thread
From: Pascal J. Bourguignon @ 2009-06-10  8:24 UTC (permalink / raw)
  To: help-gnu-emacs

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__


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: Vector and List Performance
       [not found]         ` <7c63f45we1.fsf@pbourguignon.informatimago.com>
@ 2009-06-10  8:36           ` Pascal J. Bourguignon
  0 siblings, 0 replies; 8+ messages in thread
From: Pascal J. Bourguignon @ 2009-06-10  8:36 UTC (permalink / raw)
  To: help-gnu-emacs

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__


^ permalink raw reply	[flat|nested] 8+ messages in thread

end of thread, other threads:[~2009-06-10  8:36 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2009-06-08 17:27 Vector and List Performance Nordlöw
2009-06-08 19:57 ` Tassilo Horn
2009-06-09  9:30 ` Pascal J. Bourguignon
2009-06-09 11:30   ` Nordlöw
2009-06-09 12:51     ` Pascal J. Bourguignon
2009-06-09 18:13       ` Nordlöw
2009-06-10  8:24         ` Pascal J. Bourguignon
     [not found]         ` <7c63f45we1.fsf@pbourguignon.informatimago.com>
2009-06-10  8:36           ` Pascal J. Bourguignon

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).