我们在《SVM的Shrink技巧》中提到，为了提高SVM的训练速度，从算法上我们可以收缩矩阵维数。我们也可以通过计算机系统中的缓存机制（Caching），从数据存取的角度来减少训练时间。从现在最流行的SVM工具包libSVM的C++源码中，我们可以见识到这种机制的巧妙设计。
libSVM中所采用的缓存机制是为了对核函数矩阵，也是消耗空间最大的数据结构进行存储：
\[K_{l\times l}=\begin{bmatrix} \phi(\pmb x_1)^2&\phi(\pmb x_1)\phi(\pmb x_2)&\cdots&\phi(\pmb x_1)\phi(\pmb x_l)\\ \phi(\pmb x_2)\phi(\pmb x_1)&\ddots&&\vdots\\ \vdots&&\ddots\\ \phi(\pmb x_l)\phi(\pmb x_1)&\cdots&&\phi(\pmb x_l)^2 \end{bmatrix}\]由于训练过程需要频繁使用核函数，所以相比于用一次计算一次，我们当然会选择对有限的核函数的值存储起来供以后使用，这就会带来存储空间不够用的问题，考虑$K$是对称矩阵，那我们也需要存储$\frac{l(l-1)}2$个数据，当数据量到达10000时，我们需要约200 MB去存储它们（一个浮点数最少4字节），shrink方法已经让数据量大幅度减少，但我们还是希望能从软硬件上加快速度，因此引入缓存机制：用一段不大的内存空间去存储使用最频繁的核函数，借助程序的局部性原理让数据存取速度提升。
libSVM用一个缓存类（Cache）实现内存管理，包括申请、释放等。类定义如下（svm.cpp）：
//
// Kernel Cache
//
// l is the number of total data items
// size is the cache size limit in bytes
//
class Cache {
public:
Cache(int l, long int size);
~Cache();
// request data [0,len)
// return some position p where [p,len) need to be filled
// (p >= len if nothing needs to be filled)
int get_data(const int index, Qfloat **data, int len);
void swap_index(int i, int j);
private:
int l;
long int size;
struct head_t {
head_t *prev, *next; // a circular list
Qfloat *data;
int len; // data[0,len) is cached in this entry
};
head_t *head;
head_t lru_head;
void lru_delete(head_t *h);
void lru_insert(head_t *h);
};
注：这里的QFloat是在svm.h中定义的一个和平：
#define QFloat float
观察其中的数据结构和函数变量命名，可以发现libSVM使用一个遵循LRU（最近最少用）缓存机制的循环双向链表来管理数据。
在Cache类中，l和size不难理解，分别表示样本数和用户指定分配的内存。值得注意的是，在svm.cpp中有这样的语句：
class SVC_Q {
SVC_Q(const svm_problem &prob, const svm_parameter ¶m, const schar *y_)
: Kernel(prob.l, prob.x, param) {
...
cache = new Cache(prob.l, (long int)(param.cache_size * (1 << 20)));
...
}
...
};
也就是说用户输入的存储空间参数是以MB为单位的。
此处的head_t结构除了双向链表必备的头尾指针外，还有一个float类型的指针和长度参数len，说明一个head_t节点指向一列长度为len的数组数据。
在构造函数中，我们可以看到head和lru_head的区别和联系：
Cache::Cache(int l_, long int size_) : l(l_), size(size_) {
head = (head_t *)calloc(l, sizeof(head_t)); // initialized to 0
size /= sizeof(Qfloat);
size -= l * sizeof(head_t) / sizeof(Qfloat);
size = max(size, 2 * (long int)l); // cache must be large enough for two columns
lru_head.next = lru_head.prev = &lru_head;
}
可以发现head_t指向的是长度为l的数组，也就是存储全部数据的地方，形成一个l行len列的表格。此时的size单位是字节，因为一个QFloat是四字节，上面代码的第3、4行分别将其改为可存储的数据个数（第3行），减去head_t所占空间（第四行）；最后要保证数据量至少要容纳$2l$条数据（第5行），个人认为一个$l$来存特征向量，另一个$l$用来存储标签（2021.7.14更新：并不是，其实是因为支持向量回归问题中，每个样本$x_i$对应两个拉格朗日乘子$\alpha_i$和$\alpha_i^*$）。从第六行可以看出lru_head是用来实现LRU算法的双向循环链表，由于初始无数据，所以自己指向自己。
析构函数就是简单的链表和指针的空间释放：
Cache::~Cache() {
for (head_t *h = lru_head.next; h != &lru_head; h = h->next) {
free(h->data);
}
free(head);
}
然后是实现双向链表基本功能：删除和插入节点的函数：
void Cache::lru_delete(head_t *h) {
// delete from current location
h->prev->next = h->next;
h->next->prev = h->prev;
}
void Cache::lru_insert(head_t *h) {
// insert to last position
h->next = &lru_head;
h->prev = lru_head.prev;
h->prev->next = h;
h->next->prev = h;
}
要注意的是LRU算法模拟的是FIFO队列，删除的是队首元素，所以新插入的元素应该从尾部插入。
接下来是共有接口get_data，用于从数据集里取数据：
int Cache::get_data(const int index, Qfloat **data, int len) {
head_t *h = &head[index];
if (h->len) {
lru_delete(h);
}
int more = len - h->len;
if (more > 0) {
// free old space
while (size < more) {
head_t *old = lru_head.next;
lru_delete(old);
free(old->data);
size += old->len;
old->data = 0;
old->len = 0;
}
// allocate new space
h->data = (Qfloat *)realloc(h->data, sizeof(Qfloat) * len);
size -= more;
swap(h->len, len);
}
lru_insert(h);
*data = h->data;
return len;
}
函数参数不难理解：从第l个样本取len个数据，并将其赋到data上。如果对应的head[index]被分配了内存，我们将其从链表中断开；如果内存不够用，就将其内存释放，等到内存够用了再重新分配。此时的缓存属于“未命中”，因此我们得从“内存”中将所需数据移入缓存中；由于我们刚对数据进行存取，因此我们将其从队尾插入，符合LRU规则；最后是将数据付给data，供用户使用。
最后一个函数接口，swap_index(int i, int j)，用于将head[i]和head[j]的内容对换，个人理解用处是为了在存取旧数据后改变旧数据的LRU优先级。
void Cache::swap_index(int i, int j) {
if (i == j) return;
if (head[i].len)
lru_delete(&head[i]);
if (head[j].len)
lru_delete(&head[j]);
swap(head[i].data, head[j].data);
swap(head[i].len, head[j].len);
if (head[i].len)
lru_insert(&head[i]);
if (head[j].len)
lru_insert(&head[j]);
if (i > j) swap(i, j);
for (head_t *h = lru_head.next; h != &lru_head; h = h->next) {
if (h->len > i) {
if (h->len > j)
swap(h->data[i], h->data[j]);
else {
// give up
lru_delete(h);
free(h->data);
size += h->len;
h->data = 0;
h->len = 0;
}
}
}
}
swap_index将待交换的两个节点从链表中分离，然后交换并回到链表。但笔者并不理解后面遍历链表的操作目的，尤其是将数组的index和数据的长度len进行比较。
据说Cache的存在使得libSVM的训练速度提升了20倍，说明编程技术对算法实现的重要性。我们这里只提到了数据在Cache的存取，但并没有涉及核函数缓存，是因为笔者也在探索中。只看到有人提到调用get_data后，程序会计算
并将其填入QFloat **data中。
