C 64-разрядная производительность цикла на x86

Мне нужна функция контрольной суммы Интернета (одна контрольная сумма) для некоторого кода обработки ICMP ICv4 с использованием сырых сокетов, и я наткнулся на поведение, которое я не могу объяснить на 64-разрядном процессоре Intel (с использованием gcc 4.8.2). Мне было интересно, может ли кто-нибудь пролить свет на него.

Я реализовал первую функцию контрольной суммы, используя 32-разрядный аккумулятор и выполнив 16-разрядные суммы. Затем я реализовал то же самое с использованием 64-разрядного аккумулятора и 32-разрядных сумм, считая, что меньшее количество сумм приведет к более быстрому выполнению. В результате первая реализация выполняется в два раза быстрее, чем вторая (с оптимизацией O3). Я просто не могу понять, почему...

Приведенный ниже код фактически не выполняет точные контрольные суммы (я упростил его), но иллюстрирует проблему. Оба скомпилированы как 64-разрядные, работающие на 64-битной собственной платформе (LP64: короткие 16-битные, int 32-разрядные, длинные 64-разрядные, указатели 64-разрядные).

32-разрядный аккумулятор и 16-разрядные суммы

unsigned short
cksum_16_le(unsigned char* data, size_t size)
{
    unsigned short word;
    unsigned int sum = 0;
    unsigned int i;

    for(i = 0; i < size - 1; i += 2)
        sum += *((unsigned short*) (data + i));

    sum = (sum & 0xffff) + (sum >> 16);
    sum = (sum & 0xffff) + (sum >> 16);

    return ~sum;
}

50 000 вызовов функций по тем же самым данным 10k: ~ 1,1 секунды.

64-разрядный аккумулятор и 32-разрядные суммы

unsigned short
cksum_32_le(unsigned char* data, size_t size)
{
    unsigned long word;
    unsigned long sum = 0;
    unsigned int i;

    for(i = 0; i < size - 3; i += 4)
        sum += *((unsigned int*) (data + i));

    sum = (sum & 0xffffffff) + (sum >> 32);
    sum = (sum & 0xffffffff) + (sum >> 32);
    sum = (sum & 0xffff) + (sum >> 16);
    sum = (sum & 0xffff) + (sum >> 16);

    return ~sum;
}

50 000 вызовов функций по тем же самым данным 10k: ~ 2,2 секунды.

Update:

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

Окончательное обновление:

Интересно, что замена циклов for на циклы while и компиляция с оптимизацией O3 (показана ниже для случая с 64-разрядным аккумулятором) приводит к тому, что 32-разрядные и 64-разрядные накопители будут работать с одинаковой скоростью. Это связано с тем, что компилятор выполняет некоторую циклическую развертку (как ни странно, он не разворачивает цикл for) и выполняет суммирование с помощью регистров mmx...

uint64_t sum = 0;
const uint32_t* dptr = (const uint32_t*) data;

while (size > 3)
{
    sum += (uint32_t) *dptr++;
    size -= 4;
}

Ответ 1

Ранее у меня была аналогичная проблема; Я не мог найти никаких проблем в любом из наших кодов. НО что сработало для меня, это изменение компилятора.

Я предполагаю, что GCC пишет устаревшую сборку.

Если вы можете декомпилировать свое приложение, мы можем пролить свет на проблему, но здесь недостаточно информации, чтобы продолжить здесь.

Когда я декомпилировал свой код, я обнаружил, что он несколько раз переписывал целый метод. но это может быть только для меня.

Надеюсь, это помогло вам, информации об этом практически нет.

Если бы я должен был предположить, что согласен с Learner, я вполне уверен, что декомпилированный код будет указывать на цикл for. Я очень заинтересован в этом вопросе, поэтому прокомментируйте это.

Ответ 2

Вероятный ответ: условие "i < size-1" может быть скомпилировано и выполнено более эффективно, чем "i < size-3". Сначала требуется только инструкция декремента вместо другой, которая требует, чтобы константа 3 также была загружена. Этот расчет выполняется с каждой итерацией. Вы должны сохранить результат этого расчета в другом месте.

Это не имеет никакого отношения к циклу while. Когда вы переписываете цикл while, вы также изменили условие итерации и устранили причину выше.

Я также предпочел бы делать кастинг типа вне цикла, но это также показывает одно ограничение - ваши данные должны

Ответ 3

Вы затрудняете работу компилятора. Во внутреннем цикле вы вычисляете смещение байта самостоятельно по вашему выбору шага индекса и приведения. Это может препятствовать разворачиванию цикла или любой другой оптимизации, которая пытается выполнить выравнивание. Нельзя также позволить компилятору использовать режимы адресации и выходить, чтобы вычислить сам эффективный адрес (или LEA it).

Если бы я делал это, я бы бросил указатель данных в верхней части цикла на ваш тип шага и увеличил счетчик циклов на 1. Компилятор может быть немного счастливее.

Ответ 4

Я думаю, что он не может развернуть цикл "for" из-за приведения из char * в unsigned int *. Приведение типов часто не позволяет компилятору оптимизировать код, потому что в этом случае невозможно провести идеальный анализ псевдонимов. Если вы сначала объявите дополнительный локальный указатель, чтобы передать свой "указатель данных" перед циклом, чтобы в цикле не было никакого перевода, компилятор должен иметь возможность оптимизировать цикл "для".

Ответ 5

sum += *((unsigned int*) (data + i));

Мне не нравится такой актер в

64-разрядный аккумулятор и 32-разрядные суммы

так как вы написали:

Оба скомпилированы как 64-разрядные, запущенные на 64-битной собственной платформе (LP64: короткие 16-битные, int 32-разрядные, длинные > 64-разрядные, указатели 64-разрядные).

Я бы предложил использовать (unsigned long *). Некоторые люди советуют проверять в разобранном коде, что происходит в действительности. Я думаю, это из-за вашего int * cast с длинным аккумулятором.

Как насчет без флага O2 < > O3? Не могли бы вы показать, что такое скорость в обычном режиме компиляции?