Profiling a Set implementation on 64-bit machines

Relevant Information on my system:
Core2Duo T6500
gcc (GCC) 4.4.1 20090725 (Red Hat 4.4.1-2)

Using the basic set implementation, where each set that is stored is really just the lexicographical order of the set stored, you can use standard bit operations for Set operations like Union, Intersection, elementQ, etc.

My question is about determining the size of the set. Implementations like Cliquer use a

static int set_bit_count[256]

to store how many bits are in any given possible 8 bit string, and then the algorithm would go through 8 bits at a time to determine the set's size.

I have two problems with that way:

If registers are more than 8x faster than cache or RAM, this would waste speed.
In a 64-bit machine, are not int operations slower than say, unsigned long long int which I assume are the standard operating integers on 64-bit CPU's.

But I would imagine just using a simple

while(x)
  x&=x-1;
  ++count;

could be faster as everything could be stored in registers. But on the downside, could something other than the obvious 8x times as many operations?

Also, there are so many different combinations of int, uint, unsigned long, unsigned long long that I have no Idea where to start testing.

Do you know any essays on this topic?

Do you know any other SO questions on this topic?

Do you have any insights to this?

Do you have any suggestions on how to profile this? I've never used gprof. And when I use time.h, I can't get finer than a second of granularity.

I would be very grateful if you did.

Best Answer

Most likely (though I'm too lazy to test right now), the fastest would be

int popcount(unsigned x) {
    int count;
#if defined(__GNUC__)
    __asm__("popcnt %1,%0" : "=r" (count) : "r" (x));
#elif defined(_MSC_VER)
    __asm {
        POPCNT x, count
    };
#else
    /* blah, who cares */
    for (count = 0; x; count += x&1, x >>= 1);
#endif
    return count;
}

(Though this will explode if the CPU doesn't support SSE4.2.) Of course, it would be better (and more portable) to use the compilers' built-in intrinsics, and in general I would trust the compiler to choose whatever implementation is best for the current target platform.

int popcount(unsigned x);
#if defined(__GNUC__)
# define popcount __builtin_popcount
#elif defined(_MSC_VER)
# define popcount __popcnt
#else
/* fallback implementation */
#fi

Setting a bit

Use the bitwise OR operator (|) to set a bit.

number |= 1UL << n;

That will set the nth bit of number. n should be zero, if you want to set the 1st bit and so on upto n-1, if you want to set the nth bit.

Use 1ULL if number is wider than unsigned long; promotion of 1UL << n doesn't happen until after evaluating 1UL << n where it's undefined behaviour to shift by more than the width of a long. The same applies to all the rest of the examples.

Clearing a bit

Use the bitwise AND operator (&) to clear a bit.

number &= ~(1UL << n);

That will clear the nth bit of number. You must invert the bit string with the bitwise NOT operator (~), then AND it.

Toggling a bit

The XOR operator (^) can be used to toggle a bit.

number ^= 1UL << n;

That will toggle the nth bit of number.

Checking a bit

You didn't ask for this, but I might as well add it.

To check a bit, shift the number n to the right, then bitwise AND it:

bit = (number >> n) & 1U;

That will put the value of the nth bit of number into the variable bit.

Changing the nth bit to x

Setting the nth bit to either 1 or 0 can be achieved with the following on a 2's complement C++ implementation:

number ^= (-x ^ number) & (1UL << n);

Bit n will be set if x is 1, and cleared if x is 0. If x has some other value, you get garbage. x = !!x will booleanize it to 0 or 1.

To make this independent of 2's complement negation behaviour (where -1 has all bits set, unlike on a 1's complement or sign/magnitude C++ implementation), use unsigned negation.

number ^= (-(unsigned long)x ^ number) & (1UL << n);

unsigned long newbit = !!x;    // Also booleanize to force 0 or 1
number ^= (-newbit ^ number) & (1UL << n);

It's generally a good idea to use unsigned types for portable bit manipulation.

number = (number & ~(1UL << n)) | (x << n);

(number & ~(1UL << n)) will clear the nth bit and (x << n) will set the nth bit to x.

It's also generally a good idea to not to copy/paste code in general and so many people use preprocessor macros (like the community wiki answer further down) or some sort of encapsulation.

Sqlite – Improve INSERT-per-second performance of SQLite

Several tips:

Put inserts/updates in a transaction.
For older versions of SQLite - Consider a less paranoid journal mode (pragma journal_mode). There is NORMAL, and then there is OFF, which can significantly increase insert speed if you're not too worried about the database possibly getting corrupted if the OS crashes. If your application crashes the data should be fine. Note that in newer versions, the OFF/MEMORY settings are not safe for application level crashes.
Playing with page sizes makes a difference as well (PRAGMA page_size). Having larger page sizes can make reads and writes go a bit faster as larger pages are held in memory. Note that more memory will be used for your database.
If you have indices, consider calling CREATE INDEX after doing all your inserts. This is significantly faster than creating the index and then doing your inserts.
You have to be quite careful if you have concurrent access to SQLite, as the whole database is locked when writes are done, and although multiple readers are possible, writes will be locked out. This has been improved somewhat with the addition of a WAL in newer SQLite versions.
Take advantage of saving space...smaller databases go faster. For instance, if you have key value pairs, try making the key an INTEGER PRIMARY KEY if possible, which will replace the implied unique row number column in the table.
If you are using multiple threads, you can try using the shared page cache, which will allow loaded pages to be shared between threads, which can avoid expensive I/O calls.
Don't use !feof(file)!

I've also asked similar questions here and here.