|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Cvetkov 2:5030/1334 25 Jul 2003 11:59:13
To : Victor Petrenko
Subject : Поиск долго выполняющихся фрагментов на этапе компиляции
--------------------------------------------------------------------------------
23 Июл 03 03:15, Victor Petrenko писал(ла) Alex Cvetkov:
VP>>> есть что-нибудь почитать по этому поводу? (URL, бумажные книги,
VP>>> пусть и старые).
AC>> начать искать можно с cfg (Control Flow Grapf).
AC>> но это только для общего образования. на практике такое зделать
AC>> можно только если этот cfg не зависит от данных или его
AC>> зависимость легко описываеться формально (например она cfg
AC>> зависит тоько от размеров входных массивов, но не от их
AC>> содержимого)
VP> В каком смысле "не зависит от содержимого входных массивов"? Т.е. в
VP> случае, когда мы можем получить эту информацию явно на этапе
VP> компиляции (ведь речь идет о статически размещаемых массивах)?
размещение массивов, насколько я понимаю, значения не имеет.
например алгоритм получения суммы элементов массива не зависит от содержимого
ячеек (если отбросить всякие проверки на переполнение) потомучто для двух любых
массивов одинакового размера будет произведена одинаковая последовательность
действий.
а вот быстрая сортировка таким свойством не обладает, потомучто в зависимости от
значения элемента массива мы пойдем по разным ветвям цыкла.
AC>> на практке такие алгоритмы встречаються не часто.
VP> Вот в этом-то и проблема :). Я вот сейчас думаю, а возможно ли
VP> сделать
VP> относительную оценку. Вот, например, в программе два цикла for.
VP> Hачинаются они оба, пусть, с константы. А вот заканчиваются, первый -
VP> f(X), второй - g(X). Если f и g зависят от одного и того же набора
VP> переменных, то возможно их сравнить. Интересно было бы еще как-то
VP> узнать, насколько часто такое может встретиться на практике.
если эти переменные не меняються внутри цыклов то вполне. но внутри циклов
недолжнобыть другиз операторов ветвления (или они тоже должны зависить только от
переменных не меняющихся внутри интересующего нас блока)
AC>> из бумажной литературы можно посмотреть в "паралельные
AC>> вычисления" в.в.воеводин, вл.в.воеводин бхв-петербург 2002г но
AC>> тоже только для общего образования.
VP> Угу, спасибо. Я слышал об этой книге, но пока не смог достать...
там по всей книге напиханы ссылки на http://parallel.ru
AC>> ps: а чем тебе профайлер не угодил?
VP> Тем, что для этого требуется выполнить программу, насколько я понимаю.
VP> В моем случае важно установить это на этапе компиляции (для
VP> автоматической оптимизации - хочется знать какие участки программы
VP> наиболее важно оптимизировать).
если оптимизация автоматическая то почему не оптимизировать все?
если из-за скорости компиляции, то поиск критических участков врятли будет много
бустрее самой оптимизации. а если оптимизация действительно медленная (ну
например полным перебором всех вариантов), то она займет столько времени что
время на профайлинг будет незначительным.
Alex Cvetkov
--- Клиент морга
* Origin: Life suxx (2:5030/1334)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
