例说局部性原理给程序带来的提升

网上介绍了很多局部性原理的好处，本文结合笔者最近的遭遇，简单的做个分享。
局部性原理就不介绍了，下面直接上例子。
我们以linux内核v6.15的函数collect_longterm_unpinnable_folios为例，这里简单的假设没有启用HVO特性。

static inline const struct page *page_fixed_fake_head(const struct page *page)
{return page;
}static __always_inline unsigned long _compound_head(const struct page *page)
{unsigned long head = READ_ONCE(page->compound_head);if (unlikely(head & 1))return head - 1;return (unsigned long)page_fixed_fake_head(page);
}#define page_folio(p)		(_Generic((p),				\const struct page *:	(const struct folio *)_compound_head(p), \struct page *:		(struct folio *)_compound_head(p)))static struct folio *pofs_get_folio(struct pages_or_folios *pofs, long i)
{if (pofs->has_folios)return pofs->folios[i];return page_folio(pofs->pages[i]);
}static unsigned long collect_longterm_unpinnable_folios(struct list_head *movable_folio_list,struct pages_or_folios *pofs)
{unsigned long i, collected = 0;struct folio *prev_folio = NULL;bool drain_allow = true;for (i = 0; i < pofs->nr_entries; i++) {struct folio *folio = pofs_get_folio(pofs, i);if (folio == prev_folio)continue;prev_folio = folio;*********
}

简单解释一下函数的逻辑，pofs是一个数组，数组长pofs->nr_entries，这个数组是由gup接口，通过页表，按PAGE_SIZE的步长，获取到的由用户传入的一个虚拟地址范围里对应的page/folio，函数collect_longterm_unpinnable_folios的目的就是筛选出这个数组里的page/folio是否属于“longterm_unpinnable”。逻辑非常简单，遍历数组，然后检查。
这个函数的逻辑没有什么问题，但现如今程序为了提升性能，会尽可能的使用大页（THP或者HUGETLBFS），当gup接口碰到这种情况的时候，pofs里相邻的page其实就是属于同一个large folio，这种情况下，就为局部性原理带来了可施展的空间。
那具体怎么施展的呢？
先放上优化后的代码，再做分析。

@@ -2296,6 +2296,31 @@ static void pofs_unpin(struct pages_or_funpin_user_pages(pofs->pages, pofs->nr_entries);}+static struct folio *pofs_next_folio(struct folio *folio,
+                struct pages_or_folios *pofs, long *index_ptr)
+{
+        long i = *index_ptr + 1;
+
+        if (!pofs->has_folios && folio_test_large(folio)) {
+                const unsigned long start_pfn = folio_pfn(folio);
+                const unsigned long end_pfn = start_pfn + folio_nr_pages(folio);
+
+                for (; i < pofs->nr_entries; i++) {
+                        unsigned long pfn = page_to_pfn(pofs->pages[i]);
+
+                        /* Is this page part of this folio? */
+                        if (pfn < start_pfn || pfn >= end_pfn)
+                                break;
+                }
+        }
+
+        if (unlikely(i == pofs->nr_entries))
+                return NULL;
+        *index_ptr = i;
+
+        return pofs_get_folio(pofs, i);
+}
+/** Returns the number of collected folios. Return value is always >= 0.*/
@@ -2303,16 +2328,12 @@ static void collect_longterm_unpinnable_struct list_head *movable_folio_list,struct pages_or_folios *pofs){
-        struct folio *prev_folio = NULL;bool drain_allow = true;
-        unsigned long i;
+        struct folio *folio;
+        long i = 0;-        for (i = 0; i < pofs->nr_entries; i++) {
-                struct folio *folio = pofs_get_folio(pofs, i);
-
-                if (folio == prev_folio)
-                        continue;
-                prev_folio = folio;
+        for (folio = pofs_get_folio(pofs, i); folio;
+                 folio = pofs_next_folio(folio, pofs, &i)) {if (folio_is_longterm_pinnable(folio))continue;

我们看原始collect_longterm_unpinnable_folios()函数循环体里面，每次循环获取一个folio，然后与prev_folio做比较，相同则跳过。
从pofs_get_folio()函数的实现就可以发现，如果我们将这个比较放进pofs_get_folio()函数函数中，那就可以省去不少if (pofs->has_folios)的判断了，由此带来的第一个优化点，就是branch数的减少，从而能够提升cache/tlb的命中率。
继续深入探究，page_folio()的实现，本质是调用了_compound_head()，这个函数的第一行就是一个READ_ONCE()，根据文章https://quant67.com/post/linux/access_once.html 我们知道，这是一个阻碍编译器做优化的函数，并且使用了READ_ONCE()之后，数据必须从内存/cache中去获取，而不能将其暂存在寄存器里，笔者简单试了一下，将这里的READ_ONCE去掉，gup接口能有不足5%的提升（可能只有1%，性能测试结果一直在波动，但是都是正向的。想想一行代码就影响了一个那么复杂的函数的性能就可怕），当然这里的READ_ONCE()肯定不能删掉，而是尝试去减少对他的调用，这是第二个优化点。
那怎么优化掉呢？本质上，也就是需要识别，下一个page，是否和当前page属于同一个large folio，那这简单，我们可以通过pfn就可以实现，large folio是一个大页，其物理地址肯定是连续的，那我们就可以看看下一个page是否属于这个物理地址范围就可以了。
从而接下来的优化就水到渠成了，我们把if (folio == prev_folio)给“搬进”函数pofs_get_folio()，只需要不断的获取下一个page的pfn，并进行判断即可。如果下一个page的pfn属于当前large folio的物理地址范围，那显然if (folio == prev_folio)成立，可以继续检查后一个page，否则，不属于这个large folio，需要做是否是longterm_unpinnable的检查。可以看到，如果我们遇到了连续的page属于同一个large folio，我们的代码就是读取数组下一个成员，并做一个简单的if判断，接着下一个成员做判断，这样不断地循环，函数的主要流程就能收缩在这两个连续的指令，这就是典型的使用局部性原理来优化程序，这是优化点三。
那么，原先代码里的if (folio == prev_folio)，就不属于局部性原理的优化了吗？当然属于，prev_folio是上一次访问的folio，如果运气好，肯定还在cache里，就可以很迅速地访问到。但是，鉴于pofs_get_folio()实现的较为复杂，有好几层调用，这样编译器可能就无法充分发挥其优化，并且，对于cache/tlb buffer比较小的cpu，可能因为较长的函数调用链，就会把本来想利用的局部性原理的数据/cache给冲掉了，从而对性能有较大的折扣。而这个优化的方案，相当于是把局部性原理做的更极致了而已。