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

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

#### キャッシュラインの基本概念
* データ転送の単位:
    * キャッシュは、データを小さい単位で転送するよりも、一度にまとまったブロックとしてメモリからロードして、より効率的にアクセスする仕組みです。このブロックの単位がキャッシュラインです。  
* 一般的なサイズ:
    * 通常、キャッシュラインは32、64、または128バイトのサイズです。現代の多くのシステムでは、64バイトが一般的に使われています。この大きさは、キャッシュのサイズ、アーキテクチャ、および設計方針に依存します。
* 局所性の原則:
    * プログラムは、時間的局所性と空間的局所性の特性を持つ傾向があります。時間的局所性とは、最近アクセスされたデータが近い将来にもアクセスされる可能性が高いことを指します。空間的局所性とは、一度アクセスされたデータの近くにあるデータが近い将来アクセスされる可能性が高いことを指します。キャッシュラインは特にこの空間的局所性を活かしています。

* メリット:
    * キャッシュラインに沿ったデータアクセスは、キャッシュ効率を向上させ、メモリアクセスのスループットを大幅に改善します。これは、連続するデータを一度にロードすることでキャッシュミスを減らし、全体的な処理速度を上げるのに役立ちます。
* 実際の利用
    * キャッシュラインは、ソフトウェア設計およびパフォーマンスチューニングにおいて重要です。データ構造やアルゴリズムを設計する際に、キャッシュラインを意識することで、メモリアクセスの効率を改善することができます。例えば、配列へのアクセスを行う場合、連続した配列要素を処理するようにアクセスパターンを組み立てることで、キャッシュが効率的に利用されるように設計できます。

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

------------------------

### ベンチマーク
Windows10でC#を使用して、キャッシュラインのパフォーマンス測定をしました。  
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
```

※コード

https://github.com/pea-sys/.net-performance-experiments/tree/main/Original/CachelineBench

## 参考文献

https://www.lambdanote.com/products/cpu