Go to Qiita Advent Calendar 2024 Top
LoginSignup
24
18

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@Tokeiya(時計屋)

配列に対するforとforeach

Last updated at Posted at 2018-02-20

TL;DR

前に､こんなこと書いたわけですが､配列1に対しちゃ実際どーなのさ?
と言うこともキニナルでしょ?ってコトで追いかけた｡

実行環境は､.Net Core 2.0とBenchMarkDotNet､
あと､コンパイル結果の解析などにはsharplabを使っている｡

また､今回は比較的単純なケースのみを取り上げており､網羅的に取り扱ってるわけではないので､その点ご了承頂ければ幸い｡

一般的にforeachはコンパイルするとどーなるか

こんなコード書いたとき､

public static int Sum(IEnumerable<int> source)
{
	var accum = 0;

	foreach (var i in source)
	{
		accum += i;
	}

	return accum;
}

コンパイラは､以下のような展開を行う｡

public static int Sum(IEnumerable<int> source)
{
	int num = 0;
	IEnumerator<int> enumerator = source.GetEnumerator();
	try
	{
		while (enumerator.MoveNext())
		{
			int current = enumerator.Current;
			num += current;
		}
	}
	finally
	{
		if (enumerator != null)
		{
			enumerator.Dispose();
		}
	}
	return num;
}

IEnumerable<T>なのかIEnumerableなのか､パターンマッチした似たような何かなのかでコードの生成はビミョーに変わるのだけど､概ねこんな感じだと思って頂ければ｡

流れとしては､

  1. GetEnumeratorを呼び出し､Enumerator<int>を取得する｡
  2. MoveNextを呼び出し境界をチェックしつつ､currentプロパティ経由で値にアクセスする
  3. 終了後にDisposeメソッドを呼び出す1

てかんじになる｡

配列に対するforeachはどうなのか

では､本題の配列に対するforeachはどーなるのかというと､同様に以下のようなコードを書いたとする｡

		public static int Sum(int[] source)
		{
			var accum = 0;

			foreach (var i in source) accum += i;

			return accum;
		}

これはコンパイルすると以下のようになる｡

public static int Sum(int[] source)
{
	int num = 0;
	int[] array = source;
	for (int i = 0; i < array.Length; i++)
	{
		int num2 = array[i];
		num += num2;
	}
	return num;
}

先ほどとは違って､forを使ったアクセスに展開されている｡こうすることで､GetEnumeratorや､その先にあるMoveNextの呼び出しを抑止して高速なアクセスが出来るようになっている｡

境界チェック

C#の配列は常に境界チェックが効いており､境界外にアクセスしようとするとSystem.IndexOutOfRangeExceptionが飛んできて不正な操作を許容しない様になっている｡

こいつはとても便利で安全な反面､境界内に収まることが自明な処理を行う場合､余計な処理にもなり得る｡個人的には､安全で堅牢なプログラミングを行う上で必要なコストだとは思うけど､.NETのJITは条件を満たすことでこの境界チェックをすっ飛ばすNativeCodeを吐き出す｡

それでは早速みていこう｡

単純なアクセス

境界チェックを外すに、守るべき条件は以下の通り

  1. Array.Lengthを使う
  2. 添え字はインクリメントする
  3. 配列がローカルに存在する

｢配列がローカルに存在する｣というのは､何もstackallocする必要があるというわけじゃ無く､var array=...のようにローカル変数に参照させるか､引数で受け取る必要があると言う意味となる｡

これに従えば､

public static int SumForeach(int[] source)
{
	var accum = 0;

	foreach (var i in source) accum += i;

	return accum;
}

と言うコードや､

public static int SumFor(int[] source)
{
	var accum = 0;

	for (int i = 0; i < source.Length; i++) accum += source[i];

	return accum;
}

と言ったコードは､境界チェックを外した上で高速に処理が可能だ｡

但し､以下のコードは境界チェックを外せないので注意｡

public static int SumForB(int[] source)
{
	var accum=0;
	
	for(int i=source.Length-1;i>=0;i--) accum+=source[i];
	
	return accum;

}

こっちの方が高速だとか言われてるけど 2､C#書いてる上では完全に無意味でしかも遅い｡
この場合､境界チェックが発生してパフォーマンス的に不利になる｡

ローカル以外の場所にある場合

先の例は引数で配列を受け取り処理を行っていた｡では以下のような場合どうなるだろうか?

using System.Linq;

namespace ForSurvey
{
	internal class Program
	{
		public static int[] IntArray;

		private static void Main(string[] args)
		{
			IntArray = Enumerable.Range(0, 100).ToArray();
		}

		public static int SumForeach()
		{
			var accum = 0;

			foreach (var i in IntArray) accum += i;

			return accum;
		}

		public static int SumFor()
		{
			var accum = 0;

			for (int i = 0; i < IntArray.Length; i++) accum += IntArray[i];

			return accum;
		}
	}
}

先の例に当てはめれば､どっちも変わらないでしょうと思われがちだけど､実はforeachを使った方は境界チェックが外れるけど､for使った方は境界チェックを外すことができない｡

上記のコードをコンパイルして､デコンパイルすると､以下のようになる｡

internal class Program
{
	public static int[] IntArray;

	private static void Main(string[] args)
	{
		Program.IntArray = Enumerable.Range(0, 100).ToArray<int>();
	}

	public static int SumForeach()
	{
		int num = 0;
		int[] intArray = Program.IntArray;
		for (int i = 0; i < intArray.Length; i++)
		{
			int num2 = intArray[i];
			num += num2;
		}
		return num;
	}

	public static int SumFor()
	{
		int num = 0;
		for (int i = 0; i < Program.IntArray.Length; i++)
		{
			num += Program.IntArray[i];
		}
		return num;
	}
}

foreach使ってる方は､intArrayといローカル変数に一度代入されてそのローカル変数への操作を行っている形を取っている｡
他方forの方はデコンパイル前後で当たり前だけど変化はない｡

実はここに大きな差があって､静的フィールドに有るIntArrayは別の処理が参照先の配列を変えてしまうことが出来る｡この事実とマルチスレッドが組み合わさると､ループ実行中に別の配列に差し替わって境界外アクセスが意図せず発生するというシナリオができあがる｡このケースを検知するために恐らく境界チェックを外すことができないのだ｡

また､残念ながらreadonlyを付与してもこの状況は変わらない｡3

実際どの程度差が出るのか

今までありがちなケースにおける配列に対する列挙操作の最適化がどのように行われているのか検証した｡
ここでは最後に､実際どの程度差が出るのかみてみることにしよう｡

検証コードは以下の通り｡

using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace ForSurvey
{
	public class ArrayAccessBenchmark
	{
		public static readonly int[] IntArray = Enumerable.Range(0, 100000000).ToArray();

		[Benchmark]
		public int SumForLocal()
		{
			var ary = IntArray;
			var accum = 0;


			for (var i = 0; i < ary.Length; i++) accum += ary[i];

			return accum;
		}

		[Benchmark]
		public int SumForGlobal()
		{
			var accum = 0;

			for (var i = 0; i < IntArray.Length; i++) accum += IntArray[i];

			return accum;
		}

		[Benchmark]
		public int SumForDecliment()
		{
			var accum = 0;

			for (var i = IntArray.Length - 1; i >= 0; i--) accum += IntArray[i];

			return accum;
		}

		[Benchmark]
		public int SumForeach()
		{
			var accum = 0;

			foreach (var i in IntArray) accum += i;

			return accum;
		}
	}

	internal class Program
	{
		private static void Main(string[] args)
		{
			BenchmarkRunner.Run<ArrayAccessBenchmark>();
		}
	}
}

で､結果が以下


BenchmarkDotNet=v0.10.12, OS=Windows 10 Redstone 3 [1709, Fall Creators Update] (10.0.16299.248)
Intel Core i7-3770K CPU 3.50GHz (Ivy Bridge), 1 CPU, 8 logical cores and 4 physical cores
Frequency=3410222 Hz, Resolution=293.2360 ns, Timer=TSC
.NET Core SDK=2.1.300-preview2-008012
  [Host]     : .NET Core 2.0.5 (Framework 4.6.26020.03), 64bit RyuJIT
  DefaultJob : .NET Core 2.0.5 (Framework 4.6.26020.03), 64bit RyuJIT
Method Mean Error StdDev
SumForLocal 55.71 ms 0.1490 ms 0.1394 ms
SumForGlobal 59.50 ms 0.2754 ms 0.2299 ms
SumForDecliment 59.20 ms 0.1194 ms 0.1059 ms
SumForeach 55.67 ms 0.1463 ms 0.1369 ms

大幅に速くなってるわけじゃないけど､それなりには速くなってるのがわかる｡

まとめ

以上のことから､以下のようなことが言えるのではないかと思う｡

  1. 配列に対するforeachはforと大体一緒である｡
  2. global locationsにある配列はローカル変数に一度受けて使う｡(かforeachを使う)

当たりに注意すれば良いかと思う｡

また､様々なケースはこれ以外にも当然考えられるので､その辺に関する考察は下記の参考としたページを見て頂ければと思う｡

参考文献

C#はunsafeの方が速いという幻想
Array Bounds Check Elimination in the CLR

  1. 実際ここが､何を相手にしてるかで結構変化する｡ ↩ ↩2

  2. "Some older programmers learned to write loops like this, because on some early architectures (e.g., DEC PDP-8, if memory serves) there was a hardware addressing mode that did auto-decrement, but not auto-increment. "だそうな。 ↩

  3. 実際問題リフレクション使うとreadonlyを変更できる(やるべきでもないし､やっちゃいけない) ↩

24
18
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
24
18

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?