buddy allocator workshop
1.0.0
Este repositorio contiene algunas pequeñas implementaciones de ejemplo de asignadores de amigos. Están diseñados para asignar memoria física, aunque podrían usarse para otros tipos de asignación, como el montón. Finalmente, el mejor desempeño se fusionará en flor.
Primero, clona el repositorio. Luego, cd en él y realice cargo +nightly run para ejecutar todos los asignadores de demostración. Por defecto, el tamaño del bloque es 4KIB y la cantidad de bloques es de 100 000, por lo que esto puede llevar un tiempo para el ejemplo de listas vinculadas. No se preocupe, en realidad no asignará nada, solo se simulan bloques de memoria. Pase -h o --help para obtener ayuda y ver el uso. Puede editar el código fuente para cambiar los tamaños de bloque MIN/MAX, etc. Para ejecutar las pruebas unitarias, ejecute cargo test . Desafortunadamente, todavía no hay puntos de referencia de carga, pero lo he comparado bastante no científicamente en mi máquina de Windows.
Probé los algoritmos cronometrando varias implementaciones utilizando el informe Builtin, asignando un Gibibyte en bloques 4KIB (con imprenta) en mi máquina de Windows. Si tiene algún otro punto de referencia para agregar, consulte contribuyendo.
(MSI CX61-2QF)
| Implementación | Tiempo | Rendimiento |
|---|---|---|
| Listas - Vectores | 2 min | ~ 8.33E-3 GIB/S |
| Listas: listas doblemente vinculadas | 25 minutos | ~ 6.66E-4 GIB/S |
| Árboles RB - Vectores | ~ 0.3s | ~ 3.33 gib/s |
| RB TRESES - Listas vinculadas individualmente | ~ 0.5s | ~ 2 gib/s |
| Árbol de mapa de bits | ~ 0.07s | ~ 14.28 GIB/S |
Nota: El rendimiento se extrapola desde el momento en que se necesitó para asignar 1 GIB en bloques 4KIB. Para las implementaciones que tengan complejidad> O (log n) (como la implementación basada en la lista ingenua), esto no será preciso: el rendimiento se reducirá a medida que se asignen más bloques. Sin embargo, esto debería ser preciso para aquellos que tienen una complejidad de O (log n) o menos.
Esta implementación mantiene una lista por orden de bloque. Es genérico sobre las listas de tipos de types utilizadas. Decidí usar dos tipos de listas: vectores ( Vec de std ) y listas doblemente vinculadas ( LinkedList , también de std ). Las listas vinculadas a menudo son apreciadas por su tiempo de empuje predecible (no se necesita una reasignación necesaria para empujar), mientras que los vectores tienen una mejor localidad de caché ya que los elementos se asignan en un bloque de memoria contiguo. Utilicé listas doblemente vinculadas porque son más rápidas para la indexación que las listas vinculadas individualmente, ya que pueden iterar desde la parte posterior o del frente, dependiendo de si el índice está más cerca del principio o el final de la lista. Decidí probar ambos para ver cuál funcionaría mejor en general.
La implementación es recursiva. Para asignar un bloque gratuito de pedido K , primero busca cualquier bloque gratuito en la lista de bloques K de pedido. No mantiene una lista gratuita. Si no se encuentra ninguno, se repite tratando de asignar un bloque de orden K + 1. Finalmente, si en ningún momento se encontraron bloques libres, cede y se aspiran. Tan pronto como uno lo divide por la mitad, eliminando el bloque original de su lista de pedidos y empujando las mitades a la lista de pedidos inmediatamente más baja. Luego devuelve el orden y el índice del primer bloque en su lista de pedidos. Puede encontrar este algoritmo en find_or_split .
Un punto de referencia rápido y no científico en mi máquina de Windows dice que tardó alrededor de dos minutos en asignar un Gibibyte completo (1024^3 bytes). Noté pausas de Split Second de vez en cuando cuando tuvo que reasignar todo el vector para empujar un elemento.
stdUn punto de referencia similar dice que tardó veinticinco minutos en asignar un gibibyte completo. Esto es más de doce veces más lento que la misma implementación con vectores. Sin embargo, esta implementación no fue optimizada para listas vinculadas, por lo que es un poco injusta. A diferencia de la implementación con los vectores, no noté ninguna pausa, pero la asignación gradualmente se volvió cada vez más lenta.
Podemos concluir que, aunque las listas doblemente vinculadas en teoría son más rápidas para empujar que los vectores, todavía eran 12 veces más lentas que los vectores. Esto podría deberse a que la implementación estaba ligeramente a favor de los vectores (mucha indexación), o porque los vectores tenían una localidad de caché más alta y, por lo tanto, experimentaron menos fallas de caché, mientras que las listas vinculadas experimentan fallas en caché altas, ya que tienen elementos alocados individualmente de mono.
Esta implementación mantiene un árbol rojo-negro (de intrusive_collections ) para todos los bloques y una lista gratuita para cada pedido. Las listas gratuitas se implementaron para STD's Vec e intrusive_collections 's SinglyLinkedList . Elegí una lista vinculada individualmente, ya que no habría habido ningún beneficio real en la vinculación doble: el único método que se habría beneficiado (de manera insignificante) es FreeList::remove , pero esto siempre se llama como máximo en el segundo elemento en esta lista gratuita, por lo que no hay ningún punto real en la optimización de esto. El árbol rojo-negro que el montón asigna individualmente cada nodo, lo que empeora la eficiencia del caché, pero a diferencia de BTreeSet / BTreeMap de std , su búsqueda es O(log n) , mientras que std usa una búsqueda lineal, que no es O(log n) (puede leer sobre esto aquí). Sin embargo, los árboles de std no se asignan individualmente los nodos, por lo que la localidad de caché es mejor. Decidí que aunque esto era cierto, ya que un asignador de amigos debe lidiar con un número increíblemente grande de bloques, era más importante tener un algoritmo de búsqueda más eficiente.
La implementación es recursiva. Para asignar un bloque gratuito de pedido K , primero busca cualquier bloque gratuito en la lista gratuita de los bloques K de pedidos. Si no se encuentra ninguno, se repite tratando de asignar un bloque de orden K + 1. Finalmente, si en ningún momento se encontraron bloques libres, cede y se aspiran. Tan pronto como uno lo divide por la mitad, eliminando el bloque original del árbol e insertando las mitades, empujando sus direcciones a la lista gratuita relevante. Luego devuelve un cursor que apunta al primer bloque. Puede encontrar este algoritmo en find_or_split . En la capa de recursión más externa (la función que realmente llama a la función recursiva find_or_split ), el bloque devuelto se marca como se usa y se elimina de la lista gratuita.
El uso de vectores como listas gratuitas tomaron ~ 0.3s para asignar un GIB completo. Esto es ~ 0.2s más rápido que las listas vinculadas como la versión de listas gratuitas. Esto probablemente se deba a que los vectores tienen una mejor localidad de caché.
El uso de listas vinculadas como listas gratuitas tomaron ~ 0.5s para asignar un GIB completo. Consulte los vectores como la sección de listas gratuitas anteriores.
Esta implementación fue 400x más rápida que la implementación basada en la lista ingenua (en el mejor de los casos, utilizando vectores como listas gratuitas). Esto probablemente se deba a los árboles rojos-negro que tienen operaciones O(log n) en todos los ámbitos, más rápido que las búsquedas, insertos y elimina vectores o listas vinculadas.
Esta implementación no es estrictamente un mapa de bits, per se, pero es una modificación de un sistema de mapa de bits. Esencialmente, cada bloque en el árbol almacena el orden más grande (completamente fusionado) en algún lugar debajo de él. Por ejemplo, un árbol que es gratuito con 4 pedidos se ve así:
3
2 2
1 1 1 1
0 0 0 0 0 0 0 0
Si asignamos un bloque de orden 0, parece esto (t es t aken):
2
1 2
0 1 1 1
T 0 0 0 0 0 0 0
Se implementa como una matriz aplanada, donde para un árbol como
1
2 3
La representación es 1; 2; 3 . Esto tiene la buena propiedad de que si usamos índices que comienzan en 1 (es decir, índices y no compensaciones), entonces el índice del niño izquierdo de cualquier índice dado es 2 * index , y el niño derecho es simplemente 2 * index + 1 . El padre es floor(index / 2) . Debido a que todas estas operaciones funcionan con 2S, podemos usar un cambio de bits eficiente para ejecutarlas ( index << 1 , (index << 1) | 1 e index >> 1 ).
Podemos hacer una búsqueda binaria para encontrar el bloque A que esté libre del orden deseado. Primero, verificamos si hay bloques del pedido deseado gratuito al verificar el bloqueo de la raíz. Si lo hay, verificamos si el niño izquierdo tiene suficiente gratis. Si lo hace, entonces revisamos nuevamente que es niño izquierdo, etc. Si el niño izquierdo de un bloque no tiene suficientes bloques libres, simplemente usamos su hijo derecho. Sabemos que el niño correcto debe tener suficiente libre, o el bloqueo raíz no es válido.
Esta implementación fue muy rápida. En mi computadora, solo tomó ~ 0.07 asignar 1GIB. Sin embargo, lo he visto funcionar hasta 0.04s en mi computadora: el rendimiento fluctúa un poco. Supongo que esto tiene que ver con la carga de CPU.
Esta implementación no tiene muy buena localidad de caché, ya que los niveles se almacenan lejos del otro, por lo que un bloqueo principal puede estar muy lejos de su hijo. Sin embargo, todo lo demás sigue siendo muy rápido, por lo que está compuesto por. También es O (log n), pero prácticamente es tan rápido que esto realmente no importa. Como referencia: la asignación de 8GIB me tomó 0.6s, pero lo he visto funcionar mucho mejor en> 150 ms en la computadora portátil de @Gegy1000.
Si tiene algo que agregar (como una edición al ReadMe u otra implementación o punto de referencia) ¡Siéntase libre de enviar una solicitud de extracción! También puede crear un problema. Si solo quieres chatear, siéntete libre de hacerme ping en la discordia de óxido (Restioson#8323).
