Re: [Chicken-users] Speeding up bit-vector operation (using iset)

[Lasse Kliemann]

* Message by -Alex Shinn- from Thu 2010-03-18:
> felix winkelmann <address@hidden> writes:
> 
> > On Wed, Mar 17, 2010 at 1:18 PM, Alex Shinn <address@hidden> wrote:
> >>
> >> At 2^26 bits each I would say these are *huge* bit-vectors.
> >>
> >>> (do
> >>>   ((i 0 (+ 1 i)))
> >>>   ((= i 10))
> >>>   (bit-vector-and s1 s2)
> >>>   (bit-vector-ior s1 s2)
> >>>   (bit-vector-and s1 (bit-vector-nand s2)))
> >>
> >> These operations are generating three new huge bit-vectors
> >> on each iteration, so you're spending all your time in GC
> >> (and the loop has no effect).
> >
> > I don't think this is completely true. GC-time is quite considerable,
> > but the loops
> > in iset.c are not tight enough for so many iterations (which is mostly
> > caused by slow XXXvector operations that require a full CPS call).
> 
> Oops, yes, you're right.  I wrote iset before I knew how to
> optimize code for Chicken.
> 
> I've modified iset so that it will generate tight loops on
> the bit-vector arithmetic operations, and it runs the
> original example in just over a second on my machine.  You
> might be able to make this faster by using u32/u64 vectors
> (storing only fixnum-sized values), but you'd get the
> biggest gain from rewriting the operations directly in C and
> vectorizing them.
> 
> The code is checked into SVN and a new egg should be
> available shortly.

Confirmed. I tested the SVN version. It runs in between 2 and 3 
seconds here. This is a huge speedup. Thank you!

pgpFBfcP3DHhO.pgp
Description: PGP signature