Frais d'utilisation de bignums

Question

Je me suis posé la question de savoir s'il fallait utiliser bignums dans ma langue comme type de données par défaut lorsque des nombres sont impliqués. Je l'ai évalué moi-même et je l'ai réduit à une question de confort et de confort par rapport à la performance. La réponse à cette question dépend de l’ampleur de la baisse de performances des programmes non optimisés.

Quelle est la taille de l’utilisation de bignums dans des endroits où un nombre fixe ou entier aurait suffi? Quelle taille peut-il être au mieux des implémentations? Quels types d'implémentations génèrent le moins de frais généraux et quels compromis en résultent-ils?

Quel type de succès puis-je attendre des résultats globaux en termes de performances linguistiques si je mets ma langue en défaut sur bignums?

Answer 1

Pour être honnête, la meilleure réponse est "essayez-le et consultez".

Il est clair que les bignums ne peuvent pas être aussi efficaces que les types natifs, qui s’inscrivent généralement dans un seul registre de processeurs, mais chaque application est différente. Si votre application ne fait pas une charge arithmétique entière, la surcharge risque d’être négligeable.

Answer 2

Vous pouvez peut-être regarder comment Lisp le fait. Il fera presque toujours la chose exactement juste et convertira implicitement les types à la nécessité. Il a des fixnums (entiers "normaux"), des bignums, des ratios (fractions propres réduites représentées sous la forme d'un ensemble de deux entiers) et des flottants (de tailles différentes). Seuls les flottants ont une erreur de précision et ils sont contagieux, c’est-à-dire qu’une fois qu’un calcul implique un flottant, le résultat est également un flottant. "Practical Common Lisp" a une bonne description de ce comportement.

Answer 3

Venez y penser ... Je ne pense pas qu'il y aura beaucoup de succès en performance.

Parce que les bignums ont, par nature, une très base très large, disons une base de 65 536 ou plus, valeur généralement maximale pour le fixnum et les entiers traditionnels.

Je ne sais pas quelle taille définiriez la base du bignum mais si vous le définissez suffisamment grand pour que, lorsqu'il est utilisé à la place de fixnums et / ou d’entiers, il ne dépasse jamais son premier chiffre bignum ainsi, l'opération sera presque identique à fixnums / int.

Cela ouvre la voie à des optimisations où, pour un bignum qui ne dépasse jamais son premier chiffre, vous pouvez les remplacer par une opération ultra-rapide à un chiffre.

Puis passez aux algorithmes à n chiffres lorsque vous avez besoin du deuxième chiffre bignum.

Ceci pourrait être implémenté avec un indicateur de bit et une opération de validation sur toutes les opérations arithmétiques. En gros, vous pouvez utiliser le bit de poids fort pour indiquer Bignum, si le bit de poids fort d’un bloc de données est défini sur 0, traitez-les comme s'il s'agissait de fixnum / ints normaux, mais s'il est défini sur 1, analysez le bloc en tant que structure bignum et utilisez les algorithmes bignum à partir de là.

Cela devrait éviter les problèmes de performance provenant de variables d'itérateur de boucle simples qui, selon moi, constituent la première source possible de résultats de performance.

Ce n’est que ma pensée brute, une suggestion puisque vous devriez savoir mieux que moi: -)

p.s. désolé, j'ai oublié quels étaient les termes techniques de bignum-digit et bignum-base

Answer 4

votre réduction est correcte, mais le choix dépend des caractéristiques de performance de votre langue, que nous ne pouvons pas connaître !

une fois que votre langage est implémenté, vous pouvez mesurer la différence de performances et éventuellement proposer au programmeur une directive permettant de choisir la valeur par défaut

Answer 5

Vous ne saurez jamais quelle est la performance réelle tant que vous n'avez pas créé votre propre point de repère, car les résultats varieront par langue, par révision de langue et par processeur. Il n’existe aucun moyen indépendant du langage de mesurer cela, mis à part le fait évident qu’un entier 32 bits utilise deux fois la mémoire d’un entier 16 bits.

Answer 6

  

Quelle est la taille de l’utilisation de bignums dans des endroits où un nombre fixe ou entier aurait suffi? Montrer petit peut-il être au mieux des implémentations?

La mauvaise nouvelle est que, même dans la meilleure implémentation logicielle possible, BigNum sera plus lent que l'arithmétique intégrée de plusieurs ordres de grandeur (c'est-à-dire tout, du facteur 10 au facteur 1000).

Je n'ai pas les chiffres exacts, mais je ne pense pas que les chiffres exacts aideront beaucoup dans une telle situation: si vous avez besoin de gros chiffres, utilisez-les. Si non, ne le faites pas. Si votre langue les utilise par défaut (quelle langue utilise certaines langues dynamiques…), demandez-vous si le désavantage de passer à une autre langue est compensé par le gain de performances (ce qui devrait être rarement le cas).

(Ce qui pourrait être traduit approximativement en: il y a une différence énorme mais cela ne devrait pas avoir d'importance. Si (et seulement si) c'est important, utilisez un autre langage car même avec la meilleure mise en œuvre possible, la langue ne convient évidemment pas à la tâche.)

Answer 7

Je doute fort que cela en vaille la peine, à moins que ce soit très spécifique à un domaine.

La première chose qui me vient à l’esprit, ce sont les petites boucles d’ajustement des programmes , les petites variables d’itérateur vont-elles toutes être des bignums? C'est effrayant!

Mais si votre langage est plutôt fonctionnel ... alors peut-être pas.