in reply to Re^5: Bit vector fiddling with Inline C
in thread Bit vector fiddling with Inline C

Thanks! Re this point >>BTW: You still haven't mentioned what the "complex processing" you are performing in XS is?<< -- sorry, not trying to be mysterious, was just trying to keep the question focused!

One real example is this: there are 2 bit vectors of different sizes (each in the range of 1-8m bits) with irregular, many-to-many relationships between the bits in each vector. (The relationships are represented separately by a long array of pairs of ints.) One real function is to find every set bit in vector A, then set the corresponding bit(s) in vector B.

So: simple bitwise ops are out of the question because the vectors are of different sizes. I coded it first in pure Perl using the vec() function, but it was pretty slow (one call to vec() to test/set each bit). So, I switched to Inline::C for the heavy lifting and it's now over 20x faster (ie. the entire test/set loop inside one C function).

  • Comment on Re^6: Bit vector fiddling with Inline C

Replies are listed 'Best First'.
Re^7: Bit vector fiddling with Inline C
by syphilis (Archbishop) on May 10, 2011 at 02:12 UTC
    One real function is to find every set bit in vector A, then set the corresponding bit(s) in vector B

    I deduce, therefore, that A is smaller than (or equal to) B.

    I would expect you would observe a further siginificant increase in speed if you used the gmp library for that function - either accessing that library via Inline::C, or using one of the existing perl extensions (Math::GMP, Math::GMPz). Using the gmp library in C, the code to perform the above task would be something like: 
    size = mpz_sizeinbase(A, 2);
for(i = 0; i < size; i++) {
   if(mpz_tstbit(A, i)) mpz_setbit(B,i);
}

    [download]
    (and the same approach when using the aforementioned perl modules.)

    Of course, you might consider the involvement of the gmp library to be cheating - depending upon the extent to which you want to handle things yourself :-)

    Cheers,
    Rob
[reply]
[d/l]

      Two questions:

      1. Why test the bit and then set it?

        If you are only going to set the bit if it is unset, then just setting it achieves the same thing.

      2. Why would calling a function to set a bit be quicker than setting the bit directly?

        I guess the compiler might inline the function and optimise away the overheads, but still I don't see why it would end up being any quicker. As quick possibly.

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
        Why test the bit and then set it?

        The "tstbit(i)" is being done on vector A, and the "setbit(i)" is being done on vector B - but only when the "tstbit(i)" returns true.
        This is in accordance with the op's description of finding "every set bit in vector A, then set the corresponding bit(s) in vector B".
        Of course, this is a rather naive and inefficient approach. A smarter approach would be to do B = A|B, or in gmp parlance mpz_ior(B, A, B);

        Why would calling a function to set a bit be quicker than setting the bit directly?

        As you suggest, they might not be any quicker, and could even be slower. For single bit operations, you're probably right. (The assembler code on which gmp is generally built could count as something in its favour - but it's not always going to come into play.)
        Personally however, at least where *big* vectors are involved, I'd want to see benchmarks done before ruling out gmp.

        Cheers,
        Rob
[reply]
[d/l]
[select]
        On (1) I think he's just illustrating how to iterate/test/set bits via that library. On (2) I see what you mean and will do some tests to compare. Just guessing, but maybe the library method might prove to be quicker if it operates on words rather than bytes.
[reply]
      Great tip, thanks. Wasn't aware of that, but will certainly check it out. Currently getting/setting bits byte-wise as in the OP example, which I doubt is the best way. Will definitely test this out as an alternative.
[reply]

In Section Seekers of Perl Wisdom