どのように新しいアルゴリズムの設計を最適化する操作の時間値を見つけるのですか？

Question

私の質問はiPhone、iPod、iPadに特有です。私はアーキテクチャが大きな違いを生み出していると考えています。私は、どこかに（おそらく様々なチップのための）仕様か、またはそれぞれの特定の命令のためにTを測定する信頼できる方法があると期待しています。私は使用されたプロセッサ時間の合計、使用されたメモリなどを測定するために任意の数のツールを使用できることを知っています。私はより低いレベルで定量化したいと思います。

私は、アルゴリズムの主要部分を何度も調べることができます。たとえば、純粋な実装ではn * (n-1)回、もう1つはn（最悪の場合）とn + n * (n-1)（最悪の場合）の間を繰り返します。私はまた、命令の総数（+ - =％* /とロジックステートメント）の合理的なカウントを行うことができ、それらのカウントを比較することができますが、それは各操作の重みが同じであると仮定しています。また、私はどのように論理的なステートメント（if、else、for、for）の実際の時間値を重み付けするか考えていません...数学的演算子と比較して... "これを使って？私はこの情報がどこにあるのか知りたいです。

わかりやすくするために、私の目標は、プロセッサ時間あたりに最適なアルゴリズムを設計できるように、CPU（またはGPUまたはU）をどれくらいのプロセッサ時間を要求するかを発見することです。誰かがiOSハードウェアをどこから始めるべきかというアイディアを教えてもらえますか？

編集：This link to ClockServices.cと開発者ポータルのSIMDは、これに興味のある方にとっては良いスタートになるかもしれません。今夜はもう少しコーヒーを飲みたいかもしれません;）

Answer 1

最新のプラットフォームでは、プロセッサ時間だけが限定要因ではありません。しばしば、メモリアクセスがあります。

それでも、プロセッサ時間：プロセッサの負荷の推定で
あなたの基本的なアプローチは、しかし、OKで、かつ賢明である：典型的なプラットフォームのあなたの知識に基づいて費用の概算を確認します。

In this article表1は、.NETにおける標準的なプリミティブ操作の時間を示しています。プラットフォームはさまざまですが、相対時間は通常非常に似ています。おそらく、あなたはiStuffを見つけることができます。

（私はプロセッサ/命令セットのマニュアルを除き、1渡って他のプラットフォーム用のそれほど徹底的に来ていないが、彼らはアセンブリ命令を扱う）

メモリの局所性：
キャッシュミスはあなたに何百もの費用がかかりますサイクルの数千倍のディスクアクセス。したがって、メモリアクセスパターンを制御する（つまり、ワーキングセットを減らす、キャッシュに適した方法でデータを再構成してアクセスする）ことは、アルゴリズムを評価する重要な部分です。

Answer 2

xCodeには、各機能/操作のパフォーマンスを測定するための楽器があります。