Re^10: Bit vector fiddling with Inline C

[BrowserUk]

in accordance with the op's description of finding "every set bit in vector A, then set the corresponding bit(s) in vector B".

Okay. I missed that. Makes sense now.

A smarter approach would be to do B = A|B, or in gmp parlance mpz_ior(B, A, B);

'cept that the OP also said that the two vectors aren't in the same order (or even size) and the mapping isn't one to one. But rather, driven by pairs of numbers, a better description might be if( vecA[ 123 ] ) then vecB[ 456 ] = vecB[ 012 ] = 1;

I'd want to see benchmarks done before ruling out gmp.

Me too. Though I don't think the size of the vectors will affect the results. Something like:

int mytest3(SV* sv_vec, unsigned int bit) {

    STRLEN vecbytes; // Length of vector in bytes
    unsigned __int64 *vec = (unsigned __int64 *) SvPV(sv_vec, vecbytes
+);

    if( bit / 8 >= vecbytes) return 0; // Check in range

    vec[ bit / 64] |= ( 1ULL << ( bit % 64 ) ); // Set bit (CHANGES $v
+ector)

    return 1;
}

will handle vectors up to 2 Exabytes with linear efficiency--assuming you had enough memory to hold it :)

Mind you, if I was going to be processing a list of pairs, then I'd move the acquisition of the vector addresses & lengths out of the loop and use macros for the bit testing and setting:

#define REGSIZE 64
#define TSTVEC( v, b ) v[ b / REGSIZE ] &  ( 1ULL << ( b % REGSIZE ) )
+ )
#define SETVEC( v, b ) v[ b / REGSIZE ] |= ( 1ULL << ( b % REGSIZE ) )
+ )

In theory at least, the compiler is more likely to be able to optimise common sub-expression if they do not cross function boundaries. Even in-lined function boundaries.

[syphilis]

'cept that the OP also said that the two vectors aren't in the same order (or even size) and the mapping isn't one to one

Aaah ... yes ... that makes it a little more challenging ....

Cheers,
Rob