handyfloss

Update: this script has been superseded by ChopZip

Introduction

I discovered the [[Lempel-Ziv-Markov chain algorithm|LZMA]] compression algorithm some time ago, and have been thrilled by its capacity since. It has higher compression ratios than even [[bzip2]], with a faster decompression time. However, although decompressing is fast, compressing is not: LZMA is even slower than bzip2. On the other hand, [[gzip]] remains blazing fast in comparison, while providing a decent level of compression.

More recently I have discovered the interesting pbzip2, which is a parallel implementation of bzip2. With the increasing popularity of multi-core processors (I have a quad-core at home myself), parallelizing the compression tools is a very good idea. pbzip2 performs really well, producing bzip2-compatible files with near-linear scaling with the number of CPUs.

LZMA being such a high performance compressor, I wondered if its speed could be boosted by using it in parallel. Although the [[Lempel-Ziv-Markov chain algorithm|Wikipedia article]] states that the algorithm can be parallelized, I found no such implementation in Ubuntu 9.04, where the utility provided by the lzma package is exclusively serial. Not finding one, I set myself to produce it.

About plzma.py

Any compression can be parallelized as follows:

1. Split the original file into as many pieces as CPU cores available
2. Compress (simultaneously) all the pieces
3. Create a single file by joining all the compressed pieces, and call the result “the compressed file”

In a Linux environment, these three tasks can be carried out easily by split, lzma itself, and tar, respectively. I just made a [[Python (programming language)|Python]] script to automate these tasks, called it plzma.py, and put it in my web site for anyone to download (it’s GPLed). Please notice that plzma.py has been superseded by chopzip, starting with revision 12, whereas latest plzma is revision 6.

I must remark that, while pbzip2 generates bzip2-compatible compressed files, that is not the case with plzma. The products of plzma compression must be decompressed with plzma as well. The actual format of a plzma file is just a TAR file containing as many LZMA-compressed chunks as CPUs used for compression. These chunks, once decompressed individually, can be concatenated (with the cat command) to form the original file.

Benchmarks

What review of compression tools lacks benchmarks? No matter how inaccurate or silly, none of them do. And neither does mine :^)

I used three (single) files as reference:

• molekel.tar – a 108 MB tar file of the (GPL) [[Molekel]] 5.0 source code
• usr.bin.tar – 309 MB tar file of the contens of my /usr/bin/ dir
• hackable.tar – a 782 MB tar file of the hackable:1 [[Debian]]-based distro for the [[Neo FreeRunner]]

The second case is intended as an example of binary file compression, whereas the other two are more of a “real-life” example. I didn’t test text-only files… I might in the future, but don’t expect the conclusions to change much. The testbed was my Frink desktop PC (Intel Q8200 quad-core).

The options for each tool were:

• gzip/bzip/pbzip2: compression level 6
• lzma/plzma: compression level 3
• pbzip2/plzma: 4 CPUs

Compressed size

The most important feature of a compressor is the size of the resulting file. After all, we used it in first place to save space. No matter how fast an algorithm is, if the resulting file is bigger than the original file I wouldn’t use it. Would you?

The graph below shows the compressed size ratio for compression of the three test files with each of the five tools considered. The compressed size ratio is defined as the compressed size divided by the original size for each file.

This test doesn’t surprise much: gzip is the least effective and LZMA the most one. The point to make here is that the parallel implementations perform as well or badly as their serial counterparts.

If you are unimpressed by the supposedly higher performance of bzip2 and LZMA over gzip, when in the picture all final sizes do not look very different, recall that gzip compressed molekel.tar ~ 3 times (to a 0.329 ratio), whereas LZMA compressed it ~ 4.3 times (to a 0.233 ratio). You could stuff 13 LZMAed files where only 9 gzipped ones fit (and just 3 uncompressed ones).

Compression time

However important the compressed size is, compression time is also an important subject. Actually, that’s the very issue I try to address parallelizing LZMA: to make it faster while keeping its high compression ratio.

The graph below shows the normalized times for compression of the three test files with each of the five tools considered. The normalized time is taken as the total time divided by the time it took gzip to finish (an arbitrary scale with t(gzip)=1.0).

Roughly speaking, we could say that in my setting pbzip2 makes bzip2 as fast as gzip, and plzma makes LZMA as fast as serial bzip2.

The speedups for bzip2/pbzip2 and LZMA/plzma are given in the following table:

The performance of plzma is nowere near pbzip2, but I’d call it acceptable (wouldn’t I?, I’m the author!). There are two reasons I can think of to explain lower-than-linear scalability. The first one is the overhead imposed when cutting the file into pieces then assembling them back. The second one, maybe more important, is the disk performance. Maybe each core can compress each file independently, but the disk I/O for reading the chunks and writing them back compressed is done simultaneously on the same disk, which the four processes share.

Update: I think that a good deal of under-linearity comes from the fact that files of equal size will not be compressed in an equal time. Each chunk compression will take a slightly different time to complete, because some will be easier than others to compress. The program waits for the last compression to finish, so it’s as slow as the slowest one. It is also true that pieces of 1/N size might take more than 1/N time to complete, so the more chunks, the slower the compression in total (the opposite could also be true, though).

Decompression times

Usually we pay less attention to it, because it is much faster (and because we often compress things never to open them again, in which case we had better deleted them in first place… but I digress).

The following graph shows the decompression data equivalent to the compression times graph above.

The most noteworthy point is that pbzip2 decompresses pbzip2-compressed files faster than bzip2 does with bzip2-compressed files. That is, both compression and decompression benefit from the parallelization. However, for plzma that is not the case: decompression is slower than with the serial LZMA. This is due to two effects: first, the decompression part is still not parallelized in my script (it will soon be). This would lead to decompression speeds near to the serial LZMA. However, it is slower due to the second effect: the overhead caused by splitting and then joining.

Another result worth noting is that, although LZMA is much slower than even bzip2 to compress, the decompression is actually faster. This is not random. LZMA was designed with fast uncompression time in mind, so that it could be used in, e.g. software distribution, where a single person compresses the original data (however painstakingly), then the users can download the result (the smaller, the faster), and uncompress it to use it.

Conclusions

While there is room for improvement, plzma seems like a viable option to speed up general compression tasks where a high compression ratio (LZMA level) is desired.

I would like to stress the point that plzma files are not uncompressable with just LZMA. If you don’t use plzma to decompress, you can follow the these steps:

Como siempre, estoy al límite de la novedad, comentando noticias que tienen casi un mes de antigüedad. En fin.

El caso es que quería comentar algunas perlas de la ignorante ministra esta, González-Sinde. De las muchas estupideces cosas que ha dicho, me referiré concretamente a las recogidas en esta noticia en El País.

Vayamos por partes:

La ministra de Cultura, Ángeles González Sinde, ha señalado que que no hay que generalizar y acusar a todos los internautas de hacer descargas ilegales […]

¡Y dale con “descagas ilegales”! A ver cuando nos enteramos de que bajar de Internet material con copyright NO ES ILEGAL en España, cuando se hace sin ánimo de lucro. Y en caso de que ese material se redistribuya comercialmente, el delito está en el lucro con dicha redistribución, no en la descarga en sí. La legislación española defiende los derechos de los ciudadanos (como debe), y no permite que unos pocos controlen lo que podemos acceder con interés no comercial.

González-Sinde, en declaraciones a RNE, […] s eha[sic] mostrado partidaria de la última propuesta de la Coalición de Creadores, que representa la industria cultural, de perseguir las páginas webs de enlaces en lugar de a los usuarios.

¿”Coalición de Creadores”? ¿”industria cultural”? ¿A nadie se le revuelve el estómago con tales conceptos?

En cuanto a lo de perseguir páginas de enlaces, en vez de a usuarios, es de traca. Todos sabemos que los periódicos, por poner un ejemplo, sacan una parte substancial de sus ingresos de los anuncios de servicios de prostitución ténuemente encubierta, y sin embargo el Gobierno no se pronuncia sobre ello. No oigo a nadie decir que si la prostitución es ilegal, también lo deben ser los anuncios de ella. Sin embargo con las descargas el caso es al revés: son legales (léase la Ley, ministra), pero sí se quiere perseguir no su ejecución, sino su facilitación mediante anuncios e información. ¿Cuál puede ser la diferencia? La de siempre: el dinero. Mientras los anuncios de negocios que explotan la libertad sexual de mujeres engrosan las arcas de ciertos empresarios, las descargas que hacen accesible recursos culturales y de ocio a millones de ciudadanos merman las arcas de ciertos otros empresarios. Ante esto me pregunto, ¿por qué el beneficio o perjuicio económico de ciertos empresarios puede afectar las decisiones de un Gobierno, que como tal se debe a los ciudadanos y a la aplicación de la Ley y la Justicia? También uno se pregunta por qué ganar dinero anula la injusticia de la prostitución; y a la inversa, por qué perderlo anula los beneficios sociales de una cultura, un conocimiento y un ocio más accesibles. Es decir, el dinero es la medida moral de si algo es bueno o malo, ¿no?

“[…] es importante aplicar las leyes que ya tenemos y cerrar esas 200 páginas que se lucran poniendo a disposición material audiovisual que han conseguido ilícitamente”

No sé a qué páginas se refiere. ¿Quizá se refiere a páginas que extraen música de CDs comerciales y las venden on-line como si fuera suya? Si es así, aplaudo la decisión. Es inaceptable que haya gente lucrándose del esfuerzo y el arte de los artistas.

Ahora bien, aparte de las discográficas, no conozco de sitios que hagan eso. Sí que hay sitios que hacen accesible material con copyright mediante tecnologías p2p, pero todos los casos que conozco son gratuitos. Los usuarios suben el material que desean compartir, y otros lo bajan, sin más beneficio que el quid pro quo.

Ha matizado que el problema de la música en Internet es el poco peso de las canciones y su rapidez para copiarlas.

Esta es la perla que ha desatado mi indignación, el detonante de este post.

Primero, es falso, ya que cuando la velocidad de las redes era inferior la gente también compartía ficheros. No existe un tamaño de canciones tan grande, o una línea tan lenta (dentro de límites razonables), que la gente elija no bajar música o películas.

Pero, en segundo lugar, es un razonamiento increíblemente perverso, y más aún viniendo de una ministra de Cultura. El que archivos de contenido audiovisual sea susceptible de compresión manteniendo la calidad es un avance tecnológico de tremendo valor. Nos permite almacenar más en menor espacio, permite hacer más copias de seguridad en empresas que trabajen con ello, permite su transmisión más rápida y eficiente, permite streaming de vídeo en tiempo real sobre canales que por su lentitud no lo permitirían de otra manera… En cuanto a la velocidad de las redes de comunicación, es otro avance más importante todavía. Permite la comunicación en tiempo real entre dos puntos cualquiera del globo, permite la colaboración internacional (por ejemplo en ciencia), permite la transmisión y réplica de información vital en tiempo razonable, permite las copias de seguridad remota en tiempo razonable, permite que grabe un vídeo de mi hijo jugando con un sonajero, y se lo haga llegar a sus abuelos antes de que el niño vaya a la universidad se haga futbolista.

Lo que esta tiparraca insinúa es que la tecnología nos permite hacer cosas maravillosas, y por ello es mala. Está predicando un oscurantismo encubierto.

Para la ministra, las críticas que le hacen por esa regulación demuestra “lo virulento o apasionado de esas reacciones demuestra que es un tema importante en la vida de la gente. La red ha cambiado la manera de participar en sociedad”.

No señora. Las criticas indican lo que toda crítica indica: que la gente no está de acuerdo con usted. La gente no “reacciona apasionadamente” simplemente. La gente se indigna con usted y con sus declaraciones. Así de simple.

En el caso concreto de la piratería musical, ha subrayado que “me preocupan mucho los efectos colaterales [de] que no se recupere la inversión cuando inviertes en cultura que se puede copiar”.

El argumento de siempre: la cultura se muere, porque al ser gratis acceder a ella, nadie querrá producirla.

Los defensores de tal despropósito cometen la falacia de dar por sentado que vender trozos de plástico con canciones dentro es la única manera de obtener beneficios de la producción musical. Al igual que las radios nos dan el coñazo con lo último del Loco del Canto, Bisbal y demás para “promocionarlos” y que luego la gente compre más discos y vaya más a conciertos, sigue siendo válido decir que el distribuir la música por Internet hace más visibles a muchos artistas (claro que no necesariamente a los que las mafias discográficas quieren) y les permite obtener ganancias de conciertos a los que no iría nadie si no se hubieran bajado su música de internet. No veo a nadie quejarse de que emitir música gratis por la radio puede dañar la venta de discos. Al fin y al cabo, si puedo oir la canción por la radio (y hasta puedo grabarla de la misma, si quiero), ¿para qué iba a comprarme el CD? Al contrario, las discográficas se dejan una pasta gansa en untar a las radios para que emitan lo que ellas (las discográficas) quieren que la gente oiga.

Pero incluso aunque las descargas bajen ventas de discos y los artistas reciban menos beneficios. Aunque los artistas en ciernes desistan de dedicarse a ese mundo por no tener aliciente económico (otra falacia, suponer que la única motivación para producir cultura es la económica). Aunque la producción de Cultura se resintiese por las descargas… Eso no justifica el daño causado a la ciudadanía por medidas injustamente restrictivas.

Denostando e intentando impedir las descargas de material con copyright se está haciendo un daño enorme a la sociedad. Para empezar, se está intentando mantener un modelo de negocio obsoleto, lo cual en una sociedad capitalista es inaceptable. La venta de soportes físicos para material audiovisual no es un fin en sí mismo, sino un medio para poder hacer llegar el producto a los consumidores de la manera más eficiente posible. No puede hacerse que un grupo toque para un cliente cada vez que el cliente desee, pero sí puede grabarse en un medio físico, y que luego el cliente use ese medio para reproducir la música. Como la producción y distribución de estos medios físicos cuesta dinero, es lógico cobrar por ello, como por cualquier bien (el medio físico) o servicio (la distribución). Pero observemos que se cobra por la producción y transporte del medio físico. En cuanto haya otros medios de eliminar la brecha entre músico y su audiencia, los medios físicos (CDs, etc) quedarán obsoletos, y el pago por ellos será insostenible. Ese punto ya ha llegado.

El segundo daño a la sociedad es de un ámbito moral. Se nos dice que “no se puede tener todo gratis” (yo me sigo preguntando ¿por qué no? ¿No es eso el objetivo de toda sociedad, que sus ciudadanos estén satisfechos sin tener que “pagar” por ello? ¿Es que la vida tiene que ser un “valle de lágrimas” por narices?), pero además se nos dice que “compartir está mal”. Este es un mesaje nefasto. Compartir es lo que hace, por ejemplo, que la Wikipedia sea lo que es. Compartir es lo que hace posible que haya gente que pueda ver series extranjeras subtituladas en el idioma propio por terceros desinteresados. Lo bueno del p2p y la Web 2.0 es que el material que consumimos mejora (y muchas veces se crea) con la aportación desinteresada de otros. A cambio, yo soy ese “otro desinteresado” para ellos, aportando mi ancho de banda y espacio en disco duro para que puedan ver una peli que yo ya he visto. O perdiendo mi tiempo para corregir un artículo en la Wikipedia, o comentar algo en un blog y aportar algo a su autor, o contestar a alguna pregunta en un foro sobre un tema que domino. Desde mi punto de vista, es una pena que en el mundo no funcione todo así. Que no podamos aportar desinteresadamente aquello que sabemos y podemos hacer, y beneficiarnos de la misma aportación de otros. Y para un reducto en que sí se puede, ¿nos lo quieren quitar? ¿Quieren criminalizar el ser buen vecino?

Accessing both Windows [[File Allocation Table|FAT]] and [[NTFS]] file systems from Linux is quite easy, with tools like [[NTFS-3G]]. However (following with the [[shit|MS]] tradition of making itself incompatible with everything else, to thwart competition), doing the opposite (accessing Linux file systems from Windows) is more complicated. One would have to guess why (and how!) [[closed source software|closed]] and [[proprietary software|proprietary]] and technically inferior file systems can be read by free software tools, whereas proprietary software with such a big corporation behind is incapable (or unwilling) to interact with superior and [[free software]] file systems. Why should Windows users be deprived of the choice over [[JFS (file system)|JFS]], [[XFS]] or [[ReiserFS]], when they are free? MS techs are too dumb to implement them? Or too evil to give their users the choice? Or, maybe, too scared that if choice is possible, their users will dump NTFS? Neither explanation makes one feel much love for MS, does it?

This stupid inability of Windows to read any of the many formats Linux can use gives rise to problems for not only Windows users, but also Linux users. For example, when I format my external hard disks or pendrives, I end up wondering if I should reserve some space for a FAT partition, so I could put there data to share with hypothetical Windows users I could lend the disk to. And, seriously, I abhor wasting my hardware with such lousy file systems, when I could use Linux ones.

Anyway, there are some third-party tools to help us which such a task. I found at least two:

• Ext2IFS
• ext2fsd

I have used the first one, but as some blogs point out (e.g. BloggUccio), ext2fsd is required if the [[inode]] size is bigger than 128 B (256 B in some modern Linux distros).

Getting Ext2IFS

It is a simple exe file you can download from fs-driver.org. Installing it consists on the typical windows next-next-finish click-dance. In principle the defaults are OK. It will ask you about activating “read-only” (which I declined. It’s less safe, but I would like to be able to write too), and something about large file support (which I accepted, because it’s only an issue with Linux kernels older than 2.2… Middle Age stuff).

Formatting the hard drive

In principle, Ext2IFS can read ext2/ext3 partitions with no problem. In practice, if the partition was created with an [[inode]] size of more than 128 bytes, Ext2IFS won’t read it. To create a “compatible” partition, you can mkfs it with the -I flag, as follows:

I found out about the 128 B inode thing from this forum thread [es].

Practical use

What I have done, and tested, is what follows: I format my external drives with almost all of it as ext3, as described, leaving a couple of gigabytes (you could cut down to a couple of megabytes if you really want to) for a FAT partition. Then copy the Ext2IFS_1_11a.exe executable to that partition.

Whenever you want to use that drive, Linux will see two partitions (the ext3 and the FAT one), the second one of which you can ignore. From Windows, you will see only a 2GB FAT partition. However, you will be able to open it, find the exe, double-click, and install Ext2IFS. After that, you can unplug the drive and plug it again…et voilà, you will see the ext3 partition just fine.