Компиляторы 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

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