Компиляторы C & С++ оптимизируют сравнение с вызовами функций?

Компиляторы C и С++ обычно оптимизируют сравнение с функциями?

Например, эта страница предполагает, что функция size в std:: lists в С++ может иметь линейную сложность O (N) в некоторых стандартных реализациях библиотек (что имеет смысл для связанного списка).

Но в этом случае, если myList является огромным списком, что бы это делало?

    if (myList.size() < 5) return 1;
    else return 2;

Будет ли функция size() находить и подсчитывать все элементы списка N или будет ли она оптимизирована для короткого замыкания после поиска 5 членов?

Ответ 1

Теоретически возможность существует, если size() был встроен, но для выполнения оптимизации компилятор должен был

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

Это большая куча вещей, чтобы рассчитывать на IMHO, и она включает в себя функции, которые не являются "явно полезными" и в других контекстах. Имейте в виду, что поставщики компиляторов имеют ограниченные ресурсы, поэтому для реализации этих предварительных условий должно быть действительно хорошее оправдание, а компилятор объединяет все части для оптимизации этого случая.

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

Ответ 2

Собственно, в С++ 11 оптимизируется std::list, а size() возвращается в постоянное время.

Для С++ 03, size() действительно работает в линейном времени, так как ему нужно каждый раз подсчитывать элементы.

Будет ли функция size() находить и подсчитывать все элементы списка N или будет ли она оптимизирована для короткого замыкания после поиска 5 членов?

Никогда не видел такой оптимизации на практике. Хотя это, безусловно, законно, я сомневаюсь, что какой-нибудь компилятор действительно реализует что-то вроде этого.

Ответ 3

Сама функция myList.size() не может быть скомпилирована с той целью, для которой вы ее используете, поэтому она будет определять весь размер. Чтобы получить оптимизацию, которую вы предлагаете, вам понадобится специальная функция предиката вместо общего size(), что-то вроде bool sizeLessThan(int);.

Ответ 4

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