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

[Alex Shinn]

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.

-- 
Alex