сравнить символы для равенства без разветвления

Question

сравнить символы для равенства без разветвления

На предыдущий вопрос где я хотел оптимизировать эту функцию:

static
lvh_distance levenshtein_distance( const std::string & s1, const std::string & s2 )
{
const size_t len1 = s1.size(), len2 = s2.size();
std::vector<unsigned int> col( len2+1 ), prevCol( len2+1 );

const size_t prevColSize = prevCol.size();
for( unsigned int i = 0; i < prevColSize; i++ )
prevCol[i] = i;

for( unsigned int i = 0, j; i < len1; ++i )
{
col[0] = i+1;
const char s1i = s1[i];
for( j = 0; j < len2; ++j )
{
const auto minPrev = 1 + std::min( col[j], prevCol[1 + j] );
col[j+1] = std::min( minPrev, prevCol[j] + (  s1i == s2[j] ? 0 : 1   ) );

}
col.swap( prevCol );
}
return prevCol[len2];
}

Пользователь прокомментировал, что я могу заменить s1i == s2[j] ? 0 : 1 с ((s1i - s2[j]) & 0x80) >> 7 предотвратить условный скачок. Уловка была неправильной, и пользователь удалил свой комментарий, но мне интересно, действительно ли может быть способ сделать это.

3

branch-prediction c++comparison optimization performance

Решение

Другие решения

Почему бы не использовать следующее: !(s1i == s2[j]) или же (s1i != s2[j]) потому что преобразование bool в int неявно

2

Не практический ответ, а скорее, чтобы решить загадку.
Создать массив one_or_zero[UCHAR_MAX+1] заполните его 1с, и one_or_zero[0] = 0;
Теперь вы можете сделать что-то вроде prevCol[j] + one_or_zero[s1i^s2[j]])
это приведет к 0 на s1i==s2[j] и 1 в противном случае добавляется prevCol[j]

1

Источник

Accepted Answer

Предполагая, что код

s1i == s2[j] ? 0 : 1

дает вам операцию ветвления, которую вы действительно хотите избежать, вы можете просто попробовать следующее:

!(s1i == s2[j])

Это должно дать тот же эффект и может помочь компилятору удалить ветвление. Или вы можете изменить логику и написать

s1i != s2[j]

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

3