for文でキャッシュライン効果の確認

キャッシュラインとは(GPT-4o)

キャッシュラインは、コンピュータのメモリとキャッシュメモリ間のデータ転送単位です。キャッシュメモリは、CPUの処理速度と主メモリ（RAM）のアクセス速度のギャップを埋めるために設計された、高速なメモリです。キャッシュラインの概念は、このキャッシュメモリがどのようにデータを効率的に管理するかを理解するうえで重要です。

キャッシュラインの基本概念

• データ転送の単位:

  • キャッシュは、データを小さい単位で転送するよりも、一度にまとまったブロックとしてメモリからロードして、より効率的にアクセスする仕組みです。このブロックの単位がキャッシュラインです。

• 一般的なサイズ:

  • 通常、キャッシュラインは32、64、または128バイトのサイズです。現代の多くのシステムでは、64バイトが一般的に使われています。この大きさは、キャッシュのサイズ、アーキテクチャ、および設計方針に依存します。

• 局所性の原則:

  • プログラムは、時間的局所性と空間的局所性の特性を持つ傾向があります。時間的局所性とは、最近アクセスされたデータが近い将来にもアクセスされる可能性が高いことを指します。空間的局所性とは、一度アクセスされたデータの近くにあるデータが近い将来アクセスされる可能性が高いことを指します。キャッシュラインは特にこの空間的局所性を活かしています。

• メリット:

  • キャッシュラインに沿ったデータアクセスは、キャッシュ効率を向上させ、メモリアクセスのスループットを大幅に改善します。これは、連続するデータを一度にロードすることでキャッシュミスを減らし、全体的な処理速度を上げるのに役立ちます。

• 実際の利用

  • キャッシュラインは、ソフトウェア設計およびパフォーマンスチューニングにおいて重要です。データ構造やアルゴリズムを設計する際に、キャッシュラインを意識することで、メモリアクセスの効率を改善することができます。例えば、配列へのアクセスを行う場合、連続した配列要素を処理するようにアクセスパターンを組み立てることで、キャッシュが効率的に利用されるように設計できます。

キャッシュラインを理解し活用することで、特に高性能が要求されるシステムにおいて、プログラムの実行効率を最適化することが可能となります。

---

ベンチマーク

Windows10でC#を使用して、キャッシュラインのパフォーマンス測定をしました。
C#で測定実施していますが、パフォーマンス差異は言語仕様には依存しません。

using System.Diagnostics;
using System;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace CachelineBench
{
    [ShortRunJob]
    [MinColumn, MaxColumn]
    public class Measure
    {
        PerformanceCounter cacheCounter = new PerformanceCounter("Memory", "Cache Faults/sec");
        const int Size = 1024; // 行列のサイズ
        static double[,] matrix = new double[Size, Size];
        [Benchmark]
        public void RowMajorAccess()
        {
            cacheCounter.NextValue();
            double sum = 0.0;
            for (int i = 0; i < Size; i++)
            {
                for (int j = 0; j < Size; j++)
                {
                    sum += matrix[i, j];
                }
            }
            float cacheFaults = cacheCounter.NextValue();
            Console.WriteLine($"Row Cache Faults/sec: {cacheFaults}");
        }
        [Benchmark]
        public void ColumnMajorAccess()
        {
            cacheCounter.NextValue();
            double sum = 0.0;
            for (int j = 0; j < Size; j++)
            {
                for (int i = 0; i < Size; i++)
                {
                    sum += matrix[i, j];
                }
            }
            float cacheFaults = cacheCounter.NextValue();
            Console.WriteLine($"Column Cache Faults/sec: {cacheFaults}");
        }
    }
    internal class Program
    {
        static void Main()
        {
            var summary = BenchmarkRunner.Run<Measure>();
            Console.ReadKey();
        }
    }
}

測定結果

行優先アクセスの平均実行時間は列優先アクセスの約10%となりました。

Method	Mean	Error	StdDev	Min	Max
RowMajorAccess	2.872 ms	2.041 ms	0.1119 ms	2.743 ms	2.943 ms
ColumnMajorAccess	26.863 ms	13.824 ms	0.7577 ms	26.026 ms	27.502 ms

二次元配列は一般的に行優先で格納されているため、キャッシュラインを効果的に使えます。
アドレス = ベースアドレス + (列番号 × 列の長さ + 行番号)

2x2配列:
[a00 a01]
[a10 a11]

メモリ配置:
a00 -> a01 -> a10 -> a11

※コード