Sobrecarga de usar bignums

Question

Me he topado con este problema sobre si usar bignums en mi idioma como tipo de datos predeterminado cuando hay números involucrados. Lo evalué yo mismo y lo reduje a una cuestión de conveniencia y comodidad versus rendimiento. La respuesta a esa pregunta depende de cuán grande sea el impacto en el rendimiento de los programas que no se están optimizando.

¿Qué tan pequeña es la sobrecarga de usar bignums en lugares donde hubiera sido suficiente un fixnum o un entero? ¿Qué tan pequeño puede ser en las mejores implementaciones? ¿Qué tipo de implementaciones alcanzan los gastos generales más pequeños y en qué tipo de compensaciones adicionales resultan?

¿Qué tipo de éxito puedo esperar para los resultados en el rendimiento general del idioma si pongo mi idioma predeterminado en bignums?

Answer 1

Para ser sincero, la mejor respuesta es " pruébelo y vea " ;.

Claramente, los bignums no pueden ser tan eficientes como los tipos nativos, que generalmente caben en un solo registro de CPU, pero cada aplicación es diferente: si la suya no realiza una carga completa de aritmética de enteros, entonces la sobrecarga podría ser insignificante.

Answer 2

Quizás puedas ver cómo lo hace Lisp. Casi siempre hará lo exactamente correcto y convertirá implícitamente los tipos cuando sea necesario. Tiene fixnums (enteros normales), bignums, proporciones (fracciones propias reducidas representadas como un conjunto de dos enteros) y flotantes (en diferentes tamaños). Solo los flotadores tienen un error de precisión y son contagiosos, es decir, una vez que un cálculo involucra un flotador, el resultado también es un flotador. " Lisp común práctica " tiene una buena descripción de este comportamiento.

Answer 3

Ahora que lo pienso ... no creo que tenga muchos éxitos de rendimiento en absoluto.

Debido a que los bignums por naturaleza, tendrán una base muy grande, digamos una base de 65536 o mayor para la cual generalmente es un valor máximo posible para los números fijos y enteros tradicionales.

No sé qué tan grande establecerías la base del bignum, pero si lo configuras lo suficientemente grande como para que cuando se use en lugar de fixnums y / o enteros, nunca excedería su primer dígito bignum por lo tanto, la operación será casi idéntica a los fixnums / int normales.

Esto abre una oportunidad para optimizaciones donde, para un bignum que nunca crece sobre su primer dígito bignum, podría reemplazarlos con una operación súper rápida de un dígito bignum.

Y luego cambie a algoritmos de n dígitos cuando se necesite el segundo dígito bignum.

Esto podría implementarse con un indicador de bit y una operación de validación en todas las operaciones aritméticas, más o menos pensando que podría usar el bit de orden más alto para indicar bignum, si un bloque de datos tiene su bit de orden más alto establecido en 0, entonces procesarlos como si fueran fixnum / ints normales pero si se establece en 1, luego analizar el bloque como una estructura bignum y utilizar algoritmos bignum desde allí.

Eso debería evitar los resultados de rendimiento de las variables de iterador de bucle simple, que creo que es la primera fuente posible de resultados de rendimiento.

Sin embargo, es solo mi pensamiento aproximado, una sugerencia ya que deberías saberlo mejor que yo :-)

p.s. lo siento, olvidé cuáles eran los términos técnicos de bignum-digit y bignum-base

Answer 4

su reducción es correcta, pero la elección depende de las características de rendimiento de su idioma, que no podemos saber !

una vez que haya implementado su lenguaje, puede medir la diferencia de rendimiento y tal vez ofrecerle al programador una directiva para elegir el valor predeterminado

Answer 5

Nunca conocerá el rendimiento real hasta que cree su propio punto de referencia, ya que los resultados variarán por idioma, por revisión de idioma y por CPU y. No existe una forma independiente del lenguaje para medir esto, excepto por el hecho obvio de que un entero de 32 bits usa el doble de memoria que un entero de 16 bits.

Answer 6

  

¿Qué tan pequeña es la sobrecarga de usar bignums en lugares donde hubiera sido suficiente un fixnum o un entero? Mostrar pequeño ¿puede ser en las mejores implementaciones?

La mala noticia es que, incluso en la mejor implementación de software posible, BigNum va a ser más lento que la aritmética incorporada en órdenes de magnitud (es decir, desde el factor 10 hasta el factor 1000).

No tengo números exactos, pero no creo que los números exactos ayuden mucho en tal situación: si necesita números grandes, úselos. Si no, no lo hagas. Si su idioma los usa de forma predeterminada (¿qué idioma hace? Algunos idiomas dinámicos lo hacen & # 8230;), piense si la desventaja de cambiar a otro idioma se compensa con la ganancia de rendimiento (que rara vez debería ser). >

(que podría traducirse aproximadamente a: hay una gran diferencia, pero no debería importar. Si (y solo si) importa, use otro idioma porque incluso con la mejor implementación posible, esto evidentemente el lenguaje no es adecuado para la tarea.)

Answer 7

Dudo totalmente que valga la pena, a menos que sea muy específico del dominio.

Lo primero que viene a la mente son todos los pequeños bucles de los programas , ¿las pequeñas variables iteradoras serán bignums? ¡Eso da miedo!

Pero si su lenguaje es bastante funcional ... entonces tal vez no.