Накладные расходы на использование bignums

Question

Я столкнулся с проблемой, следует ли использовать bignums на моем языке в качестве типа данных по умолчанию, когда речь идет о числах.Я сам оценил это и свел к принципу "удобство и комфорт".производительность - вопрос.Ответ на этот вопрос зависит от того, насколько велико снижение производительности в программах, которые не оптимизируются.

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

Какого эффекта я могу ожидать от результатов в общей производительности языка, если я установлю для своего языка значение по умолчанию в bignums?

Answer 1

Если честно, лучший ответ - это "попробуй и посмотри".

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

Answer 2

Вы можете посмотреть, как это делает Лисп. Он почти всегда будет выполнять точно правильно и неявно преобразовывать типы по мере необходимости. Он имеет фиксированные значения («нормальные» целые числа), bignums, отношения (сокращенные собственные дроби, представленные в виде набора из двух целых чисел) и числа с плавающей запятой (разных размеров). Только ошибки с плавающей точкой имеют погрешность точности, и они заразны, то есть, если вычисление включает в себя число с плавающей точкой, результатом также является число с плавающей точкой. " Практический Common Lisp " имеет хорошее описание этого поведения.

Answer 3

Если подумать об этом...Я не думаю, что это вообще сильно повлияет на производительность.

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

Я не знаю, насколько большим вы бы установили значение bignum, но если вы установите его достаточно большим, чтобы при использовании вместо фиксированных чисел и / или целых чисел оно никогда не превышало своей первой цифры bignum, таким образом, операция будет почти идентична обычной fixnums / int.

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

А затем переключитесь на n-значные алгоритмы, когда потребуется вторая большая цифра.

Это может быть реализовано с помощью битового флага и операции проверки для всех арифметических операций, грубо говоря, вы могли бы использовать бит высшего порядка для обозначения величины, если для блока данных установлен бит высшего порядка 0, затем обработайте их так, как если бы они были обычными фиксированными числами / целыми числами, но если для него установлено значение 1, то проанализируйте блок как структуру bignum и используйте алгоритмы bignum оттуда.

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

Хотя это всего лишь мое приблизительное мышление, предложение, поскольку вы должны знать лучше меня :-)

p.s.извините, забыл, каковы технические термины bignum-digit и bignum-base

Answer 4

ваше сокращение является правильным, но выбор зависит от характеристик производительности вашего языка, которые мы не можем знать !

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

Answer 5

Вы никогда не узнаете фактическое снижение производительности, пока не создадите свой собственный эталонный тест, поскольку результаты будут различаться в зависимости от языка, редакции языка, процессора и. Нет никакого независимого от языка способа измерить это, кроме очевидного факта, что 32-битное целое число использует вдвое больше памяти, чем 16-битное целое число.

Answer 6

  

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

Плохая новость заключается в том, что даже в самой лучшей реализации программного обеспечения BigNum будет на несколько порядков медленнее, чем встроенная арифметика (т. е. от 10 до 1000).

У меня нет точных цифр, но я не думаю, что точные цифры очень помогут в такой ситуации: если вам нужны большие цифры, используйте их. Если нет, не надо. Если ваш язык использует их по умолчанию (а какой язык? Некоторые динамические языки поддерживают & # 8230;), подумайте, компенсируется ли недостаток перехода на другой язык увеличением производительности (которым оно должно быть редко).

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

Answer 7

Я полностью сомневаюсь, что это того стоит, если только оно не очень специфично для домена.

Первое, что приходит на ум - это все циклы for в программах . Будут ли маленькие переменные-итераторы бигнумами? Это страшно!

Но если ваш язык довольно функциональный ... то, возможно, нет.