¿Por qué es que las estructuras de datos suelen tener un tamaño de 2^n?

Question

Hay una razón histórica o algo ?He visto un par de veces algo como char foo[256]; o #define BUF_SIZE 1024.Ni siquiera yo solo uso 2ⁿ tamaño de los buffers, sobre todo porque yo creo que se ve más elegante y de esa manera no tengo que pensar en un número específico.Pero no estoy muy seguro de si esa es la razón por la mayoría de la gente los usa, más información se agradece.

Answer 1

Puede haber una serie de razones, aunque muchas personas, como usted dice, lo harán por costumbre.

Un lugar donde es muy útil es en la implementación eficiente de memorias intermedias circulares, especialmente en arquitecturas donde el% de operador es costoso (aquellos sin división de hardware, principalmente microcontroladores de 8 bits). Al usar un búfer de 2 ^ n en este caso, el módulo es simplemente un caso de enmascaramiento de bits de los bits superiores, o en el caso de decir un búfer de 256 bytes, simplemente usando un índice de 8 bits y dejándolo envolver.

En otros casos, la alineación con los límites de la página, cachés, etc. puede proporcionar oportunidades para la optimización en algunas arquitecturas, pero eso sería muy específico de la arquitectura. Pero puede ser que tales amortiguadores brinden al compilador posibilidades de optimización, por lo que todas las demás cosas son iguales, ¿por qué no?

Answer 2

Las líneas de caché son generalmente múltiplos de 2 (a menudo 32 o 64). Los datos que son un múltiplo integral de ese número podrían encajar (y utilizar por completo) el número correspondiente de líneas de caché. Cuantos más datos pueda empaquetar en su caché, mejor será el rendimiento ... así que creo que las personas que diseñan sus estructuras de esa manera se están optimizando para eso.

Answer 3

Otra razón además de lo que todo el mundo ha mencionado es, las instrucciones SSE tomar varios elementos, y el número de elementos de entrada es siempre una potencia de dos.Hacer el búfer de una potencia de dos garantías de que no será la lectura de la memoria no.Esto sólo se aplica si usted está realmente en uso de las instrucciones SSE, aunque.

Creo que, al final, sin embargo, la abrumadora razón en la mayoría de los casos es que los programadores como potencias de dos.

Answer 4

Tablas hash, asignación por páginas

Esto realmente ayuda para las tablas hash, porque se calcula el módulo de índice del tamaño, y si ese tamaño es una potencia de dos, el módulo se puede calcular con un simple bit a bit y o & amp; en lugar de utilizar una instrucción de clase dividida mucho más lenta que implementa el operador % .

Mirando un viejo libro Intel i386, y son 2 ciclos y div son 40 ciclos. Hoy persiste una disparidad debido a la complejidad fundamental de división mucho mayor, a pesar de que los tiempos de ciclo generales 1000 veces más rápidos tienden a ocultar el impacto de incluso las operaciones más lentas de la máquina.

También hubo un momento en que la sobrecarga de malloc se evitaba ocasionalmente con gran extensión. Las asignaciones disponibles directamente desde el sistema operativo serían (todavía lo son) un número específico de páginas, por lo que es probable que una potencia de dos aproveche al máximo la granularidad de asignación.

Y, como otros han señalado, a los programadores les gustan los poderes de dos.

Answer 5

Puedo pensar en algunas razones fuera de mi cabeza:

1. 2 ^ n es un valor muy común en todos los tamaños de computadora. Esto está directamente relacionado con la forma en que se representan los bits en las computadoras (2 valores posibles), lo que significa que las variables tienden a tener rangos de valores cuyos límites son 2 ^ n.
2. Debido al punto anterior, a menudo encontrarás el valor 256 como el tamaño del búfer. Esto se debe a que es el número más grande que se puede almacenar en un byte. Entonces, si desea almacenar una cadena junto con un tamaño de cadena, será más eficiente si la almacena como: SIZE_BYTE + ARRAY , donde el byte de tamaño le indica el tamaño de la matriz Esto significa que la matriz puede tener cualquier tamaño de 1 a 256.
3. Muchas otras veces, los tamaños se eligen en función de las cosas físicas (por ejemplo, el tamaño de la memoria que puede elegir un sistema operativo está relacionado con el tamaño de los registros de la CPU, etc.) y estos también serán un Cantidad específica de bits. Es decir, la cantidad de memoria que puede usar generalmente tendrá un valor de 2 ^ n (para un sistema de 32 bits, 2 ^ 32).
4. Puede haber beneficios de rendimiento / problemas de alineación para tales valores. La mayoría de los procesadores pueden acceder a una cierta cantidad de bytes a la vez, por lo que incluso si tiene una variable cuyo tamaño es, digamos) 20 bits, un procesador de 32 bits seguirá leyendo 32 bits, pase lo que pase. Por lo tanto, a menudo es más eficiente hacer que la variable sea de 32 bits. Además, algunos procesadores requieren que las variables se alineen a una cierta cantidad de bytes (porque no pueden leer la memoria de, por ejemplo, direcciones en la memoria que son impares). Por supuesto, a veces no se trata de ubicaciones de memoria extrañas, sino de ubicaciones que son múltiplos de 4 o 6 de 8, etc. Por lo tanto, en estos casos, es más eficiente crear buffers que siempre estén alineados .

Ok, esos puntos salieron un poco confusos. Avíseme si necesita más explicaciones, especialmente el punto 4, cuál es la OMI más importante.

Answer 6

Debido a la simplicidad (lea también costo ) de la aritmética de base 2 en electrónica: desplazamiento a la izquierda (multiplicar por 2), desplazamiento a la derecha (dividir por 2).

En el dominio de la CPU, muchas construcciones giran en torno a la aritmética de base 2. Los buses (control y datos) para acceder a la estructura de la memoria a menudo están alineados en la potencia 2. El costo de la implementación lógica en electrónica (por ejemplo, CPU) hace que la aritmética en la base 2 sea convincente.

Por supuesto, si tuviéramos computadoras analógicas, la historia sería diferente.

---

FYI: los atributos de un sistema que se encuentra en la capa X es una consecuencia directa de los atributos de la capa servidor del sistema que se encuentra debajo, es decir, la capa < X. La razón por la que estoy afirmando esto se debe a algunos comentarios que recibí con respecto a mi publicación.

Por ejemplo. las propiedades que se pueden manipular en el compilador " nivel son heredados & amp; derivado de las propiedades del sistema debajo de él, es decir, la electrónica en la CPU.

Answer 7

Iba a usar el argumento shift, pero podría pensar en una buena razón para justificarlo.

Una cosa que es agradable de un búfer que es una potencia de dos es que el manejo del búfer circular puede usar ands simples en lugar de dividir:

#define BUFSIZE 1024

++index;                // increment the index.
index &= BUFSIZE;       // Make sure it stays in the buffer.

Si no fuera una potencia de dos, sería necesaria una división. En los viejos tiempos (y actualmente en chips pequeños) eso importaba.

Answer 8

También es común que los tamaños de página sean potencias de 2.

En Linux me gusta usar getpagesize () cuando hago algo como fragmentar un búfer y escribirlo en un socket o descriptor de archivo.

Answer 9

Es un buen número redondo en la base 2. Así como 10, 100 o 1000000 son buenos números redondos en la base 10.

Si no fuera una potencia de 2 (o algo cercano como 96 = 64 + 32 o 192 = 128 + 64), entonces podría preguntarse por qué existe la precisión adicional. El tamaño redondeado no base 2 puede provenir de restricciones externas o ignorancia del programador. Querrás saber cuál es.

Otras respuestas también han señalado un montón de razones técnicas que son válidas en casos especiales. No repetiré ninguno de ellos aquí.

Answer 10

En las tablas hash, 2 ^ n facilita el manejo de colisiones de teclas de cierta manera. En general, cuando hay una colisión clave, puede hacer una subestructura, p. una lista de todas las entradas con el mismo valor hash; o encuentras otro espacio libre. Puede agregar 1 al índice de la ranura hasta que encuentre una ranura libre; pero esta estrategia no es óptima, porque crea grupos de lugares bloqueados. Una mejor estrategia es calcular un segundo número hash h2, de modo que mcd (n, h2) = 1; luego agregue h2 al índice de la ranura hasta que encuentre una ranura libre (con envoltura). Si n es una potencia de 2, encontrar un h2 que cumpla con gcd (n, h2) = 1 es fácil, todo número impar servirá.