[IRC-DEV] Cerrando temas pendientes: Logs: el "Slab Allocator"

[Jesus Cea Avion]

Jesus Cea Avion wrote:
> 
> http://www.argo.es/%7Ejcea/wikis/irc-dev/logs/200310/irc-dev-20031015

Hoy "alguien" me ha pillado por Jabber/XMPP (JID: jcea at jabber.org) y me
ha pedido detalles de cómo implementar un "slab allocator". El trabajo a
bajo nivel, vaya.

La idea es que cada "cargador" contiene 32 (o 64) "slots". Para marcar
si un "slot" está libre u ocupado, se usa un bit. Así, necesitaríamos
32/64 bits para el mapa de libre/ocupado de cada "cargador".

Ver si un cargador está lleno o vacío es trivial, pero determinar un
"slot" libre de forma eficiente no lo es. No nos vale usar un bucle
desplazando un bit por pasada, por ejemplo. Tampoco queremos usar una
tabla, porque es previsible que no esté en caché y con las CPUs actuales
las operaciones son muy rápidas comparadas con el acceso a memoria.

Algunos ejemplos de algoritmos:

Supongamos que el mapa de asignación tiene 32 bits y se almacena en un
"unsigned", y que un bit a "1" marca el "slot" como libre.

* Dame un "slot" libre:

 1. Si el mapa es 0, no hay nada libre. Esta comprobación es necesaria.

 2. Si el mapa es 0xFFFFFFFF, están los 32 "slots" libres. Esta
comprobación NO es necesaria, pero puede ganarse eficiencia si este caso
es "habitual".

 3. En otro caso hacemos lo siguiente:

   mapa = mapa OR (mapa >> 1)
   mapa = mapa OR (mapa >> 2)
   mapa = mapa OR (mapa >> 4)
   mapa = mapa OR (mapa >> 8)
   mapa = mapa OR (mapa >> 16)

   slot_libre=(mapa >> 1) + 1

 Otro algoritmo posible sería:

  slot_libre=((mapa AND (mapa-1)) XOR mapa

* Contar el número de "slots" libres:

  mapa = (mapa >> 1 and 0x55555555) + (mapa AND 0x55555555)
  mapa = (mapa >> 2 and 0x33333333) + (mapa AND 0x33333333)
  mapa = (mapa >> 4 and 0x0f0f0f0f) + (mapa AND 0x0f0f0f0f)
  mapa = (mapa >> 8 and 0x00ff00ff) + (mapa AND 0x00ff00ff)
  mapa = (mapa >> 16) + (mapa AND 0x0000ffff)

Así, con el primer algoritmo obtenemos un valor de 32 bits con un UNO en
la posición de un "slot" libre. Con la segunda rutina, aplicado al valor
anterior MENOS UNO, obtenemos el número del slot en cuestión.

Bajo GCC hay un par de funciones "intrínsecas", y no portables a otros
compiladores, que nos dan lo que necesitamos directamente. Están
documentadas en
<http://gcc.gnu.org/onlinedocs/gcc-3.4.0/gcc/Other-Builtins.html#Other%20Builtins>

En concreto las que nos interesan son "__builtin_popcount()" y
"__builtin_ffs()", por ejemplo, y sus variantes para "long" y "long
long".

Viendo el código generado sobre SPARC, el rendimiento debe ser inferior
a los algoritmos reseñados. En x86 también hay un bucle en las funciones
intrínsecas...

Se lo podrían haber currado un poco más :-p

Otra opción que yo haría sería "decodificar" una vez el "cargador" a la
cabeza de los cargadores con "slots" libres para así solo tener que
hacer esta operación una vez por cargador, no una por "malloc", al menos
mientras quede algo libre en el mismo.

-- 
Jesus Cea Avion                         _/_/      _/_/_/        _/_/_/
jcea at argo.es http://www.argo.es/~jcea/ _/_/    _/_/  _/_/    _/_/  _/_/
                                      _/_/    _/_/          _/_/_/_/_/
PGP Key Available at KeyServ   _/_/  _/_/    _/_/          _/_/  _/_/
"Things are not so easy"      _/_/  _/_/    _/_/  _/_/    _/_/  _/_/
"My name is Dump, Core Dump"   _/_/_/        _/_/_/      _/_/  _/_/
"El amor es poner tu felicidad en la felicidad de otro" - Leibniz