数据压缩算法：对于程序员来说，这项新技术特别实用

雷锋网注：【 图片来源： MIT CSAIL 所有者：MIT CSAIL 】

数据压缩技术之一，就是通过消除冗余来释放存储容量，提高计算速度，或是带来其他好处。

但是，在目前的计算机系统中，访问主存的成本很大。因此，在存储器中使用数据压缩技术有助于减少提取数据的频率和数量，提高设备的性能。

一般来说，现代设备以固定大小的块（chunk）来进行管理和传输数据，传统的压缩技术必须在这些块上运行。然而，软件存储数据并不使用固定大小的块，而是使用对象（object），这种数据结构可以容纳各种类型的数据，它的规模的也可大可小。

因此，传统的数据压缩技术很难处理对象。

首次亮相

本周ACM国际编程语言和操作系统架构支持会议上发表的一篇论文中，MIT的研究人员描述了第一种“跨存储层次压缩对象”的技术。这种技术可以降低内存使用率，同时也可以提高性能和效率。

研究人员用改进后的 Java 虚拟机做了实验，结果表明，与传统压缩方法相比，这种新技术可以多压缩两倍的数据，还减少了一半的内存使用率。

CSAIL的研究生Po-An Tsai是这篇论文的第一作者，她表示，“我们试图提出一种新的存储层次结构，能够进行对象压缩，因为大部分现代编程语言都是以对象的形式管理数据的。”

合著者Daniel Sanchez是计算机科学和电子工程专业的教授，同时也是CSAIL的研究员，他补充道，“所有计算机系统都将从这项新技术中受益，程序的运行将变得更快，因为不再受制于内存带宽。”

由于Java、 Python 和 Go 这些现代编程语言以对象的形式管理数据，所以对于程序员来说，这项新技术特别实用。在不久的将来，我们就会看到设备拥有更快的速度，或者能在同一时间运行更多应用程序。

存在局限

传统的结构以块的形式将数据存储到缓存存储器（Cache）中，最近受访的块会上升到这里（上图黄色层），虽然这里空间小，但访问速度快。而旧块则会下降，最终回到主存（上图蓝色层）中。

虽然这种数据之间的调动十分灵活，但成本也不低。

在数据调动的过程中，如果目标数据不再Cache中，Cache就要访问主存，并大范围搜索数据的地址。入下图所示，Cache访问主存并返回的时间大约是100~300个周期。耗时太长，存在局限性。

推陈出新

Sanchez发现了传统模式的局限性，他思考着，“既然现代编程语言中数据管理的单位是对象，那我们为什么不建一个处理对象的存储层次结构呢？”

于是，研究人员在之前的传统存储层次结构上进行改进，便于直接处理对象。

1.Hotpad/pad

在去年10月发表的一篇论文中，研究人员详细介绍了一个名为Hotpad的系统，可以用来存储对象。由于这个系统的各个层次之间关系紧密，也可称为pad。

这整个结构基于一个芯片存储器，效率高且不需要进行复杂的搜索，因为程序可以直接引用整个pad所有对象的位置。新分配的，或最近引用的对象，以及它们指向的对象，都停留在速度最快的层次，以便快速访问。

当这个层被填满时，系统就会开始“筛查”。筛查的过程会保留最近引用的对象，但较旧的对象会被下放到较慢的层，除此之外，系统还会删除不再有用的对象，以释放空间。随后，每个对象的指针都会更新，指向新对象的位置。通过这种方式，程序访问对象的成本比通过缓存层来搜索要低得多。

2.Zippad

研究人员还设计了一种名为Zippad的技术，利用Hotpad系统来压缩对象。当对象第一次在较快的层次启动时，它们会被解压，但当它们被下放时又会被压缩。另一方面，跨级别的所有对象都指向那些压缩的对象，这使得它们很容易恢复到更快的级别，并且比传统技术下存储得更紧凑。

3.基础对象

与以前的技术相比，这种新技术还提供了更多的压缩机会，因为以前的技术仅限于在固定大小的块中查找冗余。首先，该算法会选取几个具有代表性的对象作为基础对象。然后，只要有新对象加入，算法就会对比基础对象和新对象，然后把它们的之间不同的数据存储起来。

卡耐基梅隆大学电子和计算机工程助教Brandon Lucia十分赞赏这个新技术，因为它利用编程语言的特性，更好地进行压缩工作。他说：“这项工作的有趣之处在于，它利用对象的抽象性让内存压缩更有效，从而使系统更快、更高效，具有新的计算机体系结构特性。”

雷锋网注：本文编译自 MIT CSAIL ，部分内容来自网络，由雷锋网 (公众号：雷锋网) 整合

雷锋网版权文章，未经授权禁止转载。详情见 转载须知 。