MSを16倍出し抜くなんとか2回目
Msを16倍出し抜くwpf開発2回目
先日やった勉強会資料2回目です。
簡素な仮想化パネルの元資料です。
参加したくて
http://qiita.com/advent-calendar/2014/xaml
これに参加したくて、思わずTwitterアカウントを拵えてしまいました。
@proprogrammer0 ああ、やってしまいましたな。という気分です。
続・ハッシュコードをバラけさせる意味はあるのか
というわけで、.NET Frameworkのご本尊様を調べてみたのですが。
http://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,290
このコードを見る限り、GetHashCode()は別にバラケさせる必要はありませんね。
コスト比皆無です。
インクリメントで十分じゃありませんか。むしろ、インクリメント確実じゃないですか。
剰余で負の値が重複することを恐れて0x7fffffff論理積とか正味31bitとか、いろいろはっきりしました。
ビット演算は別に遅いとは言いませんが、uintへのキャストの方が最適化時に高速ではないのでしょうか・・・。
自分がレビュワーならそう指摘を書きます。
Dictionaryみたいな凄い使用頻度を持つクラスでこういうこともあります。
ハッシュコードをバラけさせる意味はあるのか
随分間が空きました。やっとプロジェクトが節目っぽいので再開します。
ハッシュコードについてよく言われることがあります。また、条件と言われるものがあります。
最初の2つは意味がよくわかるんですが、最後のがどうもよくわからなかったりしています。
インスタンスごとにインクリメントするのではいけないのでしょうか。
ハッシュテーブル自体も要素数に応じた拡張が行われますが、確率的な話をしてみるとハッシュ値がバラけていることより(偶然同一値を返す事が有りえますし)、1回定めたユニーク値を返せることに注力した方が良くはないか?
等と思ったので今のハッシュはインスタンスごとに、インクリメントして値を保持してます。
GetHashCode()で変に演算するより速いし、ハッシュテーブルの辞書引きも目立った速度劣化が見当たらない気がするし。
何が気になるって、 GetHashCode()で、一生懸命に素数で乗算したりする意味を問いたい感じです。異種混合のハッシュテーブル作るなら意味がありますが。
.NET Frameworkのことだけでも調べておこうかな。
これも課題か。
久々に綺麗なMVVM
しばらく、速さに特化したコードばかり書いていたので美しく構成された正統派のMVVMを書くと心が和みますね。
イベント集約という手法
一長一短あります。
本日はイベント集約のこと。
イベントは大変便利ですが、1つのイベントにどの程度のリスナーが居るかを正確に管理するのは大切です。
WPFを手本にすると、バインディングパスとレイアウトパスに関して見事なイベント集約がなされていることに気づきます。
依存関係プロパティを書き換えるとバインディングは非同期で最後の変更だけが伝わります。
バインディングが終わると、メタデータのオプションや、計測と配置の無効化フラグを見ながら、極力1回ずつだけレイアウトパスが走ります。
特定の処理が終わるまで、イベントの有無だけを蓄積しておく。これが大雑把にイベント集約というものです。
使いこなすと最適化の効果は絶大。
ですが、イベント集約はパスの順序について明確な設計を要します。また、集約したイベントが正確性を欠くと大変なことに。
今日もそのバグで大変なことに。
foreachのILとループのパターン
糖衣構文としてとても有名なforeachはおおまかに2種類のILになる可能性があります。
- 配列に対するIL(for文とほぼ同等)
- IEnumerable
になる IL
ループだけの速度では前者が約2倍速です。
IEnumerator
実態の型に合わせて最適なコードを選ぶような積極的高速化は行われません。
foreachに渡す物が配列であるか、他のIEnumerable
過度な期待はできません。
さて、最適化というところに主眼を置いてC#を扱う場合、ループを組むときにはおおまかに3通りのパターンがあります。
LINQの内部実装について書いた際に扱ったことがありますが以下の3つです。
- 配列
- List<T> 長さが分かる(且つインデクサが速い)コレクション(←2014/12/6 修正)
- IEnumerable<T> 長さが分からないものの列挙
C#のコンパイラに、型判別と最適なループに展開する属性とかを渡せたらいいのですが。
まあ、この属性を乱用したらループの都度コードが3倍になるわけで、場合によってはキャッシュヒット率の低下などかえって有害。素人にはお勧めできない仕様になってしまいますが。
あと、yield return の展開、次のバージョンではもう少しマシになってるんでしょうか。
まだ確認はしていませんが、期待と不安でいっぱいです。
簡素な仮想化パネル
こんなXAML
<Window x:Class="Test.FastCanvas.MainWindow" xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation" xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml" xmlns:local="clr-namespace:Test.FastCanvas" Title="MainWindow" Height="350" Width="525"> <ScrollViewer x:Name="scroller" HorizontalScrollBarVisibility="Visible"> <local:FastCanvas x:Name="canvas" /> </ScrollViewer> </Window>
こんなコード(usingは省略してます)
namespace Test.FastCanvas { /// <summary> /// MainWindow.xaml の相互作用ロジック /// </summary> public partial class MainWindow : Window { public MainWindow() { InitializeComponent(); for (int y = 0; y < 1000; y++) { for (int x = 0; x < 100; x++) { var element = new Ellipse() { Width = 32, Height = 32, Fill = Brushes.LightPink }; element.MouseEnter += (s,e) =>{ ((Ellipse)s).Fill = Brushes.Blue; }; element.MouseLeave += (s, e) => { ((Ellipse)s).Fill = Brushes.LightPink; }; Canvas.SetLeft(element, x * 32); Canvas.SetTop(element, y * 32); canvas.AddElement(element); } } canvas.Height = 32 * 1000; canvas.Width = 32 * 100; scroller.ScrollChanged += scroller_ScrollChanged; } void scroller_ScrollChanged(object sender, ScrollChangedEventArgs e) { var rect = new Rect( scroller.HorizontalOffset, scroller.VerticalOffset, scroller.ViewportWidth, scroller.ViewportHeight); canvas.SetViewport(rect); } } }
こんなコントロール(usingは省略してます)
namespace Test.FastCanvas { public class FastCanvas : Canvas { private HashSet<UIElement> _virtualChildren = new HashSet<UIElement>(); public void AddElement(UIElement element) { _virtualChildren.Add(element); } public void RemoveElement(UIElement element) { _virtualChildren.Remove(element); } public void SetViewport(Rect rect) { foreach(FrameworkElement child in _virtualChildren) { var childRect = new Rect(Canvas.GetLeft(child), Canvas.GetTop(child), child.Width, child.Height); if (!rect.IntersectsWith(childRect)) { if (Children.Contains(child)) Children.Remove(child); } else { if (!Children.Contains(child)) Children.Add(child); } } } } }
分かり易く仮想化を説明する教材として作ったものです。
ScrollChangedを使うと古風なので(あとレイアウトパスが過剰に走って遅いので)、データバインディングでViewportを設定できるようにするとMVVM風ですよね。マルチバリューコンバーターの出番です。
起動時間と、マウスヒットテストは仮想化の有無だけで相当違います。それを体感するためのサンプルと思っていただけたら。
ちなみに、同じコードでFastCanvasをCanvasに入れ替え、ScrollChangedのイベントをやめるだけで、仮想化自体の威力は体感できると思います。
実は最近、Visualを細切れにしたらいいんじゃないかと思い
最近まで、よりも速い仮想化パネルを作るということに心血注いでいて一段落ついたところなのですが、まだいくつかやり残したことがあります。
というのは、あるチューニング中の出来事で、再描画領域がパネルの左上から右下まで突き抜けているベジェを変更するときに、極限まで再描画範囲を削ってみたら、画面にWPFらしからぬごみが残る現象が発生しました。
そこでふと思ったのです。
ビジュアルツリー自体は配下のどの範囲が書き換えられるかというところにはすごく厳しいのですが、じゃあ、隣接域を侵害しないように細切れに物を配置してみたらどうだろうと。
仮想化としては、その細切れを根元から着脱・・・・。
もしかして、今よりもっと速い方法につながりうるのではないかと思ったのです。
ただ、用心が必要なのは、見かけのコントロール1つが細切れになって10くらいのVisualになれば、メモリは消費する可能性が高いし、・・・・どっちがいいんでしょう。
次回の開発に入る前に、1日くらい時間を取らせてもらって、そういう実装の速度を試験してみることも必要かなと思った次第です。
ペンはブラシに負けます
ペンは仕掛けが複雑なので、図形を書く際には縁が要らないならブラシだけで書きましょう。場合によっては、四角形を回転拡縮して描いた方が速い事すら有ります。やや極端ですが。
余談ですが、最近短いのが多いのは、スマホ端末から書いているからです。
Color.GetHashCode( )は一意ではない
32bitしか情報を持っていないのに、一意なハッシュコードを返さないとは。
最近のショックな事例の一つです。