UDN-企业互联网技术人气社区

板块导航

浏览  : 856
回复  : 0

[其它] Facebook开源新的压缩算法,性能超zlib

[复制链接]
胭脂粉的头像 楼主
发表于 2016-9-6 09:31:39 | 显示全部楼层 |阅读模式
  近日,Facebook开源了新的压缩算法Zstandard1.0。据Facebook工程师YannCollet和ChipTurner介绍,该算法是少数能够在性能和效率方面超过zlib的压缩算法之一,而后者当前是“占统治地位的标准”。FacebookZstandard利用了Collet之前所做的工作。Collet是LZ4的作者,他在2015年发布了其新算法的第一个版本。

  Facebook的基准测试显示,在任意压缩率和压缩带宽组合下,Zstandard的性能都要高于zlib。

1.jpg



  特别地,当使用标准无损压缩语料库Silesia时,相比zlib,Zstandard展示了出色的性能:

  在压缩率相同的情况下,它的速度快大约3到5倍;

  在压缩速度相同的情况下,它生成的文件小10%到15%;

  不管压缩率多大,它解压缩的速度都要快2倍;

  它的最大压缩率要高许多(大约为4比3.15)。

  Zstandard使用了有限状态熵,并以JarekDuda在熵编码非对称数字系统(ANS)方面的工作为基础。ANS的目标是“避免在压缩速度和压缩率之间进行取舍”,它既可以用于精确编码,也可以用于快速编码,并且支持数据加密。但是,从根本上讲,Zstandard之所以提供了更好的性能是因为它的多项设计和实现选择。

  zlib受一个32KB的窗口限制,而Zstandard并没有任何固有的限制,它可以更充分地利用现代环境中的内存,包括移动和嵌入式环境。

  一个新的Huffman解码器Huff0。它可以借助多个ALU并行解码符号,减少算术操作之间的依赖。

  Zstandard设法尽量减少分支,从而将因为分支预测错误而导致的、开销很高的管道清理最小化。下面的例子展示了如何在不使用分支的情况下重写while循环:

  /*经典版本*/

  while(nbBitsUsed>=8){/*每个while测试都是一个分支*/

  accumulator<<=8;

  accumulator+=*byte++;

  nbBitsUsed-=8;

  }

  /*无分支版本*/

  nbBytesUsed=nbBitsUsed>>3;

  nbBitsUsed&=7;

  ptr+=nbBytesUsed;

  accumulator=read64(ptr);

  对于差别只有几个字节的序列,重复码建模极大地改善了压缩。

  Zstandard是使用C语言编写的。它既是一个命令行工具,也是一个库。它提供了20多个压缩级别,让用户可以根据具体可用的硬件、待压缩的数据和待优化的瓶颈进行仔细地调整。Facebook建议开始时使用默认级别3。该级别适合大多数情况。然后,可以尝试9以下的级别,合理地平衡速度和空间,或者使用更高的级别获得更高的压缩率,而20以上的级别则适合那些你不关心压缩速度的情况。

  对于Zstandard的未来版本会带来什么特性,Collet和Turner也提供了一些信息,其中包括支持多线程,以及可以提供更快压缩速度和更高压缩率的新的压缩级别。

  Zstandard是继苹果的ZLFSE和谷歌的Brotli之后的又一个开源压缩算法。ZLFSE和Brotli都是开源的,每一种算法都针对特定的应用场景进行了优化:Brotli似乎为实现Web资产和AndroidAPK的高压缩率进行了优化,而LZFSE的目标是,在压缩率相同的情况下,提供比zlib更快的压缩速度和更低的电量消耗。

文章来源:InfoQ
文章作者: Sergio De Simone

相关帖子

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部