Add the snappy-c compressor to lib

From: Andi Kleen <[email protected]>

This is a C port of the google snappy compressor. It has roughly comparable compression to LZO, but is significantly faster on many file types. For example it beats all other compressors on already compressed data.

I ported the original C++ code over to C and did some changes to make it better fit into the kernel. It preallocates the worst case memory consumption now. While the code being larger than lzo it is still reasonable (about 5K on x86).

Decompression needs very little memory, Compression currently 192K on 64bit and 128K on 32bit. For comparison LZO compression needs 128K on 64bit and 64K on 32bit.

[This could be lowered significantly by not preallocating for most use cases, typically the footprint is much lower. The original C++ version only allocated most of this when (rarely) needed, but this is more problematic in the kernel]

There are some minor divergences from the Linux coding standards:
in particular I kept the C++/C99 style mixed statement/declarations. This was mainly to not diverge too much from the reference C++ source, so that improvements from there can be easily ported. There are some other left overs from the google style, but very little now.

checkpatch.pl has some complaints, but they are either caused by the above or checkpatch.pl bugs (it misparsed #define foo do {} while(0))

Performance:

The compressor performs best on 64bit-LE systems, but is also quite good on 32bit. I haven't tested BE, but I don't expect that to add a lot of overhead.

Here is some performance data (32bit, Nehalem):
c/b = cycles/byte; lower numbers are better.

x86-64 executable: (compression minimally slower than qlz, but much better at decompression, lzo is left in the dust):

snappy: emacs-gtk: 11007968 b: ratio 0.38: comp 8.13 uncomp 2.65 c/b
lzo : emacs-gtk: 11007968 b: ratio 0.33: comp 12.74 uncomp 4.70 c/b
zlib1 : emacs-gtk: 11007968 b: ratio 0.27: comp 49.96 uncomp 13.14 c/b zlib3 : emacs-gtk: 11007968 b: ratio 0.26: comp 64.17 uncomp 12.33 c/b
lzf : emacs-gtk: 11007968 b: ratio 0.37: comp 9.85 uncomp 4.33 c/b
qlz : emacs-gtk: 11007968 b: ratio 0.34: comp 7.51 uncomp 6.28 c/b
fastlz: emacs-gtk: 11007968 b: ratio 0.37: comp 10.73 uncomp 4.97 c/b

Compressed data (beats everything else):

snappy: udev-151.tar.gz: 634842 b: ratio 1.00: comp 0.99 uncomp 0.33 c/b
lzo : udev-151.tar.gz: 634842 b: ratio 1.00: comp 41.44 uncomp 0.66 c/b
zlib1 : udev-151.tar.gz: 634842 b: ratio 1.00: comp 116.99 uncomp 3.94 c/b zlib3 : udev-151.tar.gz: 634842 b: ratio 1.00: comp 117.68 uncomp 3.94 c/b
lzf : udev-151.tar.gz: 634842 b: ratio 1.03: comp 16.32 uncomp 1.14 c/b
qlz : udev-151.tar.gz: 634842 b: ratio 1.00: comp 10.42 uncomp 0.42 c/b
fastlz: udev-151.tar.gz: 634842 b: ratio 1.03: comp 19.35 uncomp 2.07 c/b

Text file (compression somewhat slower than qlz, but decompression much better, lzo is much worse):

snappy: manual.txt: 445343 b: ratio 0.47: comp 12.01 uncomp 3.12 c/b
lzo : manual.txt: 445343 b: ratio 0.44: comp 16.32 uncomp 7.53 c/b
zlib1 : manual.txt: 445343 b: ratio 0.35: comp 56.37 uncomp 15.59 c/b zlib3 : manual.txt: 445343 b: ratio 0.31: comp 73.45 uncomp 13.99 c/b
lzf : manual.txt: 445343 b: ratio 0.46: comp 13.43 uncomp 5.47 c/b
qlz : manual.txt: 445343 b: ratio 0.44: comp 9.16 uncomp 8.19 c/b
fastlz: manual.txt: 445343 b: ratio 0.46: comp 14.22 uncomp 7.28 c/b

As you can see snappy is a good all-around compressor.

On 64bit the compression is even faster and beats everything else easily:

snappy: emacs-gtk: 11007968 b: ratio 0.38: comp 4.90 uncomp 2.65 c/b
lzo : emacs-gtk: 11007968 b: ratio 0.33: comp 11.24 uncomp 4.46 c/b
zlib1 : emacs-gtk: 11007968 b: ratio 0.27: comp 41.67 uncomp 11.13 c/b zlib3 : emacs-gtk: 11007968 b: ratio 0.26: comp 51.80 uncomp 10.54 c/b
lzf : emacs-gtk: 11007968 b: ratio 0.37: comp 8.79 uncomp 4.05 c/b
qlz : emacs-gtk: 11007968 b: ratio 0.34: comp 5.44 uncomp 5.46 c/b
fastlz: emacs-gtk: 11007968 b: ratio 0.37: comp 9.91 uncomp 4.77 c/b

On 64bit it's now nearly as fast as qlz on the text file too:

snappy: manual.txt: 445343 b: ratio 0.47: comp 7.79 uncomp 3.47 c/b
lzo : manual.txt: 445343 b: ratio 0.44: comp 15.46 uncomp 7.27 c/b
zlib1 : manual.txt: 445343 b: ratio 0.35: comp 45.79 uncomp 12.78 c/b zlib3 : manual.txt: 445343 b: ratio 0.31: comp 60.52 uncomp 11.72 c/b
lzf : manual.txt: 445343 b: ratio 0.46: comp 12.62 uncomp 5.30 c/b
qlz : manual.txt: 445343 b: ratio 0.44: comp 6.81 uncomp 7.65 c/b
fastlz: manual.txt: 445343 b: ratio 0.46: comp 13.75 uncomp 6.52 c/b

Overall it's a good alternative to lzo, with the only drawback being the somewhat higher memory use. The memory use can be fixed for most cases (e.g. some of the current buffers are only used for SG), but isn't yet in this version.

Open: it's pretty easy to add scatter-gather support since input/output is quite abstracted. This would benefit some users who could avoid temporary buffers.

---
 include/linux/snappy.h |   26 +
 lib/Kconfig            |    8 +
 lib/Makefile           |    4 +
 lib/snappy.c           | 1294 ++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 1332 insertions(+), 0 deletions(-)
 create mode 100644 include/linux/snappy.h
 create mode 100644 lib/snappy.c

new file mode 100644
index 0000000..4119803
@@ -0,0 +1,26 @@
+#ifndef _LINUX_SNAPPY_H
+#define _LINUX_SNAPPY_H 1
+
+#include <linux/types.h>
+
+/* Only needed for compression. This preallocates the worst case */
+struct snappy_env {
+	u16 *hash_table;
+	void *scratch;
+	void *scratch_output;
+};
+
+int snappy_init_env(struct snappy_env *env);
+void snappy_free_env(struct snappy_env *env);
+bool snappy_uncompress(const char *compressed, size_t n, char *uncompressed);
+int snappy_compress(struct snappy_env *env,
+		    const char *input,
+		    size_t input_length,
+		    char *compressed,
+		    size_t *compressed_length);
+bool snappy_uncompressed_length(const char *buf, size_t len, size_t *result);
+size_t snappy_max_compressed_length(size_t source_len);
+
+
+
+#endif

index 6c695ff..416dc08 100644
@@ -279,4 +279,12 @@ config CORDIC
 config LLIST
 	bool
 
+config SNAPPY
+       tristate "Snappy compressor"
+       help
+          Add the snappy compressor. This is a reasonable compressor that
+	  compresses and decompresses extremly fast. In general it's a better
+	  replacement for LZO.
+
+
 endmenu

index 3f5bc6d..e38e580 100644
@@ -117,6 +117,10 @@ obj-$(CONFIG_CORDIC) += cordic.o
 
 obj-$(CONFIG_LLIST) += llist.o
 
+CFLAGS_snappy.o += $(call cc-disable-warning, declaration-after-statement) \
+		   -DNDEBUG=1
+obj-$(CONFIG_SNAPPY) += snappy.o
+
 hostprogs-y	:= gen_crc32table
 clean-files	:= crc32table.h
 

1.7.4.4

Sounds cool, thanks Andi! Is any UBIFS user interested to try this out? I think this stuff needs some real users to make it go into mainline smoothly.

Artem.

Hi,

I could be interresting to have benchmarks on arm (or other system where UBIFS is used).

snappy use lot's of unaligned access.
They need to be emulated on pre-armv6 core.
And even in newer core (armv6+), u64 unaligned access are not supported.

Matthieu

I'm currently testing ubifs on armv5 (xscale). If you'd like me to collect some benchmark data, I'd be glad to help if you can provide a little guidance.

Thanks,
Mike

Yeah, of course it would be interesting to see. If snappy is a win-win on ARM, we should merge it.

Artem.

It might be interesting to use it for the compressed cache type in regmap as well.

For info we did some bench mark on omap3 (cortexa-8) for decompressing hibernation image.
And snappy was a lose-lose against lzf (bigger compressed result, slower to decompress) :

algo : compressed size , time to decompress
snappy (16 and 32 bits unaligned access done by hardware) : 45Mo, 3.5 s snappy (unaligned access done by software) : 45Mo, 2.50 s lzf (unalign access done by softare) : 40Mo, 2.35 s

Of course this is against one pattern (hibernation image) and benchmark should be done on other patterns.

Matthieu