Оптимизация for

++i однозначно быстрее чем i++

хороший вопрос, однако... Мну тоже волновала эта проблема, но так явно её описать не получалось :)

судя по твоему описанию, надо делать:

const int end_x = x + width;

(int i=x; i < end_x; i++)

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

А для косвенного изменения через указатель, наверное надо смотреть в сторону volatile - чтобы явно указать что переменная может менятся неподвластным для компилятора методом.

Семантически, компилятор должен вычислять x+width каждый раз. Если оптимизатор потом сочтёт это излишним, он имеет право это вынести. А может и не вынести. Зависит от степени его разумности (точнее, от степени прозрачности языка и твоего кода).

Лично я, когда профилирую код, в среднем на 3000 строк кода в одном цикле выношу x+width в отдельную переменную. Правда, иногда это напротив, замедляет работу, но это уже редкости/частности.

PS. а вот strlen(s) (если речь о сях) я бы, напротив, рекомендовал выносить всегда, кроме случаев, когда тебе лень по кнопкам стучать.

for (i = 0; i < strlen(s); i++) {} - это сложность O(n^2), и такой код лучше вообще не порождать без особой на то нужды.

> ++i однозначно быстрее чем i++

Только в плюсах и далеко не всегда.

Если ни x, ни width в теле цикла не изменяется, то оптимизатор обычно это замечает, если уровень оптимизации >= O1 Можешь взять свою программу (скажем prog.c) и попробовать сделать

gcc -O2 -S prog.c

Создастся файл prog.s, в котором твоя программа будет переведена на ассемблер с заданным уровнем оптимизации. Найди там свой цикл и посмотри, что с ним стало.

При уровне оптимизации O3 могут твориться вообще необъяснимые казалось бы вещи.

Оптимизатор, как правило, очень толковая вестчь.

Тоже самое с strlen. Если s не изменяется, то компилятор должен это заметить.

Но это не значит, что можно во всём надеяться на оптимизатор. :)

> Тоже самое с strlen. Если s не изменяется, то компилятор должен это заметить.

Немного хитрее.

Вообще говоря, компиляторы не оптимизируют через вызовы функций (это, вроде, документировано). Даже если компилятор вынесет strlen() за цикл, он не сможет соптимизировать обращения к локальным переменным. На x86 это не так смертельно, а на Альфе, к примеру, это может быть весьма критично. Но на x86 это тоже заметно. Для for (i = 0; i < strlen(s); i++) gcc -O3 выносит strlen(s) из цикла (я только что на ассемблерный листинг посмотрел), но сам цикл организуется немного менее оптимально, в результате цикл работает на несколько процентов дольше.

>++i однозначно быстрее чем i++

Смотря в каком языке. В Си при любом нормальном оптимизаторе - одинаково :)

...

То же самое и с for.

Вот если будет не "; i < x+width ;", а "; i < x+width() ;" - тогда в каждом цикле суммировать должен. И функцию вызывать.

>for (i = 0; i < strlen(s); i++)

for (i = 0, len = strlen(s); i < len; i++)

>gcc -O3 выносит strlen(s) из цикла

Надо же. А, ведь, подводный камень...

> Надо же. А, ведь, подводный камень...

Еще какой!

Мало того, никакой volatile не помогает -- орет warning: passing argument 1 of 'strlen' discards qualifiers from pointer target type и выносит. IMHO баг это: если в теле цикла переопределять s, даже совсем тупо (s=s, я не шучу!), то strlen(s) остается в цикле. По идее, квалификация volatile должна иметь тот же эффект...

> ++i однозначно быстрее чем i++

Если "i" является итератором, то да. Если это int, то с чего бы ему быть быстрее?

> IMHO баг это: если в теле цикла переопределять s, даже совсем тупо (s=s, я не шучу!), то strlen(s) остается в цикле. По идее, квалификация volatile должна иметь тот же эффект...

Ой-ли? Есть часть функций, которые есть как в стдлибе, так и в самом "компиляторе", т.е. что-то вроде __builtin_strlen().

При включении оптимизации, компилятор в твоём случае определяет, что в цикле вызывается чистая функция strlen(), и именно поэтому он выносит её из цикла.

Разве не так? Вообще, попробуй собрать код с -fno-builtin -ffree-standing (ключи по-памяти, могу немножко ошибаться)

>> IMHO баг это: если в теле цикла переопределять s, даже совсем тупо (s=s, я не шучу!), то strlen(s) остается в цикле. По идее, квалификация volatile должна иметь тот же эффект...

> Ой-ли? Есть часть функций, которые есть как в стдлибе, так и в самом "компиляторе", т.е. что-то вроде __builtin_strlen().

Я -- про другое.

Функция strlen() действительно, gcc интринсик, так что компилятор все про нее знает. Но не в этом дело -- она объявлена в /usr/include/string.h с аттрибутом __attribute_pure__, так что сам по себе вынос этой функции из цикла правомерен -- компилятор знает, что она не имеет побочных эффектов. Если написать свою функцию, то компилятор ее не вынесет, а если добавить в ее описание __attribute_pure__, то будет выносить уже с -O1.

Проблема в том, что когда я говорю, что у меня s volatile, компилятор не должен предполагать, что s в процессе выполнения цикла не меняется.

Например, делаю так: int k=123; ..... for (i = 0; i < k; i++) -- k запихивается в регистр _до_ цикла. А если я так говорю: volatile int k=123; ....., то k запихивается в регистр в теле цикла. В чем принципиальная разница с обсуждаемым циклом?

> Проблема в том, что когда я говорю, что у меня s volatile, компилятор не должен предполагать, что s в процессе выполнения цикла не меняется.

Верно.

Можно gcc -v?

Если вынести volatile s из функции, то компилятор вызывает функцию на каждой итерации.

А если эта переменная локальная и обьявленна без модификатора static - то gcc выносит strlen из цикла. В принципе, всё правильно - ведь переменная изменится не может (она локальная для функции и не static).

>for (i = 0; i < strlen(s); i++) {} - это сложность O(n^2), и такой код лучше вообще не порождать без особой на то нужды.

+1

если не предполагается, что строка будет усекаться, то лучше

for (i = 0; s[i]; i++) {}

в противном случае:

for (i = 0, l = strlen(s); i < l; i++) {... l -= кол-во вырезанных символов ...}

Тогда уж кошернее
for(p = s; *p; p++)

По теме: "машина должна работать, человек - думать".
Если программист ЗНАЕТ (исходя из логики программы), что width/strlen(s)/... не меняются по ходу цикла - он обязан завести временную переменную для них.ну или вообще цикл вывернуть:
for (i=strlen(s);--i>=0;)
Если же в цикле меняются значения пределов - не очень понятно, какого рода оптимизацию Вы ожидаете от компилятора.

> Можно gcc -v?

Using built-in specs.

Target: i586-suse-linux

Configured with: ../configure --enable-threads=posix --prefix=/usr --with-local-prefix=/usr/local --infodir=/usr/share/info --mandir=/usr/share/man --libdir=/usr/lib --libexecdir=/usr/lib --enable-languages=c,c++,objc,f95,java,ada --disable-checking --with-gxx-include-dir=/usr/include/c++/4.0.2 --enable-java-awt=gtk --disable-libjava-multilib --with-slibdir=/lib --with-system-zlib --enable-shared --enable-__cxa_atexit --without-system-libunwind --host=i586-suse-linux

Thread model: posix

gcc version 4.0.2 20050901 (prerelease) (SUSE Linux)

> Если вынести volatile s из функции, то компилятор вызывает функцию на каждой итерации.

Я не понял словосочетания "...вынести volatile s из функции". У меня, как я уже несколько раз тут писАл, компилятор выносит strlen(s) из цикла НЕЗАВИСИМО от волатильности s, чего он делать не должен ИМХО.

> А если эта переменная локальная и обьявленна без модификатора static - то gcc выносит strlen из цикла.

У меня компилятор выносит strlen(s) (и вообще любую функцию, декларированную как __attribute_pure__) из цикла и для локальной переменной s, и для глобальной, и для volatile (и глобальной, и стековой).

> По теме: "машина должна работать, человек - думать". Если программист ЗНАЕТ (исходя из логики программы), что width/strlen(s)/... не меняются по ходу цикла - он обязан завести временную переменную для них.ну или вообще цикл вывернуть: ...

Гы!

Сергей, просто странно такое слышать от жабовода !:) Как раз всякие "юзерфрендли" языки типа Жабки позиционируются как "освобождающие программиста от мыслительного процесса". Типа, встретив for(i=0; i<strlen(s);i++) компилятор сам должен рюхнуть (исходя из семантики strlen), что хотел сказать программист и все правильно соптимизировать.

Но по существу сказанного я абсолютно согласен.

> Если же в цикле меняются значения пределов - не очень понятно, какого рода оптимизацию Вы ожидаете от компилятора.

А я и хочу сказать тупой программе, что значение предел _может_ измениться, несмотря на __attribute_pure__ у strlen. А оно знай себе оптимизирует...

> Сергей, просто странно такое слышать от жабовода !:)
Все правильно. Я для того и балуюсь в оперсорце сями, чтоб от земли не отрываться;)

> А оно знай себе оптимизирует...
Если оно игнорирует такие вещи, это ИМХО бага в компиляторе.

> А я и хочу сказать тупой программе, что значение предел _может_ измениться, несмотря на __attribute_pure__ у strlen. А оно знай себе оптимизирует...

пишите багрепорт. пока можно сказать volatile на указатель вместо значения, тогда вроде не выносит, тоесть вместо volatile char *s; --- char * volatile s;

> ...пока можно сказать volatile на указатель вместо значения, тогда вроде не выносит, тоесть вместо volatile char *s; --- char * volatile s;

Так не выносит, действительно.

С другой стороны, может, то и не баг, а грабли: компилятор же честно предупреждает, что passing argument ... discards qualifiers, так что с точки зрения компилятора все верно, функция волатильность похерила.

Нет, все равно что-то не так.

Вот, попробовал:

volatile char *s;

int slen(volatile char *s) __attribute_pure__;

. . .

int main (void)

. . .

for (i = 0; i < slen(s); i++) ...

gcc -Wall -O3 -S try.c

МОЛЧА выносит slen(s) из цикла.

Говорят, есть пакеты, которые с -O3 вообще не работают. Вроде, тоже на сях написаны.

> Говорят, есть пакеты, которые с -O3 вообще не работают.

:-)

Сам встречал пакеты, которые работают, только будучи собранными с -g -O0. А mplayer дык вообще только определенными версиями ГеЦЦ собирается.

> Сам встречал пакеты, которые работают, только будучи собранными с -g -O0.

А можно посмотреть на эти пакеты? Из любопытства. А то, может, они содержат баги, чувствительные к начальному распределению памяти или вообще пытаются свой код модифицировать ;-)

Да, в студию такие пакеты!

Насчет мплеера -- он умеет запускать бинарные кодеки, выдернутрые из виндов, возможно поэтому он к компилятору критичен?

> А можно посмотреть на эти пакеты? Из любопытства.

Не помню я.

Помню, читал в одном файле INSTALL, что из-за багов оно не будет работать, если компилить с оптимизацией и без отладки.

Насчет глюков с -O3.

Есть у меня пара Итаников, там icc приходится юзать -- gcc процентов на 30 - 100 сливает. Вот оно:

Intel(R) C++ Itanium(R) Compiler for Itanium(R)-based applications Version 8.0 Build 20031017 Package ID: l_cc_p_8.0.055 Copyright (C) 1985-2003 Intel Corporation. All rights reserved. FOR NON-COMMERCIAL USE ONLY

При попытке откомпилить этим чудом сколько-нибудь нетривиальный Цешный файл с -O3 оно тут же сегфолтится.

> А можно посмотреть на эти пакеты?

опен оффис =) он вообще может и не собраться с -O2 или с -O3.

Если работа толстенной программы зависит от -O2, то я бы скорее подозревал баг в толстенной программе, чем некорректность оптимизации. В конце концов, если бы разработчики толстенной программы тестировали её на -O2, а не на -O0, то, возможно, всё было бы наоборот - с оптимизацией работает, а без оптимизации - нет. Или я не прав?

Честно говоря, я ожидал каких-то более объятных примеров :-)

>>> МОЛЧА выносит slen(s) из цикла.

В общем, я хотел сказать, что должен быть чётко оговорённый предел, после которого оптимизация становится некорректной. Вроде, это и есть -O2/-O3.

И, соответственно, за этим пределом нет смысла ожидать, что результат будет работать аккуратно или хотя бы оптимизатор будет выдавать варнинги. На то он и оптимизатор, чтобы работать молча - если бы он мог наперёд знать, какое его действие поломает твою задумку, он бы просто его не делал. А выводить предупреждение на каждый вынос вызова функции из цикла - это, имхо, совершенно неправильно.

PS. хорошо в Джаве - там модель памяти простая и прозрачная (и притом высокоуровневая) по сравнению с низкоуровневыми сложностями сей.