i ++ менее эффективен, чем ++ i, как это показать? - PullRequest
Новая
       43

i ++ менее эффективен, чем ++ i, как это показать?

15 голосов
/ 12 июля 2009

Я пытаюсь показать на примере, что приращение префикса более эффективно, чем приращение постфикса.

Теоретически это имеет смысл: i ++ должен иметь возможность возвращать неотмеченное исходное значение и, следовательно, сохранять его, тогда как ++ я могу вернуть увеличенное значение без сохранения предыдущего значения.

Но есть ли хороший пример, чтобы показать это на практике?

Я попробовал следующий код: 

int array[100];

int main()
{
  for(int i = 0; i < sizeof(array)/sizeof(*array); i++)
    array[i] = 1;
}

Я скомпилировал его, используя gcc 4.4.0, вот так: 

gcc -Wa,-adhls -O0 myfile.cpp

Я сделал это снова, с приращением постфикса, измененным на приращение префикса: 

for(int i = 0; i < sizeof(array)/sizeof(*array); ++i)

В результате идентичный код сборки в обоих случаях.

Это было несколько неожиданно. Казалось, что, отключив оптимизацию (с -O0), я должен увидеть разницу, чтобы показать концепцию. Что мне не хватает? Есть ли лучший пример, чтобы показать это?

Ответы [ 9 ]

23 голосов
/ 13 июля 2009

В случае general , пост-увеличение приведет к копии, а предварительное увеличение не будет. Конечно, это будет оптимизировано во многих случаях, а в случаях, когда это не так, операция копирования будет незначительной (т. Е. Для встроенных типов).

Вот небольшой пример, который показывает потенциальную неэффективность постинкремента. 

#include <stdio.h>

class foo 
{

public:
    int x;

    foo() : x(0) { 
        printf( "construct foo()\n"); 
    };

    foo( foo const& other) { 
        printf( "copy foo()\n"); 
        x = other.x; 
    };

    foo& operator=( foo const& rhs) { 
        printf( "assign foo()\n"); 
        x = rhs.x;
        return *this; 
    };

    foo& operator++() { 
        printf( "preincrement foo\n"); 
        ++x; 
        return *this; 
    };

    foo operator++( int) { 
        printf( "postincrement foo\n"); 
        foo temp( *this);
        ++x;
        return temp; 
    };

};


int main()
{
    foo bar;

    printf( "\n" "preinc example: \n");
    ++bar;

    printf( "\n" "postinc example: \n");
    bar++;
}

Результаты оптимизированной сборки (которая фактически удаляет вторую операцию копирования в случае постинкрементного увеличения из-за RVO): 

construct foo()

preinc example: 
preincrement foo

postinc example: 
postincrement foo
copy foo()

В общем, если вам не нужна семантика постинкремента, зачем полагать, что возникнет ненужная копия?

Конечно, хорошо иметь в виду, что пользовательский оператор ++ () - вариант pre или post - может свободно возвращать все, что хочет (или даже делать, что хочет), и я думаю, что есть многие из них не следуют обычным правилам. Иногда я сталкивался с реализациями, которые возвращают «void», что устраняет обычную семантическую разницу.

8 голосов
/ 12 июля 2009

Вы не увидите никакой разницы с целыми числами. Вам нужно использовать итераторы или что-то, где post и prefix действительно делают что-то другое. И вам нужно включить все оптимизации на , а не выключить!

5 голосов
/ 12 июля 2009

Мне нравится следовать правилу «говори, что ты имеешь в виду».

++i просто увеличивается. i++ увеличивает и имеет специальный неинтуитивный результат оценки. Я использую i++ только если я явно хочу такое поведение, и использую ++i во всех других случаях. Если вы будете следовать этой практике, когда увидите в коде i++, очевидно, что поведение после инкремента действительно было задумано.

4 голосов
/ 13 июля 2009

Несколько баллов:

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

Если вы хотите показать разницу, самый простой вариант - просто помешать обоим операторам и указать, что один требует дополнительной копии, а другой - нет.

0 голосов
/ 13 июля 2009

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

Если пример предназначен для студентов, не знакомых с набором инструкций x86, вы можете рассмотреть возможность использования набора инструкций MIPS32 - по какой-то странной причине многим кажется, что его легче понять, чем сборку x86.

0 голосов
/ 13 июля 2009

В ответ Михаилу, это несколько более переносимая версия его кода: 

#include <cstdio>
#include <ctime>
using namespace std;

#define SOME_BIG_CONSTANT 100000000
#define OUTER 40
int main( int argc, char * argv[] ) {

    int d = 0;
    time_t now = time(0);
    if ( argc == 1 ) {
        for ( int n = 0; n < OUTER; n++ ) {
            int i = 0;
            while(i < SOME_BIG_CONSTANT) {
                d += i++;
            }
        }
    }
    else {
        for ( int n = 0; n < OUTER; n++ ) {
            int i = 0;
            while(i < SOME_BIG_CONSTANT) {
                d += ++i;
            }
        }
    }
    int t = time(0) - now;  
    printf( "%d\n", t );
    return d % 2;
}

Здесь есть внешние петли, которые позволяют мне управлять временем, чтобы получить что-то подходящее на моей платформе.

Я больше не использую VC ++, поэтому я скомпилировал его (в Windows) с помощью: 

g++ -O3 t.cpp

Затем я запустил его, чередуя: 

a.exe

и 

a.exe 1

Мои результаты были примерно одинаковыми для обоих случаев. Иногда одна версия будет быстрее на 20%, а иногда другая. Я думаю, это связано с другими процессами, запущенными в моей системе.

0 голосов
/ 13 июля 2009

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

class a {
    int index;
    some_ridiculously_big_type big;

    //etc...

};

// prefix ++a
void operator++ (a& _a) {
    ++_a.index
}

// postfix a++
void operator++ (a& _a, int b) {
    _a.index++;
}

// now the program
int main (void) {
    a my_a;

    // prefix:
    // 1. updates my_a.index
    // 2. copies my_a.index to b
    int b = (++my_a).index; 

    // postfix
    // 1. creates a copy of my_a, including the *big* member.
    // 2. updates my_a.index
    // 3. copies index out of the **copy** of my_a that was created in step 1
    int c = (my_a++).index; 
}

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

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

0 голосов
/ 12 июля 2009

Хорошо, все эти префиксы / постфиксы "оптимизация" просто ... какое-то большое недоразумение.

Основная идея, что i ++ возвращает свою оригинальную копию и, следовательно, требует копирования значения.

Это может быть правильным для некоторых неэффективных реализаций итераторов. Однако в 99% случаев даже с итераторами STL нет никакой разницы, потому что компилятор знает, как его оптимизировать, а фактические итераторы - это просто указатели, которые выглядят как класс. И, конечно, нет разницы для примитивных типов, таких как целые числа в указателях.

Так что ... забудь об этом.

РЕДАКТИРОВАТЬ: Очистка

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

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

В качестве небольшого доказательства, возьмите этот код: 

int sum1(vector<int> const &v)
{
    int n;
    for(auto x=v.begin();x!=v.end();x++)
            n+=*x;
    return n;
}

int sum2(vector<int> const &v)
{
    int n;
    for(auto x=v.begin();x!=v.end();++x)
            n+=*x;
    return n;
}

int sum3(set<int> const &v)
{
    int n;
    for(auto x=v.begin();x!=v.end();x++)
            n+=*x;
    return n;
}

int sum4(set<int> const &v)
{
    int n;
    for(auto x=v.begin();x!=v.end();++x)
            n+=*x;
    return n;
}

Скомпилируйте его в сборку и сравните sum1 и sum2, sum3 и sum4 ...

Я просто могу вам сказать ... GCC дает точно такой же код с -02.

0 голосов
/ 12 июля 2009

Попробуйте использовать while или сделайте что-нибудь с возвращаемым значением, например ::

#define SOME_BIG_CONSTANT 1000000000

int _tmain(int argc, _TCHAR* argv[])
{
    int i = 1;
    int d = 0;

    DWORD d1 = GetTickCount();
    while(i < SOME_BIG_CONSTANT + 1)
    {
        d += i++;
    }
    DWORD t1 = GetTickCount() - d1;

    printf("%d", d);
    printf("\ni++ > %d <\n", t1);

    i = 0;
    d = 0;

    d1 = GetTickCount();
    while(i < SOME_BIG_CONSTANT)
    {
        d += ++i;

    }
    t1 = GetTickCount() - d1;

    printf("%d", d);
    printf("\n++i > %d <\n", t1);

    return 0;
}

Скомпилировано с VS 2005 с использованием / O2 или / Ox, опробовано на моем рабочем столе и на ноутбуке.

Стабильно разберитесь на ноутбуке, на десктопе номера немного разные (но скорость примерно одинакова): 

i++ > 8xx < 
++i > 6xx <

хх означает, что числа разные, например 813 против 640 - все еще около 20% ускорения.

И еще один момент - если вы замените «d + =» на «d =», вы увидите хороший прием оптимизации: 

i++ > 935 <
++i > 0 <

Однако это довольно специфично. Но, в конце концов, я не вижу причин менять свое мнение и думаю, что нет никакой разницы:)

...