Векторная скорость доступа, какой метод быстрее?

Question

Мне любопытно, какой метод быстрее при доступе к векторам.

Для простоты, скажем, у меня есть два объекта: Player и Ship.

Существует вектор указателей игроков vector<Player*> players, и каждый объект игрока содержит вектор указателей корабля vector<Ship*> ships, а затем каждый корабль имеет несколько функций, которые он может вызвать, и так далее.

В этих ситуациях быстрее ли получить доступ к этим функциям? Или создать временный указатель объекта для доступа ко всему?

Это быстрее, чтобы сделать это:

for (int i = 0; i < players.size(); i++) 
{ 
    for (int j = 0; j < players.at(i)->ships.size(); j++) 
    { 
     players.at(i)->ships.at(j)->update(); 
     if (
       (players.at(i)->ships.at(j)->get_x() > 0) && 
       (players.at(i)->ships.at(j)->get_x() < screen_x) && 
       (players.at(i)->ships.at(j)->get_y() > 0) && 
       (players.at(i)->ships.at(j)->get_y() < screen_y) 
      ) 
     { 
      players.at(i)->visible.push_back(j); 
     } 
    } 
} 

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

for (int i = 0; i < players.size(); i++) 
{ 
    Player* play = players.at(i); 
    for (int j = 0; j < play->ships.size(); j++) 
    { 
     Ship* ship = play->ships.at(j); 
     ship->update(); 

     int ship_x = ship->get_x(); 
     int ship_y = ship->get_y(); 
     if (
       (ship_x > 0) && 
       (ship_x < screen_x) && 
       (ship_y > 0) && 
       (ship_y < screen_y) 
      ) 
     { 
      play->visible.push_back(j); 
     } 
    } 
} 

Я знаю, что второй визуально опережает, но на самом деле не знает, обязательно ли это быстрее.

Мысли?

Answer 1

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

Это может быть первый или может быть второй. Это определенно будет первым, если координата X большинства кораблей будет отрицательной.

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

Answer 2

Я думаю, что вы на милость своего оптимизирующего компилятора здесь. Любой может быть быстрее, в зависимости от того, как он оптимизируется.

• В первой версии, вполне возможно, что компилятор решит вытащить players.at(i)->ships.at(j) общего подвыражения, возможно с get_x() или get_y() превращая его в нечто , который выглядит очень похожа на вашу вторую версию.

• Во втором варианте, вполне возможно, что переупорядочивания может переместить int ship_y = ship->get_y() в петлю условного так, что она может короткое замыкание с ship_y > 0.

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

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

Answer 3

Спасибо за информацию всем. Поскольку не было четкого разреза «вариант A определенно быстрее, чем вариант B», я принял ваш совет и выполнил стендовый тест.

Вот код, который я собрал.

В принципе, он создает 100 игроков. У каждого игрока есть вектор из 100 кораблей. На каждом корабле есть вектор из 100 человек. (Как только он побежал, он потреблял около 500 МБ ОЗУ).

я запустил тест как неоптимизированная и оптимизированы (флаг -O3)

Тест 1 был цепь указателей (т.е..> Корабельного> crew-> номер player- и т.д.) Тест 2 был то же, что и для теста 1, но я заменил все .at() на оператор []. Тест 3 использовал временные указатели для доступа ко всему.

Я проверил каждый тест несколько раз и усреднил результаты. Вот мои результаты:

неоптимизированному:

Test 1: 13000 
Test 2: 5500 
Test 3: 2800 

Оптимизированный:

Test 1: 1050 
Test 2: 650 
Test 3: 450 

Это показывает, что оптимизация значительно увеличена скорость во всех случаях. В любом случае, оптимизированный или неоптимизированный, .at() определенно замедляет движение вещей. Использование оператора [] было значительно быстрее. Но в конце концов, использование временного указателя было самым быстрым во всех случаях.

#include <vector> 
#include <ctime> 
#include <iostream> 

using namespace std; 

class People 
{ 
    public: 
     vector<int> number; 
}; 

class Ship 
{ 
    public: 
     Ship(int f); 
     vector<People*> crew; 
     int get_x(); 
     int get_y(); 

    private: 
     int x; 
     int y; 
}; 

Ship::Ship(int f) 
{ 
    //Assign some nonsense for testing purposes 
    x = f * 50; 
    y = f * 75; 
} 

int Ship::get_x() 
{ 
    return x; 
} 

int Ship::get_y() 
{ 
    return y; 
} 

class Player 
{ 
    public: 
    vector<Ship*> ships; 
}; 

int main(int argc, char *argv[]) 
{ 
    vector<Player*> players; 

    int start, end; 
    unsigned int i, j, k, l; 

    //Create 100 players, each with 100 ships, and each ship with 100 crew. 
    for (i = 0; i < 100; i++) 
    { 
     Player* play = new Player; 
     players.push_back(play); 
     for (j = 0; j < 100; j++) 
     { 
      Ship* new_ship = new Ship(j); 
      play->ships.push_back(new_ship); 
      for (k = 0; k < 100; k++) 
      { 
       People* newbie = new People; 
       new_ship->crew.push_back(newbie); 
       for (l = 0; l < 100; l++) 
       { 
        newbie->number.push_back(0); 
       } 
       newbie->number.clear(); 
      } 
     } 
    }  


    //Test 1 


    start = clock(); 

    for (i = 0; i < players.size(); i++) 
    { 
     for (j = 0; j < players.at(i)->ships.size(); j++) 
     { 
      for (k = 0; k < players.at(i)->ships.at(j)->crew.size(); k++) 
      { 
       for (l = 0; l < 100; l++) 
       { 
        //Give each crew some number to hold on to. 
        players.at(i)->ships.at(j)->crew.at(k)->number.push_back(players.at(i)->ships.at(j)->get_x() * players.at(i)->ships.at(j)->get_y() + l); 
       } 
       //Clear the number list for the next test. 
       players.at(i)->ships.at(j)->crew.at(k)->number.clear(); 
      } 
     } 
    } 
    end = clock(); 

    cout << "Test 1: " << (end - start) << endl; 


    //Test 2 

    start = clock(); 

    for (i = 0; i < players.size(); i++) 
    { 
     for (j = 0; j < players[i]->ships.size(); j++) 
     { 
      for (k = 0; k < players[i]->ships[j]->crew.size(); k++) 
      { 
       for (l = 0; l < 100; l++) 
       { 
        players[i]->ships[j]->crew[k]->number.push_back(players[i]->ships[j]->get_x() * players[i]->ships[j]->get_y() + l); 
       } 
       players[i]->ships[j]->crew[k]->number.clear(); 
      } 
     } 
    } 
    end = clock(); 

    cout << "Test 2: " << (end - start) << endl; 


    //Test 3 


    start = clock(); 

    for (i = 0; i < players.size(); i++) 
    { 
     Player* temp_play = players.at(i); 
     for (j = 0; j < temp_play->ships.size(); j++) 
     { 
      Ship* temp_ship = temp_play->ships.at(j); 
      for (k = 0; k < temp_ship->crew.size(); k++) 
      { 
       People* temp_crew = temp_ship->crew.at(k); 
       for (l = 0; l < 100; l++) 
       { 
        temp_crew->number.push_back(temp_ship->get_x() * temp_ship->get_y() + l); 
       } 
       temp_crew->number.clear(); 
      } 
     } 
    } 
    end = clock(); 

    cout << "Test 3: " << (end - start) << endl; 

    return 0; 
} 

Answer 4

Мне кажется, что упор на скорость неуместен. Я думаю, вы должны начать писать код более удобочитаемым:

auto is_visible = [=](Ship const &s) { return s.get_x() > 0 && s.get_x() < screen_x 
              && s.get_y() > 0 && s.get_y() < screen_y; 
            }; 

for (auto & player : players) 
    std::copy_if(ships.begin(), ships.end(), 
       std::back_inserter(player.visible), 
       is_visible); 

По крайней мере, ИМО, это, по крайней мере, столь же безопасна, как с помощью at для индексации, но, вероятно, по крайней мере, столь же быстро, как и с помощью [] и более удобным для чтения чем один.

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

std::vector<Ship> visible; 

std::copy_if(ships.begin(), ships.end(), 
      std::back_inserter(visible), 
      [=](Ship const &s) { return s.get_x() > 0 && s.get_x() < screen_x 
             && s.get_y() > 0 && s.get_y() < screen_y; }); 

for (auto &player : players) 
    player.visible = visible;