From: ··········@questions.com
Subject: speed of bit-vector access in Lispworks
Date: 
Message-ID: <eheggtgau6a8mn0o2mtbhcoaplvqdq96rs@4ax.com>
I want to test how fast Lispworks can access bits in a bit-vector.  I tried
the following code, and tried decorating it various ways, but I can't seem to
make it very fast.  It tends to take around 150 CPU cycles per bit, with only
about a 10% speedup from adding various declarations of optimizations.

(defun test1 (n k)
  (let ((v (make-sequence 'bit-vector n)))
    (loop as j below k sum
      (loop as i below n sum
        (sbit v i)))))

If you wanted to optimize bit access, would you implement your own sbit, and
make it inline?

From: Wade Humeniuk
Subject: Re: speed of bit-vector access in Lispworks
Date: 
Message-ID: <9e9i5v$e8a$1@news3.cadvision.com>
Why the interest in bit-vectors?  Do you have an application area in mind?
How might you use them?

Wade
From: ··········@questions.com
Subject: Re: speed of bit-vector access in Lispworks
Date: 
Message-ID: <9llggtgtbjtsj1nn6jpb47sqcegeg01dbu@4ax.com>
On Sun, 20 May 2001 16:56:52 -0600, "Wade Humeniuk" <········@cadvision.com>
wrote:

>Why the interest in bit-vectors?  Do you have an application area in mind?
>How might you use them?

Actually I just happened to be playing with them as part of my random
learning of Lisp when I noticed that they seemed to be somewhat slower than
they should be.  I'm just curious to know what Lisp programmers tend to do
when they want to speed up something like that.  I assume if it's important
to speed it up you might write some kind of fancy macro to use in place of
sbit.  But in practice do Lisp programmers tend to actually do such things?

I would also like to have a "tbit" returning t or nil instead of 1 or 0.  Is
it a very common practice for Lisp programmers to add large numbers of such
things?  What package do they tend to put them in?  Their own ad-hoc package
for a particular project?  Or is there a canonical my-features-added-to-lisp
package?
From: Kent M Pitman
Subject: Re: speed of bit-vector access in Lispworks
Date: 
Message-ID: <sfwr8xjplta.fsf@world.std.com>
··········@questions.com writes:

> On Sun, 20 May 2001 16:56:52 -0600, "Wade Humeniuk" <········@cadvision.com>
> wrote:
> 
> >Why the interest in bit-vectors?  Do you have an application area in mind?
> >How might you use them?
> 
> Actually I just happened to be playing with them as part of my random
> learning of Lisp when I noticed that they seemed to be somewhat slower than
> they should be.  I'm just curious to know what Lisp programmers tend to do
> when they want to speed up something like that.  I assume if it's important
> to speed it up you might write some kind of fancy macro to use in place of
> sbit.  But in practice do Lisp programmers tend to actually do such things?

One normally programs as if all operators will be adequately fast.  Do
make sure you have properly type-declared the array.  Some
implementations may do better if you set the optimize qualities of
SPEED, SAFETY, DEBUG, etc. in various ways. (Some implementations will
have an array-register declaration that may help, but there's no such
standard concept.)  If all of this is right and you're still losing, I
agree with Pierre--you should get a support contract and talk to your
vendor.  If you have a mission-critical application and no support
contract, you shouldn't be surprised if your vendor doesn't treat your
priority the same as you think it should be.  You get what you pay for.

You seem, by the way, to use the word "macro" in a too-automatic way here.
Macros are not necessarily faster than inline functions, and are often a
less-good abstraction to use for any of a number of reasons.

However, macro or function, you can't add faster support without having a
faster underlying primitive to appeal to.  There is nothing faster than
sbit in the language.  Individual vendors might have something faster, which
is why you should talk to them.  But also they should be able to get sbit up
to reasonable speed for you.

> I would also like to have a "tbit" returning t or nil instead of 1 or 0.  Is
> it a very common practice for Lisp programmers to add large numbers of such
> things?

Well, it's common practice for seasoned programmers to have little collections
of operators they either write each time or carry around with them.  

> What package do they tend to put them in?

Whichever one you're using if they're one-shot things.  One of your own
devising otherwise.  Your question suggests you think you are looking for
a central package to put them in.  You should never do that.  If you don't
uniquely own a package, you should find a package you do uniquely own.  
Group packages, except among a very tight group of people who all know and
like each other and see each other every day, are probably a bad idea.
And even then they are probably a bad idea.

> Their own ad-hoc package for a particular project?

Yes.

> Or is there a canonical my-features-added-to-lisp package?

Absolutely not, and for a reason.

If you grabbed a symbol in such a package for your use and didn't coordinate
it with me, then when we loaded each other's packages later we would clobber
each other's essential tools.
From: Paolo Amoroso
Subject: Re: speed of bit-vector access in Lispworks
Date: 
Message-ID: <CFoJO2k5isNWv3Q2xiOfX=7Oa6om@4ax.com>
On Mon, 21 May 2001 00:07:43 GMT, ··········@questions.com wrote:

> they should be.  I'm just curious to know what Lisp programmers tend to do
> when they want to speed up something like that.  I assume if it's important

Check the book:

  "Paradigms of Artificial Intelligence Programming - Case Studies in
  Common Lisp"
  Peter Norvig
  Morgan Kaufmann, 1992


Paolo
-- 
EncyCMUCLopedia * Extensive collection of CMU Common Lisp documentation
http://cvs2.cons.org:8000/cmucl/doc/EncyCMUCLopedia/
From: Pierre R. Mai
Subject: Re: speed of bit-vector access in Lispworks
Date: 
Message-ID: <87pud3pnqj.fsf@orion.bln.pmsf.de>
··········@questions.com writes:

> I want to test how fast Lispworks can access bits in a bit-vector.  I tried
> the following code, and tried decorating it various ways, but I can't seem to
> make it very fast.  It tends to take around 150 CPU cycles per bit, with only
> about a 10% speedup from adding various declarations of optimizations.
> 
> (defun test1 (n k)
>   (let ((v (make-sequence 'bit-vector n)))
>     (loop as j below k sum
>       (loop as i below n sum
>         (sbit v i)))))

CMU CL on an AMD K6-2/550 takes around 107ns per bit (using n=10000
and k=1000) completely unoptimized (default optimize settings, test1
as is), which is around 59 cycles per bit.  With speed=3 and
safety=space=debug=0 and fixnum arithmethic, this can be lowered to
29ns per bit (n=10000 and k=10000), or around 16 cycles per bit, which
seems quite good, actually.  With the optimized version and a
completely zero bit-vector, LWL seems to take around an order of
magnitude more time, probably because sbit performance is less bummed
than on CMU CL.

The optimal version is included below:

(defun test1 (n k)
  (declare (optimize (speed 3) (safety 0) (debug 0) (space 0))
           (fixnum n k))
  (let ((v (make-sequence 'bit-vector n)))
    (declare (type simple-bit-vector v))
    (loop as j of-type fixnum below k sum
      (loop as i of-type fixnum below n sum (sbit v i) of-type fixnum)
      of-type fixnum)))

> If you wanted to optimize bit access, would you implement your own sbit, and
> make it inline?

I don't think that your own implementation of sbit would be faster
than the implementations version, unless you could work on more than
one bit at a time when doing this.  If I really needed sbit to be very
fast for my application to succeed, i.e. if this isn't a question of
"let's bum the hell out of code that get's used 0.01% of total
run-time in setup code", then I'd contact my vendor of choice and
discuss implementation-specific ways to optimize sbit performance,
and/or maybe a custom patch that improves the sbit code-generator.  Of
course this is dependant on a valid support contract.

Regs, Pierre.

-- 
Pierre R. Mai <····@acm.org>                    http://www.pmsf.de/pmai/
 The most likely way for the world to be destroyed, most experts agree,
 is by accident. That's where we come in; we're computer professionals.
 We cause accidents.                           -- Nathaniel Borenstein