Локальность кэша при одновременной итерации двух контейнеров - PullRequest
Новая
       15

Локальность кэша при одновременной итерации двух контейнеров

0 голосов
/ 31 октября 2018

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

int main()
{
    const std::size_t BIG_SIZE = 2000000;  // A number such that both ivec and fvec won't fit the cache

    std::vector<int> ivec(BIG_SIZE, 0);
    int start = 0;
    for (auto& i : ivec)
        i = start++;


    std::vector<float> fvec(BIG_SIZE, 0.f);


    auto iit = ivec.cbegin();
    auto fit = fvec.begin();
    for (; iit != ivec.cend() && fit != fvec.end(); ++iit, ++fit) 
        *fit = *iit * 3.14;  // What happens here?
}

В последнем цикле будет ли кэш загружать как блоки памяти около *iit, так и около *fit, или я буду пропускать кэш каждый раз, когда получаю доступ к *iit, а затем *fit?

Если в последнем случае я должен произвольно назначать ivec и fvec с чередованием для предотвращения этих пропусков?

1 Ответ

0 голосов
/ 31 октября 2018

Самый простой способ узнать, что быстрее - это сравнительный анализ. Ответ будет зависеть от: аппаратного обеспечения, размера ввода и других вещей (компилятор, флаги и т. Д.). Однако для целей этого примера я буду использовать сайт quick-bench.com с clang-6.0, C + +17, -O3 и libstdc ++. Вот код для сравнения: 

static void One(benchmark::State& state) {
  for (auto _ : state) {
    const std::size_t BIG_SIZE = 20000000;

    std::vector<int> ivec(BIG_SIZE, 0);
    benchmark::DoNotOptimize(ivec);
    int start = 0;
    for (auto& i : ivec)
        i = start++;

    std::vector<float> fvec(BIG_SIZE, 0.f);
    benchmark::DoNotOptimize(fvec);

    auto iit = ivec.cbegin();
    auto fit = fvec.begin();
    for (; iit != ivec.cend() && fit != fvec.end(); ++iit, ++fit) 
        *fit = *iit * 3.14;
  }
}
BENCHMARK(One);

static void Two(benchmark::State& state) {
  for (auto _ : state) {
    const std::size_t BIG_SIZE = 20000000;

    std::vector<int> ivec(BIG_SIZE, 0);
    std::vector<float> fvec(BIG_SIZE, 0.f);
    benchmark::DoNotOptimize(ivec);
    benchmark::DoNotOptimize(fvec);
    int start = 0;
    auto fit = fvec.begin();
    for (auto& i : ivec) {
        i = start++;
        *fit = i * 3.14;
        ++fit;
    }
  }
}
BENCHMARK(Two);

Первая функция - ваш исходный код, а вторая - модифицированная версия. benchmark::DoNotOptimize просто предотвращает оптимизацию двух векторов. Результаты для N 2000:

enter image description here

Результаты для N 20000000:

enter image description here

Как видите, для большого N страдает второй пример. Вам нужно будет тщательно разрабатывать свой код и проводить тесты, а не делать предположения (тест для Google - базовая технология для quick-bench.com)

<ч />

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

static void Three(benchmark::State& state) {
  for (auto _ : state) {
    const std::size_t BIG_SIZE = 20000000;

    std::vector<int> ivec(BIG_SIZE, 0);
    std::vector<float> fvec(BIG_SIZE, 0.f);
    benchmark::DoNotOptimize(ivec);
    benchmark::DoNotOptimize(fvec);
    int start = 0;
    auto fit = fvec.begin();
    std::iota(ivec.begin(), ivec.end(), 0);
    std::transform(ivec.begin(), ivec.end(), 
      fvec.begin(),
      [] (const auto a) {
        return a * 3.14;
      });
  }
}
BENCHMARK(Three);

Мы заменили ваш свернутый вручную цикл на std::iota и std::transform. Результаты для большого N:

enter image description here

Как вы можете видеть, версия 3 быстрее (хотя и незначительно), чем # 1 и # 2. Поэтому сначала используйте стандартные библиотечные функции, и сверните их только вручную, если они слишком медленные.

...