Hi,
I encountered the following strange behavior I don't understand: I
needed
to generate a random list of <n> unique integers with a maximum of
<max>. So I did the following:
(defun unique-random-ints (n max)
(declare (optimize (speed 3) (safety 0) (debug 0))
(type (unsigned-byte 16) n max))
(when (> n max) (error "n > max, can't create that many unique
integers"))
(let ((result nil))
(do ((i 0)
(j (random max) (random max)))
((= n i) result)
(declare (type (unsigned-byte 32) i j))
(unless (member j result :test #'=)
(progn (push j result)
(incf i))))))
It works fine with sbcl 1.0.1 (on linux i686), but it gets faster if
the :test #'= is replaced by #'eql. Why is that? Shouldn't the #'=
version be faster (since it's a more specific test)?
Any pointer would be appreciated.
Albert
On Feb 28, 4:20 pm, ·········@gmx.net wrote:
> It works fine with sbcl 1.0.1 (on linux i686), but it gets faster if
> the :test #'= is replaced by #'eql. Why is that? Shouldn't the #'=
> version be faster (since it's a more specific test)?
>
> Any pointer would be appreciated.
If the compiler can make the right assumptions they should be compiled
into the same code. But it's not at all clear to me that it can - it
would have to know an awful lot about MEMBER to be able to do this.
It may well be that by the time the comparison predicate is called by
MEMBER, it knows nothing about the types, and = may then have to do
more work (check things actually are numbers, be prepared to signal an
error) than EQL.
But more to the point, the performance of your code will probably be
dominated by list traversal if N is not a fairly small number. You
need a better way of checking for duplicates. If you *really* care
about performance, I'd suggest:
if N is small allocate an N-element array of some good type (bit array
might be worth trying, else array of some immediate type). Use this
to know when you have dups. (try and allocate it on the stack...)
If N is large use a hashtable.
--tim
On 28 Feb., 17:43, "Tim Bradshaw" <··········@tfeb.org> wrote:
> On Feb 28, 4:20 pm, ·········@gmx.net wrote:
>
> > It works fine with sbcl 1.0.1 (on linux i686), but it gets faster if
> > the :test #'= is replaced by #'eql. Why is that? Shouldn't the #'=
> > version be faster (since it's a more specific test)?
>
> > Any pointer would be appreciated.
>
> If the compiler can make the right assumptions they should be compiled
> into the same code. But it's not at all clear to me that it can - it
> would have to know an awful lot about MEMBER to be able to do this.
> It may well be that by the time the comparison predicate is called by
> MEMBER, it knows nothing about the types, and = may then have to do
> more work (check things actually are numbers, be prepared to signal an
> error) than EQL.
>
> But more to the point, the performance of your code will probably be
> dominated by list traversal if N is not a fairly small number. You
> need a better way of checking for duplicates. If you *really* care
> about performance, I'd suggest:
>
> if N is small allocate an N-element array of some good type (bit array
> might be worth trying, else array of some immediate type). Use this
> to know when you have dups. (try and allocate it on the stack...)
>
> If N is large use a hashtable.
>
> --tim
Thanks a lot Tim and André, that really helped me. Now, after you
explained it, the answer seems so obvious. N is rather small, so I
guess I'll use an array.
Thanks again,
Albert
From: Thomas A. Russ
Subject: Re: eql faster than = (integer comparison on sbcl)?
Date:
Message-ID: <ymi7iu17v38.fsf@sevak.isi.edu>
·········@gmx.net writes:
> Hi,
>
> I encountered the following strange behavior I don't understand: I
> needed
> to generate a random list of <n> unique integers with a maximum of
> <max>. So I did the following:
>
> (defun unique-random-ints (n max)
> (declare (optimize (speed 3) (safety 0) (debug 0))
> (type (unsigned-byte 16) n max))
> (when (> n max) (error "n > max, can't create that many unique
> integers"))
> (let ((result nil))
> (do ((i 0)
> (j (random max) (random max)))
> ((= n i) result)
> (declare (type (unsigned-byte 32) i j))
> (unless (member j result :test #'=)
> (progn (push j result)
> (incf i))))))
>
> It works fine with sbcl 1.0.1 (on linux i686), but it gets faster if
> the :test #'= is replaced by #'eql. Why is that? Shouldn't the #'=
> version be faster (since it's a more specific test)?
Well, it isn't really a more specific test. It is a different equality
test. The reason I don't think it is more specific is because it acts
differently:
(eql 1 1.0) => NIL
(= 1 1.0) => T
(eql 1 'x) => NIL
(= 1 'x) => ERROR
Furthermore, the default test for MEMBER is EQL, so one could expect
that a compiler may be likely to have that particular scenario
optimized. For other equality predicates, the underlying test code is
most likely not as efficient, since it will rely on something like
FUNCALL, which can't effectively open code the test.
--
Thomas A. Russ, USC/Information Sciences Institute
·········@gmx.net schrieb:
> Hi,
>
> I encountered the following strange behavior I don't understand: I
> needed
> to generate a random list of <n> unique integers with a maximum of
> <max>. So I did the following:
>
> (defun unique-random-ints (n max)
> (declare (optimize (speed 3) (safety 0) (debug 0))
> (type (unsigned-byte 16) n max))
> (when (> n max) (error "n > max, can't create that many unique
> integers"))
> (let ((result nil))
> (do ((i 0)
> (j (random max) (random max)))
> ((= n i) result)
> (declare (type (unsigned-byte 32) i j))
> (unless (member j result :test #'=)
> (progn (push j result)
> (incf i))))))
>
> It works fine with sbcl 1.0.1 (on linux i686), but it gets faster if
> the :test #'= is replaced by #'eql. Why is that? Shouldn't the #'=
> version be faster (since it's a more specific test)?
>
> Any pointer would be appreciated.
>
> Albert
>
What you saw is expected behaviour.
eql is more specific than =.
This is because = compares mathematical equality:
(= 1 1.0) => T
(eql 1 1.0) => NIL
1 is of type BIT while 1.0 is of type SINGLE-FLOAT.
Andr�
--