Compress Objects, Not Cache Lines: An Object-Based Compressed Memory Hierarchy

2019 ASPLOS

Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems

现有的缓存和主存压缩技术将数据压缩在固定大小的小块中，通常是缓存线。这些技术适用于以数组为主的程序。然而，它们在基于对象的程序中是无效的，因为对象不能整齐地落入固定大小的块中，并且具有更不规则的布局。

提出了第一个为基于对象的应用程序设计的压缩内存层次结构，包括Zippads(基于对象的压缩内存层次结构)和COCO(跨对象压缩算法)。

Zippads的性能始终优于最先进的压缩内存层次结构:在数组和对象主导的混合工作负载上，Zippads实现了1.63倍的高压缩比，并提高了17%的性能

---

不同压缩技术在BTree上的对比：

图3a展示了4-entry B-tree节点在内存的布局。

图3b应用LCP技术对BTree进行压缩，每2^6也就是64B行被压缩到32B的块，但是有的块是可以被压缩到少于32B的，但是由于LCP的设计，使得剩下的空间被浪费。压缩比只有10%

图3c表示对对象进行压缩的内存布局。压缩的对象连续存储，没有剩余的空间。

压缩比1.56倍

图3d表示跨对象压缩，不存储Entry的所有对象，而是存储一个基本对象(条目[0])。对于其他Entry对象，我们只存储这些对象与基对象之间的差异字节(∆Entry)。这进一步减少了图3c的占用空间，实现了更高的压缩比1.95×。

Baseline system:Hotpads

Zippads和COCO压缩对象而不是缓存行。因此，它们更适合基于对象的内存层次结构，而不是传统的缓存层次结构。作者在Hotpads(最近的一个基于对象的层次结构)之上实现对象的压缩。

Hotpads 内存层次系统的例子：

图5里面：Hotpads结构有三个pad(可以有任意数量)

每个pad的结构如图6，大部分空间用于数据数组，数据数组作为循环缓冲区进行管理。数据数组有一个连续的已分配对象块，后面跟着一个空闲空间块。

pad有两个辅助结构:(i)标准标签(canonical tag, c-tag)数组，这是一个解耦的标签存储，部分访问使用它来查找对象的常驻副本;以及(ii)元数据数组(metadata array)，跟踪存储在数据数组中的对象的信息。

Hotpad 的一个例子：

Zippads: An object-based compressed memory hierarchy

Zippads利用Hotpads

(i)操作和压缩对象而不是缓存行，

(ii)通过直接指向压缩对象，避免了传统压缩主存中的额外间接级别。

Zippads不确定所使用的压缩算法，可以使用BDI或FPC等传统算法，但与COCO压缩算法一起工作效果最好。

图8表示了一个Zippads层次结构的例子：

最后一级pad和主内存是压缩的，而核心专用L1和L2pad则不是，Zippads直接在压缩级别之间传输压缩对象

Zippads旨在紧凑地存储压缩对象，它们之间没有未使用的空间，以最大化压缩比。对象从未压缩存储移动到压缩存储有两个原因：对象的新移动和脏回写。

对象的新移动：对象在L1 pad开始它们的生命周期，当它们最近没有被使用时，它们被移动到更大的pad和主内存中。Hotpads利用这个对象流来最小化死对象的影响，尽快收集它们。Zippads进一步利用这一点来促进压缩:对象在其生命周期开始时是未压缩的，当它们不再使用时，它们被逐出到最后一层垫中并在那里进行压缩。

脏回写：一个对象可以达到压缩级别，然后被取到L1中并进行修改。这个对象最终会被写回压缩层。这个级别的其他对象可能有指向这个对象的指针，所以Zippads不能简单地移动它。

如果新的大小更小，这将浪费一些空间，而这些空间将被闲置

如果压缩对象的新大小大于旧大小，则不能将对象存储在旧位置。我们称之为溢出。Zippads为压缩对象分配一个新位置(通常使用碰撞指针分配)。因为指向旧位置的其他指针可能仍然存在，所以Zippads将旧位置转换为转发池:它将新指针存储在对象的第一个word中。通过增加一个转发找到原来的对象

COCO: Cross-object-compression algorithm

Zippads适用于任何压缩算法。但是每个对象内部的冗余是有限的

COCO(Cross-Object COmpression，跨对象压缩)，一种利用跨对象冗余的新压缩算法。COCO实现了高压缩比，实现成本低

COCO是一种差分压缩算法:它通过只存储与不同基本对象不同的字节来压缩对象。

压缩对象格式包含三个元素：

1. 基本对象id，一个整数(在我们的实现中是32位)，唯一标识基本对象

2. 一个diff位图，对象的每个字节有一个位。如果对象的第i个字节与基对象不同，则设置第i位。

3. 一个字节差异字符串，包含与基对象不同的字节。

COCO压缩对象的例子图13：压缩的对象在第一个和第二个单词中有相同的值，在第三个单词中有2个字节的差异，在第四个单词中有4个字节的差异。因此，除了头文件外，压缩对象只存储六个不同的字节。

Evaluation

我们在基于数组和基于对象的混合工作负载上评估Zippads和COCO。

Zippads提高了压缩比：

Zippads减少了主内存流量：减少了到主存取数据的数量

Zippads提高了系统性能：