И снова clang: Почему (при оптимизации) реализация на указателях получилась хуже чем с использованием оператора [ ]?

Question

[MrBman]

В общем суть такая, есть код:

int str_cmp1(const char *s, const char *t)
{
    while (*s == *t && *s != '\0')
        ++s, ++t;
    return *s - *t;
}

int str_cmp2(const char *s, const char *t)
{
	int  i;
    for (i = 0; s[i] == t[i] && s[i] != '\0'; ++i)
        ;
	return s[i] - t[i];
}

Почему сlang оптимизировал второй вариант лучше?
Посмотреть данный пример (Compiler Explorer):

Answer 1

[Mercury13]

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

Кстати, посмотри интереса ради gcc -Os.

Comments

[res2001]

Похоже, что gcc без -Os считает, что более объемный вариант будет работать быстрее. Возможно он прав.

[MrBman]

Кстати, посмотри интереса ради gcc -Os.

Спасибо, за полезную информацию!

[MrBman]

res2001, Если вы имеете в виду вообще без каких-либо оптимизаций, Эм .. если я правильно понимаю, то вполне логично что первый вариант лучше, посколько компилятор всегда транслирует выражение s[i] в *(s + K*i),
где i надо умножить на размер объекта (K) (в данном случае это не важно так как K = 1 поскольку это тип char), а вот в остальных случаях надо будет еще и УМНОЖАТЬ.
Но даже и без учета умножения во втором варианте много выражений вида s[i], а значит при вычислении таких выражений надо будет каждый раз выполнять сложение!
P\S меня интересует именно при оптимизации

[MrBman]

Компилятор первую версию превращает во вторую

Эм .. а разве тогда код не должен был получиться одинаковый при одном и том же флаге оптимизации? Мне просто не понятно почему он не может сообразить при флаге -O1 сделать тоже самое что он сделал со вторым вариантом при этом же флаге!
Он не смог в первом варианте распознать "шаблон", а во втором случае смог, так как второй случай очень распространенный "прием"?

[res2001]

MrBman,

Но даже и без учета умножения во втором варианте много выражений вида s[i], а значит при вычислении таких выражений надо будет каждый раз выполнять сложение!

Вы же видите по вашей же ссылке, что компилятор достаточно умный, что бы не выполнять сложение каждый раз - сложение происходит один раз:

movsx   eax, byte ptr [rdi + rcx]
movzx   edx, byte ptr [rsi + rcx]

Дальше используется загруженное в регистры значения.

[MrBman]

Вы же видите по вашей же ссылке, что компилятор достаточно умный, что бы не выполнять сложение каждый раз - сложение происходит один раз:

Эм .. по моей ссылке используется флаг оптимизации -O1.
Я же написал: что именно ВООБЩЕ БЕЗ оптимизаций первый вариант ВСЕГДА будет лучше второго!
P\S смысл всего вопроса изначально и был в том: Почему то что без оптимизации лучше - после оптимизации оказалось хуже? Как я понял просто компилятор тупо во втором распознал "шаблон" решения некоторой задачи так как это распространенный прием, а в первом случае не смог понять что это тот же самый шаблон! - иначе почему он не сгенерировал одинаковый код?

Answer 2

[res2001]

В первом случае первая итерация цикла выполняется вне цикла (отсюда и больше размер). Во втором варианте все итерации выполняются в цикле.
Код внутри цикла один и тот же. Скорость исполнения будет одинакова.
Разница только в том, что первый вариант на несколько байт больше размером.
Кстати, gcc показывает идентичный код в обоих случаях.

Предлагаю еще такой вариант:

int str_cmp1(const char *s, const char *t)
{
 while (*s == *t++ && *s != '\0')  ++s;
    return *s - *t;
}

Comments

[res2001]

Кстати - t[i] - то же надо проверять на конец строки!

[q2zoff]

res2001, скажите, пожалуйста, какая конкретно итерация выполняется вне цикла?

И зачем нужно проверять t[i] на конец строки, если сначала выполняется проверка на равенство?

PS В вашем варианте кода на одну операцию инкремента больше.

[res2001]

В варианте str_cmp1() первая итерация цикла компилятором реализуется перед входом в цикл, а все остальное уже в цикле.

[MrBman]

res2001, Уж бог с ней с лишней операцией инкремента, Ваш код вообще не будет работать, точнее он будет делать не то что надо:)))

1) выражение вида *t++ означет следующее *(t++)
2) значение выражение вида t++ равно t, ОДНАКО после вычисления этого выражения значение t будет увеличено на 1 (хотя это не обязательно выполнится после вычисления этого выражения) возможно это произойдет после вычисления всего выражения *(t++) - всё завсиит от реализации компилятора
3) таким образом значение всего выражения *(t++) равно *t, где как было сказано выше t это значение до увеличения на 1, ОДНАКО для тех кто будет использовать значение t ниже оно уже увеличено на 1
4) а значит в последней инструкции return *s - *t;
значение t будет не то которое нам нужно и как результат мы получим неправильный результат

Ну, Например:
char *s = "Hello!";
char *t = "Hello!#";
тогда получим что строки равны
потому что когда мы дойдем до конца и будет сравнивать '\0' из s
с '#' из t то мы после увеличим t на 1 и как результат тепеть t указывает также на '\0'
и как результат получим return '\0' - '\0'
=> равны, что конечно же не так:)))

Вот такой вот хитрый и типичный баг, когда используешь подобные выражения c побочными эффектами. В Си это целая история:)))
Рекомендую прочитать, если интересно книжку:
The C puzzle book by Alan R. Feuer
эта книга просто божественна

[res2001]

MrBman, Извиняюсь за паузу.
Откуда у вас такая уверенность что *t++ работает именно так как вы пишете? Хочу ссылку увидеть!
Вы ошибаетесь на счет *t++ - оно работает именно так как задумывается, а именно - возвращает значение *t, затем увеличивает на 1 адрес в t.
https://stackoverflow.com/questions/18481740/point...
https://ideone.com/qKYDPj

Но вы правы в том, что return будет возвращать не верное значение из-за *t++, я не обратил на это внимания, согласен.

[MrBman]

Вы ошибаетесь на счет *t++ - оно работает именно так как задумывается, а именно - возвращает значение *t, затем увеличивает на 1 адрес в t.
Но вы правы в том, что return будет возвращать не верное значение из-за *t++, я не обратил на это внимания, согласен.

Эм... так в чем проблема то? я же написал тоже самое:))) в пункте 3:
3) таким образом значение всего выражения *(t++) равно *t, где как было сказано выше t это значение до увеличения на 1, ОДНАКО для тех кто будет использовать значение t ниже оно уже увеличено на 1
Смотрите приоритеты операторов:
https://en.cppreference.com/w/c/language/operator_...
книга о которой я писал выше:
https://www.amazon.com/Puzzle-Book-Alan-R-Feuer/dp...

[MrBman]

MrBman,
t++ это выражение, а его значение это t. В результате вычисления этого выражения получаем побочный эффект (значение самого t увеличивается на 1). Инструкция вида t++;
означает вычислить значение выражения ради побочного эффекта (значение самого выражения просто отбрасывается)
++t это выражение, а его значение это t + 1. Всё остальное тоже самое как и выше.
Другими словами, инструкции вида t++; и ++t; дают один и тот же побочный эффект, однако значения самих выражений t++ и ++t РАЗНЫЕ, а это уже оказывает влияние на то каким образом вычисляются эти выражения, когда они являются частью составного выражения.
Например, выражение *t++
Приоритет оператора ++ выше чем у опереатора *, а это означает следующее *(t++)
Сперва должно быть вычислено значение выражения t++, а как было сказано выше это t, и в результате побочного эффекта значение t должно быть увеличено на 1, а это означает что нам потребуется сохранить предыдущее значение t, для последующего его использования в качестве операнда для оператора *
Выражение *++t
Тоже самое, *(++t), Однако значение выражения ++t это t + 1, а это означает что нам НЕ потребуется сохранять предыдущее значение t
Именно поэтому говорят, что ++t эффективнее t++, Просто компилятор разруливает всю ситуацию и мы не видим разницы. Хотя говорят что в более дилекатных ситуациях это может оказать влияние на производительность.
Однако, ЕСЛИ я не ошибаюсь, то в стандарте языка ничего не говорится о том когда именно должен быть сохранен результат побочного эффекта (это будет зависеть от компилятора), таким образом, например в выражении:
t / ++t
Нет гарантии чему будет равно значение всего этого выражения (сперва мы вычисляем значение выражения ++t)
НО вот далее возникает закономерный вопрос: левый операнд t будет вычислен ДО того как результат побочного эффекта будет сохранен, или уже ПОСЛЕ?

[res2001]

MrBman, Зачем столько текста? Я знаю как работает постинкремент. В примере использовал его сознательно в целях заставить компилятор немного по другому построить цикл - это кстати вполне получилось. Но не обратил внимание, на то что из-за изменений результат работы функции стал не верным, о чем уже писал выше.
Дальнейшее недопонимание возникло видимо из-за того что либо я плохо понял ваши пространные разъяснения, либо вы их написали не достаточно понятно, скорее всего оба фактора сыграли.
Так что предлагаю тему закрыть :-)

[MrBman]

Дальнейшее недопонимание возникло видимо из-за того что либо я плохо понял ваши пространные разъяснения, либо вы их написали не достаточно понятно, скорее всего оба фактора сыграли.

В будущем постараюсь исправить свой недостаток подробного (чрезмерного) многословия. В любом случае, огромное вам спасибо за оказанную помощь и потраченное время, особенно за ссылку на https://stackoverflow.com/ - Думаю это то, что мне нужно, так что буду перебираться туда, поскольку Тостер это явно не то место, где мне смогут ответить на мои извращенные вопросы:)))

Answer 3

[Михаил Потанин]

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