wiprog

C# とか,数学とか,社会とか.

C# Span<char> を使って snake_case な文字列を PascalCase に変換する

ネットで検索してもなかなか良い実装が見つからなかったので自分で書きました。

他の実装と違う点として、

  • 部分文字列 (string インスタンス) を一切アロケートしない
  • 極力すべての操作を stack 上で済ませる

ことで、パフォーマンスを意識した作りにしています。

public static string SnakeCaseToPascalCase(this string snake)
{
    ReadOnlySpan<char> snakeSpan = snake;
    Span<char> buffer = stackalloc char[snakeSpan.Length];

    int bufferPos = 0;
    bool toUpper = true;
    for (var i = 0; i < snake.Length; i++)
    {
        var target = snakeSpan[i];
        
        if (target == '_')
        {
            toUpper = true;
        }
        else
        {
            buffer[bufferPos++] = toUpper ? char.ToUpper(target) : target;
            toUpper = false;
        }
    }

    return buffer.Slice(0, bufferPos).ToString();
}

C# で同時実行数制御つき ForEachAsync

2020/03/26 Qiita から移行. 現在下記の実装には例外ハンドリングの不具合が確認されていますので使用は推奨しません

同時実行数を抑えながら非同期を走らせる方法として、下記の記事で ForEachAsync 拡張メソッドが紹介されています。 ForEachAsync - 非同期の列挙の方法 Part2

で、これを参考に別の実装をしてみました。 (使い方等は上記のブログ記事を御覧ください)

public static Task ForEachAsync<T>(this IEnumerable<T> source, Func<T, Task> asyncAction, int concurrency,
    CancellationToken cancellationToken = default)
{
    source.ThrowIfArgumentNull(nameof(source));
    asyncAction.ThrowIfArgumentNull(nameof(asyncAction));
    concurrency.ThrowIfArgumentOutOfRange(1, int.MaxValue, nameof(concurrency));

    async Task ForEachInner()
    {
        int throwedCount = 0;

        void OnFault(Exception e)
        {
            Interlocked.Add(ref throwedCount, 1);
            throw e;
        }

        using (var tasks = new TaskSet(concurrency, OnFault))
        {
            foreach (var x in source)
            {
                if (throwedCount > 0) break;
                cancellationToken.ThrowIfCancellationRequested();

                await tasks.AddAsync(x, asyncAction).ConfigureAwait(false);
            }

            await tasks.WhenAll().ConfigureAwait(false);
        }
    }

    return ForEachInner();
}

private sealed class TaskSet : IDisposable
{
    private readonly Task[] _tasks;
    private readonly ConcurrentStack<int> _unusedIndexes;
    private readonly Action<Exception> _faultedAction;
    private readonly SemaphoreSlim _semaphore;

    public TaskSet(int concurrency, Action<Exception> faulted)
    {
        _tasks = new Task[concurrency];
        _unusedIndexes = new ConcurrentStack<int>(Enumerable.Range(0, concurrency));
        _faultedAction = faulted;
        _semaphore = new SemaphoreSlim(concurrency, concurrency);
    }

    public async Task AddAsync<T>(T arg, Func<T, Task> asyncAction)
    {
        await _semaphore.WaitAsync().ConfigureAwait(false);
        if (!_unusedIndexes.TryPop(out int index)) throw new Exception();

        var task = asyncAction(arg).ContinueWith(t =>
        {
            _unusedIndexes.Push(index);
            _semaphore.Release();

            if (t.IsFaulted)
            {
                _faultedAction(t.Exception);
            }
        });

        _tasks[index] = task;
    }

    public Task WhenAll() => Task.WhenAll(_tasks.Where(t => t != null));

    void IDisposable.Dispose() => _semaphore.Dispose();
}

この実装と冒頭のブログとの違いは、生成した Task の管理に TaskSet クラスを導入したことです。
これによって、source の長さ分まで大きくなり続ける List<Task> を使うことなく、長さが concurrency で固定の配列 Task[] を使うことができ、 List.Add 時の拡張等のコストが削減できます。

コードは GitHub にあります。 https://github.com/wipiano/cisis/blob/master/Cisis/Linq/ForEachAsync.cs https://github.com/wipiano/cisis/blob/master/Cisis.Test/Linq/ForEachAsyncTest.cs

今からできる、速くシンプルに LINQ を書くためのコツ 3 個

たびたび 「LINQ が遅い」 と言われているのを見かけるので、どうやったら速く書けるのか、どう書くと遅くなるのかについてまとめてみます。
LINQ は非常に強力で、ぼくが出会った「LINQ 遅い」のほとんどは、 実装の仕方がまずいものばかりです。
LINQ はいくつかポイントを意識するだけでかなり安全に速く書けるようになります。
いろいろとポイントはありますが、 3 つだけに絞って書いてみました。

私自身 C# 書き始めてようやく 2 年たったぐらいなので、間違っているところはバシバシご指摘いただけると嬉しいです。

こちらの記事も参考になるので、合わせてご覧ください。

blog.okazuki.jp

「LINQ 遅い」の 3 パターン

まあ LINQ は速くないこともたまにあるのですが、大抵の場合は十分なパフォーマンスを提供してくれます。
「LINQ が遅い」 と言う時はだいたい以下のどれかかなと思います。

  1. よくわからないけどイメージで「遅そう」と言っている (要するに使いたくない、覚えたくない)
  2. LINQ のしくみがよくわからず、誤った使い方、明らかに遅い書き方をしている (例: なんとなく Count(), ToArray() などしてしまう)
  3. LINQ の内部実装をよく知っているプロフェッショナルが LINQ が適していない場合に「遅い」と言う

1 の場合はどうにもできないです。 3 の場合は必要に応じて LINQ 以外の方法を取ることもできますし、 LINQ を使うと判断した場合は最も適切なメソッドを選んで使用できるので遅くなりません。プログラマとしてはここを目指したい。
問題は 2 の場合で、「なんとなく動くものは書けるけど遅い、どこが遅いのかよくわからない」というのが多いです。
今回は最も多いと思われる 2 のパターンをターゲットに書いていきます。

1. 不用意に要素数を取得しない (Count メソッド)

一番良く見かけるのがこれです。簡単に書けてしまいますが非常に危険です。

IEnumerable<Hoge> source = // ...

if (source.Count() > 0)
{
    // 要素があるときの処理
}

IEnumerable<T> はカウントを持ちません。いくつ要素があるのかも全部列挙してみないとわかりません。 もしかしたら非常に長かったり、列挙におおきなコストがかかったり、無限につづくシーケンスでそもそもカウントできないかもしれません。
Count メソッドは基本的には 100 万個要素があったら 100 万個全部を 1 個ずつ列挙して数えていくため非常に遅く、ほとんどの場合に意図していない列挙を発生させます。
もちろん Count の前に SelectWhere をかけていて、列挙の際になんらかの計算が発生するような場合にはその計算のコストもかかります。 実体が Count プロパティをもつコレクションである場合には Count プロパティの値を取得するような最適化は入っているものの、本当に「何個あるか知りたい時」以外使うべきでないです。

source.Count() > 0 と書くのであれば、代わりに source.Any() と書きましょう。

「ある条件を満たす要素が n 個以上あるかどうかを判定したいとき」には下記のように Skip や Take を使用することで、一部だけの列挙におさえることができます。

var filtered = source.Where(predicateFunc);

// 列挙した要素を一切使わず、ただ n 個以上あることをたしかめたいとき
// 列挙したものを保存する必要がないのであれば、この方法で無駄な配列確保を避けられる
if (filtered.Skip(n - 1).Any())
{
    // n 個あった時の処理
}

// 列挙した要素を n 個使用するとき
// 複数回同じものに対しての列挙を避けるには、ToArray() が有効。
// ただし、 n が大きくなった場合、それだけ大きい配列が確保されるので注意。これは ToList() でも同様
var part = filtered.Take(n).ToArray();

if (part.Length == n)
{
    foreach (var item in part)
    {
        // なにか処理
    }
}

2. なんとなく配列やリストに突っ込まない。ライブラリを作るときはなるべく IEnumerable<T> で受ける。

ToArray()ToList() は非常に便利なメソッドですが、ほとんどの場合 LINQ の途中で呼ぶ必要はありません。 たとえば、下記のような ToArray は意味がないばかりか、無駄な配列のためのメモリを確保してパフォーマンスを著しく低下させます。

IEnumerable<Hoge> source = // ...

var array = source.ToArray() // むだな配列生成
    .Select(x => ごにょごにょ)
    .Where(x => ごにょごにょ)
    .Distinct()
    .ToArray(); // むだな配列生成

// foreach するだけならむだな array はいらない
foreach (var x in array)
{
    // なにかする
}

下記のように書いてもまったく動作上問題がなく、パフォーマンスがよくなります。

IEnumerable<Hoge> source = // ...

var array = source
    .Select(x => ごにょごにょ)
    .Where(x => ごにょごにょ)
    .Distinct();

// foreach するだけならむだな array はいらない
foreach (var x in array)
{
    // なにかする
}

また、配列である必要がないのに配列で引数を要求するメソッドを書くのはやめましょう。 IEnumerable<T> で受けましょう。 本当は 1 個ずつ処理するだけのメソッドなのに、渡す側で ToArray() して渡す必要があるのは無駄です。

3. 巨大なファイルを 1 行ずつ処理するときも、リストはいらない。

たとえば、こんなコードを書いたことはありませんか?これはほんとうに無駄なのでやめましょう。

// 1 行ずつ処理したいけど、 LINQ つかうから IEnumerable<T> がほしい。 List<T> に Add していこう

List<Hoge> sourceList = new List<Hoge>();

using (var reader = new StreamReader(stream))
{
    string line;
    while ((line = reader.ReadLine()) != null
    {
        sourceList.Add(MapToHoge(line));
    }
}

sourceList.Select(xxx).Where(xxx). // ...

こんなふうに書けば、一気に全部読んでしまう必要はまったくありません。

IEnumerable<Hoge> Read()
{
    using (var reader = new StreamReader(stream))
    {
        string line;
        while ((line = reader.ReadLine()) != null
        {
            yield return MapToHoge(line);
        }
    }
}

Read().Select(xxx).Where(xxx) // ...

あるいは、ファイルから読むことがわかっているならこれでも良いです。

File.ReadLines("filepath")
    .Select(xxx)
    .Where(xxx)
    . // ...

File.ReadAllLines メソッドもありますが、こちらはすべてを読んで配列に入れてから返してくるので気をつけましょう。巨大なファイルを読む場合に大量のメモリが必要になります。

まとめ

たくさん書きましたが、要するにおなじシーケンスに対しての複数回の列挙や、必要のないものの列挙、巨大なメモリ確保にもっと慎重になりましょうということです。
LINQ は遅延評価が基本ですが、誤った使い方をすればそのメリットを活かせないばかりか、非常に遅いコードが簡単に出来上がってしまいます。
遅いのは LINQ のバグでも、 .NET Core 開発チームの怠慢でも、マシンのスペックが足りないからでもなく、ただ遅くなるように書いたからです。そうでないこともありますが、だいたいそうです。

自分で書いたコードが遅かったり、すっきり書けなかったりして困ったときに、Qiita や twitter に投稿するといろんな人のアドバイスが受けられて楽しいです。
読む人にとってはその投稿についたコメントや、反応の記事のほうが役にたつことがたくさんありますが、最初の投稿がなければそれらの記事も生まれません。

LINQ の内部の実装を読むことは非常に勉強になります。
GitHub で .NET Core の完全な実装を読むことができます。
難しく見えるかもしれませんが、単純なもの、きになるものから読んでいくといいと思います。 また、簡単そうなメソッドを自分で書いてみるのも理解するには効果がありました。
LINQ を書く際に気をつけることはこれがすべてではありませんが、ドキュメントやコードをきちんと読んだり、信頼できる先輩にアドバイスをもらったりしながらだんだんと身についていくものだと思います。

github.com

あと、 ReSharper などのツールを入れると multiple enumeration の注意を出してくれたりもします。

www.jetbrains.com

(ReSharper は他にもいろいろなことを教えてくれる素晴らしい先生になるのでめちゃくちゃおすすめです)

(おまけ) 記事を書いたきっかけ

もともと微妙なコードをちょくちょく見かけていて、 LINQ ってそんなに難しいのかなーと思っていたのですが、 twitter で
C#でLinqを使うよりPythonの方が2倍速かったのでベンチマークをしてみた - Qiita
という記事が回ってきました。

公開から短時間でいいねが複数ついていたことから、ほんとうは速くシンプルに書けるにもかかわらず、 LINQ が遅いと判断してしまう人は多いのではないかと思い、 急いで記事を書いている次第です (そもそもこのブログ自体そんなに見られてないのでどの程度効果があるかは疑問ですが)。

この記事の具体的な内容についてはもう十分他の方が指摘などされていると思いますので、ここでは細かく言及しません。 ただ、もし初心者の方が読まれる場合には下記の点だけは頭においてほしいです。

  1. (意図的にそうしているとは思いませんが、結果として) 検証用のコードが非常に遅くなるように書かれています。 検証用のコードを改善することでだいぶ速い結果になる、という記事がすでにあります。GroupBy が遅いように書かれていますが、それよりも 無駄な ToList 何度も呼んでいるめにループの回数が増えてしまっていることのほうがはるかに大きな問題です。C# の Linq が python の2倍遅い、は嘘 - Qiita
  2. Span<T> に関しては用途が違うように思います。 Qiita の記事とは全く無関係ですが、 日本語で読める Span<T> の記事としては Span<T>構造体 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C がとても参考になります。
  3. 実際には、LINQ に限らず .NET のパフォーマンスの改善や新機能の開発に多くの優秀なエンジニアが取り組んでいます。また、明らかに遅かったり問題があり、改善方法があることが本当にわかっているなら、 issue をあげたり、プルリクエストを送ってみたりする手段は誰にでも開かれています。 GitHub - dotnet/corefx: This repo contains the .NET Core foundational libraries, called CoreFX. It includes classes for collections, file systems, console, XML, async and many others. We welcome contributions.

BenchmarkDotnet を使って LINQ の部分のベンチマークをとってみたところ、標準の LINQ メソッドだけで 3 倍以上高速になりました。

SlowLinq が Qiita の元記事、 NormalLinq がそれを書き直したもの、 UseGroupSum が GroupBy を使わないものです。

Method Mean Error Gen 0 Gen 1 Gen 2 Allocated
SlowLinq 321.59 ms NA 12400.0000 6200.0000 800.0000 78916.81 KB
NormalLinq 85.77 ms NA 1400.0000 600.0000 - 8415.32 KB
UseGroupSum 62.12 ms NA - - - 147.43 KB

Utf8Json で JSONP を書く

Utf8Json.JSONP というライブラリを作りました。 ざっくりしたライブラリの紹介と、どうやって実装したかのメモです。

簡単な紹介

nuget でインストールできます。

NuGet Gallery | Utf8Json.Jsonp 1.1.0

nuget パッケージを入れると、 Utf8Json の名前空間Jsonp というクラスが追加されます。
これが JSONP 版の JsonSerializer です。

使いごこちは JsonSerializer と同じになるようにしてあります。 QuickStart にも載せたのですが、こんな感じでかけます。

var p = new Person { Age = 99, Name = "foobar" };
var callback = "callbackFunc";

// result: callbackFunc({"Age":99,"Name":"foobar"});

// obj -> byte[]
byte[] bytes = Jsonp.Serialize(callback, p);

// write to stream
using (var stream = new MemoryStream())
{
    Jsonp.Serialize(stream, callback, p);
}

ソースはこちら。

github.com

対応してないもの

とりあえず仕事ですぐに使いたくて週末にざざっと作ったので最低限の機能にしています。
落ち着いたら対応していく予定です。

  • 型なしのシリアライズにまだ対応していません
  • ASP.NET Core への組み込みもまだです(仕事では webforms だったので。。。。。。。)

作った目的

ちょうど仕事で Utf8Json への置換えを進めていて、 JSONP に対応してる API どうしよう・・・って考えたのがきっかけです。 せっかく Utf8Json で超高速な JSON シリアライズができるのに、 JSONP のために文字列とか byte 配列の結合はやりたくなかった。

最初の実装

まず Utf8Json 置き換え前のコードはこんな感じでした。 (Utf8Json に比べると) すごく遅そう。

string json = Newtonsoft.Json.JsonConvert.SerializeObject(obj);
string jsonp = string.Format("{0}({1})", callback, obj);

で、 Utf8Json に置き換えて最初にやった実装がだいたいこんなかんじ。

// json と callback の文字列をそれぞれ byte[] に変換
byte[] jsonBytes = Utf8Json.JsonSerializer.Serialize(obj);
byte[] callbackBytes = Encoding.UTF8.GetBytes(callback);

// 結果の byte[] を作る
int byteCount = jsonBytes.Length + callbackBytes.Length + 2;
var jsonpBytes = new byte[byteCount];

// コピーしていく
Array.Copy(callbackBytes, 0, jsonpBytes, 0, callbackBytes.Length);
jsonpBytes[callbackBytes.Length] = (byte) '(';
Array.Copy(jsonBytes, 0, jsonpBytes, callbackBytes.Length + 1, jsonBytes.Length);
jsonpBytes[byteCount - 1] = (byte) ')';

Utf8Json を使っているのでなんとなく速そうに見えますが、 byte[] を 3 つもつくっています。そしてこのあとさらに stream に書き込んだりするのです。これは遅い。
utf8json の SerializeUnsafe() を使えば多少は良くなりそうですがそれにしても完璧ではなさそうです。

Utf8Json の primitive API

配列のコピーをなくして、そのまま JSONP の形になっている byte[] がとれればいちばんよいです。
で、それをやるには Primitive API として公開されている JsonWriter を使って、 シリアライザが内部で持っているバッファに直接書き込んじゃうのが簡単そうでした。

単純にやればとても簡単で、まずやったのはこんな実装でした。 v1.0.0 の実装はこれです。

public static byte[] Serialize<T>(string callback, T value, IJsonFormatterResolver resolver)
{
    // MemoryPool, BufferPool は自分で用意する必要があった
    var writer = new JsonWriter(MemoryPool.GetBuffer());
    
    // callback の文字列と ( を書く
    writer.WriteRaw(Encoding.UTF8.GetBytes(callback));
    writer.WriteRaw((byte) '(');

    // Utf8Json の API をつかって json を書く
    Utf8Json.JsonSerializer.Serialize(ref writer, value, resolver);

    // ) を書く
    writer.WriteRaw((byte) ')');

    return writer.ToUtf8ByteArray();
}

callback 文字列のシリアライズでの配列確保を避ける

これで満足していたのですが、さっきのコードのこの部分

// callback の文字列と ( を書く
writer.WriteRaw(Encoding.UTF8.GetBytes(callback));

これが気になりはじめました。
これだと callbackbyte[] に変換するためだけに新しく配列を作ってしまいますし、それを JsonWriter 内部の配列にコピーしないといけません。
最初の実装とそこまで違うの?という感じです。

で、 GetBytes() には任意の配列に書けるオーバーロードがあるのでそれを使ってこんなふうにしました。 すこし無理やりな実装ですが、これで配列が作られるのを防ぎます。

public static byte[] Serialize<T>(string callback, T value, IJsonFormatterResolver resolver)
{
    // MemoryPool, BufferPool は自分で用意する必要があった
    var writer = new JsonWriter(MemoryPool.GetBuffer());
    
    // writer の内部バッファを取得する
    ArraySegment<byte> buffer = writer.GetBuffer();
    
    // バッファに callback の文字列を書いて、その分だけバッファの現在位置を進めてあげる
    // ここがずれると大変なので、渡すのが byte[] でいい時は WriteRaw() とかをつかうのが良さそう。
    var filledCount = Encoding.UTF8.GetBytes(callback, 0, callback.Length, buffer.Array, buffer.Count);
    writer.AdvanceOffset(filledCount);

    writer.WriteRaw((byte) '(');

    // ( を書く
    writer.WriteRaw((byte) '(');

    // Utf8Json の API をつかって json を書く
    Utf8Json.JsonSerializer.Serialize(ref writer, value, resolver);

    // ) を書く
    writer.WriteRaw((byte) ')');

    return writer.ToUtf8ByteArray();
}

簡単なベンチマークをとってみたらかなり速くなってました。

Method Mean Error StdDev Gen 0 Allocated
OldVersion 205.1 ns 3.017 ns 3.816 ns 0.0608 96 B
NewVersion 159.0 ns 2.347 ns 2.196 ns 0.0405 64 B

おまけ: SerializeUnsafe について

Utf8Json の APISerializeUnsafe() というメソッドがあります。 (もちろん Jsonp でもサポートしてます)
このメソッドは何が unsafe かというと、スレッドごとに一個しかないシリアライズ用のバッファをそのまま返してきます。
つまり、結果を受け取ったらすぐに使ってしまわないと、他のオブジェクトをシリアライズした場合に書き換えられてしまう可能性があるということです。
unsafe でない API はこれを避けるために、新しく byte[] を作って返してくれます。

どんなときに使うと良いか

たとえば結果をすぐに使って捨ててしまう場合 (たとえば stream に書くとか) の場合は SerializeUnsafe() をつかったほうがお得です。
逆に結果を引き回したり、スレッドをまたいで共有したり、複数のオブジェクトをシリアライズしてあとでまとめて何かする、という時には使えません。

実際、今回も stream に書き込みをする API はこんな感じで実装していますが、これで安全に速く動きます。
この API は本家の Utf8Json にもあるものなので、stream に書いてしまう場合はこれを呼んでもらえれば大丈夫だと思います。

public static void Serialize<T>(Stream stream, string callback, T value, IJsonFormatterResolver resolver)
{
    var buffer = SerializeUnsafe(callback, value, resolver);
    stream.Write(buffer.Array, buffer.Offset, buffer.Count);
}

dotnet pack で XML Document つきのパッケージを作成する

.NET Core では dotnet pack コマンドで簡単に nuget パッケージを作ることができます。
ただデフォルトでは XML document が出力されなくてちょっと困ったので対策を書いておきます。

忙しい人のために

csproj に下記の行を追加すれば XML Document が出力されます

<GenerateDocumentationFile>true</GenerateDocumentationFile>

まずふつうに dotnet pack してみる

こんなてきとうなプロジェクトをつくります。
サンプルなので省略しますがほんとうは PackageId などいろいろ指定します。

docs.microsoft.com

XmlDocSample.csproj

<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <TargetFramework>netstandard2.0</TargetFramework>
  </PropertyGroup>
</Project>

Sample.cs

using System;

namespace XmlDocSample
{
    public static class Sample
    {
        /// <summary>
        /// 文字列をコンソールに出力します
        /// </summary>
        /// <param name="s">出力する文字列</param>
        public static void Print(string s)
        {
            Console.WriteLine(s);
        }
    }
}

これでいったん pack してみます。

dotnet pack XmlDocSample.csproj -c Release

XML Doc がない。。

できあがった nuget パッケージを参照できるようにソリューションのディレクトリに nuget.config を置きます。

dotnet new nugetconfig

コマンドで nuget.config を作成して、以下のように書き換えます

<?xml version="1.0" encoding="utf-8"?>
<configuration>
 <packageSources>
    <add key="local" value="nuget パッケージのパス" />
 </packageSources>
</configuration>

てきとうなプロジェクトを作って nuget パッケージの管理を開くと、こんな感じで作成した nuget パッケージがでてきます。

f:id:wipiano:20180408114644p:plain

パッケージをインストールして使ってみると・・・

f:id:wipiano:20180408114927p:plain

ほんとうはここにさっき書いたコメントが出てきてほしいのですが、表示されません。

展開された nuget パッケージを見てみると、xml が出力されていないことがわかります。

f:id:wipiano:20180408115509p:plain

XML Document を出力するおまじない

いろいろ調べると、 csproj に 1 個おまじないを書けば XML が出力されることがわかりました。

wmpratt.com

<GenerateDocumentationFile>true</GenerateDocumentationFile>

これを csproj に追加して、もう一度 pack してみます。

すると、ビルド時に XML doc が書かれてないものは警告も出るようになりました。

Sample.cs(5,25): warning CS1591: 公開されている型またはメンバー 'Sample' の XML コメントがありません。

これで作成されたパッケージをインストールして使ってみると・・・

f:id:wipiano:20180408120503p:plain

ちゃんと intellisense にも表示されています。