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

C++

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

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

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

Цитата Сообщение от niXman Посмотреть сообщение
compile-time алгоритмы
А есть от них хоть какая-то практическая польза? По-моему нет
1
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2011, 14:54
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Что такое compile-time алгоритмы и для чего они нужны? (C++):

Compile-time алгоритмы. сборник - C++
всем привет. предлагаю в этой теме обсуждать/реализовывать/выкладывать compile-time алгоритмы. под CUT'ом. подсчет FNV1a-хеш суммы...

.elf и для чего они нужны - C++
Собственно сабж Почитал Вики, как-то для новичка не очень много прояснилось И объясните еще пожалуйста разницу с ехе

Создать список ф-ций определяемых в файле (а-ля initializer list) в compile time - C++
Привет! Хочу как-то регистрировать все ф-ции, объявляемые в файле, например есть вот это std::string f1() { return "asdf1"; } ...

Что такое шейдеры и для чего они нужны? - Видеокарты
Всем привет! Кто сможет описать что такое шейдеры и для чего они нужны только более понятным русским языком(а не скачивая кусок из...

Что такое атрибуты и зачем они? Для чего нужны директивы препроцессора? - C#
Короче,товарищи,задаю вопрос не первый раз,поэтому,если уже отвечали,то прошу прощения,но я забыл уточнить в вопросе то,что мне всё-таки...

Что за драйвера такие, для чего они и нужны ли они вообще? - Драйверы
Что за драйвера такие, для чего они и нужны ли они вообще? 1 Intel SATA Preinstall driver (For AHCI / RAID Mode) Note: Press F6...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Evg
Эксперт CАвтор FAQ
17826 / 6036 / 388
Регистрация: 30.03.2009
Сообщений: 16,567
Записей в блоге: 26
28.12.2011, 17:45  [ТС] #31
Цитата Сообщение от niXman Посмотреть сообщение
и что из этого? сложная/непонятная реализация?
Ты считаешь это поводом к тому, что нужно усложнять понимание и без того плохо понимаемого исходника, чтобы ускорить программу на 6 сотых секунды?
0
niXman
Эксперт C++
3137 / 1449 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.12.2011, 21:32 #32
Evg, скажи, ты случаем не знаешь где раздобыть стандарт и реализации математических функции? а то я даже не знаю как оно зовется, по этому наверняка и ничего найти не могу..
0
Evg
Эксперт CАвтор FAQ
17826 / 6036 / 388
Регистрация: 30.03.2009
Сообщений: 16,567
Записей в блоге: 26
28.12.2011, 23:01  [ТС] #33
Реализации можно посмотреть в glibc. Стандарт - скорее всего оно около ieee-754 где-то, но если завтра напомнишь - уточню.

Не по теме:

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

0
niXman
Эксперт C++
3137 / 1449 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.12.2011, 23:38 #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, стандартной соответствует? выполняется в компайл-тайм?
3
Evg
Эксперт CАвтор FAQ
17826 / 6036 / 388
Регистрация: 30.03.2009
Сообщений: 16,567
Записей в блоге: 26
29.12.2011, 11:37  [ТС] #35
Та же самая беда. Воткни в начало main "std::cout.precision(40);" и увидишь, что результат отличается от стандартного. А для отрицательного значения считает неправильно (стандартная реализация возвращает nan)
0
Evg
Эксперт CАвтор FAQ
17826 / 6036 / 388
Регистрация: 30.03.2009
Сообщений: 16,567
Записей в блоге: 26
29.12.2011, 11:37  [ТС] #36
Цитата Сообщение от niXman Посмотреть сообщение
Evg, стандартной соответствует?
В соседней теме отписал те же самые два косяка. Плюс то же самое очевидное отсутсвие практической пользы
0
niXman
Эксперт C++
3137 / 1449 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
29.12.2011, 11:48 #37
Цитата Сообщение от Evg Посмотреть сообщение
результат отличается от стандартного
для подавляющего большинства задач это не имеет никакого значения. (я и вправду не проверял до такой точности)

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

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

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

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


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

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

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

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

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

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

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

Добавлено через 10 минут
Evg, придумай задачу, которая, как тебе кажется, покажет профит. тогда подумаем над реализацией. и напоследок - над тестами.
0
Evg
Эксперт CАвтор FAQ
17826 / 6036 / 388
Регистрация: 30.03.2009
Сообщений: 16,567
Записей в блоге: 26
29.12.2011, 13:37  [ТС] #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, придумай задачу, которая, как тебе кажется, покажет профит. тогда подумаем над реализацией. и напоследок - над тестами
Дык я уверен в том, что эти алгоритмы не дают ощутимого профита в большой РЕАЛЬНОЙ задаче. Как же я могу задачу придумать
0
niXman
Эксперт C++
3137 / 1449 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
29.12.2011, 13:51 #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);
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2011, 13:51
Привет! Вот еще темы с ответами:

Что такое векторы, и для чего нужны? - C++
читаю читаю но ответа в книге зачем нужны вектора так и не могу найти!!! пожалуйста напишите пример!! что бы я понял! спасибо!

Что такое Ant и Struts, и для чего нужны? - JAVA IDE
Доброго времени суток! Во многих IDE очень много упоминается про Ant и Struts. Хотелось бы узнать по подробнее от профессионалов, что...

Compile - time алгоритмы - C++
мне итересно, с появлением constexpr надобность в шаблонных компиле-тайм алгоритмах полностью отпала?..)

Объясните человеческим языком мне чайнику что такое singleton, статический класс. Зачем они нужны. Что рекомендуете прочитать мне для начала - C++
Объясните человеческим языком мне чайнику что такое singleton, статический класс. Зачем они нужны. Что рекомендуете прочитать мне для...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
29.12.2011, 13:51
Ответ Создать тему
Опции темы

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