[C#/.NET] Fill遅すぎ問題

C#(.NET Core)環境に於いて、配列を任意の整数で埋め尽くす処理(`Fill`)が想像より遅かったので、各種方法を比較してみました。

ゼロクリアするのであれば、手段は色々あります(極端な話`new`する)ので対象外です。
また整数以外も扱いません。

## TL;DR

`Span`の`Fill`を使え。
`char`を速くしたければ、最適化したコードを書け。

## 環境

``` ini
BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19042
AMD Ryzen 7 3700X, 1 CPU, 16 logical and 8 physical cores
.NET Core SDK=3.1.400-preview-015203
  [Host]        : .NET Core 2.1.13 (CoreCLR 4.6.28008.01, CoreFX 4.6.28008.01), X64 RyuJIT
  .NET Core 2.1 : .NET Core 2.1.13 (CoreCLR 4.6.28008.01, CoreFX 4.6.28008.01), X64 RyuJIT
  .NET Core 3.1 : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT
```

.NET Core 3.1と2.1の両方で実行しましたが、大差がないので以降は3.1の結果のみを記載します。

## 計測手法

BenchmarkDotNetを使います。
配列のサイズは、`byte`の場合は`8`、`char`の場合は`4`から始めて10倍させて行きます。
`int`/`long`も視野に入れバイト数としては同じになるようにこのサイズにしましたが、`char`までで挫折しました。

## `byte`の場合

`0xFF`で埋めたい時ありますよね。

### 手法

| グラフ上での表記    | 説明                                                                                                                                                    |
| ------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------- |
| ForLoop             | 一番シンプルな`for`を使った方法です。                                                                                                                                |
| ArrayFill           | .NET Core 2から追加されている`Array.Fill`メソッドを使います。比較的新しいメソッドなので期待していました。(過去形)                                                         |
| CrtMemset           | 実行環境に依存してしまいますが、Cランタイムの`memset`をP/Invokeを呼び出します。<br>恐らくかなり最適化されているはずです。                                                                    |
| SpanFill            | `Span<byte>.Fill`を使います。                                                                                                                                                        |
| UnsafeFill          | `unsafe`コンテキストで、ForLoopと同様です。<br>以前は半ば常識的に「配列に対する操作が遅ければ`unsafe`コンテキストでコードを書く」という最適化がありましたが、JITが進歩したので最近はやらない手法です。 |
| UnsafeInit          | `System.Runtime.CompilerServices.Unsafe`クラスに`memset`相当の`InitBlock`があるのでそれを使います。                                                     |
| UnsafeInitUnaligned | `System.Runtime.CompilerServices.Unsafe`クラスの`InitBlockUnaligned`を使用します。                                                                      |

### native intに整列されている場合の結果
(算術的平均値,ns単位)

| Method              |     8 |     80 |     800 |     8000 |     80000 |
| ------------------- | ----: | -----: | ------: | -------: | --------: |
| ArrayFill           | 6.791 | 42.335 | 391.853 | 3,796.60 | 37,916.30 |
| CrtMemset           | 9.097 | 10.014 |   19.81 |  125.399 |  1,224.16 |
| ForLoop             | 5.893 | 41.825 | 401.916 | 3,854.56 | 40,224.29 |
| SpanFill            | 5.701 |  8.072 |   14.94 |   120.31 |  1,218.88 |
| UnsafeFill          | 4.642 |  28.31 | 230.496 | 2,226.19 | 22,422.91 |
| UnsafeInit          | 3.157 |  5.118 |   13.52 |  118.895 |  1,213.85 |
| UnsafeInitUnaligned | 3.156 |  5.089 |  13.546 |  118.907 |  1,219.88 |

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/124276/e43db3e2-142c-e0f5-be77-204496352316.png)

- `Array.Fill`に失望しますね。ForLoopと大差ありません。全く最適化されていないのでしょう。
- `unsafe`コンテキストは思ったより早くならないですね。
- それ以外は大差ありませんが、小さいサイズも視野に入れた最適化するなら`Unsafe.InitBlock`ですね。面倒なら`Span<byte>.Fill`が最も手軽です。

### native intに整列されていない場合の結果

通常、配列を作成すればnative int(x64であれば8)に揃ったアドレスに配置されるされるはずです。
(根拠はありません。)
したがって、SIMDなども行いやすく、一番良い結果がでると想像しています。
整列されていない領域に対して行った場合も見てみましょう。

| Method              |     8 |     80 |     800 |     8000 |     80000 |
| ------------------- | ----: | -----: | ------: | -------: | --------: |
| ArrayFill           | 7.047 | 41.946 | 385.586 | 3,787.28 | 38,310.79 |
| CrtMemset           | 9.116 | 10.239 |  19.985 |   125.36 |  1,224.70 |
| ForLoop             |  5.95 | 41.574 | 400.755 | 3,848.20 | 40,529.76 |
| SpanFill            | 5.654 |  8.057 |  14.761 |  120.282 |  1,221.64 |
| UnsafeFill          |  4.21 | 25.201 | 228.644 | 2,220.78 | 22,444.06 |
| UnsafeInit          | 3.171 |  5.073 |  13.729 |  119.307 |  1,216.36 |
| UnsafeInitUnaligned |  3.16 |  5.039 |  13.781 |  119.715 |  1,231.68 |

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/124276/e94c3ab6-519b-8522-c002-e2aba165e1e5.png)

整列されている場合と変わらないですね。

## `char`の場合

「あ」とかで埋めることは無いかもしれませんが、空白(0x0020)で埋めたいことはありますよね。

### 手法

`byte`の場合に試した手法は引数が`byte`に固定されている事が多いので、`char`(またはそれ以上のサイズの整数)では適用できません。

- Cランタイム(msvcrt.dll)は`wmemset`がエクスポートされていません。
- `Unsafe.InitBlock`も引数が`byte`です

| グラフ上での表記                | 説明                                                                                                          |
| ------------------------------- | ------------------------------------------------------------------------------------------------------------- |
| ForLoop                         | `byte`の場合と同じ                                                                                            |
| SpanFill                        | `Span<char>.Fill`を使います。                                                                                              |
| ArrayFill                       | `byte`の場合と同じ                                                                                            |
| UnsafeFill                      | `byte`の場合と同じ                                                                                            |
| UnsafeWrite                     | UnsafeFillと似ていますが、領域に書き込む時に`Unsafe.WriteUnaligned`を使っています。                           |
| SpanFillAsNativeInt             | 要素がnative intの配列として扱い、まとめて`Span.Fill`します。セットする値はnative intに合わせて倍化させます。 |
| UnsafeFillAsNativeIntAggressive | SpanFillAsNativeIntと似ていますが、整列されてない位置でない場合の考慮を入れています。                         |


### native intに整列されている場合の結果

| Method                          |      4 |     40 |     400 |     4000 |     40000 |
| ------------------------------- | -----: | -----: | ------: | -------: | --------: |
| ArrayFill                       |  4.042 | 16.989 | 150.009 | 1,453.72 | 14,246.69 |
| ForLoop                         |  3.636 | 21.536 | 204.639 | 1,973.49 | 20,440.59 |
| SpanFill                        |  5.171 | 13.493 |  96.808 |  958.507 |  9,475.19 |
| SpanFillAsNativeInt             |  5.743 |  7.366 |  27.219 |  245.084 |  2,406.38 |
| UnsafeFill                      |   2.97 | 13.875 | 120.151 | 1,124.27 | 11,280.51 |
| UnsafeFillAsNativeIntAggressive | 14.457 | 15.925 |  34.435 |   255.51 |  2,412.59 |
| UnsafeWrite                     |  3.449 | 14.731 | 134.332 | 1,260.53 | 12,518.17 |

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/124276/24b47c4e-42ee-99f1-1f44-8de8111998e3.png)

ArrayFill / ForLoop / UnsafeFill は `byte`と同じ傾向ですね。
SpanFillは`byte`の時ほど良くはありませんが、手軽な割には優秀です。
SpanFillAsNativeInt / UnsafeFillAsNativeIntAggressive は、サイズが小さいとオーバーヘッドが大きいですが、最適化しているだけあって速いですね。

### nanative intに整列されていない場合の結果

| Method                          |      4 |     40 |     400 |     4000 |     40000 |
| ------------------------------- | -----: | -----: | ------: | -------: | --------: |
| ArrayFill                       |   4.24 | 17.016 | 147.027 | 1,437.69 | 14,161.09 |
| ForLoop                         |  4.338 | 21.711 | 213.703 | 1,960.62 | 20,485.48 |
| SpanFill                        |  5.187 | 12.721 |  97.965 |  950.592 |  9,591.40 |
| SpanFillAsNativeInt             |    5.8 |  7.382 |  34.033 |    309.7 |  3,172.02 |
| UnsafeFill                      |  2.974 | 13.909 | 121.698 | 1,109.99 | 11,350.63 |
| UnsafeFillAsNativeIntAggressive | 14.454 |  17.03 |  41.157 |  251.983 |  2,431.65 |
| UnsafeWrite                     |  3.431 | 14.789 | 135.019 | 1,249.34 | 12,676.44 |

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/124276/c8fb76ae-c621-6b8f-0034-d9cdef2947d0.png)

x64で実行しているせいか整列されている場合と大きく差はないですが、SpanFillAsNativeInt は落ちてますね。
UnsafeFillAsNativeIntAggressive はnative intに合わせる考慮が入っているので落ちていません。

ARMとかだと結果が変わるかもしれません。

## ベンチマークコード全文

長いので折りたたみ

<details><div>

```csharp
using BenchmarkDotNet.Running;
using BenchmarkDotNet.Configs;
using System;
using System.Runtime.InteropServices;
using System.Runtime.CompilerServices;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Jobs;
using System.Reflection;
using System.Collections.Generic;
using System.Linq;

namespace FillBenchMark
{
    internal class BenchmarkConfig : ManualConfig
    {
        public BenchmarkConfig()
        {
            AddJob(Job.ShortRun.
                WithWarmupCount(1).
                WithIterationCount(1).
                WithLaunchCount(5));
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            _ = new FillBytesBenchmarks();
            var testee = new FillCharsBenchmarks();
            testee.UnsafeFillAsNativeIntAggressive("", new ArraySegment<char>(new char[44], 2, 4));
            _ = BenchmarkSwitcher.FromAssembly(Assembly.GetExecutingAssembly()).Run();
        }
    }

    [GroupBenchmarksBy(BenchmarkLogicalGroupRule.ByParams)]
    [SimpleJob(runtimeMoniker: RuntimeMoniker.NetCoreApp21)]
    [SimpleJob(runtimeMoniker: RuntimeMoniker.NetCoreApp31)]
    public unsafe class FillBytesBenchmarks
    {
        byte value;
        public IEnumerable<object[]> ArrayPatterns()
        {
            yield return new object[] { "    8,a", new ArraySegment<byte>(new byte[8]) };
            yield return new object[] { "   80,a", new ArraySegment<byte>(new byte[80]) };
            yield return new object[] { "  800,a", new ArraySegment<byte>(new byte[800]) };
            yield return new object[] { " 8000,a", new ArraySegment<byte>(new byte[8000]) };
            yield return new object[] { "80000,a", new ArraySegment<byte>(new byte[80000]) };
            yield return new object[] { "    8,u", new ArraySegment<byte>(new byte[8 + 1], 1, 8) };
            yield return new object[] { "   80,u", new ArraySegment<byte>(new byte[80 + 1], 1, 80) };
            yield return new object[] { "  800,u", new ArraySegment<byte>(new byte[800 + 1], 1, 800) };
            yield return new object[] { " 8000,u", new ArraySegment<byte>(new byte[8000 + 1], 1, 8000) };
            yield return new object[] { "80000,u", new ArraySegment<byte>(new byte[80000 + 1], 1, 80000) };
        }

        public FillBytesBenchmarks()
        {
            var r = new Random();
            value = (byte)r.Next();

            foreach (var segment in ArrayPatterns())
            {
                var expect = new byte[((ArraySegment<byte>)segment[1]).Count];
                expect.AsSpan().Fill(value);

                if (!ForLoop("", (ArraySegment<byte>)segment[1]).AsSpan().SequenceEqual(expect))
                {
                    throw new Exception();
                }
                if (!CrtMemset("", (ArraySegment<byte>)segment[1]).AsSpan().SequenceEqual(expect))
                {
                    throw new Exception();
                }
                if (!SpanFill("", (ArraySegment<byte>)segment[1]).AsSpan().SequenceEqual(expect))
                {
                    throw new Exception();
                }
                if (!ArrayFill("", (ArraySegment<byte>)segment[1]).AsSpan().SequenceEqual(expect))
                {
                    throw new Exception();
                }
                if (!UnsafeInit("", (ArraySegment<byte>)segment[1]).AsSpan().SequenceEqual(expect))
                {
                    throw new Exception();
                }
                if (!UnsafeInitUnaligned("", (ArraySegment<byte>)segment[1]).AsSpan().SequenceEqual(expect))
                {
                    throw new Exception();
                }
                if (!UnsafeFill("", (ArraySegment<byte>)segment[1]).AsSpan().SequenceEqual(expect))
                {
                    throw new Exception();
                }
            }
        }

        [Benchmark(Baseline = true), ArgumentsSource(nameof(ArrayPatterns))]
        public ArraySegment<byte> ForLoop(string name, ArraySegment<byte> segment)
        {
            for (var i = 0; i < segment.Count; i++)
            {
                segment[i] = value;
            }
            return segment;
        }

        [Benchmark, ArgumentsSource(nameof(ArrayPatterns))]
        public ArraySegment<byte> CrtMemset(string name, ArraySegment<byte> segment)
        {
            fixed (byte* p = segment.Array)
            {
                NativeMethods.MemSet(p + segment.Offset, value, segment.Count);
            }
            return segment;
        }

        [Benchmark, ArgumentsSource(nameof(ArrayPatterns))]
        public ArraySegment<byte> SpanFill(string name, ArraySegment<byte> segment)
        {
            segment.AsSpan().Fill(value);
            return segment;
        }

        [Benchmark, ArgumentsSource(nameof(ArrayPatterns))]
        public ArraySegment<byte> ArrayFill(string name, ArraySegment<byte> segment)
        {
            System.Array.Fill(segment.Array, value, segment.Offset, segment.Count);
            return segment;
        }

        [Benchmark, ArgumentsSource(nameof(ArrayPatterns))]
        public ArraySegment<byte> UnsafeInit(string name, ArraySegment<byte> segment)
        {
            Unsafe.InitBlock(ref segment.Array[segment.Offset], value, (uint)segment.Count);
            return segment;
        }

        [Benchmark, ArgumentsSource(nameof(ArrayPatterns))]
        public ArraySegment<byte> UnsafeInitUnaligned(string name, ArraySegment<byte> segment)
        {
            Unsafe.InitBlockUnaligned(ref segment.Array[segment.Offset], value, (uint)segment.Count);
            return segment;
        }

        [Benchmark, ArgumentsSource(nameof(ArrayPatterns))]
        public ArraySegment<byte> UnsafeFill(string name, ArraySegment<byte> segment)
        {
            fixed (byte* begin = segment.Array)
            {
                var end = begin + segment.Count;
                for (var p = begin + segment.Offset; p < end; ++p)
                    *p = value;
            }
            return segment;
        }
    }


    [GroupBenchmarksBy(BenchmarkLogicalGroupRule.ByParams)]
    [SimpleJob(runtimeMoniker: RuntimeMoniker.NetCoreApp21)]
    [SimpleJob(runtimeMoniker: RuntimeMoniker.NetCoreApp31)]
    public unsafe class FillCharsBenchmarks
    {
        char value;

        public FillCharsBenchmarks()
        {
            var r = new Random();
            value = '\xD4D5';

            foreach (var segment in ArrayPatterns())
            {
                var expect = new char[((ArraySegment<char>)segment[1]).Count];
                expect.AsSpan().Fill(value);

                if (!ForLoop("", (ArraySegment<char>)segment[1]).AsSpan().SequenceEqual(expect))
                {
                    throw new Exception();
                }
                if (!SpanFill("", (ArraySegment<char>)segment[1]).AsSpan().SequenceEqual(expect))
                {
                    throw new Exception();
                }
                if (!ArrayFill("", (ArraySegment<char>)segment[1]).AsSpan().SequenceEqual(expect))
                {
                    throw new Exception();
                }
                if (!UnsafeFill("", (ArraySegment<char>)segment[1]).AsSpan().SequenceEqual(expect))
                {
                    throw new Exception();
                }
                if (!UnsafeWrite("", (ArraySegment<char>)segment[1]).AsSpan().SequenceEqual(expect))
                {
                    throw new Exception();
                }
                if (!SpanFillAsNativeInt("", (ArraySegment<char>)segment[1]).AsSpan().SequenceEqual(expect))
                {
                    throw new Exception();
                }
                if (!UnsafeFillAsNativeIntAggressive("", (ArraySegment<char>)segment[1]).AsSpan().SequenceEqual(expect))
                {
                    throw new Exception();
                }
            }
        }

        public IEnumerable<object[]> ArrayPatterns()
        {
            yield return new object[] { "    4,a", new ArraySegment<char>(new char[4]) };
            yield return new object[] { "   40,a", new ArraySegment<char>(new char[40]) };
            yield return new object[] { "  400,a", new ArraySegment<char>(new char[400]) };
            yield return new object[] { " 4000,a", new ArraySegment<char>(new char[4000]) };
            yield return new object[] { "40000,a", new ArraySegment<char>(new char[40000]) };
            yield return new object[] { "    4,u", new ArraySegment<char>(new char[4 + 1], 1, 4) };
            yield return new object[] { "   40,u", new ArraySegment<char>(new char[40 + 1], 1, 40) };
            yield return new object[] { "  400,u", new ArraySegment<char>(new char[400 + 1], 1, 400) };
            yield return new object[] { " 4000,u", new ArraySegment<char>(new char[4000 + 1], 1, 4000) };
            yield return new object[] { "40000,u", new ArraySegment<char>(new char[40000 + 1], 1, 40000) };
        }

        [Benchmark(Baseline = true), ArgumentsSource(nameof(ArrayPatterns))]
        public ArraySegment<char> ForLoop(string name, ArraySegment<char> segment)
        {
            for (var i = 0; i < segment.Count; i++)
            {
                segment[i] = value;
            }
            return segment;
        }

        [Benchmark, ArgumentsSource(nameof(ArrayPatterns))]
        public ArraySegment<char> SpanFill(string name, ArraySegment<char> segment)
        {
            segment.AsSpan().Fill(value);
            return segment;
        }

        [Benchmark, ArgumentsSource(nameof(ArrayPatterns))]
        public ArraySegment<char> ArrayFill(string name, ArraySegment<char> segment)
        {
            System.Array.Fill(segment.Array, value, segment.Offset, segment.Count);
            return segment;
        }

        [Benchmark, ArgumentsSource(nameof(ArrayPatterns))]
        public ArraySegment<char> UnsafeFill(string name, ArraySegment<char> segment)
        {
            fixed (char* begin = &segment.Array[segment.Offset])
            {
                var end = begin + segment.Count;
                for (var p = begin; p < end; ++p)
                    *p = value;
            }
            return segment;
        }

        [Benchmark, ArgumentsSource(nameof(ArrayPatterns))]
        public ArraySegment<char> UnsafeWrite(string name, ArraySegment<char> segment)
        {
            fixed (char* begin = &segment.Array[segment.Offset])
            {
                var N = segment.Count;
                var p = begin;
                for (var i = N; 0 < i; ++p, --i)
                    Unsafe.WriteUnaligned(p, value);
            }
            return segment;
        }

        [Benchmark, ArgumentsSource(nameof(ArrayPatterns))]
        public ArraySegment<char> SpanFillAsNativeInt(string name, ArraySegment<char> segment)
        {
            var N = segment.Count;
            if (IntPtr.Size == 4)
            {
                uint source = (uint)(value | value << 16);
                var span = MemoryMarshal.Cast<char, uint>(segment.AsSpan());
                span.Fill(source);

                var count = span.Length * sizeof(uint) / sizeof(char);
                for (var i = count; i < N; ++i)
                    segment.Array[segment.Offset + i] = value;

                return segment;
            }
            else
            {
                ulong source = ((ulong)value | (ulong)value << 16 | (ulong)value << 32 | (ulong)value << 48);
                var span = MemoryMarshal.Cast<char, ulong>(segment.AsSpan());
                span.Fill(source);

                var count = span.Length * sizeof(ulong) / sizeof(char);
                for (var i = count; i < N; ++i)
                    segment.Array[segment.Offset + i] = value;

                return segment;
            }
        }

        [Benchmark, ArgumentsSource(nameof(ArrayPatterns))]
        public ArraySegment<char> UnsafeFillAsNativeIntAggressive(string name, ArraySegment<char> segment)
        {
            fixed (char* begin = segment.Array)
            {
                var p = begin + segment.Offset;
                var rem = (uint)p % IntPtr.Size;
                var i = 0;

                if (IntPtr.Size == 4)
                {
                    switch (rem)
                    {
                        case 1 * sizeof(char):
                            p[i++] = value;
                            if (i == segment.Count)
                                goto END;
                            break;
                        case 0:
                            break;
                        default:
                            throw new ArgumentException();
                    }
                    uint source = (uint)(value | value << 16);
                    var span = new Span<uint>(p + i, (segment.Count - i) / (sizeof(uint) / sizeof(char)));
                    span.Fill(source);
                    i += span.Length * (sizeof(uint) / sizeof(char));
                }
                else
                {
                    switch (rem)
                    {
                        case 3 * sizeof(char):
                            p[i++] = value;
                            if (i == segment.Count)
                                goto END;
                            break;
                        case 2 * sizeof(char):
                            p[i++] = value;
                            if (i == segment.Count)
                                goto END;
                            p[i++] = value;
                            if (i == segment.Count)
                                goto END;
                            break;
                        case 1 * sizeof(char):
                            p[i++] = value;
                            if (i == segment.Count)
                                goto END;
                            p[i++] = value;
                            if (i == segment.Count)
                                goto END;
                            p[i++] = value;
                            if (i == segment.Count)
                                goto END;
                            break;
                        case 0:
                            break;
                        default:
                            throw new ArgumentException();
                    }
                    ulong source = ((ulong)value | (ulong)value << 16 | (ulong)value << 32 | (ulong)value << 48);
                    var span = new Span<ulong>(p + i, (segment.Count - i) / (sizeof(ulong) / sizeof(char)));
                    span.Fill(source);
                    i += span.Length * (sizeof(ulong) / sizeof(char));
                }

                for (; i < segment.Count; ++i)
                    segment[i] = value;

                END:
                return segment;
            }
        }
    }

    unsafe static class NativeMethods
    {
        [DllImport("msvcrt.dll", EntryPoint = "memset", CallingConvention = CallingConvention.Cdecl, SetLastError = false, CharSet = CharSet.Ansi)]
        public static extern IntPtr MemSet(byte* dest, int c, int byteCount);

    }
}

```
</div></details>