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

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

Страницы: 1 2
#15
15:25, 5 июня 2019

gammaker
Кстати, там можно a[j] ^ b[j] попробовать заменить на a[j] != b[j].
В моих тестах для MSVC это разницы не дало, но clang смог заменить пачку psrldq на одно pmovmskb.
Возможно, какой-то хитрой обвязкой получится и MSVC заставить это сделать.


#16
(Правка: 17:48) 17:32, 5 июня 2019

}:+()___ [Smile]
> Возможно, какой-то хитрой обвязкой получится и MSVC заставить это сделать.
Поэкспериментировал, что-то не получается.

Интересно, а с лексикографическим сравнением можно ли придумать что-то лучше реализации в лоб? А то его бы тоже хорошо было бы сделать constexpr. Без него строки в compile-time сортировать не получится.

Правка: а ну да, если он a[j] != b[j] векторизует, то и a[j] < b[j] векторизует тоже. Но только с char. С char16_t и char32_t уже не прокатывает.

#17
18:20, 5 июня 2019

gammaker
> то и a[j] < b[j] векторизует тоже
a < b векторизовать бесполезно.
Оптимальная функция сравнения выглядит как-то так:
1) векторно сравниваем строки на равенство с помощью pcmpeqb;
2) выколупываем (инвертированную) маску результата с помощью pmovmskb;
3) если маска нулевая, сдвигаем указатели и возвращаемся в п. 1;
4) если маска ненулевая, то битсканом определяем номер отличного символа и возвращаем результат сравнения.

#18
(Правка: 20:01) 20:00, 5 июня 2019

}:+()___ [Smile]
> a < b векторизовать бесполезно.
А, ну да, точно. В таком виде оно может строку которая больше, посчитать, что она меньше.

}:+()___ [Smile]
> 4) если маска ненулевая, то битсканом определяем номер отличного символа и
> возвращаем результат сравнения.
Я правильно понимаю, что в моём случае можно взять существующий compare и вместо

if(c != 0) return false;
написать
if(c != 0) for(size_t i = 0; i < n; i++)
  if(a[j] < b[j]) return true;
  else if(a[j] > [j]) return false;

Это и есть битскан или в SSE такая инструкция есть?

#19
(Правка: 22:24) 22:22, 5 июня 2019

gammaker
> Я правильно понимаю, что в моём случае можно взять существующий compare и вместо
Да, причем этот кусок кода можно объединить вместе с хвостом:

constexpr int compare(const char *a, const char *b, size_t n)
{
    constexpr size_t m = 16;
    for(; n >= m; n -= m)
    {
        char c = 0;
        for(int i = 0; i < m; i++)c |= a[i] ^ b[i];
        if(c != 0)break;
        a += m;  b += m;
    }
    for(int i = 0; i < n; i++)
        if(a[i] != b[i])return a[i] < b[i] ? -1 : 1;
    return 0;
}
Только такой вариант на случайных строках будет медленнее наивного варианта.

> Это и есть битскан или в SSE такая инструкция есть?
В x86 такая инструкция (BSR/BSF) есть, но я не думаю, что можно будет заставить компилятор сгенерировать pmovmskb для использования вместе с битсканами.

#20
22:28, 5 июня 2019
OMG, люди, на что вы тратите свою молодость...
Страницы: 1 2
ПрограммированиеФорумОбщее