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

Evg · Регистрация: 30.03.2009

Author24 — интернет-сервис помощи студентам

Сообщение от niXman

compile-time алгоритмы

А есть от них хоть какая-то практическая польза? По-моему нет

Evg · 28.12.2011, 17:12 **[ТС]**

ForEveR, списибо за такой пример. Далее взял я этот пример и через него как бы начал вычислять корень из отрицательного значения. Компилятор ушёл в глубокий штопор, но через минуту из него всё-таки вылез и посчитал, естественным образом, неправильное значение. Ну конкретно в данном случае в конечном итоге можно понять, что неправильное значение было у переменной s и гляда на исходник понять, что мы пытаемся вычислить корень из отрицательного значения. Но вот теперь ели какой-то умник вместо пары чисел, определяющих константу -2.0 подставить ещё какую-нибудь хрень, порождённую другим шаблоном, то много ли шансов найти ошибку в этой программе, особенно если искать будет человек, который эту программу видит впервые в жизни? Стоит ли этот гемор сэкономленных трёх сотых секунд времени по сравнению с:

C

1	const double s = sqrt(2.0);

не говоря уж о том, что вычисление корня от константного значения в общем-то редкое дело

@niXman · 28.12.2011, 17:20

Сообщение от Evg

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

для этого нужно добавить компайл-тайм ассерт.

Добавлено через 1 минуту

Сообщение от Evg

А они compile-time?

конечно. в boost.mpl все компайл-тайм.

Сообщение от Evg

На у тогда зачем делать сложным то, что можно сделать простым.

не понимаешь ты меня.

Evg · 28.12.2011, 17:31 **[ТС]**

Сообщение от niXman

для этого нужно добавить компайл-тайм ассерт

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

Добавлено через 2 минуты

Сообщение от niXman

не понимаешь ты меня

Скорее всего. Только при программировании я всегда руководствуюсь тем, что самым первым критерием должна быть понятность кода, и только потом производительность. Т.е. непонятный код, работающий на 3% быстрее понятного кода, я почти всегда отмету. За исключением тех редких случаев, когда это действительно обосновано

@niXman · 28.12.2011, 17:34

Сообщение от Evg

как потом с этим другим людям работать.

это субъективно.
мне вполне понятен код.

Сообщение от Evg

Какой компайл-тайм ассерт в данном случае спас бы нас?

стандартный. ибо версии начиная 4.6.0 содержат ВМ для вычисления значений с плавающей точкой.

Добавлено через 1 минуту

Сообщение от Evg

первым критерием должна быть понятность кода

это тоже субъективно. приведенный выше код вполне понятен. а если ему уделить несколько минут, то вообще ни одного неясного момента не останется.

Evg · 28.12.2011, 17:35 **[ТС]**

Сообщение от niXman

стандартный

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

Добавлено через 1 минуту

Сообщение от niXman

а если ему уделить несколько минут

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

@niXman · 28.12.2011, 17:40

Сообщение от Evg

Далее, можно этим алгоритмом вычислить корень из 1.000006 и увидеть, что результат отличается от того, что положено по стандарту.

это вопрос?
вот что считает это код из 1.000006: 1.000002999991

Добавлено через 3 минуты

Сообщение от Evg

compile-time, который к тому же ещё и неправильно работает

что неправильно? у тебя какой результат выдает? какая версия компилятора?

Добавлено через 1 минуту

Сообщение от Evg

скажи в каком месте хода какой ассерт воткнуть

http://liveworkspace.org/code/... 17811f80b4
шестая строка.

Evg · 28.12.2011, 17:40 **[ТС]**

Сообщение от niXman

это вопрос?
вот что считает это код из 1.000006: 1.000002999991

Это утверждение. Теперь вычисли корень через библиотечный sqrt (который заведомо по стандарту работает). Можно увеличить precision при печати для наглядности. Ну и вот сколько времени понадобилось бы мозахисту на отладку, если бы он напоролся на такую ситуацию? Ладно это коротенький пример, когда просто вычисляется корень, а то ведь большая задача. И ведь самое-то дебильное, в случае реализации в виде нормальной функции можно было бы печати в неё поставить (печать входного и выходного значения), а в случае с шаблоном и этого сделать нельзя.

@niXman · 28.12.2011, 17:43

Сообщение от Evg

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

опять ты говоришь про себя.
С/С++ вообще не интуитивно понятные ЯП. и кому-то даже Си реализация покажется не понятной. и что из этого? сложная/непонятная реализация?

Evg · 28.12.2011, 17:43 **[ТС]**

Сообщение от niXman

шестая строка.

Я говорю не про случай корня из отрицательного значения (благо, не настолько тупой, чтобы не понять этого), а про случай, когда корень из 1.000006 вычисляется неправильно

@niXman · 28.12.2011, 17:44

Сообщение от Evg

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

юнит тестирование наше всё!

Evg · 28.12.2011, 17:45 **[ТС]**

Сообщение от niXman

и что из этого? сложная/непонятная реализация?

Ты считаешь это поводом к тому, что нужно усложнять понимание и без того плохо понимаемого исходника, чтобы ускорить программу на 6 сотых секунды?

@niXman · 28.12.2011, 21:32

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

Evg · 28.12.2011, 23:01 **[ТС]**

Реализации можно посмотреть в glibc. Стандарт - скорее всего оно около ieee-754 где-то, но если завтра напомнишь - уточню.

Не по теме:

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

@niXman · 28.12.2011, 23:38

кстати, вот и компайл-тайм реализация sqrt() без единого шаблона

C++

#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/... c93086cf4d

Evg, стандартной соответствует? выполняется в компайл-тайм?

Evg · 29.12.2011, 11:37 **[ТС]**

Та же самая беда. Воткни в начало main "std::cout.precision(40);" и увидишь, что результат отличается от стандартного. А для отрицательного значения считает неправильно (стандартная реализация возвращает nan)

Evg · 29.12.2011, 11:37 **[ТС]**

Сообщение от niXman

Evg, стандартной соответствует?

В соседней теме отписал те же самые два косяка. Плюс то же самое очевидное отсутсвие практической пользы

@niXman · 29.12.2011, 11:48

Сообщение от Evg

результат отличается от стандартного

для подавляющего большинства задач это не имеет никакого значения. (я и вправду не проверял до такой точности)

Сообщение от Evg

для отрицательного значения считает неправильно

это уже придирки. добавь проверку и возвращай nan.

@niXman · 29.12.2011, 11:48

Сообщение от Evg

отсутсвие практической пользы

предыдущие четыре страницы мы не с тобой общались?

Evg · 29.12.2011, 11:59 **[ТС]**

Сообщение от niXman

предыдущие четыре страницы мы не с тобой общались?

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

Evg · 29.12.2011, 12:03 **[ТС]**

Сообщение от niXman

для подавляющего большинства задач это не имеет никакого значения

Для этого же подавляющего значение точно так не имеет никакого значения, что будет что-то вычисляться в compile-time вместо run-time.

Сообщение от niXman

это уже придирки. добавь проверку и возвращай nan

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

Перенеси последние посты в соседнюю тему, потому что опять всё свелось к тому же самому

@niXman 3211 / 1459 / 74 Регистрация: 09.08.2009 Сообщений: 3,441 Записей в блоге: 2
	28.12.2011, 17:20	22
	Сообщение от Evg неправильное значение было у переменной s и гляда на исходник понять, что мы пытаемся вычислить корень из отрицательного значения для этого нужно добавить компайл-тайм ассерт. Добавлено через 1 минуту Сообщение от Evg А они compile-time? конечно. в boost.mpl все компайл-тайм. Сообщение от Evg На у тогда зачем делать сложным то, что можно сделать простым. не понимаешь ты меня. 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	28.12.2011, 17:35 [ТС]	25
	Сообщение от niXman стандартный Ты не словами говори, а скажи в каком месте хода какой ассерт воткнуть (что конеретно должно быть больше или меньше чего конкретно). Т.е. посмотри на это дело с позиции человека, которому дали найти ошибку в существующем коде. Добавлено через 1 минуту Сообщение от niXman а если ему уделить несколько минут Можно написать так, что понятно будет с первого взгляда, а можнонаписать так - что после уделения нескольких минут. Зато compile-time, который к тому же ещё и неправильно работает 0

@niXman 3211 / 1459 / 74 Регистрация: 09.08.2009 Сообщений: 3,441 Записей в блоге: 2
	28.12.2011, 17:40	26
	Сообщение от Evg Далее, можно этим алгоритмом вычислить корень из 1.000006 и увидеть, что результат отличается от того, что положено по стандарту. это вопрос? вот что считает это код из 1.000006: 1.000002999991 Добавлено через 3 минуты Сообщение от Evg compile-time, который к тому же ещё и неправильно работает что неправильно? у тебя какой результат выдает? какая версия компилятора? Добавлено через 1 минуту Сообщение от Evg скажи в каком месте хода какой ассерт воткнуть http://liveworkspace.org/code/... 17811f80b4 шестая строка. 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	28.12.2011, 17:40 [ТС]	27
	Сообщение от niXman это вопрос? вот что считает это код из 1.000006: 1.000002999991 Это утверждение. Теперь вычисли корень через библиотечный sqrt (который заведомо по стандарту работает). Можно увеличить precision при печати для наглядности. Ну и вот сколько времени понадобилось бы мозахисту на отладку, если бы он напоролся на такую ситуацию? Ладно это коротенький пример, когда просто вычисляется корень, а то ведь большая задача. И ведь самое-то дебильное, в случае реализации в виде нормальной функции можно было бы печати в неё поставить (печать входного и выходного значения), а в случае с шаблоном и этого сделать нельзя. 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	28.12.2011, 23:01 [ТС]	33
	Реализации можно посмотреть в glibc. Стандарт - скорее всего оно около ieee-754 где-то, но если завтра напомнишь - уточню. Не по теме: Спорить мы начали по теме "compile-time алгоритмы", а не "mpl-алгоритмы", как оно сейчас озаглавлено 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	28.12.2011, 17:31 [ТС]	23
	Сообщение от niXman для этого нужно добавить компайл-тайм ассерт Да вопрос не в том, как нужно было писать, а в том, как потом с этим другим людям работать. Это находится на том же уровне, что и отладка. Которая в случае нормального написания программы была бы понятной. Далее, можно этим алгоритмом вычислить корень из 1.000006 и увидеть, что результат отличается от того, что положено по стандарту. Какой компайл-тайм ассерт в данном случае спас бы нас? Ты тут даже в отладчике пощёлкать не сможешь, чтобы ход процесса посмотреть Добавлено через 2 минуты Сообщение от niXman не понимаешь ты меня Скорее всего. Только при программировании я всегда руководствуюсь тем, что самым первым критерием должна быть понятность кода, и только потом производительность. Т.е. непонятный код, работающий на 3% быстрее понятного кода, я почти всегда отмету. За исключением тех редких случаев, когда это действительно обосновано 0

@niXman 3211 / 1459 / 74 Регистрация: 09.08.2009 Сообщений: 3,441 Записей в блоге: 2
	28.12.2011, 17:34	24
	Сообщение от Evg как потом с этим другим людям работать. это субъективно. мне вполне понятен код. Сообщение от Evg Какой компайл-тайм ассерт в данном случае спас бы нас? стандартный. ибо версии начиная 4.6.0 содержат ВМ для вычисления значений с плавающей точкой. Добавлено через 1 минуту Сообщение от Evg первым критерием должна быть понятность кода это тоже субъективно. приведенный выше код вполне понятен. а если ему уделить несколько минут, то вообще ни одного неясного момента не останется. 0

@niXman 3211 / 1459 / 74 Регистрация: 09.08.2009 Сообщений: 3,441 Записей в блоге: 2
	28.12.2011, 17:43	28
	Сообщение от Evg Можно написать так, что понятно будет с первого взгляда, а можнонаписать так - что после уделения нескольких минут. опять ты говоришь про себя. С/С++ вообще не интуитивно понятные ЯП. и кому-то даже Си реализация покажется не понятной. и что из этого? сложная/непонятная реализация? 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	28.12.2011, 17:43 [ТС]	29
	Сообщение от niXman шестая строка. Я говорю не про случай корня из отрицательного значения (благо, не настолько тупой, чтобы не понять этого), а про случай, когда корень из 1.000006 вычисляется неправильно 0

@niXman 3211 / 1459 / 74 Регистрация: 09.08.2009 Сообщений: 3,441 Записей в блоге: 2
	28.12.2011, 17:44	30
	Сообщение от Evg в случае реализации в виде нормальной функции можно было бы печати в неё поставить (печать входного и выходного значения), а в случае с шаблоном и этого сделать нельзя. юнит тестирование наше всё! 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	28.12.2011, 17:45 [ТС]	31
	Сообщение от niXman и что из этого? сложная/непонятная реализация? Ты считаешь это поводом к тому, что нужно усложнять понимание и без того плохо понимаемого исходника, чтобы ускорить программу на 6 сотых секунды? 0

@niXman 3211 / 1459 / 74 Регистрация: 09.08.2009 Сообщений: 3,441 Записей в блоге: 2
	28.12.2011, 21:32	32
	Evg, скажи, ты случаем не знаешь где раздобыть стандарт и реализации математических функции? а то я даже не знаю как оно зовется, по этому наверняка и ничего найти не могу.. 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	29.12.2011, 11:37 [ТС]	35
	Та же самая беда. Воткни в начало main "std::cout.precision(40);" и увидишь, что результат отличается от стандартного. А для отрицательного значения считает неправильно (стандартная реализация возвращает nan) 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	29.12.2011, 11:37 [ТС]	36
	Сообщение от niXman Evg, стандартной соответствует? В соседней теме отписал те же самые два косяка. Плюс то же самое очевидное отсутсвие практической пользы 0

@niXman 3211 / 1459 / 74 Регистрация: 09.08.2009 Сообщений: 3,441 Записей в блоге: 2
	29.12.2011, 11:48	37
	Сообщение от Evg результат отличается от стандартного для подавляющего большинства задач это не имеет никакого значения. (я и вправду не проверял до такой точности) Сообщение от Evg для отрицательного значения считает неправильно это уже придирки. добавь проверку и возвращай nan. 0

	29.12.2011, 12:03

@niXman 3211 / 1459 / 74 Регистрация: 09.08.2009 Сообщений: 3,441 Записей в блоге: 2
	29.12.2011, 11:48	38
	Сообщение от Evg отсутсвие практической пользы предыдущие четыре страницы мы не с тобой общались? 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	29.12.2011, 11:59 [ТС]	39
	Сообщение от niXman предыдущие четыре страницы мы не с тобой общались? ТОгда приведи пример, где вычисление корня от константы на этапе компиляции даст какое-то реальное преимущество. Не выигрыш в одну сотую секунду, а реально ощутимый выигрыш в производительности, который бы реально оправдал те геморозатраты, которые на это потребуются 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	29.12.2011, 12:03 [ТС]	40
	Сообщение от niXman для подавляющего большинства задач это не имеет никакого значения Для этого же подавляющего значение точно так не имеет никакого значения, что будет что-то вычисляться в compile-time вместо run-time. Сообщение от niXman это уже придирки. добавь проверку и возвращай nan Нет, это не придирки. Это кроткий пример, вкотором изначально известно, где была допущена ошибка. В общем случае это может вылиться в кучу потерянного времени. И ладно это более простая реализация из-за того, что поддерживается конструкция constexpr. Однако весь мир (особенно крупные компании) не так спешит за прогрессом и переходом но новые версии компилятора, новые стандарты и т.п. В итоге я опять не вижу никакого оправдания разведению геморроя на ровном месте Перенеси последние посты в соседнюю тему, потому что опять всё свелось к тому же самому 0

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

Решение