ループアンローリング

標準ライブラリでも用いられているループアンローリングについて。

参考: Source Browser
（リンク先：SpanHelpers.IndexOf<T>（MemoryExtensions.IndexOf<T>からの非SIMDの分岐で行くメソッド））

みなさんご存知 ―― のような書きぶりだけれど、IndexOf<T>の内部を見たとき見かけた次第。

さて、標準ライブラリでも用いられているけれど、小規模ループだったりするとどんなもんだろう、ということで確認してみる。
ループ回数が小さいと境界チェックの関係とかで案外結果も分からないかも……？

// 通常ループ
private int RegularRoopCore(ReadOnlySpan<int> span)
{
    int sum = 0;
    foreach (var i in span) sum += i;

    return sum;
}

// アンローリング
private int UnrolledRoopCore(ReadOnlySpan<int> span)
{
    int sum = 0;
    int len = span.Length;
    int i = 0;

    // 前述 IndexOf<T>がまず8個飛びで行っているのでそれに習う
    while(len >= 8)
    {
        len -= 8;

        sum += span[i];
        sum += span[i + 1];
        sum += span[i + 2];
        sum += span[i + 3];
        sum += span[i + 4];
        sum += span[i + 5];
        sum += span[i + 6];
        sum += span[i + 7];

        i += 8;
    }

    while(len > 0)
    {
        sum += span[i++];
        len--;
    }

    return sum;
}

ループ回数 = 32768 / 1028 / 24 として BenchmarkDotNet へ。なお、.NET 7 で高速化したLINQのSum()（参考）も一緒に確認。

計測メソッドを並べているだけならので折りたたみ

private int[] array32768 = Enumerable.Range(0, 32768).ToArray();
private int[] array1024 = Enumerable.Range(0, 1024).ToArray();
private int[] array24 = Enumerable.Range(0, 24).ToArray();

[Benchmark]
public int RegularLoop32768() => RegularRoopCore(array32768);
[Benchmark]
public int UnrolledLoop32768() => UnrolledRoopCore(array32768);
[Benchmark]
public int LINQ32768() => array32768.Sum();
[Benchmark]
public int RegularLoop1024() => RegularRoopCore(array1024);
[Benchmark]
public int UnrolledLoop1024() => UnrolledRoopCore(array1024);
[Benchmark]
public int LINQ1024() => array1024.Sum();
[Benchmark]
public int RegularLoop24() => RegularRoopCore(array24);
[Benchmark]
public int UnrolledLoop24() => UnrolledRoopCore(array24);
[Benchmark]
public int LINQ24() => array24.Sum();

            Method |         Mean |        Error |     StdDev | Allocated |
------------------ |-------------:|-------------:|-----------:|----------:|
  RegularLoop32768 | 18,508.10 ns | 1,067.525 ns |  58.515 ns |         - |
 UnrolledLoop32768 | 14,248.74 ns | 8,965.244 ns | 491.415 ns |         - |
         LINQ32768 | 18,267.23 ns | 1,346.602 ns |  73.812 ns |         - |
   RegularLoop1024 |    573.84 ns |    70.756 ns |   3.878 ns |         - |
  UnrolledLoop1024 |    448.51 ns |    31.439 ns |   1.723 ns |         - |
          LINQ1024 |    580.13 ns |    60.395 ns |   3.310 ns |         - |
     RegularLoop24 |     15.21 ns |    13.469 ns |   0.738 ns |         - |
    UnrolledLoop24 |     12.17 ns |     2.250 ns |   0.123 ns |         - |
            LINQ24 |     17.15 ns |     7.923 ns |   0.434 ns |         - |

結果、省命令は正義。

標準ライブラリのメソッドで使われてるから、回数が少ないと微妙みたいのがないのは良い感じ。標準のメソッドは加えて可能な場合SIMDを用いてくれたりするし、使うだけで恩恵を受けれるのは良い。

手法そのものについては常用するようなものじゃないけれど、引き出しに。

なお、LINQが通常ループにそう後れない（というか、32768だと今回はより良い）数字だった。
これについても、標準ライブラリが頑張ってくれるのは良い感じ。

てくメモ

trivial な notes

ループアンローリング