Необходимо ускорить код на C ++, включающий многоиндексный Boost и поиск в unordered_multimap - PullRequest
Новая
       41

Необходимо ускорить код на C ++, включающий многоиндексный Boost и поиск в unordered_multimap

3 голосов
/ 26 января 2011

Я ищу стратегии для ускорения агентной модели, основанной на объектах класса Host, указатели на которые хранятся в многоиндексном контейнере Boost.Я использовал Shark, чтобы определить, что подавляющее большинство времени занимает функция calcSI():

enter image description here

Функция calcSI() должна вычисляться для каждого экземпляра классаHost определенные вероятности, которые зависят от атрибутов других экземпляров класса Host.(Примерно 10 000–50 000 экземпляров Host, и эти вычисления выполняются для каждого хоста приблизительно 25 600 раз.)

Если я правильно интерпретирую профиль, большую часть времени я потратил на calcSI() переходит к Host::isInfectedZ(int), который просто считает экземпляры чего-либо в Boost unordered_multimap типа InfectionMap: 

<code>struct Infection {
public:
  explicit Infection( double it, double rt ) : infT( it ), recT( rt ) {}
  double infT;
  double recT;
};
typedef boost::unordered_multimap< int, Infection > InfectionMap;

Все члены Host содержат InfectionMap carriage, а Host::isInfectedZ(int) просто подсчитывает число Infections, связанное с определенной клавишей int: 

<code>int Host::isInfectedZ( int z ) const {
  return carriage.count( z );
}

  1. Явозникли проблемы с поиском информации о том, насколько дорогой является функция count для неупорядоченных мультикарт в Boost.Стоит ли увеличивать накладные расходы, добавляя к Host отдельный двумерный массив для отслеживания количества экземпляров каждого ключа (т. Е. Числа Infections, связанного с каждым int)?

  2. Мне интересно, был бы более полезным структурный пересмотр мультииндекса Boost, такой как устранение одного или двух менее необходимых составных ключевых индексов.Фоновое обслуживание мультииндекса не отображается в профилировщике, что (возможно, глупо) заставляет меня беспокоиться, что оно может быть большим.У меня есть 8 индексов в мультииндексе, большинство из которых - order_non_unique.

  3. Есть ли еще какие-то вопросы, которые могут меня беспокоить, которые могут не отображаться в профилировщике, или я пропускаюосновной результат от профилировщика?

Распараллеливание и многопоточность calcSI(), к сожалению, не подходят.

Обновление: Может быть полезно знатьчто InfectionMap carriage редко имеет более 10 пар и обычно <5. </p>

Обновление 2: Я попробовал стратегию, предложенную в № 1 выше, давая каждому Hostмассив int carriageSummary[ INIT_NUM_STYPES ], который индексируется возможными значениями z (для большинства симуляций существует <10 возможных значений).Значение каждой записи отслеживает изменения, сделанные до <code>carriage.Функция Host::isInfectedZ( int z ) теперь читает: 

<code>int Host::isInfectedZ( int z ) const {
  //return carriage.count( z );
  return carriageSummary[ z ];
}
И время, выделенное для этой функции , кажется значительно уменьшилось - я не могу сейчас сделать точное сравнение: enter image description here Очевидно, что использование массива довольно громоздко, но хорошо для небольших диапазонов z.Может ли какой-нибудь другой контейнер (т.е. не unordered_map) быть более эффективным для больших диапазонов?

Хотелось бы также получить какие-либо отзывы об изменении мультииндекса.

1 Ответ

1 голос
/ 26 января 2011

Как вы предложили в # 1, попробуйте сохранить массив количества кареток рядом с Host :: carriage unordered_multimap и держите их обоих "синхронизированными".Тогда ваш Host :: isInfectedZ будет использовать (надеюсь) массив с более быстрым счетом каретки: 

int Host::isInfectedZ( int z ) const {
  return carriageCount[ z ];
}

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

Вы можете использовать std :: map или boost :: unordered для ассоциативного массива.Для поисков первый имеет логарифмическую временную сложность, а второй имеет постоянную временную сложность.Но поскольку этот ассоциативный массив обычно очень мал, std :: map может быть быстрее.std :: map также может занимать меньше места.Попробуйте оба и запустите ваш профилировщик, чтобы увидеть.Моя ставка на std :: map.: -)

РЕДАКТИРОВАТЬ:

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

EDIT2:

Возможно, вы захотите удалить 

typedef boost::unordered_multimap< int, Infection > InfectionMap;

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

ОТВЕТ НА ОБНОВЛЕНИЕ № 2:

Рад видеть, что вы сделали улучшение.Я сомневаюсь, что вы найдете контейнер, который "менее громоздкий", чем фиксированный массив, скажем, 16 целых чисел.Контейнеры STL и Boost выделяют память порциями и в конечном итоге будут такими же большими, как ваш массив фиксированного размера, даже если в них мало элементов.

Возможно, вас заинтересует boost :: array, который упаковывает STL-подобные элементы.интерфейс вокруг фиксированного массива в стиле C.Это облегчит «замену» вашего массива фиксированного размера на std :: vector или std :: map.

...