почему быстрее изменить размер указателя на вектор * (в массиве вектор *), чем вектор (в массиве вектор)? - PullRequest
Новая
       10

почему быстрее изменить размер указателя на вектор * (в массиве вектор *), чем вектор (в массиве вектор)?

1 голос
/ 15 апреля 2020

изменение размера вектора может быть медленным? В поисках решений для повышения скорости моего программного обеспечения я попытался изменить размеры векторов в массиве vector, а vector * в массиве vector * Второе кажется быстрее. Даже если я чувствую причину, у меня нет ясного чистого рационального объяснения (я не хочу использовать резерв для векторов в массиве, поскольку реальные огромны).

Вот моя тестовая программа (результаты могут отличаться на другом Lenovo ThinkCenter i5 с Debian 8: выполняется другая задача, которую я не хочу останавливать): 

int main (int argc, char* argv []) {
  const int n = 10;
  const int s2 (10000);
  {
    std::vector<int> tab [n];
    clock_t begt, endt;
    begt = clock ();
    {
      std::vector<int>* pv ((std::vector<int>*) tab);
      for (int i (0); i < n; ++i, ++pv) {
        pv->resize (s2);
      }
    }
    endt = clock ();
    std::cout << "vector resize duration == " << (unsigned int) (endt - begt) <<  " ticks" << std::endl;
  }

  {
    std::vector<int> *tab [n];
    for (int i (0); i != n; ++i) {
      tab [i] = new std::vector<int> ();
    }
    clock_t begt, endt;
    begt = clock ();
    {
      std::vector<int>** pv ((std::vector<int>**) tab);
      for (int i (0); i < n; ++i, ++pv) {
        (*pv)->resize (s2);
      }
    }
    for (int i (0); i != n; ++i) {
      delete tab [i];
    }
    endt = clock ();
    std::cout << "*vector resize duration== " << (unsigned int) (endt - begt) <<  " ticks" << std::endl;
  }
  return 0;
}

и типичные результаты: 

vector resize duration == 114 ticks
*vector resize duration== 78 ticks

1 Ответ

3 голосов
/ 15 апреля 2020

Мне стало любопытно по поводу заявленных наблюдений, и я смог их воспроизвести сам. Затем я поменял две альтернативные реализации, и теперь таблицы были перевернуты. Версия std::vector<int> *tab [n], которая теперь выполняется первой, теперь была значительно медленнее, чем другая, которая теперь выполняется второй.

Объяснение очень простое. Библиотека C ++ повторно использует выделенную память. Когда вы используете память самостоятельно, через new или косвенно, выделяя память для значений в контейнерах, а затем освобождаете ее, библиотека C ++ не освобождает освобожденную память обратно операционной системе, а использует ее повторно. в следующий раз ему понадобится больше памяти без необходимости запрашивать у операционной системы больше. Нет закона, который говорит, что это то, что должна делать библиотека C ++, но это типичное поведение современных реализаций C ++.

Итак, что это, очень просто. Ваш первый тест включает в себя время, необходимое для выделения части памяти из операционной системы. С ++ требовалась память для этих векторов, и это заняло дополнительное время. Ваш второй раздел кода не должен был это делать, потому что эта память уже была выделена, а затем освобождена первым тестом; поэтому второй тест просто привел к тому, что ваша библиотека C ++ повторно использовала уже имеющуюся память, но не использовалась (это было видно по трассировке системного вызова).

Типичные результаты от простого повторения первого теста во второй раз: 

vector resize duration == 191 ticks
vector resize duration == 48 ticks
*vector resize duration== 63 ticks
...