Go to Qiita Advent Calendar 2024 Top
LoginSignup
35
37

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(時計屋)

List<T>に対するforとforeachとForEachのアクセス速度のホントの所

Last updated at Posted at 2018-02-19

TL;DR

forとforeachのアクセス速度比較を見てて､完全に間違った結論に達していたからなんとなく､ホントの所を書いておこうかなって｡
最初コメントを書こうかと思ったのだけど､思いのほか書くことが増えたので別のエントリとさせて頂いた次第｡その辺ご了承の程｡
また､ここでは処理効率だけを検証し､書き方としていずれかが望ましいのかという視点はこのエントリでは持っていないので､合わせてご理解頂ければこれ幸い。

で､先に結論だけ言うと､単純にアクセスコストだけ比較すればforの方がforeach使うより190%程度速いよ!

あと､蛇足だけど､ForEachメソッドはCoreではOmitされる程度に使えないし1､使うとやう゛ぁいシナリオがあるから使うべきじゃないよ!

実行環境は.Net Framework 4.7の64bit､使ったライブラリは安心と信頼のBenchMarkDotNetを使った｡また､特に断りが無い限り､デバッガアタッチ無しのReleaseビルドで実行している｡2

どこがマズいのか

画面バッファの状態と実行効率

さて､先のテストではIterationの中身をコンソールへの書き出しとしていた｡
これが実はとんでもなくマズくて､実はコンソールの状態によって書き込みに対する効率が大きく変わる｡
実際に試したのが以下


using System;
using System.Diagnostics;

namespace IterationSurvey
{
	internal class Program
	{
		private static void Main(string[] args)
		{
			const int iterationSize = 100000;

			var first = ConsoleWriteTest(iterationSize);
			var second = ConsoleWriteTest(iterationSize);

			Console.WriteLine($"first:{first.TotalMilliseconds}");
			Console.WriteLine($"second:{second.TotalMilliseconds}");
		}

		private static TimeSpan ConsoleWriteTest(int size)
		{
			GC.Collect();
			GC.WaitForPendingFinalizers();
			GC.Collect();

			var chrono = new Stopwatch();

			chrono.Start();

			for (var i = 0; i < size; i++) Console.WriteLine("");

			chrono.Stop();

			return chrono.Elapsed;
		}
	}
}

上記テストコードの実行結果は

first:4928.8788
second:2797.899

となり､全く同様の処理をしているにも拘わらず､その完了までにかかった時間が2.1秒も違うという結果が出てくる｡

このような差異が出てくる理由を､コンソールの画面バッファが空で､新たにバッファに追記しながら出力が実行された場合と､すでに画面バッファが一杯であり､追記ではなく､古い行を消去しながら出力する場合では､大きな差が出ているのではと仮定した｡

この仮定の下に､以下のように書き換えてみた｡


private static void Main(string[] args)
{
	const int iterationSize = 100000;

	var first = ConsoleWriteTest(iterationSize);
	Console.Clear();	
	var second = ConsoleWriteTest(iterationSize);

	Console.WriteLine($"first:{first.TotalMilliseconds}");
	Console.WriteLine($"second:{second.TotalMilliseconds}");
}

上記テストコードの実行結果は

first:5027.1656
second:4934.7282

となり､当初約2.1秒有った差が､93msと激減している｡

リストに参照型を使うと言うこと

List<T>に対する､Primitiveなアクセス効率を計測しようとしたとき､文字列型を使うのは少々問題がある｡
極めて素朴に考えた場合､C#におけるstringは参照型であり､Listの中身は参照情報､有り体に言ってしまえば文字列実体へのポインタが格納されていることになる｡3

そして､文字列にアクセスすると言うことは､

  1. 配列の参照へのアクセス
  2. 文字列実体へのデリファレンス

という2ステップを取ることになる｡

これは､実際計測しようとしている部分に計測するには邪魔な処理が挟まってしまっていることになり､好ましくはないので､このような場合､intなどのPrimitive型を使うべきだろう｡4

ループ内方でConsole.WriteLineを行うと言うこと｡

現在､比較しようとしていることは､リストに対する各々のIterationの実行効率に差異があるかないか､有るとすればどの程度なのかと言うことであり､
ループ内の処理は素朴に考えれば必要ない｡

また､Console.WriteLineは結構重い処理かつ､先に述べたとおり､全く関係の無い場所で条件により実行効率が大きく変わるので､ループ内の処理としては適当ではないと言える｡
で、重い処理というのは字義通り処理に時間もリソースも食う。結果それは先のように、外部に起因する処理効率の差異を生み出しやすく、また処理に時間がかかると言うことはそれだけばらつきも発生することから、本当に欲しかった結果をマスクしてしまう可能性が非常に高い。

それ故、ループ内にこのような処理を挟むのは極めて不適切である。

その他考慮すべきコト

実際､このほかにもJITにかかる時間をどのように除去するか､とかManagedHeapの容量がリサイズされて安定させるにはどうすれば良いのかなど､結構面倒な考慮事項は多い｡
ただ､この辺はBenchMarkDotNetを使うことで､相当緩和可能なことから､割愛することにした｡

この辺考えて処理効率を改めて検証する

以上のように､なぜマズいのかと言うことを検証してみた｡
それでは実際に､これまでの検証を踏まえた上で処理効率を計ってみたい｡

実験用のコードは以下のようにした｡


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


namespace IterationSurvey
{

	public class IterationBenchmark
	{
		private static readonly List<int> TargetList = Enumerable.Range(0, 100000).ToList();

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

			for (var i = 0; i < TargetList.Count; i++) accum += TargetList[i];

			return accum;
		}

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

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

			return accum;
		}


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

			TargetList.ForEach(i => accum += i);

			return accum;
		}
	}



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

		}

	}
}

ループ内では､uncheckで加算している｡
これは､検証する際に､同じコトをしているか否かの簡易的なチェックをするために行った｡5

で､出てきた結果が以下


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
  [Host]     : .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2633.0
  DefaultJob : .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2633.0
Method Mean Error StdDev
UseFor 117.7 us 0.4220 us 0.3948 us
UseExtForEach 229.9 us 0.7188 us 0.6724 us
UseIntForEach 378.8 us 0.6833 us 0.6392 us

このように､全く違う結果が出てくる｡

なぜforeachが遅いのか?　~まとめに変えて~

結論として､forが一番早く､ついforeach､最後にForEachと言う結果になった｡
なぜforeachはforに勝てなかったかというと､foreachは内部で､GetEnumeratorを呼び出し､Enumeratorを取得している｡
通常の場合､EnumeratorはIEnumeratorとなり､参照型なのだけど､Listの場合､マネージヒープを汚さないためとアロケーションコストを払わないようにするため､foreachを普通に使うのなら､List.Enumerator構造体を使う｡
このように､最適化は掛かってるのだけど､Enumeratorの内部では､Enumerator作成後に元のリストに変更がなかったかのチェック､Currentへの代入など､余計なコストがどうしても発生することになる｡

この辺がforループに勝てない理由じゃないかなと思う｡

また､ForEachによる内部イテレータはactionがCount回呼ばれるのでその呼び出しオーバーヘッドが効いてるのだと思う｡

  1. 記載当時のCore2.1Previewは持ってなかったんだけど、復活してたw ↩

  2. 本当は､Coreの方使いたかったが､ListのForEachメソッドがOmitされていたので､Frameworkを使うこととした｡こー言うことがあるので､まーOmitされてしかるべきだと思う｡ ↩

  3. 実際は""への参照なので､文字列はインターニングされるのと､恐らくインスタンスはCPUのキャッシュに乗っかるので､こんな単純な話にはならない｡ ↩

  4. あくまで今回の目的に限定した結論であると言うことで一つ｡ ↩

  5. 実際の所､foreachはともかくforはこーでもしないと最適化されてループが除去されるかと思ったけど､どーもそうでもないみたい｡この辺参照 ↩

35
37
4

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
35
37

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?