Профилирование реализации Set на 64-битных машинах

Question

Соответствующая информация о моей системе: Core2Duo T6500 gcc (GCC) 4.4.1 20090725 (Red Hat 4.4.1-2)

Используя реализацию базового набора, где каждый сохраненный набор является просто лексикографическим порядком сохраненного набора, вы можете использовать стандартные битовые операции для операций Set, таких как объединение, пересечение, elementQ и т. Д.

Мой вопрос касается определения размера набора. Реализации типа Cliquer используют

static int set_bit_count[256]

для хранения количества битов в любой данной возможной 8-битной строке, а затем алгоритм будет проходить через 8 битов за раз, чтобы определить размер набора.

У меня две проблемы с этим:

1. Если регистры более чем в 8 раз быстрее, чем кэш или ОЗУ, это приведет к потере скорости.
2. На 64-битной машине не являются int операции медленнее, чем, скажем, unsigned long long int, которые я предполагаю, являются стандартными целыми числами на 64-битных процессорах.

Но я хотел бы представить, просто используя

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

может быть быстрее, поскольку все может храниться в регистрах. Но с другой стороны, может ли что-то отличаться от очевидного в 8 раз больше операций?

Кроме того, существует так много различных комбинаций int, uint, unsigned long, unsigned long long, что я понятия не имею, с чего начать тестирование.

Знаете ли вы какие-либо очерки на эту тему?

Знаете ли вы какие-либо другие вопросы по этой теме?

Есть ли у вас какие-либо идеи по этому поводу?

Есть ли у вас какие-либо предложения по профилированию? Я никогда не использовал gprof. И когда я использую time.h, я не могу получить тоньше, чем секунда детализации.

Я был бы очень признателен, если бы вы сделали.

Answer 1

Скорее всего (хотя мне сейчас лень проверять), самым быстрым будет

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;
}

(Хотя это взорвется, если процессор не поддерживает SSE4.2.) Конечно, было бы лучше (и более переносимо) использовать встроенные встроенные функции компилятора, и в целом я бы доверял компилятору выбрать наиболее подходящую реализацию для текущей целевой платформы.

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

Answer 2

Я бы профилировал две разные реализации, используя генератор случайных чисел для создания битовых комбинаций. Я зациклился бы на многих итерациях, накапливая что-то во время каждой итерации (например, исключающее ИЛИ счетчика битов), которые я распечатывал в конце цикла. Накопление и печать необходимы для того, чтобы компилятор не оптимизировал ничего важного.