Накладные расходы, используя работу со сверхбольшими числами
Я столкнулся с этой проблемой о том, следует ли использовать bignums в моем языке в качестве типа данных по умолчанию, когда речь идет о числах. Я сам оценил это и свел его к вопросу "удобство и комфорт против производительности". Ответ на этот вопрос зависит от того, насколько велика производительность в программах, которые не оптимизируются.
Насколько малы накладные расходы при использовании бигнумов в тех местах, где хватило бы фиксированного числа или целого числа? Насколько она может быть маленькой в лучшем случае реализации? Какие реализации достигают наименьших накладных расходов и к каким дополнительным компромиссам они приводят?
Какого хита Я могу ожидать от результатов в общей производительности языка, если я поставлю свой язык по умолчанию на bignums?
7 ответов:
Честно говоря, лучший ответ - "попробуй и увидишь".
Очевидно, что бигнумы не могут быть такими же эффективными, как нативные типы, которые обычно помещаются в один регистр ЦП, но каждое приложение отличается - если ваше не выполняет целую нагрузку целочисленной арифметики, то накладные расходы могут быть незначительными.
Возможно, вы можете посмотреть, как это делает Lisp. Он почти всегда будет делать точно правая вещь и неявно преобразует типы по мере необходимости. Он имеет фиксированные числа ("нормальные" целые числа), бигнумы, отношения (уменьшенные собственные дроби, представленные в виде набора двух целых чисел) и поплавки (в разных размерах). Только поплавки имеют погрешность точности, и они заразительны, т. е. как только вычисление включает поплавок, результат также является поплавком. "Практический общий шепелявый" имеет хороший описание такого поведения.
Если подумать... Я не думаю, что он будет иметь много хитов производительности вообще.
Потому что бигны по своей природе будут иметь очень большое основание, скажем, основание 65536 или больше, для которого обычно максимально возможное значение для традиционных фиксированных чисел и целых чисел.
Я не знаю, насколько большим будет основание бигнума, но если вы установите его достаточно большим, чтобы при использовании вместо фиксированных чисел и/или целых чисел оно никогда не превышало своего первого значения. bignum-цифра, таким образом, операция будет почти идентична обычной fixnums/int.
Это открывает возможность для оптимизации, где для бигнума, который никогда не растет над своей первой цифрой бигнума, вы можете заменить их Убер-быстрой операцией с одной цифрой бигнума.
, а затем переключиться на N-значные алгоритмы, когда требуется вторая бигнум-цифра.
Это может быть реализовано с помощью битового флага и операции проверки всех арифметических операций, грубо говоря, вы можете используйте самый старший бит для обозначения bignum, если блок данных имеет наивысший бит установлен в 0, то обрабатывать их, как если бы они были нормальными fixnum/ИНЦ но если он установлен в 1, то разобрать блок как bignum структуру и использовать bignum алгоритмов оттуда.
, что должно избегать попаданий производительности от простых переменных итератора цикла, которые, я думаю, являются первым возможным источником попаданий производительности.
Это просто мое грубое мышление, хотя это предложение, так как вы должны знать лучше, чем я. :- )
P. s. извините, забыл, что такое технические термины bignum-digit и Bignum-base
Ваше сокращение верно, но выбор зависит от характеристик производительности вашего языка, которые мы не можем знать!
После того, как вы внедрили свой язык, вы можете измерить разницу в производительности и, возможно, предложить программисту директиву для выбора значения по умолчанию
Вы никогда не узнаете фактическую производительность, пока не создадите свой собственный бенчмарк, поскольку результаты будут варьироваться в зависимости от языка, версии языка и процессора. Нет независимого от языка способа измерить это, за исключением очевидного факта, что 32-битное целое число использует в два раза больше памяти, чем 16-битное целое число.
Плохая новость заключается в том, что даже в самой лучшей программной реализации BigNum будет медленнее, чем встроенная арифметика на порядки (т. е. все от фактора 10 до фактора 1000).Насколько малы накладные расходы при использовании бигнумов в местах, где хватило бы фиксированного числа или целого числа? Показать маленькие могут ли это быть в лучшем случае реализации?
У меня нет точных цифр, но я не думаю, что точные цифры очень помогут в такой ситуации: если вам нужны большие числа, используйте их. Если ваш язык использует их по умолчанию (какой язык использует? некоторые динамические языки делают ...), подумайте, компенсируется ли недостаток перехода на другой язык увеличением производительности (что должно быть редко).
(что можно приблизительно перевести как: есть огромная разница, но это не должно иметь значения. Если (и только если) это имеет значение, используйте другой язык, потому что даже при наилучшей возможной реализации это язык явно не подходит для этой задачи.)
Я полностью сомневаюсь, что это будет стоить того, если только это не очень специфично для конкретной области.
Первое, что приходит на ум, - это все маленькие циклы для всех программ, Все ли маленькие переменные итератора будут бигнумами? Это страшно!
Но если ваш язык достаточно функционален... а может, и нет.