Asp Forum - array performance

Taoufik Dachraoui

1/15/2016 3:18:00 PM

Hi

I am using CCL 1.11 64 bits on mac os x

any explanation for the following:

? (defvar a (make-array 100 :element-type 'double-float))
? (time (dotimes (i 100) (incf (aref a i) i)))
(DOTIMES (I 100) (INCF (AREF A I) I))
took 13 microseconds (0.000013 seconds) to run.
During that period, and with 2 available CPU cores,
14 microseconds (0.000014 seconds) were spent in user mode
5 microseconds (0.000005 seconds) were spent in system mode
3,200 bytes of memory allocated.
NIL
?

;; note that a is defined by defvar
? (let ((a (make-array 100 :element-type 'double-float)))
(time (dotimes (i 100) (incf (aref a i) (coerce i 'double-float)))))
(DOTIMES (I 100) (INCF (AREF A I) (COERCE I 'DOUBLE-FLOAT)))
took 11 microseconds (0.000011 seconds) to run.
During that period, and with 2 available CPU cores,
12 microseconds (0.000012 seconds) were spent in user mode
6 microseconds (0.000006 seconds) were spent in system mode
4,800 bytes of memory allocated.
NIL
?

? (let ((b (make-array 100 :element-type 'double-float)))
(time (dotimes (i 100) (incf (aref b i) (coerce i 'double-float)))))
(DOTIMES (I 100) (INCF (AREF B I) (COERCE I 'DOUBLE-FLOAT)))
took 5 microseconds (0.000005 seconds) to run.
During that period, and with 2 available CPU cores,
8 microseconds (0.000008 seconds) were spent in user mode
7 microseconds (0.000007 seconds) were spent in system mode
NIL
?

Why the consing in the first and second examples and not in the third example? and
why the second example conses more than the first?

Kind regards
Taoufik

38 Answers

Barry Margolin

1/15/2016 5:26:00 PM

In article <1eb1aba7-1f85-4387-9773-f805747ac6d6@googlegroups.com>,
Taoufik Dachraoui <dachraoui.taoufik@gmail.com> wrote:

> Hi
>
> I am using CCL 1.11 64 bits on mac os x
>
> any explanation for the following:
>
> ? (defvar a (make-array 100 :element-type 'double-float))
> ? (time (dotimes (i 100) (incf (aref a i) i)))
> (DOTIMES (I 100) (INCF (AREF A I) I))
> took 13 microseconds (0.000013 seconds) to run.
> During that period, and with 2 available CPU cores,
> 14 microseconds (0.000014 seconds) were spent in user mode
> 5 microseconds (0.000005 seconds) were spent in system mode
> 3,200 bytes of memory allocated.
> NIL
> ?
>
> ;; note that a is defined by defvar
> ? (let ((a (make-array 100 :element-type 'double-float)))
> (time (dotimes (i 100) (incf (aref a i) (coerce i 'double-float)))))
> (DOTIMES (I 100) (INCF (AREF A I) (COERCE I 'DOUBLE-FLOAT)))
> took 11 microseconds (0.000011 seconds) to run.
> During that period, and with 2 available CPU cores,
> 12 microseconds (0.000012 seconds) were spent in user mode
> 6 microseconds (0.000006 seconds) were spent in system mode
> 4,800 bytes of memory allocated.
> NIL
> ?
>
> ? (let ((b (make-array 100 :element-type 'double-float)))
> (time (dotimes (i 100) (incf (aref b i) (coerce i 'double-float)))))
> (DOTIMES (I 100) (INCF (AREF B I) (COERCE I 'DOUBLE-FLOAT)))
> took 5 microseconds (0.000005 seconds) to run.
> During that period, and with 2 available CPU cores,
> 8 microseconds (0.000008 seconds) were spent in user mode
> 7 microseconds (0.000007 seconds) were spent in system mode
> NIL
> ?
>
> Why the consing in the first and second examples and not in the third
> example? and

My guess is in the third example it noticed that B is never returned. So
it allocated the array on the stack instead of consing.

> why the second example conses more than the first?

Due to (coerce i 'double-float)?

--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

taruss

1/15/2016 8:36:00 PM

On Friday, January 15, 2016 at 7:18:13 AM UTC-8, Taoufik Dachraoui wrote:
> Hi
>
> I am using CCL 1.11 64 bits on mac os x
>
> any explanation for the following:
>
> ? (defvar a (make-array 100 :element-type 'double-float))

You should also realize that without type declarations in the code that is
being used (and appropriate compiler safety & speed settings), you might not
get much of a speed up from specialized arrays.

From the consing results it seems that when stored in the global variable, you
are creating new floating point objects.

Barry had a good explanation for some of the differences.

Pascal J. Bourguignon

1/15/2016 8:43:00 PM

Taoufik Dachraoui <dachraoui.taoufik@gmail.com> writes:

> Hi
>
> I am using CCL 1.11 64 bits on mac os x
>
> any explanation for the following:
>
> ? (defvar a (make-array 100 :element-type 'double-float))
> ? (time (dotimes (i 100) (incf (aref a i) i)))

Not conforming.

> ;; note that a is defined by defvar
> ? (let ((a (make-array 100 :element-type 'double-float)))
> (time (dotimes (i 100) (incf (aref a i) (coerce i
> 'double-float)))))

Not conforming.

> ? (let ((b (make-array 100 :element-type 'double-float)))
> (time (dotimes (i 100) (incf (aref b i) (coerce i
> 'double-float)))))

Not conforming.

> Why the consing in the first and second examples and not in the third example? and
> why the second example conses more than the first?

You're lucky what you did, didn't provoke the launch of an ICBM over
your house. Or any other nasal daemons.

You're just not writing conforming lisp code, so anything can happen.

Why all those expressions are not conforming?

Because you are _reading_ an array slot in an array that hasn't been
initialized, with a :inital-element, :initial-contents or a (setf aref)
or other functions calling (setf aref).

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.â? -- Carl Bass CEO Autodesk

Taoufik Dachraoui

1/15/2016 9:20:00 PM

On Friday, January 15, 2016 at 9:43:34 PM UTC+1, informatimago wrote:
> Taoufik Dachraoui <dachraoui.taoufik@gmail.com> writes:
>
> > Hi
> >
> > I am using CCL 1.11 64 bits on mac os x
> >
> > any explanation for the following:
> >
> > ? (defvar a (make-array 100 :element-type 'double-float))
> > ? (time (dotimes (i 100) (incf (aref a i) i)))
>
> Not conforming.
>
>
> > ;; note that a is defined by defvar
> > ? (let ((a (make-array 100 :element-type 'double-float)))
> > (time (dotimes (i 100) (incf (aref a i) (coerce i
> > 'double-float)))))
>
> Not conforming.
>
>
> > ? (let ((b (make-array 100 :element-type 'double-float)))
> > (time (dotimes (i 100) (incf (aref b i) (coerce i
> > 'double-float)))))
>
> Not conforming.
>
>
> > Why the consing in the first and second examples and not in the third example? and
> > why the second example conses more than the first?
>
> You're lucky what you did, didn't provoke the launch of an ICBM over
> your house. Or any other nasal daemons.
>
>
> You're just not writing conforming lisp code, so anything can happen.
>
> Why all those expressions are not conforming?
>
> Because you are _reading_ an array slot in an array that hasn't been
> initialized, with a :inital-element, :initial-contents or a (setf aref)
> or other functions calling (setf aref).
>
>
>
> --
> __Pascal Bourguignon__ http://www.informat...
> "The factory of the future will have only two employees, a man and a
> dog. The man will be there to feed the dog. The dog will be there to
> keep the man from touching the equipment." -- Carl Bass CEO Autodesk

Ok write conforming code and then explain; thanks

-Taoufik

Taoufik Dachraoui

1/15/2016 9:33:00 PM

Taoufik Dachraoui

1/15/2016 9:53:00 PM

On Friday, January 15, 2016 at 9:35:38 PM UTC+1, tar...@google.com wrote:
> On Friday, January 15, 2016 at 7:18:13 AM UTC-8, Taoufik Dachraoui wrote:
> > Hi
> >
> > I am using CCL 1.11 64 bits on mac os x
> >
> > any explanation for the following:
> >
> > ? (defvar a (make-array 100 :element-type 'double-float))
>
> You should also realize that without type declarations in the code that is
> being used (and appropriate compiler safety & speed settings), you might not
> get much of a speed up from specialized arrays.
>
> From the consing results it seems that when stored in the global variable, you
> are creating new floating point objects.
>
> Barry had a good explanation for some of the differences.

For the example 3, just by declaring b to special the conses increases; I would
like to understand why the compiler is behaving differently when the the array is
bound to a special variable?

? (let ((b (make-array 100 :element-type 'double-float))) (declare (special b))
(time (dotimes (i 100) (incf (aref b i) (coerce i 'double-float)))))
(DOTIMES (I 100) (INCF (AREF B I) (COERCE I 'DOUBLE-FLOAT)))
took 85 microseconds (0.000085 seconds) to run.
During that period, and with 2 available CPU cores,
25 microseconds (0.000025 seconds) were spent in user mode
68 microseconds (0.000068 seconds) were spent in system mode
4,800 bytes of memory allocated.
1 minor page faults, 0 major page faults, 0 swaps.
NIL
? (let ((b (make-array 100 :element-type 'double-float)))
(time (dotimes (i 100) (incf (aref b i) (coerce i 'double-float)))))
(DOTIMES (I 100) (INCF (AREF B I) (COERCE I 'DOUBLE-FLOAT)))
took 5 microseconds (0.000005 seconds) to run.
During that period, and with 2 available CPU cores,
8 microseconds (0.000008 seconds) were spent in user mode
5 microseconds (0.000005 seconds) were spent in system mode
NIL
?

-Taoufik

Günther Thomsen

1/15/2016 10:24:00 PM

On Friday, January 15, 2016 at 12:43:34 PM UTC-8, informatimago wrote:

> Why all those expressions are not conforming?
>
> Because you are _reading_ an array slot in an array that hasn't been
> initialized, with a :inital-element, :initial-contents or a (setf aref)
> or other functions calling (setf aref).
>

Indeed. Would have been nice, if the compiler would have said so, instead of having to rely on the c.l.l. lint ;-}

Barry Margolin

1/15/2016 11:13:00 PM

In article <0ace2e45-7087-4cc0-8ba6-ea506428c346@googlegroups.com>,
Günther Thomsen <guenthert@gmail.com> wrote:

> On Friday, January 15, 2016 at 12:43:34 PM UTC-8, informatimago wrote:
>
> > Why all those expressions are not conforming?
> >
> > Because you are _reading_ an array slot in an array that hasn't been
> > initialized, with a :inital-element, :initial-contents or a (setf aref)
> > or other functions calling (setf aref).
> >
>
> Indeed. Would have been nice, if the compiler would have said so, instead of
> having to rely on the c.l.l. lint ;-}

While it's not required, I think most implementations have built-in
defaults for :initial-element. So a general array will initialize
everything to NIL, and arrays specialized to numeric types will
initialize everything to 0.

So even though your code is non-conforming, in practice it probably does
what you were expecting.

--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Barry Margolin

1/15/2016 11:19:00 PM

In article <3f9c12e0-566c-4a2c-afaf-3956ea45f568@googlegroups.com>,
Taoufik Dachraoui <dachraoui.taoufik@gmail.com> wrote:

> For the example 3, just by declaring b to special the conses increases; I
> would
> like to understand why the compiler is behaving differently when the the
> array is
> bound to a special variable?

I explained that in my earlier response.

When the variable is lexical, and the value isn't returned or assigned
to a global variable, the compiler determines that the array doesn't
need to be allocated on the heap. It can be allocated locally on the
stack.

When you declare the variable special, other threads can access that
variable while your code is running, and they could assign the array to
another variable. So it can't assume that the array can be destroyed
when the LET returns.

You may get the same behavior with (declare (dynamic-extent b)).
Basically, it seems that in the earlier example, the compiler figured
out automatically that it could do this optimization.

--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Taoufik Dachraoui

1/16/2016 9:35:00 AM

On Saturday, January 16, 2016 at 12:19:05 AM UTC+1, Barry Margolin wrote:
> In article <3f9c12e0-566c-4a2c-afaf-3956ea45f568@googlegroups.com>,
> Taoufik Dachraoui <dachraoui.taoufik@gmail.com> wrote:
>
> > For the example 3, just by declaring b to special the conses increases; I
> > would
> > like to understand why the compiler is behaving differently when the the
> > array is
> > bound to a special variable?
>
> I explained that in my earlier response.
>
> When the variable is lexical, and the value isn't returned or assigned
> to a global variable, the compiler determines that the array doesn't
> need to be allocated on the heap. It can be allocated locally on the
> stack.
>
> When you declare the variable special, other threads can access that
> variable while your code is running, and they could assign the array to
> another variable. So it can't assume that the array can be destroyed
> when the LET returns.
>
> You may get the same behavior with (declare (dynamic-extent b)).
> Basically, it seems that in the earlier example, the compiler figured
> out automatically that it could do this optimization.
>
> --
> Barry Margolin, barmar@alum.mit.edu
> Arlington, MA
> *** PLEASE post questions in newsgroups, not directly to me ***

note in the following that the optimise declaration is necessary to avoid conses:

? (let ((arr (make-array 100)))
(defun test ()
(declare (optimize (speed 3) (safety 0) (debug 0)))
(incf (aref arr 1)))
(defmacro with-test (&rest body)
`(let ((arr ,arr))
(declare (optimize (speed 3) (safety 0) (debug 0)))
,@body)))
WITH-TEST
? (time (with-test (incf (aref arr 1))))
(WITH-TEST (INCF (AREF ARR 1)))
took 4 microseconds (0.000004 seconds) to run.
During that period, and with 2 available CPU cores,
6 microseconds (0.000006 seconds) were spent in user mode
6 microseconds (0.000006 seconds) were spent in system mode
3
? (time (progn (test)))
(PROGN (TEST))
took 5 microseconds (0.000005 seconds) to run.
During that period, and with 2 available CPU cores,
6 microseconds (0.000006 seconds) were spent in user mode
5 microseconds (0.000005 seconds) were spent in system mode
4
?

As you can see the array cannot be destroyed when the (test) returns, and still there is no consing
when the optimise declaration is used.

Kind regards
Taoufik

comp.lang.lisp

array performance

Taoufik Dachraoui

Barry Margolin

taruss

Pascal J. Bourguignon

Taoufik Dachraoui

Taoufik Dachraoui

Taoufik Dachraoui

Günther Thomsen

Barry Margolin

Barry Margolin

Taoufik Dachraoui

x Login to ForumsZone