Upgrade to Pro — share decks privately, control downloads, hide ads and more …

R3のコードから見る実践LINQ実装最適化・コンカレントプログラミング実例

 R3のコードから見る実践LINQ実装最適化・コンカレントプログラミング実例

C#パフォーマンス勉強会
https://cs-reading.connpass.com/event/309714/

Yoshifumi Kawai

April 27, 2024
Tweet

More Decks by Yoshifumi Kawai

Other Decks in Technology

Transcript

  1. About Speaker 河合 宜文 / Kawai Yoshifumi / @neuecc Cysharp,

    Inc. - CEO/CTO 株式会社Cygamesの子会社として2018年9月設立 C#関連の研究開発/OSS/コンサルティングを行う Microsoft MVP for Developer Technologies(C#) since 2011 CEDEC AWARDS 2022エンジニアリング部門優秀賞 .NETのクラスライブラリ設計 改訂新版 監訳 50以上のOSSライブラリ開発(UniRx, UniTask, MessagePack C#, etc...) C#では世界でもトップレベルのGitHub Star(合計30000+)を獲得
  2. Latest FAST Stacks MemoryPack https://github.com/Cysharp/MemoryPack FAST Serialization Utf8StreamReader https://github.com/Cysharp/Utf8StreamReader FAST

    Text/Stream Processing KcpTransport https://github.com/Cysharp/KcpTransport FAST Socket Network 様々なジャンルでのパフォーマンスへの挑戦と実証
  3. R3 – The new future of Rx 完全に新しいReactive Extensionsの実装 https://github.com/Cysharp/R3/

    dotnet/reactiveとUniRxの実装経験から生まれた新しいRx インターフェイスから見直したため完全な互換性はない 新しい実装が必要な理由 async/await以降Rxの価値は急速に低下 機能が被るところもあり、相性が悪く無駄な複雑さを招いている 基礎設計が古い(.NET Framework 3.5時代!)ので、パフォーマンスが考 慮されていない箇所が多数あり性能面でも現代的には劣る async/awaitとの共存を意識して、モダンC#を活用し現代的に再設計 互換性はないけど、Push型でLINQのオ ペレーターが使えればRxという理屈
  4. 列挙時のパフォーマンスとスレッドセーフの ためにImmutableArrayとして保持しているた め、Subscribe毎に新規配列を生成している (C#組み込みのeventも同様なのでこれ自体は 普通のつくりではありますが……) Performance Improvement subject.Subscribe()を10000回 subscription.Disposeを10000回 dotnet/reactiveのSubject.Subscribe

    R3ではImmutableArrayを廃して、イテレーション効率に最大限配慮しつつ、メモリ効率も考慮 した実装に変更。また、Subjectの種類(ReactiveProperty)によってはメモリ効率を最大化する実 装にするなど、複数種類の手法を用意して使い分けている。
  5. Many platforms support • Avalonia • Blazor • Godot •

    LogicLooper • MAUI • MonoGame • Stride • Unity • WinForms • WinUI3 • WPF それぞれのプラットフォーム固有の TimeProviderとFrameProviderを提供 時間系のオペレーターがThreadPoolTimerではなく、プ ラットフォーム固有のタイマーで動くことにより、明 示的なObserveOnで戻してあげる必要性なくなる CUI以外の多くのアプリケーションフレームワークは 内部的にフレームベースの処理を持つ(ゲームルー プ・イベントループ・レンダリングループなど) R3ではこれを抽象化するFrameProviderを追加し、時間 軸を使ったオペレーターと同様のフレームベースのオ ペレーターを多数用意した
  6. Operators 合計149メソッド オーバーロードも多いので実装完遂 させるのめげそうになった…… 一部メソッドの命名を標準に合わせて変更 ・Buffer -> Chunk ・StartWith ->

    Prepend ・Distinct(selector) -> DistinctBy ・Throttle -> Debounce ・Sample -> ThrottleLast Rxは時代が早すぎたので、結果的に非標準な 命名になってしまったものがあるので是正
  7. public abstract class Observable<T> { public IDisposable Subscribe(Observer<T> observer) {

    var subscription = SubscribeCore(observer); if (ObservableTracker.TryTrackActiveSubscription(subscription, 2, out var trackableDisposable)) { subscription = trackableDisposable; } observer.SourceSubscription.Disposable = subscription; return observer; } protected abstract IDisposable SubscribeCore(Observer<T> observer); } 予約済みスペース(SingleAssgiment)にアタッチ この構造じゃないとDisposeがすり抜けてしま うケースがある public abstract class Observer<T> : IDisposable { internal SingleAssignmentDisposableCore SourceSubscription; int disposed = 0; public void Dispose() { if (Interlocked.Exchange(ref disposed, 1) != 0) return; DisposeCore(); // Dispose self SourceSubscription.Dispose(); // Dispose attached parent Observable/Observer 抽象クラスにすることで100%全ての ノードが繋がる状態を保証する 抽象クラスにすることで全ての購読を 確実にトラッキング(デバッグ用) IDisposable生成の節約
  8. mutable structの定義 public struct SingleAssignmentDisposableCore { IDisposable? current; public bool

    IsDisposed => Volatile.Read(ref current) == DisposedSentinel.Instance; public IDisposable? Disposable { // snip… } public void Dispose() { var field = Interlocked.Exchange(ref current, DisposedSentinel.Instance); if (field != DisposedSentinel.Instance) field?.Dispose(); } sealed class DisposedSentinel : IDisposable { public static readonly DisposedSentinel Instance = new(); // snip… } } 単一フィールドのmutable struct Singletonオブジェクトに置換・比較することで節約
  9. public abstract class Observer<T> : IDisposable { internal SingleAssignmentDisposableCore SourceSubscription;

    int disposed = 0; public void Dispose() { if (Interlocked.Exchange(ref disposed, 1) != 0) return; DisposeCore(); // Dispose self SourceSubscription.Dispose(); // Dispose attached parent } protected virtual void DisposeCore() { } // OnNext(T value); OnErrorResume(Exception error) } mutable structの活用 public struct SingleAssignmentDi { IDisposable? current; public bool IsDisposed => Vo public IDisposable? Disposab { // snip… } public void Dispose() { var field = Interlocked. if (field != DisposedSen } sealed class DisposedSentine メモリ的には展開されるようなイメージ mutable structを活用することで、制約(継承)や追加のコ スト(heap allocation)なしにロジックを共通化できる R3では(今後の紹介でも出てきますが) mutable structを多用しています……!
  10. mutable structの注意点1 var mc = new MyClass(); mc.Increment(); mc.Show(); //

    ??? public class MyClass { public readonly Counter Counter; public void Increment() => Counter.Increment(); public void Show() => Counter.Show(); } public struct Counter { int count; public void Increment() => count++; public void Show() => Console.WriteLine(count); } 出力は?
  11. mutable structの注意点1 var mc = new MyClass(); mc.Increment(); mc.Show(); //

    0 public class MyClass { public readonly Counter Counter; public void Increment() => Counter.Increment(); public void Show() => Counter.Show(); } public struct Counter { int count; public void Increment() => count++; public void Show() => Console.WriteLine(count); } 「0」!mutableな挙動をしてくれない! readonly fieldにするとメモリ領域がロックされて書き換わらなくなってしまう mutable structを使うときは必ず非readonlyにすること 残念ながらコンパイルは通るし特に警告も出ないので注意するしかない
  12. public class MyClass { public Counter Counter; public void Increment()

    { var c = Counter; c.Increment(); } public void Show() => Counter.Show(); } mutable structの注意点2 ローカル変数に代入するとそこでコピーされるの でフィールドの値は書き換わらない public class MyClass { public Counter Counter; public void Increment() { ref var c = ref Counter; c.Increment(); } public void Show() => Counter.Show(); } 基本は必ずフィールドを直接触って絶対に代入しないことだが、どうしても 変数に持ちたかったり、他のメソッドに渡す必要がある場合はrefで渡す
  13. IDisposable Containers 複数のIDisposableを単一のIDisposableにまとめる ・Disposable.Combine(IDisposable d1, ..., IDisposable d8) ・Disposable.Combine(params IDisposable[])

    ・Disposable.CreateBuilder(); ・DisposableBag ・CompositeDisposable RxはSubscribeで出てくるIDisposableをまとめる頻度が高い 何も考えずCompositeDisposable一択、ではない! 最適なものを使い分けることでパフォーマンス向上を狙う
  14. CombinedDisposable internal sealed class CombinedDisposable2(IDisposable disposable1, IDisposable disposable2) : IDisposable

    { public void Dispose() { disposable1.Dispose(); disposable2.Dispose(); } } internal sealed class CombinedDisposable(IDisposable[] disposables) : IDisposable { public void Dispose() { foreach (var disposable in disposables) { disposable.Dispose(); } } } 静的に個数が決まっているなら、それをまとめた オブジェクト1つのアロケーションで済ませられる 8引数まではフィールドを並べたものを使用 9引数以上は配列のアロケーショ ンが追加される
  15. DisposableBuilder public ref struct DisposableBuilder { IDisposable? disposable1; IDisposable? disposable2;

    IDisposable? disposable3; IDisposable? disposable4; IDisposable? disposable5; IDisposable? disposable6; IDisposable? disposable7; IDisposable? disposable8; IDisposable[]? disposables; int count; public void Add(IDisposable disposable) { } public IDisposable Build() { } public void Dispose() {} } public class Foo { IDisposable disposable; public Foo(int n) { var d = Disposable.CreateBuilder(); for (int i = 0; i < n; i++) { Observable.IntervalFrame(1) .Subscribe() .AddTo(ref d); } disposable = d.Build(); } } 個数が動的で、1関数内で生成 する場合に使う Build時にAddされている個数に応じて CombinedDisposableを生成する。中間の IDisposable[]はArrayPoolから取得する(Build時に返 却)ため、生成結果以外のアロケーションはない 当然のようにmutable struct。 ref structにすることでフィールドに保持 することを禁止している。
  16. public struct DisposableBag : IDisposable { IDisposable[]? items; bool isDisposed;

    int count; public void Add(IDisposable item) { if (isDisposed){item.Dispose(); return;} if (items == null) { items = new IDisposable[4]; } else if (count == items.Length) { Array.Resize(ref items, count * 2); } items[count++] = item; } public void Clear() {} public void Dispose() {} } DisposableBag 個数が動的で、関数外で追加 or 全削除のみ発生する 場合に使う。単一の削除が必要な場合の最後の選択 肢としてCompositeDisposable。 当然のようにmutable struct コンテナのアロケーションはない public partial class MainWindow : Window { // DisposableBag is struct, no need new DisposableBag disposable; void OnClick() { Observable.IntervalFrame(1) .Subscribe() .AddTo(ref disposable); } }
  17. Create Operator public static partial class ObservableExtensions { public static

    Observable<TResult> Select<T, TResult>(this Observable<T> source, Func<T, TResult> selector { return new Select<T, TResult>(source, selector); } } internal sealed class Select<T, TResult>(Observable<T> source, Func<T, TResult> selector) : Observable<TResult> { protected override IDisposable SubscribeCore(Observer<TResult> observer) { return source.Subscribe(new _Select(observer, selector)); } sealed class _Select(Observer<TResult> observer, Func<T, TResult> selector) : Observer<T> { protected override void OnNextCore(T value) => observer.OnNext(selector(value)); protected override void OnErrorResumeCore(Exception error) => observer.OnErrorResume(error); protected override void OnCompletedCore(Result result) => observer.OnCompleted(result); } } 抽象クラスに重要な箇所を押し付けているた め、非常にシンプルもOperatorが書ける! primary constructorが威力を発揮する
  18. なおdotnet/reactiveの場合 static IQueryLanguage s_impl; public static IObservable<TResult> Select<TSource, TResult> (this

    IObservable<TSource> source, Func<TSource, TResult> selector) { return s_impl.Select(source, selector); } なにこれ? public virtual IObservable<TResult> Select<TSource, TResult>( IObservable<TSource> source, Func<TSource, TResult> selector) { return new Select<TSource, TResult>.Selector(source, selector); } 無駄に1段階呼び出しが深い(IQueryLanguageという抽象 化層は意味をなしていない)。現代的観点からいうと Source Linkで読みに行きづらいという欠点もある
  19. internal static class Select<TSource, TResult> { internal sealed class Selector

    : Producer<TResult, Selector._> { private readonly IObservable<TSource> _source; private readonly Func<TSource, TResult> _selector; public Selector(IObservable<TSource> source, Func<TSource, TResult> selector) { _source = source; _selector = selector; } protected override _ CreateSink(IObserver<TResult> observer) => new(_selector, observer protected override void Run(_ sink) => sink.Run(_source); internal sealed class _ : Sink<TSource, TResult> { なおdotnet/reactiveの場合 Producer? _? _? _?
  20. internal sealed class _ : Sink<TSource, TResult> { private readonly

    Func<TSource, TResult> _selector; public _(Func<TSource, TResult> selector, IObserver<TResult> observer) : base(observer) { _selector = selector; } public override void OnNext(TSource value) { TResult result; try { result = _selector(value); } catch (Exception exception) { ForwardOnError(exception); return; } ForwardOnNext(result); } } なおdotnet/reactiveの場合 Sink? _? というわけで、正直読みづらい public abstract class Notification<T> public readonly struct Notification<T> あとなんかNotification<T>(値の種別 OnNext|OnError|OnCompleted をまとめたもの)が、class それでOnNext毎にアロケーションされるのは めっちゃ厳しいので、R3ではstructにした
  21. 話戻ってSelect/Where最適化 public static Observable<TResult> Select<T, TResult> (this Observable<T> source, Func<T,

    TResult> selector) { if (source is Where<T> where) { // Optimize for WhereSelect return new WhereSelect<T, TResult>(where.source, selector, where.predicate); } return new Select<T, TResult>(source, selector); } public static Observable<T> Where<T>(this Observable<T> source, Func<T, bool> predicate) { if (source is Where<T> where) { // Optimize for Where.Where, create combined predicate. var p = where.predicate; return new Where<T>(where.source, x => p(x) && predicate(x)); // lambda captured alloc } return new Where<T>(source, predicate); } Where().Select()は一つのオペレーター にまとめることができる Where().Where()は一つのオペレー ターにまとめることができる LINQ to Objects(Enumerable)でも実装されている定番ネタです
  22. Observable.Return public static Observable<T> Return<T>(T value) { return new ImmediateScheduleReturn<T>(value);

    // immediate } internal sealed class ImmediateScheduleReturn<T>(T value) : Observable<T> { protected override IDisposable SubscribeCore(Observer<T> observer) { observer.OnNext(value); observer.OnCompleted(); return Disposable.Empty; } } 通常のReturn(単一要素を返すObservable<T>を生成)
  23. Return cached singleton 幾つかの(しかしよく使われる)既知の型 はシングルトン返しが可能 public static Observable<Unit> ReturnUnit() {

    return R3.ReturnUnit.Instance; // singleton } public static Observable<Unit> Return(Unit value) { return R3.ReturnUnit.Instance; } public static Observable<bool> Return(bool value) { return value ? ReturnBoolean.True : ReturnBoolean.False; // singleton } public static Observable<int> Return(int value) { return ReturnInt32.GetObservable(value); // -1~9 singleton }
  24. Return cached singleton internal sealed class ReturnInt32(int value) : Observable<int>

    { internal static readonly Observable<int> _m1 = new ReturnInt32(-1); internal static readonly Observable<int> _0 = new ReturnInt32(0); // snip... internal static readonly Observable<int> _9 = new ReturnInt32(9); public static Observable<int> GetObservable(int value) { switch (value) { case -1: return _m1; case 0: return _0; // snip... case 9: return _9; default: return new ReturnInt32(value); } } protected override IDisposable SubscribeCore(Observer<int> observer) { observer.OnNext(value); observer.OnCompleted(); return Disposable.Empty; } } Task<TResult>でもこういったキャッシュが使われている (Task<bool>(true | false), Task<int>(-1 ~ 9)
  25. Use IThreadPoolWorkItem internal sealed class ThreadPoolScheduleReturn<T>(T value) : Observable<T> {

    protected override IDisposable SubscribeCore(Observer<T> observer) { var method = new _Return(value, observer); ThreadPool.UnsafeQueueUserWorkItem(method, preferLocal: false); return method; } sealed class _Return(T value, Observer<T> observer) : IDisposable, IThreadPoolWorkItem { bool stop; public void Execute() { if (stop) return; observer.OnNext(value); observer.OnCompleted(); } public void Dispose() => stop = true; } } ReturnにTimeProvider.System を指定した場合はThreadPool 経由で値を発行する ThreadPool.UnsafeQueueUserWorkItemにはlambdaではなく IThreadPoolWorkItemを実装したオブジェクトを渡すことで、 内部でのアロケーションを抑えることができる。 どうせ戻り値と返すIDisposableのオブジェクトを生成する 必要があるので、同居させることにより節約できる。
  26. Concurrency Policy of Rx sealed class _Take(Observer<T> observer, int count)

    : Observer<T> { int remaining = count; protected override void OnNextCore(T value) { if (remaining > 0) { remaining--; observer.OnNext(value); if (remaining == 0) { observer.OnCompleted(); } } } internal sealed class CountAsync<T>(Cancellatio : TaskObserverBase<T, int>(cancellationToke { int count; protected override void OnNextCore(T _) { count = checked(count + 1); } 特に何のlockも入っていないのでOnNextが並列 で呼ばれると壊れる、これは仕様
  27. Concurrency Policy of Rx OperatorのThreadSafety オペレーターは ・複数のストリームの合流 ・TimeProvider(IScheduler)を利用した別スレッドからの処理 に関してはスレッドセーフを保証する 単一ストリームが並列で呼びだされる(例えばOnNextが並列で届く)

    場合の動作は保証しない SubjectそのものはThreadSafe(OnNextを並列で呼んでもいい)だが、 その先のオペレーターは、その状況はスレッドセーフではない Observableの源流を叩く側の責任として、単一ストリームはシングルス レッドにする。FromEventなどで包んだ場合に保証できない場合があるので、 その場合はSynchronize()で全体をlockして回避しなければならない。 (じゃあ別にSubjectってスレッドセーフに作らなくてもいいのでは説……)
  28. lockの技法 sealed class _Debounce : Observer<T> { int timerId; protected

    override void OnNextCore(T value) { lock (gate) { latestValue = value; hasvalue = true; Volatile.Write(ref timerId, unchecked(timerId + 1)); timer.InvokeOnce(timeSpan); // restart timer } } static void RaiseOnNext(object? state) { var self = (_Debounce)state!; var timerId = Volatile.Read(ref self.timerId); lock (self.gate) { if (timerId != self.timerId) return; if (!self.hasvalue) return; self.observer.OnNext(self.latestValue!); self.hasvalue = false; self.latestValue = default; } } } Debounce(タイマー動作中に新しい値が来たらタ イマーを再実行して以前のタイマーは破棄する) タイマー起動時にIDを 変更する 基本的にはInvokeOnceで前のタイマーは破棄される OnNextCoreが先行して実行されて、 InvokeOnceで破棄される前にここに到達して lock待ちしている可能性がある! lock前に取得したidと比較することによって、 lock中にOnNextCoreが発火している(新しい値が 来て別のタイマーが動作中)ことを検知できる なお、このテクニックはdotnet/reactiveのコードを見て知りました!
  29. Stopwatch.GetElapsedTime from .NET 7 DateTime.UtcNow – nowは使わない! ある地点からの経過時間(TimeSpan)を取得するのに日付はいらない Stopwatch.StartNew(heap allocation)もいらない

    オレオレValueStopwatchもいらない 開始地点のlongをGetTimstampで取得して保持するだけ Stopwatch.GetTimestampは昔からあるけれど、2点のtimestampから TimeSpanを取得するGetElapsedTimeは.NET 7から……! 日付の取得 is not FREE ただのlongなので、普通に取り回しがいいです
  30. あなあきList public struct FreeListCore<T> where T : class { readonly

    object gate; T?[]? values = null; public void Add(T item, out int removeKey) { lock (gate) { var index = FindNullIndex(values); values[index] = item; if (lastIndex < index) { Volatile.Write(ref lastIndex, index); } removeKey = index; // index is remove key. } } } public struct FreeListCore<T> where T : class { public void Remove(int index) { lock (gate) { if (values == null) return; if (index < values.Length) { ref var v = ref values[index]; if (v == null) throw new KeyNotF v = null; } } } } Addではnullの場所を検索してそのindexに追加 する、削除キーとしてindexも返す Removeはnull埋め (説明のためコード上省略してますが)リサ イズは拡大のみ(なのでindexがズレない)
  31. あなあきList 性能特性: 配列そのものはあまり弄ら ないため、追加・削除が比 較的高速。ImmutableArray を使う場合に比べてアロ ケーション・コピー回数が 劇的に減る 列挙時に穴があいたままイテレートされるの で?.でnullを無視する

    (説明のため前のページでは省略しています が)indexを維持して縮められるタイミングを 判定してlastIndexを変更して、穴だらけの配列 列挙になることを多少回避 性能特性: 列挙はSpanをそのまま取り 出すためそこそこ高速、た だし穴(null)が多いと無駄が 多くなるので低速化する
  32. 高速なnull index判定 Add時に、T[]? where T: classから nullのindexを取得する必要がある Remove時に空いたindexを保存していくと いうのも手ですが、頻繁に使うSubjectで 多くのメモリ領域を確保したくない

    というわけで前方からの線形検索 という条件で、速くしたい (あるいは後方からnull「以外」の indexを高速な線形検索したい)
  33. 高速なnull index判定 うまくそっちに行かない場 合は普通のしょぼい検索 T?[] where T: class を高速に検索できる特定条件(1バイ ト、2バイト、4バイト、8バイトのプリミティブ)に変

    換するためにIntPtrのSpanに強引に変換 IntPtrそのものはアドレスなので情報として使い道は ないが、nullは0なのでnull判定になら使える