Войти
ПрограммированиеФорумОбщее

Заставить MSVC оптимизировать сравнение

Страницы: 1 2 Следующая »
#0
(Правка: 21:43) 21:42, 3 июня 2019

Есть такой код:

bool compare(const char* a, const char* b, size_t n)
{
  for(size_t i = 0; i < n; i++)
    if(a[i] != b[i])
      return false;
  return true;
}
Нужно переписать его так, чтобы компилятор (MSVC 2017 и 2019 x86 и x64) считывал не байт за байтом, а работал с более крупными словами: хотя бы 64-битными, но лучше 128 SSE. А в идеале просто распознал, что это memcmp и сгенерировал вызов к ней.
При этом есть ограничения:
1) Нельзя использовать никакие intrinsic и функции кроме своих.
2) Нельзя кастить указатели - в коде работаем только с char'ами.
3) Нельзя кастить через union
4) Нельзя использовать inline assembler

Я уже как только не извращался. Пробовал разворачивать цикл и побитовыми операциями собирать большой uint64_t из 8 разностей a[ i ]-b[ i ], а потом сравнивать это число с 0. Надеялся, что компилятор догадается, что надо просто считать uint64_t, но компилятор всё равно генерирует код, оперирущий байтами по одному и ничего не векторизирует.
Может кто-нибудь знает, как сделать так, чтобы компилятор до этого догадался?


#1
21:52, 3 июня 2019

C++ не знаю, а на паскале так:

type QWord = UInt64;
type PQWord = ^QWord;

if PQWord(Addr01)^ <> PQWord(Addr02)^ then Exit(False);

или если с Char, то так:

if PChar(Addr01)^ <> PChar(Addr02)^ then Exit(False);
Только Char в Delphi = 2 байтам, поэтому надо сравнивать как PAnsiChar.
if PAnsiChar(Addr01)^ <> PAnsiChar(Addr02)^ then Exit(False);
Но AnsiChar и байт одно и тоже, поэтому можно сократить до
if PByte(Addr01)^ <> PByte(Addr02)^ then Exit(False);
#2
22:07, 3 июня 2019

gammaker
> if(a[i] != b[i])

info C5002: loop not vectorized due to reason '1100'
Meaning : Loop contains control flow—for example, "if" or "?".
#3
22:08, 3 июня 2019

gammaker
может не гадать на кофейной гуще, и если надо, то написать на ассемблере?

#4
(Правка: 22:28) 22:25, 3 июня 2019

tac
> может не гадать на кофейной гуще, и если надо, то написать на ассемблере?
Если бы я мог пожертвовать хоть одним условием, я бы просто использовал memcmp. Это был бы идеальный вариант. Но надо сделать так, чтобы компилятор сам догадался вызвать memcmp, либо сгенерировал что-то не сильно уступающее ему в производительности.

eDmk
> C++ не знаю, а на паскале так:
Каст указателя же, противоречит пункту 2. Ну и вообще MSVC неявно предполагает, что это не Паскаль.

0iStalker
> Meaning : Loop contains control flow—for example, "if" or "?".
Это понятно, да. И какие варианты решения? Как переписать код функции так, чтобы с соблюдением тех четырёх условий компилятор использовал SSE или хотя бы читал QWORD, а не BYTE?

#5
22:25, 3 июня 2019

memcmp вызвать не судьба?

#6
(Правка: 22:32) 22:29, 3 июня 2019

https://habr.com/ru/post/440566/
Вкратце- если массивы выровненные и не пересекающиеся, а длина кратна 4 то можно пошалить, иначе облом. Еще можно посмотреть реализацию memcmp b копип-пастнуть себе, раз уж есть желания извратиться.

#7
(Правка: 22:32) 22:29, 3 июня 2019

ShadowTeolog
> memcmp вызвать не судьба?
К сожалению не судьба, но я буду рад, если компилятор сделает это за меня :)

ShadowTeolog
> https://habr.com/ru/post/440566/
Я знаю про SIMD интринсики, но они противоречат условию 1. Но если компилятор сгенерирует SIMD сам, миссия будет выполнена.

#8
(Правка: 22:46) 22:44, 3 июня 2019

В общем, вот: https://godbolt.org/z/naMRAR
Задача: поменять тело функции так, чтобы компилятор сгенерировал эффективный код, но static_assert'ы продолжали работать. Если нарушить хотя бы одно из 4 условий из #0, constexpr сломается и не скомпилируется.

Для Clang и GCC есть обходные пути, там можно задетектить constexpr vs runtime и выбирать медленную реализацию только для constexpr. А в Clang 4.0 и выше вообще есть __builtin_memcmp, который может работать в constexpr.

#9
22:54, 3 июня 2019

gammaker
> Задача: поменять тело функции так, чтобы компилятор сгенерировал эффективный код
Как-то так. Результат, конечно, далек от оптимальности, но лучше чем то что было.

Отладкой и тестированием не занимался, так что корректность не гарантирую, но идею иллюстрирует.
Еще стоит начальное выравнивание обрабатывать, однако это большой геморрой.
#10
22:54, 3 июня 2019

gammaker

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

#11
(Правка: 23:05) 23:03, 3 июня 2019

Ghost2
> Если ты скажешь, зачем это нужно и откуда взялись ограничения, ты сэкономишь
> всем (возможно даже себе) очень много времени.
Если не все ещё поняли по ссылке на Godbolt - это всё ради того, чтобы научить строки работать в compile time и при этом не потерять в производительности runtime.

}:+()___ [Smile]
> Как-то так. Результат, конечно, далек от оптимальности, но лучше чем то что было.
Неплохо, да. У меня тоже была подобная идея, но ты чуть дальше зашёл и получше сделал. Наверное возьму эту версию, если никто не придумает, как избавиться от этих psrldq.

}:+()___ [Smile]
> Еще стоит начальное выравнивание обрабатывать, однако это большой геморрой.
Это по-моему вообще нереально в constexpr, там же нельзя указатель в число кастить.

#12
23:09, 4 июня 2019

В итоге остановился на таком варианте: https://godbolt.org/z/WG7eNC
Обработка 32 байта от 16 по числу инструкций почти не отличается, поэтому сделал сначала цикл по 32, потом кусок хвоста на 16 и остаток хвоста наивным самым простым методом из #0.
Внедрю в свою либу и буду мерить скорость.

#13
2:06, 5 июня 2019

gammaker
> Наверное возьму эту версию, если никто не придумает, как избавиться от этих
> psrldq.
Я попробовал от одного через union избавиться

#14
9:05, 5 июня 2019

foxes
> Я попробовал от одного через union избавиться
Union нельзя, он constexpr ломает. Оно компилируется, потому что при сравнении коротких строк он не попадает в развёрнутый цикл с union. Если в static_assert запихнуть более длинную строчку, то не скомпилируется.

Страницы: 1 2 Следующая »
ПрограммированиеФорумОбщее