メモリから、データはアーキテクチャの自然なワードサイズでのみ読み取ることができます。たとえば、32ビットシステムでは、データは4バイトのチャンクでメモリから読み取られます。2バイトまたは1バイトの値がメモリに追加された場合でも、それらの読み取りには4バイトのワードにアクセスする必要があります。(2バイト値の場合、値がワード境界に格納されていれば、2つの4バイトアクセスが必要になることがあります。)
したがって、個々の値へのアクセスは、単一の単語にアクセスする必要がある場合に最速であり、最小限の追加作業(マスキングなど)が必要です。私が正しければ、これが仮想マシン(JVMやAndroidのDalvikObject
など)がインスタンスの4バイト境界にメンバー変数を配置する理由です。
もう1つの概念は、キャッシュの使いやすさ、つまりローカリティ(L1、L2など)です。多くの値を次々にトラバース/処理する必要がある場合は、それらを互いに近くに(理想的には連続したブロックに)格納することが有益です。これは空間的な局所性です。これが不可能な場合は、少なくとも同じ値に対する操作を同じ期間に実行する必要があります(一時的な局所性-つまり、操作が実行されている間、値がキャッシュに保持される可能性が高くなります)。
私が見る限り、上記の2つの概念は「矛盾する」場合があり、どちらを選択するかは使用シナリオによって異なります。たとえば、連続するデータの量が少ないほど、量が多い(些細な)よりもキャッシュに適していますが、一部のデータでランダムアクセスが一般的に必要な場合は、単語に合わせた(ただしサイズが大きい)構造が有益な場合があります。構造全体がキャッシュに収まります。したがって、局所性(〜arrays)とアライメントの利点のどちらを優先するかは、値の操作方法に依存すると思います。
私にとって興味深いシナリオがあります。入力グラフ(およびその他の補助構造)を配列として受け取るパスファインディングアルゴリズムを想定しましょう。(その入力配列のほとんどは、32767未満の値を格納します。)
パスファインディングアルゴリズムは、配列に対して非常に多くのランダムアクセスを実行します(いくつかのループで)。この意味で、int[]
(Android / ARMの)入力データには、アクセス時に値が単語の境界にあるため、が望ましい場合があります。(一方、シーケンシャルトラバーサルが必要な場合は、キャッシュに適している可能性が高いため、特に大きなアレイの場合は、より小さなデータ型が推奨されます。)
ただし、(ランダムにアクセスされる)入力データがとして指定された場合はL1 / L2に適合しshort[]
、として指定された場合は適合しない場合はどうなりますint[]
か?このような場合、int[]
ランダムアクセスの4バイトアラインメントの利点は、キャッシュの使いやすさよりも重要short[]
ですか?
もちろん、具体的なアプリケーションでは、比較のために測定を行います。ただし、それは必ずしも上記の質問に答えるとは限りません。