AtariSMN82
@AtariSMN82
Разработчик игр

C++: Как ускорить этот многопоточный код?

Суть кода - для каждого объекта формируется список соседних, надо создать список пар с этим объектом и найденными соседями, потом это всё объединить в общий список пар. Функция поиска соседей очень медленная и я захотел вызывать её многопоточно, но итоговый список всего один и я не знаю как сделать в него быструю и безопасную вставку.
Код упрощённо:
// collision_pairs - unordered_map<Entity*, Entity*>
// entitys - std::vector<Entity*>

/* найти ближайших соседей и создать
списки пар для проверки пересечений хитбоксов */
#pragma omp parallel for \
  schedule(dynamic) \
  shared(root, collision_pairs)
for (auto entity: entitys) {
  ...
  Vector<Entity*> list
  /* очень тяжёлая функция, которая работает разное
  количество времени и вернёт список соседних объектов в list*/
  root->find(area, list)

  // добавить этих соседей в пары на проверки
  for (auto other: list) {
    auto addr_a = entity
    auto addr_b = other
    // сами себя не проверяем
    continue_if (addr_a == addr_b)
    // эта перестановка сократит число одинаковых пар
    if (addr_b > addr_a)
      std::swap(addr_a, addr_b)
        
    #pragma omp critical(dataupdate)
    collision_pairs.emplace( {addr_a, addr_b} )
  }
}

Было бы лучше создать для каждого потока свою локальную копию collision_pairs, а потом объединить её с релизной, но не думаю что в omp есть такая прагма ( shared(collision_pairs) здесь не помогает, нужна синхронизация, а private(collision_pairs) создаст локальные копии, но они в конце не объединятся).
  • Вопрос задан
  • 123 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
А вы не добавляйте все в один список сразу. Пусть каждый поток использует свой список. Наверно, стоит заветси массив списков и использовать номер потока как индекс в массиве - в тот список ответ и добавляйте.

В самом конце можно списки объединить. Последовательно. Или с критической секцией. Каждый поток должен получить первый и последний элемент списка. За две операции добавить список к глобальному и изменить последний элемент в глобальном списке. Ну, это если std::list использовать.

Вообще, если один раз в конце собирать все ответы, то можно их и в vector в критической секции складывать. Это все займет не больше времени, чем один раз ответ вывести.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы