[IRC-DEV] Pruebas de compresión

[Jesus Cea Avion]

El método de compresión que usamos es, básicamente,
http://www.faqs.org/rfcs/rfc1951.html. Se trata de un algoritmo de la
familia LZ77, donde los valores literales se codifican mediante HUFFMAN.
No se realizan predicciones de un literal al siguiente.

He tomado un BURST de IRC Hispano de 4 megas, con unos 24.000 usuarios.

- Comprimiendo directamente con "GZIP -9", comparable al sistema actual
  de compresión del IRCD, reducimos el BURST al 36.98%.

- Si comprimimos "NICK"->"N" y "BURST"->"B", y luego "GZIP -9", nos
  reducimos el BURST a 36.73%. Se advierte que no se gana apenas
  compresión por el simple hecho de usar comandos más cortos. Esto ya lo
  comenté en #irc-dev y por privado a varias personas: el sistema de
  compresión que utilizamos se basa en buscar repeticiones (familia
  de algoritmos LZ77). El usar comandos más cortos no ayuda
  especialmente.

- Los "timestamps" de los burst ocupan 9 bytes. Si se codifican en
  BASE64 bastarían con 6 bytes. Además, esos valores no se comprimen
  bien, porque suelen no coincidir entre nicks y canales. No obstante
  eso no tiene mucho efecto sobre los nicks, ya que antes del TIMESTAMP
  aparece un valor (distancia) fácilmente comprimible, e incluirá los
  primeros bytes del número. Los tres primeros dígitos probablemente
  se comprimirán sin problemas, por lo que la ganancia será mínima.

  Pasando los usuarios de 9 a 6 caracteres (su TS), nos da una
  reducción al 36.52%.

  En el caso de los canales esa ganancia sí que puede ser importante,
  porque lo que tiene antes no es fácilmente comprimible.

  Pasando los TS de canales de 9 a 6 caracteres, nos da una reduccion
  al 36.16%. Nada espectacular, pero es donde más hemos ganado.

  Los modos de canales se comprimen una barbaridad, ya que se remiten
  con mucha frecuencia.

El único factor interesante que queda a la hora de comprimir son los
numéricos de los usuarios. No se comprimen con eficacia porque aunque un
usuario esté en varios canales, es perfectamente posible que entre un
canal y otro haya más de 32 kbytes, por lo que ya no se detectaría.
Ahora mismo un "numeric" mide 3 o 5 bytes, según se trate de un nodo
pequeño o grande. Eso son 18 o 30 bits. Usando los 8 bits de un byte
(protocolo binario), pero cambiando SOLO el comando BURST y SOLO los
burst largos (5 bytes -> 4 bytes), en el mejor de los casos nos
ahorraríamos un BYTE por usuario y por canal. En el BURST que tengo
capturado hay 18911, en los cuales hay 115347 usuarios (muchos
repetidos). Osea, que cada usuario está en una media de 7-8 canales
(bots como SHADOW rompen un poco las estadísticas).

Ahorrando 1 byte por usuario (suponiendo que todos tienen numerics
largos) nos supondría ahorrar unos 115347 bytes, a groso modo. O un 3%.

Sumando todas las ganancias, no llegamos ni al 5% de compresión añadida
respecto al sistema actualmente en producción. No parece que por aquí se
pueda tirar mucho más, incluso eliminando, por ejemplo, las comas que
separan a los usuarios en el BURST, etc.

El sistema actual parece que no es muy mejorable sin cambiar el
algoritmo de compresión en sí. Pero algoritmos como el BZIP2 son mucho
más lentos, requieren mucha más memoria y, sobre todo, no son apropiados
para "streaming", como resulta necesario para IRC-Hispano. El paso a un
protocolo binario tampoco parece que pueda proporcionar una compresión
elevada, aunque podría reducir bastante el consumo de CPU.

GZIP -9 comprime el BURST actual al 37.02%.
BZIP2 -9 comprime el BURST actual al 29.04%.

La ganancia de BZIP2 (que usa técnicas predictivas, no diccionarios
deslizantes) es importante, pero no se ajusta a nuestras necesidades.

- 

-- 
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