Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 153, средняя оценка - 4.83
Evg
Эксперт CАвтор FAQ
17543 / 5781 / 370
Регистрация: 30.03.2009
Сообщений: 15,921
Записей в блоге: 26
#1

Что такое compile-time алгоритмы и для чего они нужны? - C++

28.12.2011, 14:54. Просмотров 18699. Ответов 45
Метки нет (Все метки)

Цитата Сообщение от niXman Посмотреть сообщение
compile-time алгоритмы
А есть от них хоть какая-то практическая польза? По-моему нет
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Evg
Эксперт CАвтор FAQ
17543 / 5781 / 370
Регистрация: 30.03.2009
Сообщений: 15,921
Записей в блоге: 26
28.12.2011, 17:45  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #31
Цитата Сообщение от niXman Посмотреть сообщение
и что из этого? сложная/непонятная реализация?
Ты считаешь это поводом к тому, что нужно усложнять понимание и без того плохо понимаемого исходника, чтобы ускорить программу на 6 сотых секунды?
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.12.2011, 21:32     Что такое compile-time алгоритмы и для чего они нужны? #32
Evg, скажи, ты случаем не знаешь где раздобыть стандарт и реализации математических функции? а то я даже не знаю как оно зовется, по этому наверняка и ничего найти не могу..
Evg
Эксперт CАвтор FAQ
17543 / 5781 / 370
Регистрация: 30.03.2009
Сообщений: 15,921
Записей в блоге: 26
28.12.2011, 23:01  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #33
Реализации можно посмотреть в glibc. Стандарт - скорее всего оно около ieee-754 где-то, но если завтра напомнишь - уточню.

Не по теме:

Спорить мы начали по теме "compile-time алгоритмы", а не "mpl-алгоритмы", как оно сейчас озаглавлено

niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.12.2011, 23:38     Что такое compile-time алгоритмы и для чего они нужны? #34
Сообщение было отмечено автором темы, экспертом или модератором как ответ
кстати, вот и компайл-тайм реализация sqrt() без единого шаблона
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <cmath>
 
constexpr double my_sqrt_impl(double lower, double upper, double v, bool d) {
   return
   upper-lower>0.0000000000001
      ? ((lower+upper)/2)*((lower+upper)/2)>v
         ? my_sqrt_impl(lower, (lower+upper)/2, v, d)
         : my_sqrt_impl((lower+upper)/2, upper, v, d)
      : d?lower:upper
   ;
}
 
constexpr double my_sqrt(double v) {
   return (my_sqrt_impl(v<1?v:1, v<1?1:v, v, true)+my_sqrt_impl(v<1?v:1, v<1?1:v, v, false))/2;
}
 
int main() {
   constexpr double v = 1.00006;
 
   std::cout << "standard implementation: " << sqrt(v) << std::endl;
   std::cout << "my own   implementation: " << my_sqrt(v) << std::endl;
 
   char array[int(my_sqrt(v))]; // check if my_sqrt(v) is constant expression
   std::cout << sizeof(array) << std::endl;
}
http://liveworkspace.org/code/1949cd...135dc93086cf4d

Evg, стандартной соответствует? выполняется в компайл-тайм?
Evg
Эксперт CАвтор FAQ
17543 / 5781 / 370
Регистрация: 30.03.2009
Сообщений: 15,921
Записей в блоге: 26
29.12.2011, 11:37  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #35
Та же самая беда. Воткни в начало main "std::cout.precision(40);" и увидишь, что результат отличается от стандартного. А для отрицательного значения считает неправильно (стандартная реализация возвращает nan)
Evg
Эксперт CАвтор FAQ
17543 / 5781 / 370
Регистрация: 30.03.2009
Сообщений: 15,921
Записей в блоге: 26
29.12.2011, 11:37  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #36
Цитата Сообщение от niXman Посмотреть сообщение
Evg, стандартной соответствует?
В соседней теме отписал те же самые два косяка. Плюс то же самое очевидное отсутсвие практической пользы
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
29.12.2011, 11:48     Что такое compile-time алгоритмы и для чего они нужны? #37
Цитата Сообщение от Evg Посмотреть сообщение
результат отличается от стандартного
для подавляющего большинства задач это не имеет никакого значения. (я и вправду не проверял до такой точности)

Цитата Сообщение от Evg Посмотреть сообщение
для отрицательного значения считает неправильно
это уже придирки. добавь проверку и возвращай nan.
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
29.12.2011, 11:48     Что такое compile-time алгоритмы и для чего они нужны? #38
Цитата Сообщение от Evg Посмотреть сообщение
отсутсвие практической пользы
предыдущие четыре страницы мы не с тобой общались?
Evg
Эксперт CАвтор FAQ
17543 / 5781 / 370
Регистрация: 30.03.2009
Сообщений: 15,921
Записей в блоге: 26
29.12.2011, 11:59  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #39
Цитата Сообщение от niXman Посмотреть сообщение
предыдущие четыре страницы мы не с тобой общались?
ТОгда приведи пример, где вычисление корня от константы на этапе компиляции даст какое-то реальное преимущество. Не выигрыш в одну сотую секунду, а реально ощутимый выигрыш в производительности, который бы реально оправдал те геморозатраты, которые на это потребуются
Evg
Эксперт CАвтор FAQ
17543 / 5781 / 370
Регистрация: 30.03.2009
Сообщений: 15,921
Записей в блоге: 26
29.12.2011, 12:03  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #40
Цитата Сообщение от niXman Посмотреть сообщение
для подавляющего большинства задач это не имеет никакого значения
Для этого же подавляющего значение точно так не имеет никакого значения, что будет что-то вычисляться в compile-time вместо run-time.

Цитата Сообщение от niXman Посмотреть сообщение
это уже придирки. добавь проверку и возвращай nan
Нет, это не придирки. Это кроткий пример, вкотором изначально известно, где была допущена ошибка. В общем случае это может вылиться в кучу потерянного времени. И ладно это более простая реализация из-за того, что поддерживается конструкция constexpr. Однако весь мир (особенно крупные компании) не так спешит за прогрессом и переходом но новые версии компилятора, новые стандарты и т.п. В итоге я опять не вижу никакого оправдания разведению геморроя на ровном месте

Перенеси последние посты в соседнюю тему, потому что опять всё свелось к тому же самому
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
29.12.2011, 12:23     Что такое compile-time алгоритмы и для чего они нужны? #41
для хеловорда такие времязатраты никак не оправдаются.
но если пишется реальный проект у которого есть требования к производительности, и в проекте компайл-тайм вычесления будут использоваться везде где возможно(мой пример с mpl.map) - тогда смысл появляется.

Добавлено через 14 минут
вот еще простые примеры основанные на свойствах типов: http://www.boost.org/doc/libs/1_48_0.../examples.html


Evg, использовать только одну какую-то возможность предоставляемую шаблонами и только в одном случае - ничего не изменит.
использование шаблонов и алгоритмов времени компиляции - это стиль разработки. и только комплексное применение этих возможностей дает смысл в разных пониманиях.
Evg
Эксперт CАвтор FAQ
17543 / 5781 / 370
Регистрация: 30.03.2009
Сообщений: 15,921
Записей в блоге: 26
29.12.2011, 12:59  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #42
Цитата Сообщение от niXman Посмотреть сообщение
но если пишется реальный проект у которого есть требования к производительности
Я уже говорил об этом. В своём случае ты почему-то меряешь ускорение в процентах, в то время как надо считать его в секундах (а точнее - вдолях секунды). Потому что код, который делает статическую инициализацию, например, квадратного корня через шаблонный механизм или через вызов функции, выполняется за время программы ОДИН раз. Поэтому в данном случае правомочны только сравнения абсолютного вренеми, а не относительного. При этом на двух чашах весов оказываются небольшое ускорение с одной стороны и разведение геморроя в исходниках с другой стороны.

Ну и дополнительно могу сказать, что данный механизм будет давать профит только в том случае, когда работа идёт над константами, что опять-таки случается не так уж и часто.

Все ваши примеры сводились к ссылкам на какие-то документации в boost'е, которые не особенно и интересны. Вот если бы кто-то хотя бы схематично нарисовал код по РЕАЛЬНОМУ использованию этого добра - тогда хотя бы был предмет для обсуждений. На предмет того, что ты приводил пример со словесным описанием того, что ты по строковым представлениями имён функций вычислял какие-то хэш-суммы. Тут по крайней мере было понятно о чём и зачем идёт речь (в то время как глядя на твою реализацию без пояснений, нафига и где оно нужно, понять ничего нельзя). Из твоих словесных пояснений и наводящих вопросов я хоть выяснил, что выигрыш по времени всего 13 (или 6) сотых секунды - хоть какая-то конкретика. Правда я так и не понял, что с чем мерялось, но тем не менее
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
29.12.2011, 13:28     Что такое compile-time алгоритмы и для чего они нужны? #43
Цитата Сообщение от Evg Посмотреть сообщение
Я уже говорил об этом. В своём случае ты почему-то меряешь ускорение в процентах, в то время как надо считать его в секундах (а точнее - вдолях секунды). Потому что код, который делает статическую инициализацию, например, квадратного корня через шаблонный механизм или через вызов функции, выполняется за время программы ОДИН раз. Поэтому в данном случае правомочны только сравнения абсолютного вренеми, а не относительного. При этом на двух чашах весов оказываются небольшое ускорение с одной стороны и разведение геморроя в исходниках с другой стороны.
Ну и дополнительно могу сказать, что данный механизм будет давать профит только в том случае, когда работа идёт над константами, что опять-таки случается не так уж и часто.
не очень понял...

я говорил о том, что 13 процентов затрат на поиск сериализатора/десериализатора. вывод профайлера я рассматривал как 100 процентов времени работы. далее, для уменьшения значений, я поделил 100 процентов времени работы на единицы, по одной секунде на единицу. и какая разница, 13 процент затрат на 100 процентов работы, или на 1 процент, или на одну секунду? если кол-во обращений к std::map фиксировано.

Цитата Сообщение от Evg Посмотреть сообщение
данный механизм будет давать профит только в том случае, когда работа идёт над константами
rpc процедуры + их типы + имена = константы.

Цитата Сообщение от Evg Посмотреть сообщение
примеры сводились к ссылкам на какие-то документации в boost'е, которые не особенно и интересны
для того чтоб что-то понять, должен быть интерес. а насильно, сам знаешь..

Цитата Сообщение от Evg Посмотреть сообщение
если бы кто-то хотя бы схематично нарисовал код по РЕАЛЬНОМУ использованию этого добра - тогда хотя бы был предмет для обсуждений
тебе уже приводили коды. но все тебе не так, и все не эдак.

Добавлено через 10 минут
Evg, придумай задачу, которая, как тебе кажется, покажет профит. тогда подумаем над реализацией. и напоследок - над тестами.
Evg
Эксперт CАвтор FAQ
17543 / 5781 / 370
Регистрация: 30.03.2009
Сообщений: 15,921
Записей в блоге: 26
29.12.2011, 13:37  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #44
Цитата Сообщение от niXman Посмотреть сообщение
я говорил о том, что 13 процентов затрат на поиск сериализатора/десериализатора. вывод профайлера я рассматривал как 100 процентов времени работы. далее, для уменьшения значений, я поделил 100 процентов времени работы на единицы, по одной секунде на единицу. и какая разница, 13 процент затрат на 100 процентов работы, или на 1 процент, или на одну секунду? если кол-во обращений к std::map фиксировано
Не понял вообще ничего. Ещё раз чётко и конкретно можешь сказать, сколько В СЕКУНДАХ ты получил выигрыш в скорости работы и сколько секунд работало приложение целиком

Цитата Сообщение от niXman Посмотреть сообщение
rpc процедуры + их типы + имена = константы
Естественно. Как и строковые литералы

Цитата Сообщение от niXman Посмотреть сообщение
для того чтоб что-то понять, должен быть интерес. а насильно, сам знаешь..
Ну скажи, какой мне смысл читать какую-то документацию от boost'а, если я этот самый boost и в глаза не видел. Ссылка на эту документацию эквивалентно ответу "тут много раз уже на форуме было, поищи": и вроде бы как ответил на вопрос и вроде бы как конкретно ответил, но полезной информации в этом ответе нет.

Цитата Сообщение от niXman Посмотреть сообщение
тебе уже приводили коды. но все тебе не так, и все не эдак
Из конкретных кодов, по которым хоть что-то можно понять человеку, не владеющему глубиной познаний в конкретной области, пока привели только два: вычисление хэш-суммы и вычисление квадратного корня. Пока в обоих случаях я оцениваю выигрыш как доли секунды. И лично моё мнение пока сводится к тому, что особенной практической пользы в этих compile-time алгоритмах я пока не вижу.

То, что авторы boost'а реализовали какие-то интерфейсы таким образом, что в compile-time что-то там вычисляется - это безусловно хорошо. Только принципальное отличие этого момента - это код, написанный другими людьми (точно так же как и функция sqrt написана другими людьми). И пусть выигрыш на исполнении будет мизерным, но это с лихвой компенсируется тем, что пользователи boost'а не делают никаких дополнительных затрат ради этого мизерного выигрыша. Правда эти вещи я бы не стал называть словом "алгоритм", а назвал бы словом "технология". А вот вычисление хэш-суммы и квадратного корня - да, это уже алгоритмы, работая с которыми вычисления можно переложить на компилятор. Хотя я бы постарался их избегать по той причине, которую указывал уже не раз: в случае чего, невозможно оттрасировать работу этого шаблона, чтобы выяснить, в каком же месте он косячит, а потому нужно отладивать это кучей извращенческих способов. Вариант с constexpr ко всему прочему поддерживается не на всех версиях компиляторов. Стоят ли те выигранные доли секунды потери возможности компилировать на не самых современных компиляторов - это каждый решает для себя сам. Пока я для себя не увидел ни одного compile-time алгоритма, который по каким-то причинам захотелось бы включить в свой проект

Добавлено через 1 минуту
Цитата Сообщение от niXman Посмотреть сообщение
Evg, придумай задачу, которая, как тебе кажется, покажет профит. тогда подумаем над реализацией. и напоследок - над тестами
Дык я уверен в том, что эти алгоритмы не дают ощутимого профита в большой РЕАЛЬНОЙ задаче. Как же я могу задачу придумать
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2011, 13:51     Что такое compile-time алгоритмы и для чего они нужны?
Еще ссылки по теме:
C++ Что такое h -файл и obj-файл?Зачем они нужны?
Перечисления (enum): для чего они нужны? Как, когда и какими перечислениями уместнее пользоваться? C++
C++ Compile-time и run-time методы и функции
Что такое static const и для чего он нужен? C++
Что такое полис и конечные автоматы и для чего используются в с++? C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
29.12.2011, 13:51     Что такое compile-time алгоритмы и для чего они нужны? #45
Цитата Сообщение от Evg Посмотреть сообщение
чётко и конкретно можешь сказать, сколько В СЕКУНДАХ ты получил выигрыш в скорости работы и сколько секунд работало приложение целиком
нет. такие замеры я не производил.
а обнаружил что на std::map я тратил 13 процентов процессорного времени. и свел этот показатель к нулю.

Цитата Сообщение от Evg Посмотреть сообщение
какой мне смысл читать какую-то документацию от boost'а, если я этот самый boost и в глаза не видел
зависит от цели.
последняя мой ссылка была на оптимизацию полученную путем оперирования описаниями типов. пример - проще некуда.

Цитата Сообщение от Evg Посмотреть сообщение
эти вещи я бы не стал называть словом "алгоритм", а назвал бы словом "технология". А вот вычисление хэш-суммы и квадратного корня - да, это уже алгоритмы
т.е. mpl::sort и mpl::find все же не алгоритмы? почему же std::find и std::sort алгоритмы?

Добавлено через 3 минуты
еще раз повторю: использовать только какую-то одну возможность предоставляемую шаблонами и алгоритмами времени компиляции - бессмысленно. использование этих принципов/технологий должно быть комплексным на уровне планирования архитектуры проекта. поэтому, использование в проекте моей реализации sqrt() не даст ровным счетом ничего.
хотя, возможно, в таком случае и даст что-то, ибо реализация стандартной функции sqrt() компилятору недоступна.
C++
1
2
3
4
for ( ;; ) {
   double v = sqrt(3.14159265);
   printf("%.15f\n", v);
}
Yandex
Объявления
29.12.2011, 13:51     Что такое compile-time алгоритмы и для чего они нужны?
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru