Опять об оптимизации. gcc -O3 Intel i5-2500 Segmentation fault

#gcc #оптимизация #intel

Это скорее сообщение, навеянное темами Методы оптимизации, основанные на эффективном
использовании оборудования и Примеры оптимизации путём группировки данных в памяти,
чем вопрос. Надеюсь, что для кому-нибудь оно окажется полезным.

Недавно подбирал с помощью SMHasher подходящую для реализации хэш-таблиц в одной
конкретной задаче хэш-функцию.  Заметил, что на скорость поиска в таблице с длинными
(несколько десятков байт) ключами в основном влияет именно скорость работы функции,
вычисляющей хэш-код (число), а не "качество" хэш-кода.

Известно, что в X-86 и X-64 допустимо обращение к невыровненным целым числам. Поэтому
я попробовал вот такую примитивную функцию (стиль для запуска в SMHasher):

#include 
#include 

void 
dummyhash (const void *key, int len, uint32_t seed, void *out)
{
  uint32_t h = seed, *pk = (uint32_t *)key;

  for (; len > 3; len -= 4, pk++)
    h ^= (*pk + len);

  const u_char *s = (u_char *)pk;
  switch (len) {
  case 3:
    h ^= ((*s++ + 3) << 24);
  case 2:
    h ^= ((*s++ + 2) << 16);
  case 1:
    h ^= (*s + 1);
  }

  *(uint32_t*)out = h;
}


И действительно, результаты оказались самыми лучшими. Однако, если оттранслировать
ее gcc -O3 компилятор GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3, то на

 Intel(R) Core(TM) i5-2500 CPU @ 3.30GHz


для невыровненных на границу 4 байта ключах, длиннее 15 байт программа падает с Segmentation
Fault, но на CPU

Intel(R) Xeon(R) CPU           E5520  @ 2.27GHz


ОНА ЖЕ работает нормально (именно исполнимый файл, полученный на i5 и падающий там(!)),
ну, на машинах с X-86 тоже все работает (естественно собранное для X-86).

(Если вдруг кому-то интересен ассемблерный код, то я его выложил сюда.)

Такое, вот, любопытное наблюдение.

Кстати, а под конец все-таки вопрос: как вы считаете, где на самом деле ошибка в
GNU или в Intel?

Update, вызывающий код.

t.c:

#include 
#include 
#include 
#include 


void dummyhash(const void *, int, uint32_t, void *);

int
main (int ac, char *av[])
{
  char t[256], res[16];
  memset(t, 0, 256);

  printf ("Hi, i am %ld bit\n", (long)sizeof(long) * 8);

  for (int i = 0; i < 100; i += 3) {
    printf("%p  %d ", t+i, i); fflush(stdout);
    dummyhash((void *)(t + i), 32, 0, (void *)res);
  }

  puts("end");

}


Еще раз повторюсь, работает gcc -O2 -c dummyhash.c на Xeon и i5-2500.

C gcc -O3 работает на Xeon, а на i5-2500 валится по Segmentation Fault.

Один и тот же загрузочный модуль, созданный на i5-2500.

То что данные не выровнены на границу слова, я естественно знаю, по идее это все
равно должно работать (медленнее, но это к делу не относится) в X-64.



Update 2

Ответ и комментарии @user1034749 побудили меня все же вернуться к этому хламу и модифицировать
код так, чтобы он работал независимо от выравнивания данных на разных CPU (в т.ч. требующих
выравнивания для типа int).

Сразу скажу, что сделать тот же самый алгоритм (конкретно, такое же использование
длины ключа при вычислении хэша как в коде выше) без копирования данных мне не удалось
(кто сможет, пишите ответы!!!). 

Понятно, что копирование в выровненную область напрочь убивает производительность
подобных функций, поэтому я просто отказался от сложения очередной 4-ки байт ключа
с оставшейся его длиной при вычислениях хэша. И тут снова неожиданное открытие. Оказалось,
что даже при компиляции с -msse2 -O3 (которая вызывала падение на i5 и x-86) программа
на невыровненных данных валиться перестала. Т.е. к падению приводила не собственно
загрузка невыровненных int в xmm-регистр, а последующая команда сложения (что-то с
конвейером в этих моделях? (в общем, конечно, вопросы к Intel остаются...)). 

Впрочем, наверное хватит слов. Для интересующихся код. Естественно, качество хэш-функции
по сравнению с первым вариантом упало.

#include 
#include 
#include 

#define ROTL32(v,n) (((uint32_t)(v) << (n)) | ((uint32_t)(v) >> (32 - (n))))

void
dummyhash (const void *key, int keylen, uint32_t seed, void *out)
{
  uint32_t h = 0, h1 = 0, 
    *pkey, len = keylen > 0 ? keylen : 0, 
    i = 0, 
    bnd = __alignof__(h), ofs = ((long)key & (bnd - 1));
  u_char *ph1 = (u_char *)&h1, 
    *s = (u_char *)key;


  if (ofs && len > sizeof(*pkey) - 1)
    for (; i < bnd - ofs; i++, len--)
      ph1[i] = *s++;

  for (pkey = (uint32_t *)s; 
       len > sizeof(*pkey) - 1; len -= sizeof(*pkey), pkey++)
    h ^= *pkey;
  h = ROTL32(h, (bnd - ofs) * CHAR_BIT);

  for (s = (u_char *)pkey; len; len--, i++)
    ph1[i % sizeof(h1)] ^= *s++;

  *(uint32_t*)out = h ^ h1 ^ seed;
}

    

Ответы

Ответ 1

Кстати, а под конец все-таки вопрос: как вы считаете, где на самом деле ошибка в
GNU >или в Intel?


Ошибка в вашем коде. В стандарте C есть упоминание
"memory align requirements". "Сколько именно в байтах"
отдано на откуп компилятору.


  То что данные не выровнены на границу слова, я естественно знаю, по идее это все
>равно должно работать (медленнее, но это к делу не относится) в X-64.


Компилятор может предъявлять более строгие требования,
чем процессор (и ABI на платформу), это никак стандарту не противоречит.
И gcc как раз предъявляет, на amd64 скомпилируйте и запустите
такой код:

#include 
#include 
int main()
{
    printf("%u\n", (unsigned)__alignof__(int32_t));
}


и вы узнаете, что требования по выравниванию 4.
И компилятор расчитывает, что вы соблюдаете эти требования,
а если нет то он будет генерировать код который может падать,
а может не падать и работать нормально, в общем корректная
работа gcc гарантируется, только если вы соблюдаете требования
по выравниваю.