{"thread":{"id":"44359","subject":"revisiting zstd timings","startedAt":"2016-10-23T08:06:06Z","lastAt":"2016-10-24T21:36:40Z","messageCount":2,"participants":["Jeff King","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"304725","messageId":"20161023080552.lma2v6zxmyaiiqz5@sigill.intra.peff.net","threadId":"44359","inReplyTo":null,"subject":"revisiting zstd timings","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-10-23T08:05:52Z","receivedAt":"2016-10-23T08:06:06Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"You may recall some \"what if\" timings I did recently, where I replaced\nzlib with zstd:\n\n  http://public-inbox.org/git/20160914235843.nacr54ekvl6rjipk@sigill.intra.peff.net/\n\nThe aim was that it would give us about the same compression level, but\nmuch faster inflating and deflating. My numbers there showed that yes,\ninflate is faster (which speeds up normal operations like traversals and\ndiffs), but that compression seemed to be much slower.\n\nSince then, zstd has released a new version of their zlib wrapper which\nperforms much better for our case. Basically, the prior version's\ntransparent zstd setup was not optimized well for our case of doing tons\nof small deflates. I'm cc-ing Przemyslaw Skibinski, who wrote the\nwrapper code, and who pointed me in the right direction (thanks!).\n\nI'll include the new patch at the end, but it's basically the same as\nthe old with one minor symbol change:\n\n\tdiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n\tindex 7da2fd44b0..07f45aa171 100644\n\t--- a/builtin/pack-objects.c\n\t+++ b/builtin/pack-objects.c\n\t@@ -2287,7 +2287,7 @@ static int git_pack_config(const char *k, const char *v, void *cb)\n\t \t\t\treturn config_error_nonbool(k);\n\t #ifdef USE_ZSTD\n\t \t\tif (skip_prefix(v, \"zstd\", &v)) {\n\t-\t\t\tuseZSTD(1);\n\t+\t\t\tZWRAP_useZSTDcompression(1);\n\t \t\t\t/* XXX doesn't seem to be a constant? */\n\t \t\t\tpack_compression_max = 22;\n\t \t\t}\n\nHere are the numbers I get with the newer version (see the prior email\nfor descriptions of each test, but I did run them all from scratch\nagain).\n\n    zlib\n     - pack\n     1127899484\n     - repack\n     real    4m55.099s\n     user    17m46.796s\n     sys     0m6.164s\n     - rev-list\n     real    0m27.402s\n     user    0m27.080s\n     sys     0m0.320s\n     - log -Sfoo\n     real    5m16.326s\n     user    5m13.860s\n     sys     0m2.448s\n\nThat gives us a baseline for the time of each operation, and the size of\nthe compressed pack. The rest of the values will be expressed as\npercentages from this baseline.\n\n    zstd=disabled\n     - pack\n     1127884778\n     (+0%)\n     - repack\n     real    4m49.443s\n     user    17m39.468s\n     sys     0m5.996s\n     (-1.9%)\n     - rev-list\n     real    0m27.527s\n     user    0m27.316s\n     sys     0m0.208s\n     (+0.4%)\n     - log -Sfoo\n     real    5m21.029s\n     user    5m17.704s\n     sys     0m3.308s\n     (+1.4%)\n\nTiming the wrapper making use of zlib, it produces the same output and\ntakes a slightly larger amount of time (the repack is quicker, but\nthere's quite a bit of run-to-run noise in that measurement). Nothing\nsurprising.\n\n    zstd=1\n     - pack\n     1191357029\n     (+5.6%)\n     - repack\n     real    4m8.323s\n     user    16m24.664s\n     sys     0m6.816s\n     (-15.8%)\n     - rev-list\n     real    0m25.780s\n     user    0m25.488s\n     sys     0m0.288s\n     (-5.9%)\n     - log -Sfoo\n     real    4m19.301s\n     user    4m16.488s\n     sys     0m2.796s\n     (-18%)\n\nHere's where we get interesting; zstd turned down to its lowest setting.\nAs before, the inflate step shows a nice speedup for some common\nread-only operations. The repack is much faster, and the resulting pack\nis slightly larger. We'd probably want to tune the cpu/size tradeoff for\ndeflate a bit higher.\n\n    zstd=3\n     - pack\n     1163632679\n     (+3.1%)\n     - repack\n     real    4m11.800s\n     user    16m34.260s\n     sys     0m6.788s\n     (-14.6%)\n     - rev-list\n     real    0m25.678s\n     user    0m25.376s\n     sys     0m0.296s\n     (-6.2%)\n     - log -Sfoo\n     real    4m19.902s\n     user    4m16.604s\n     sys     0m3.280s\n     (-17.8%)\n\nAnd here that is. Without spending much more CPU on deflate, we shaved\noff a few percent. The reading side remains fast (I wondered if it might\nget faster as we shrink the pack just because there are fewer bytes to\ndeal with on the input side, but it doesn't seem to really matter. And\nanyway, we're only talking a few percent of the input size).\n\n    zstd=5\n     - pack\n     1137697830\n     (+0.8%)\n     - repack\n     real    4m20.930s\n     user    16m45.844s\n     sys     0m7.100s\n     (-11.5%)\n\nTurning it up higher, we're starting to reach parity with zlib for the\npack size. And the deflate process is still faster. I stopped measuring\nthe read side, since it seemed to be remaining constant.\n\n    zstd=7\n     - pack\n     1130545314\n     (+0.2%)\n     - repack\n     real    4m28.960s\n     user    16m50.028s\n     sys     0m6.884s\n     (-8.8%)\n\n    zstd=9\n     - pack\n     1128847500\n     (+0%)\n     - repack\n     real    4m52.234s\n     user    17m22.644s\n     sys     0m7.080s\n     (-0.9%)\n\n    zstd=11\n     - pack\n     1128415787\n     (+0%)\n     - repack\n     real    5m33.187s\n     user    18m12.792s\n     sys     0m7.436s\n     (+12.9%)\n\nAnd these numbers show we can pretty much dial in the cpu/size tradeoff\nwherever we want.  Going past 9 doesn't seem to really help. I'd\nprobably leave it at 5, as 0.8% is close enough.\n\nNote that this repack scenario _isn't_ especially realistic. It's\nfinding new deltas for the whole pack from scratch, which is something\nthat isn't generally done. Instead, we'd generally deflate a small\nnumber of new objects during a repack, or perhaps when packing objects\nto serve a fetch or push. And in that case, compression would be a much\nsmaller part of the whole task (because we'd spend a lot of our time\nwriting out the already-compressed objects verbatim).\n\nSo saving 10% here really _isn't_ that interesting. I mostly wanted to\nconfirm that we could use zstd without increasing the CPU time used for\ndeflating, so that we could reap the benefits on the inflate side. Which\nis definitely the case. With these numbers, there's basically no\ndownside at all to using zstd. It's just faster to read the objects\nlater.\n\nIf we were designing git today, it seems like a no-brainer to use zstd\nover zlib. But given backwards-compatibility issues, I'm not sure.\n10-20% speedup on reading is awfully nice, but I don't think there's a\ngood way to gracefully transition, because zlib is part of the\non-the-wire format for serving objects. We could re-compress on the fly,\nbut that gets expensive (in existing cases, we can quite often serve the\nzlib content straight from disk, but this would require an extra\ninflate/deflate. At least we wouldn't have to reconstitute objects from\ndeltas, though).\n\nA transition would probably look something like:\n\n  0. The patch below, or something like it, to teach git to read both\n     zlib and zstd, and optionally write zstd. We'd probably want to\n     make this an unconditional requirement like zlib, because the point\n     is for it to be available everywhere (I assume the zstd code is\n     pretty portable, but I haven't put it to the test).\n\n  1. Another patch to add a \"zstd\" capability to the protocol. This\n     would require teaching pack-objects an option to convert zstd back\n     to zlib on the fly.\n\n     Servers which handle a limited number of updated clients can switch\n     to zstd immediately to get the benefit, and their clients can\n     handle it directly. Likewise, clients of older servers may wish to\n     repack locally using zstd to get the benefit. They'll have to\n     recompress on the fly during push, but pushes are rare than other\n     operations (and often limited by bandwidth anyway).\n\n  2. After a while, eventually flip the default to zstd=5.\n\n  3. If \"a while\" is long enough, perhaps add a patch to let servers\n     tell clients \"go upgrade\" rather than recompressing on the fly.\n\nI don't have immediate plans for any of that, but maybe something to\nthink about.\n\nHere's the patch which produce the numbers above. Build it with:\n\n  make ZSTD_PATH=/path/to/zstd\n\nwhere /path/to/zstd is a built clone of\nhttps://github.com/facebook/zstd.\n\n---\ndiff --git a/Makefile b/Makefile\nindex 1aad150b34..7e7c8c73e1 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1140,6 +1140,15 @@ else\n endif\n IMAP_SEND_LDFLAGS += $(OPENSSL_LINK) $(OPENSSL_LIBSSL) $(LIB_4_CRYPTO)\n \n+# for linking straight out of zstd build directory\n+ifdef ZSTD_PATH\n+\tLIB_OBJS += $(ZSTD_PATH)/zlibWrapper/zstd_zlibwrapper.o\n+\tBASIC_CFLAGS += -I$(ZSTD_PATH)/zlibWrapper\n+\tBASIC_CFLAGS += -I$(ZSTD_PATH)/lib -I$(ZSTD_PATH)/lib/common\n+\tBASIC_CFLAGS += -DUSE_ZSTD\n+\tEXTLIBS += $(ZSTD_PATH)/lib/libzstd.a\n+endif\n+\n ifdef ZLIB_PATH\n \tBASIC_CFLAGS += -I$(ZLIB_PATH)/include\n \tEXTLIBS += -L$(ZLIB_PATH)/$(lib) $(CC_LD_DYNPATH)$(ZLIB_PATH)/$(lib)\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 166e52c700..07f45aa171 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -62,6 +62,7 @@ static int num_preferred_base;\n static struct progress *progress_state;\n static int pack_compression_level = Z_DEFAULT_COMPRESSION;\n static int pack_compression_seen;\n+static int pack_compression_max = Z_BEST_COMPRESSION;\n \n static struct packed_git *reuse_packfile;\n static uint32_t reuse_packfile_objects;\n@@ -2281,11 +2282,17 @@ static int git_pack_config(const char *k, const char *v, void *cb)\n \t\treturn 0;\n \t}\n \tif (!strcmp(k, \"pack.compression\")) {\n-\t\tint level = git_config_int(k, v);\n-\t\tif (level == -1)\n-\t\t\tlevel = Z_DEFAULT_COMPRESSION;\n-\t\telse if (level < 0 || level > Z_BEST_COMPRESSION)\n-\t\t\tdie(\"bad pack compression level %d\", level);\n+\t\tint level;\n+\t\tif (!v)\n+\t\t\treturn config_error_nonbool(k);\n+#ifdef USE_ZSTD\n+\t\tif (skip_prefix(v, \"zstd\", &v)) {\n+\t\t\tZWRAP_useZSTDcompression(1);\n+\t\t\t/* XXX doesn't seem to be a constant? */\n+\t\t\tpack_compression_max = 22;\n+\t\t}\n+#endif\n+\t\tlevel = git_config_int(k, v);\n \t\tpack_compression_level = level;\n \t\tpack_compression_seen = 1;\n \t\treturn 0;\n@@ -2826,7 +2833,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\treuse_delta = 0;\n \tif (pack_compression_level == -1)\n \t\tpack_compression_level = Z_DEFAULT_COMPRESSION;\n-\telse if (pack_compression_level < 0 || pack_compression_level > Z_BEST_COMPRESSION)\n+\telse if (pack_compression_level < 0 || pack_compression_level > pack_compression_max)\n \t\tdie(\"bad pack compression level %d\", pack_compression_level);\n \n \tif (!delta_search_threads)\t/* --threads=0 means autodetect */\ndiff --git a/cache.h b/cache.h\nindex ed3d5dfce1..acc05720a0 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -37,7 +37,11 @@\n #define git_SHA1_Update\t\tgit_SHA1_Update_Chunked\n #endif\n \n+#ifdef USE_ZSTD\n+#include \"zstd_zlibwrapper.h\"\n+#else\n #include <zlib.h>\n+#endif\n typedef struct git_zstream {\n \tz_stream z;\n \tunsigned long avail_in;\n"},{"id":"304807","messageId":"xmqqh981too0.fsf@gitster.mtv.corp.google.com","threadId":"44359","inReplyTo":"20161023080552.lma2v6zxmyaiiqz5@sigill.intra.peff.net","subject":"Re: revisiting zstd timings","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-24T21:36:31Z","receivedAt":"2016-10-24T21:36:40Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> If we were designing git today, it seems like a no-brainer to use zstd\n> over zlib. But given backwards-compatibility issues, I'm not sure.\n> 10-20% speedup on reading is awfully nice, but I don't think there's a\n> good way to gracefully transition, because zlib is part of the\n> on-the-wire format for serving objects. We could re-compress on the fly,\n> but that gets expensive (in existing cases, we can quite often serve the\n> zlib content straight from disk, but this would require an extra\n> inflate/deflate. At least we wouldn't have to reconstitute objects from\n> deltas, though).\n>\n> A transition would probably look something like:\n>\n>   0. The patch below, or something like it, to teach git to read both\n>      zlib and zstd, and optionally write zstd. We'd probably want to\n>      make this an unconditional requirement like zlib, because the point\n>      is for it to be available everywhere (I assume the zstd code is\n>      pretty portable, but I haven't put it to the test).\n>\n>   1. Another patch to add a \"zstd\" capability to the protocol. This\n>      would require teaching pack-objects an option to convert zstd back\n>      to zlib on the fly.\n>\n>      Servers which handle a limited number of updated clients can switch\n>      to zstd immediately to get the benefit, and their clients can\n>      handle it directly. Likewise, clients of older servers may wish to\n>      repack locally using zstd to get the benefit. They'll have to\n>      recompress on the fly during push, but pushes are rare than other\n>      operations (and often limited by bandwidth anyway).\n>\n>   2. After a while, eventually flip the default to zstd=5.\n>\n>   3. If \"a while\" is long enough, perhaps add a patch to let servers\n>      tell clients \"go upgrade\" rather than recompressing on the fly.\n>\n> I don't have immediate plans for any of that, but maybe something to\n> think about.\n\nThanks for a write-up.  This is quite interesting.\n\nThanks to d98b46f8d, this does not have to impact the object naming\n;-)\n\n"}]}