#include #include #include #include #define FirstLowInvalidHeapAttributeNumber (-8) #define FLEXIBLE_ARRAY_MEMBER 1 #define elog(elevel, s) \ do { \ printf("%s\n", s); \ exit(EXIT_FAILURE); \ } while(0) #define BITS_PER_BITMAPWORD 32 #define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD) #define BITNUM(x) ((x) % BITS_PER_BITMAPWORD) #define BITMAPSET_SIZE(nwords) \ (offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword)) typedef unsigned int bitmapword; /* must be an unsigned type */ typedef int signedbitmapword; /* must be the matching signed type */ typedef char bool; #define true 1 #define false 0 typedef struct Bitmapset { int nwords; /* number of words in array */ bitmapword words[FLEXIBLE_ARRAY_MEMBER]; /* really [nwords] */ } Bitmapset; void * palloc0(size_t size) { void *p = malloc(size); if (!p) elog(ERROR, "out of memory"); memset(p, 0, size); return p; } /* * bms_is_member - is X a member of A? */ bool bms_is_member(int x, const Bitmapset *a) { int wordnum, bitnum; /* XXX better to just return false for x<0 ? */ if (x < 0) elog(ERROR, "negative bitmapset member not allowed"); if (a == NULL) return false; wordnum = WORDNUM(x); bitnum = BITNUM(x); if (wordnum >= a->nwords) return false; if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0) return true; return false; } static const unsigned char rightmost_one_pos[256] = { 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 }; int bms_next_member(const Bitmapset *a, int prevbit) { int nwords; int wordnum; bitmapword mask; if (a == NULL) return -2; nwords = a->nwords; prevbit++; mask = (~(bitmapword) 0) << BITNUM(prevbit); for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++) { bitmapword w = a->words[wordnum]; /* ignore bits before prevbit */ w &= mask; if (w != 0) { int result; result = wordnum * BITS_PER_BITMAPWORD; while ((w & 255) == 0) { w >>= 8; result += 8; } result += rightmost_one_pos[w & 255]; return result; } /* in subsequent words, consider all bits */ mask = (~(bitmapword) 0); } return -2; } Bitmapset * bms_make_singleton(int x) { Bitmapset *result; int wordnum, bitnum; if (x < 0) elog(ERROR, "negative bitmapset member not allowed"); wordnum = WORDNUM(x); bitnum = BITNUM(x); result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1)); result->nwords = wordnum + 1; result->words[wordnum] = ((bitmapword) 1 << bitnum); return result; } int has_system_columns(Bitmapset *attrs_used) { int i; for (i = FirstLowInvalidHeapAttributeNumber + 1; i < 0; i++) { if (bms_is_member(i - FirstLowInvalidHeapAttributeNumber, attrs_used)) { return 1; } } return 0; } int has_system_columns2(Bitmapset *attrs_used) { int first = bms_next_member(attrs_used, -1); if (first >= 0 && first < -FirstLowInvalidHeapAttributeNumber) return 1; return 0; } #define LOOPS 100000000 int main(void) { clock_t start, finish; int firstcol; for (firstcol = 1; firstcol <= 1024; firstcol <<= 1) { int loop; int dummycounter; Bitmapset *attrs_used = bms_make_singleton(firstcol - FirstLowInvalidHeapAttributeNumber); start = clock(); for (loop = 0; loop <= LOOPS; loop++) dummycounter += has_system_columns(attrs_used); finish = clock(); printf("%d has_system_columns complete in %f\n", firstcol, (double) (finish - start) / CLOCKS_PER_SEC); start = clock(); for (loop = 0; loop <= LOOPS; loop++) dummycounter += has_system_columns2(attrs_used); finish = clock(); printf("%d has_system_columns2 complete in %f\n", firstcol, (double) (finish - start) / CLOCKS_PER_SEC); } }