Построение статической (но сложной) таблицы поиска с использованием шаблонов

В настоящее время я занимаюсь оптимизацией кода численного анализа. В коде есть таблица поиска элементов размером 200x150 (в настоящее время статическая std::vector <std::vector<double>> ), которая создается в начале каждого запуска. На самом деле построение интерполяционной таблицы довольно сложное — значения в интерполяционной таблице строятся с использованием итеративного метода секущих на сложном наборе уравнений. В настоящее время для моделирования построение таблицы поиска занимает 20% времени выполнения (время выполнения составляет порядка 25 секунд, построение таблицы поиска занимает 5 секунд). Хотя 5 секунд могут показаться не такими уж большими, при запуске наших симуляций MC, где мы запускаем более 50 000 симуляций, они внезапно становятся большим отрезком времени.

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

Итак, я предлагаю следующий (значительно упрощенный) сценарий. Допустим, вы хотите сгенерировать статический массив (используйте любой контейнер, который вам больше всего подходит — 2D-массив c, вектор векторов и т. д.) во время компиляции. У вас есть определенная функция-

double  f(int row, int col);

где возвращаемое значение — это запись в таблице, row — строка таблицы поиска, а col — столбец таблицы поиска. Можно ли сгенерировать этот статический массив во время компиляции с использованием шаблонов и как?


c++ optimization templates lookup compilation
person MarkD    schedule 15.01.2011    source источник
comment
Еще один вариант: почему нельзя сгенерировать таблицу один раз во время выполнения, а не на каждой итерации?   -  person Oliver Charlesworth    schedule 15.01.2011
comment
@Oli Charlesworth. Если под итерацией вы подразумеваете каждую итерацию одной симуляции, она генерируется только один раз для каждого сима. Если по одному разу для каждой симуляции, то это на столе, но требует некоторых довольно существенных изменений в структуре кода с точки зрения того, как код распараллелен (изменения, которые должны и будут сделаны, но я искал быстрое изменение, которое могло бы сделать за это время). В настоящее время каждое моделирование — это новый процесс на узлах. Цель состоит в том, чтобы реализовать более нативную параллелизацию OpenMPI.   -  person MarkD    schedule 15.01.2011

Ответы (5)


arrow_upward
4
arrow_downward

Обычно лучшим решением является генерация кода. Там у вас есть полная свобода, и вы можете быть уверены, что вывод на самом деле double[][].

person ruslik    schedule 15.01.2011
comment
+1: Согласен. Хотя это требует отдельного шага в процессе сборки, сделать это таким образом будет намного чище, чем пытаться заставить шаблоны делать то, что вы хотите. - person Oliver Charlesworth; 15.01.2011
comment
Этот метод также позволит вам повторно использовать ваш существующий код для создания таблицы и сохранить ее в удобной для вас форме (вы говорите, что она постоянно корректируется, так что это важное соображение). - person zwol; 15.01.2011
comment
Я пошел по этому пути, и он прекрасно сработал. Таблицы уже обновлялись несколько раз в ходе разработки, и с нашими make-файлами это происходит без проблем. Спасибо за предложение (и извините, что так долго не принимал ответ!). - person MarkD; 09.02.2011

arrow_upward
1
arrow_downward

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

Включите в файл строку версии, чтобы она создавалась заново при изменении кода.

person Pete Kirkham    schedule 15.01.2011
comment
Я ставлю на Disk IO, и все это в конечном итоге будет медленнее, но, возможно, это будет более быстрое решение .... особенно если вы использовали что-то очень быстрое, например флэш-накопитель. - person Edward Strange; 15.01.2011
comment
Двойники @Noah 200x150 составляют 1/4 МБ, а создание таблицы на лету занимает пять секунд. Если для загрузки файла размером 1/4 мегабайта на обычный диск требуется пять секунд, значит, с ним что-то не так. - person Pete Kirkham; 18.01.2011

arrow_upward
1
arrow_downward

Несколько вещей здесь.

  1. То, что вы хотите сделать, почти наверняка возможно хотя бы частично.

  2. Значения с плавающей запятой являются недопустимыми аргументами шаблона (просто так, не спрашивайте почему). Хотя вы можете представлять рациональные числа в шаблонах, используя представление N1/N2, количество математических операций, которые вы можете выполнить с ними, не охватывает весь набор, который можно выполнить с рациональными числами. Например, root(n) недоступен (см. root(2)). Если вам не нужны баджиллионы экземпляров статических двойных переменных, вам нужно, чтобы ваш метод доступа value был функцией. (может быть, вы можете придумать новое представление шаблона с плавающей запятой, которое разделяет exp и mant, и тогда вы так же хорошо, как и с двойным типом ... получайте удовольствие: P)

  3. Код метапрограммирования трудно отформатировать в удобочитаемом виде. Кроме того, по самой своей природе его довольно сложно читать. Даже эксперту будет нелегко проанализировать фрагмент кода TMP, который он не написал, даже если он довольно прост.

  4. Если стажер или кто-либо младше старшего уровня даже ДУМАЕТ о том, чтобы просто взглянуть на код TMP, у него взорвется голова. Хотя иногда старшие разработчики взрываются громче, потому что они сходят с ума из-за новых вещей (заставить вашего босса чувствовать себя некомпетентным может иметь серьезные последствия, хотя этого не должно быть).

Все это говорит о том, что шаблоны — это язык, полный по Тьюрингу. Вы можете делать с ними "что угодно"... и под чем угодно мы подразумеваем все, что не требует какой-либо внешней возможности, такой как доступ к системе (потому что вы просто не можете заставить компилятор создавать новые потоки, например). Вы можете построить свой стол. Вопрос, на который вам нужно будет ответить, заключается в том, хотите ли вы этого на самом деле.

person Edward Strange    schedule 15.01.2011

arrow_upward
0
arrow_downward

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

person Benjamin Lindley    schedule 15.01.2011

arrow_upward
0
arrow_downward

Если бы ваша таблица состояла из множества целых чисел, то да, вы могли бы. Может быть. Но чего вы, конечно, не можете сделать, так это генерировать двойники во время компиляции.

Что еще более важно, я думаю, что простой двойной [][] был бы лучше, чем вектор векторов здесь - вы выдвигаете МНОГО динамического распределения для таблицы статического размера.

person Puppy    schedule 15.01.2011