Go to Qiita Advent Calendar 2024 Top
LoginSignup
12
14

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.

@cherry0212(アナミ ゲンタ)

【改訂版】C#におけるループ処理の速度 ～条件／演算子編～

Last updated at Posted at 2019-04-18

#概要
プログラミングにおいて最もボトルネックとなりやすいのが、ループ処理です。
なので、ループ処理の速度に関する事を調べて記述していきます。
環境やループ内の処理によっても違いが出るので、あくまでも参考程度に考えてください。
この記事は C#におけるループ処理の速度 ～条件／演算子編～ の改訂版です。
上記記事にミスがあったため、調べ直した結果をこちらに書いていきます。

テスト環境 プロセッサ　　　：Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz 3.41 GHz 実装メモリ(RAM)：32.0GB システム　　　　：64ビットオペレーティングシステム 言語　　　　　　：C# 7.3 .NET Framework 3.5 ツール　　　　　：Microsoft Visual Studio 2017 #テスト内容 **10億回**または**1億回**のループを行い、ループ内で **[System.Int64](https://docs.microsoft.com/ja-jp/dotnet/api/system.int64?view=netframework-3.5 "System.Int64")** 型の変数に添え字を加算しているだけの処理です。 **[System.Console.WriteLine()](https://docs.microsoft.com/ja-jp/dotnet/api/system.console.writeline?view=netframework-3.5 "System.Console.WriteLine()")** で出力しても良かったんですが、そもそも時間がかかって面倒なのと、コンソールのバッファが作られているか、そもそも文字列は参照を使っている等の理由でテストに向いていないと考えたため、なるべくプリミティブな型のみを使用するように心がけました。 時間の計測は **[System.Diagnostics.Stopwatch](https://docs.microsoft.com/ja-jp/dotnet/api/system.diagnostics.stopwatch?view=netframework-3.5 "System.Diagnostics.Stopwatch")** を使用し、**10回分の平均値**を結果として算出しています。
時間を計測する方法
System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
sw.Reset();
sw.Start();

/* ループ処理 */

sw.Stop();
/* ElapsedMilliseconds メンバから経過したミリ秒を取得 */
long res = sw.ElapsedMilliseconds;

#演算子による速度の違い
forループの再初期化式での演算子の使い方を６つのケースで見ていきます。
インクリメントとデクリメントの前置・後置、+=代入演算子と-=代入演算子です。
##結果
結果から記載します。
テストコードや解説は後述を参照してください。

※2019/04/19
　何故かテスト結果の1の位が抜けていたのを修正

演算子 経過時間（ミリ秒）
i++ 1999
++i 1999
i+=1 1999
i-- 1999
--i 1999
i-=1 2000

すべてのテストでほぼ同じ結果が出ました。
唯一のズレも1ミリ秒なので完全に誤差と考えて良いでしょう。
では、何故同じ結果となるのでしょうか？
###同じ結果となる理由
コンパイル結果を見てみれば一目瞭然です。

コンパイル前後
/* C#コード */
using System;
public class C {
    private static void PostInc()
    {
        for(int i = 0; i < 1000000000; i++)
        {
        }
    }
    
    private static void PreInc()
    {
        for(int i = 0; i < 1000000000; ++i)
        {
        }
    }
    
    private static void SubInc()
    {
        for(int i = 0; i < 1000000000; i+=1)
        {
        }
    }
}

/* 中間言語（CIL） */
.class private auto ansi '<Module>'
{
} // end of class <Module>

.class public auto ansi beforefieldinit C
    extends [mscorlib]System.Object
{
    // Methods
    .method private hidebysig static 
        void PostInc () cil managed 
    {
        // Method begins at RVA 0x2050
        // Code size 17 (0x11)
        .maxstack 2
        .locals init (
            [0] int32
        )

        IL_0000: ldc.i4.0
        IL_0001: stloc.0
        // sequence point: hidden
        IL_0002: br.s IL_0008
        // loop start (head: IL_0008)
            IL_0004: ldloc.0
            IL_0005: ldc.i4.1
            IL_0006: add
            IL_0007: stloc.0

            IL_0008: ldloc.0
            IL_0009: ldc.i4 1000000000
            IL_000e: blt.s IL_0004
        // end loop

        IL_0010: ret
    } // end of method C::PostInc

    .method private hidebysig static 
        void PreInc () cil managed 
    {
        // Method begins at RVA 0x2070
        // Code size 17 (0x11)
        .maxstack 2
        .locals init (
            [0] int32
        )

        IL_0000: ldc.i4.0
        IL_0001: stloc.0
        // sequence point: hidden
        IL_0002: br.s IL_0008
        // loop start (head: IL_0008)
            IL_0004: ldloc.0
            IL_0005: ldc.i4.1
            IL_0006: add
            IL_0007: stloc.0

            IL_0008: ldloc.0
            IL_0009: ldc.i4 1000000000
            IL_000e: blt.s IL_0004
        // end loop

        IL_0010: ret
    } // end of method C::PreInc

    .method private hidebysig static 
        void SubInc () cil managed 
    {
        // Method begins at RVA 0x2090
        // Code size 17 (0x11)
        .maxstack 2
        .locals init (
            [0] int32
        )

        IL_0000: ldc.i4.0
        IL_0001: stloc.0
        // sequence point: hidden
        IL_0002: br.s IL_0008
        // loop start (head: IL_0008)
            IL_0004: ldloc.0
            IL_0005: ldc.i4.1
            IL_0006: add
            IL_0007: stloc.0

            IL_0008: ldloc.0
            IL_0009: ldc.i4 1000000000
            IL_000e: blt.s IL_0004
        // end loop

        IL_0010: ret
    } // end of method C::SubInc

    .method public hidebysig specialname rtspecialname 
        instance void .ctor () cil managed 
    {
        // Method begins at RVA 0x20ad
        // Code size 7 (0x7)
        .maxstack 8

        IL_0000: ldarg.0
        IL_0001: call instance void [mscorlib]System.Object::.ctor()
        IL_0006: ret
    } // end of method C::.ctor

} // end of class C

/* JITによるコンパイル後 */
C..ctor()
    L0000: ret

C.PostInc()
    L0000: push ebp
    L0001: mov ebp, esp
    L0003: xor eax, eax
    L0005: inc eax
    L0006: cmp eax, 0x3b9aca00
    L000b: jl L0005
    L000d: pop ebp
    L000e: ret

C.PreInc()
    L0000: push ebp
    L0001: mov ebp, esp
    L0003: xor eax, eax
    L0005: inc eax
    L0006: cmp eax, 0x3b9aca00
    L000b: jl L0005
    L000d: pop ebp
    L000e: ret

C.SubInc()
    L0000: push ebp
    L0001: mov ebp, esp
    L0003: xor eax, eax
    L0005: inc eax
    L0006: cmp eax, 0x3b9aca00
    L000b: jl L0005
    L000d: pop ebp
    L000e: ret

中間言語やJITのコンパイル後の部分に注目して貰えれば、まったく同じコードが生成されている事が分かります。
最近のコンパイラは結構賢くて、多少ロスがあるコードを組んでも自動的に最適化してくれるんですね。
当然ですが最適化されていなければ（まずそんな環境に出くわす事はないとは思いますが）内部で行っている処理が違うので、速度にも差が出ることになります。
ですが、その辺りまで詳しくやると記事の情報がとっちらかってしまうので、気になった人は自分で調べてみてください。
##テストコード

演算子の速度の違いを調べるテストコード
using System;
using System.Diagnostics;

namespace C
{
	class Program
	{
		static void Main (string[] args)
		{
			long sum;
			long[] result = new long[6];
			Stopwatch sw = new Stopwatch();
			/* 10回分の平均速度を求める */
			for (int loop = 0 ; loop < 10 ; loop++)
			{
				/* i++ */
				sum = 0;
				sw.Reset();
				sw.Start();
				for (int i = 0 ; i < 1000000000 ; i++)
				{
					sum += i;
				}
				sw.Stop();
				result[0] += sw.ElapsedMilliseconds;

				/* ++i */
				sum = 0;
				sw.Reset();
				sw.Start();
				for (int i = 0 ; i < 1000000000 ; ++i)
				{
					sum += i;
				}
				sw.Stop();
				result[1] += sw.ElapsedMilliseconds;

				/* i += 1 */
				sum = 0;
				sw.Reset();
				sw.Start();
				for (int i = 0 ; i < 1000000000 ; i += 1)
				{
					sum += i;
				}
				sw.Stop();
				result[2] += sw.ElapsedMilliseconds;

				/* i-- */
				sum = 0;
				sw.Reset();
				sw.Start();
				for (int i = 999999999 ; i >= 0 ; i--)
				{
					sum += i;
				}
				sw.Stop();
				result[3] += sw.ElapsedMilliseconds;

				/* --i */
				sum = 0;
				sw.Reset();
				sw.Start();
				for (int i = 999999999 ; i >= 0 ; --i)
				{
					sum += i;
				}
				sw.Stop();
				result[4] += sw.ElapsedMilliseconds;

				/* i -= 1 */
				sum = 0;
				sw.Reset();
				sw.Start();
				for (int i = 999999999 ; i >= 0 ; i -= 1)
				{
					sum += i;
				}
				sw.Stop();
				result[5] += sw.ElapsedMilliseconds;
			}
			Console.WriteLine("i++：" + result[0] / 10);
			Console.WriteLine("++i：" + result[1] / 10);
			Console.WriteLine("i+=1：" + result[2] / 10);
			Console.WriteLine("i--：" + result[3] / 10);
			Console.WriteLine("--i：" + result[4] / 10);
			Console.WriteLine("i-=1：" + result[5] / 10);
			Console.ReadKey();
		}
	}
}

#条件式の書き方による速度の違い
ループ処理は、ループ条件の書き方によって速度に差が出ることがあります。
例として配列を使用したループ処理でテストしてみました。
1つは配列のLengthプロパティを用いる方法、2つ目はそのLengthプロパティをローカル変数にキャッシュする方法、最後にループ回数をリテラルで指定する方法です。
配列の要素数の上限の問題で、このテストは1億回のループとなっています。
##結果
結果から記載します。
テストコードや解説は後述を参照してください。

演算子 経過時間（ミリ秒）
プロパティ 359
キャッシュ 319
リテラル 335

1億回のループで最大でも40ミリ秒の差ですから誤差のようなものですが、速度は違うようです。
プロパティを用いる方法が遅い理由は、単純に呼び出しに時間がかかるからですね。
1億回ループを行うという事は、条件式の部分は1億回実行されます。
なので、配列変数を呼び出す時間、そして配列のLengthプロパティを呼び出す時間だけ遅くなってしまいます。
逆にキャッシュが早い理由は、ローカル変数を1つ呼び出すだけで済むため、プロパティよりも早くなります。
リテラルがキャッシュよりも遅い理由ですが、それはコンパイルしたコードを見てみれば分かります。
###リテラルがキャッシュよりも遅い理由
コンパイル結果を見てみれば遅くなる理由は分かります。
ですが、すみませんが何故そのようなコードを生成するのかは私が調べた限りでは分かりませんでした。
分かる方がいらっしゃればコメントお願いします。

コンパイル前後
/* C#コード */
using System;
class C
{
    static void UseProperty (int[] dataArray)
    {
        long sum = 0;
        for (int i = 0 ; i < dataArray.Length ; i++)
        {
            sum += dataArray[i];
        }
    }

    static void UseCache (int[] dataArray)
    {
        long sum = 0;
        for (int i = 0, len = dataArray.Length ; i < len ; i++)
        {
            sum += dataArray[i];
        }
    }

    static void UseLiteral (int[] dataArray)
    {
        long sum = 0;
        for (int i = 0 ; i < 100000000 ; i++)
        {
            sum += dataArray[i];
        }
    }
}

/* 中間言語（CIL） */
.class private auto ansi '<Module>'
{
} // end of class <Module>

.class private auto ansi beforefieldinit C
    extends [mscorlib]System.Object
{
    // Methods
    .method private hidebysig static 
        void UseProperty (
            int32[] dataArray
        ) cil managed 
    {
        // Method begins at RVA 0x2050
        // Code size 25 (0x19)
        .maxstack 3
        .locals init (
            [0] int64,
            [1] int32
        )

        IL_0000: ldc.i4.0
        IL_0001: conv.i8
        IL_0002: stloc.0
        IL_0003: ldc.i4.0
        IL_0004: stloc.1
        // sequence point: hidden
        IL_0005: br.s IL_0012
        // loop start (head: IL_0012)
            IL_0007: ldloc.0
            IL_0008: ldarg.0
            IL_0009: ldloc.1
            IL_000a: ldelem.i4
            IL_000b: conv.i8
            IL_000c: add
            IL_000d: stloc.0
            IL_000e: ldloc.1
            IL_000f: ldc.i4.1
            IL_0010: add
            IL_0011: stloc.1

            IL_0012: ldloc.1
            IL_0013: ldarg.0
            IL_0014: ldlen
            IL_0015: conv.i4
            IL_0016: blt.s IL_0007
        // end loop

        IL_0018: ret
    } // end of method C::UseProperty

    .method private hidebysig static 
        void UseCache (
            int32[] dataArray
        ) cil managed 
    {
        // Method begins at RVA 0x2078
        // Code size 27 (0x1b)
        .maxstack 3
        .locals init (
            [0] int64,
            [1] int32,
            [2] int32
        )

        IL_0000: ldc.i4.0
        IL_0001: conv.i8
        IL_0002: stloc.0
        IL_0003: ldc.i4.0
        IL_0004: stloc.1
        IL_0005: ldarg.0
        IL_0006: ldlen
        IL_0007: conv.i4
        IL_0008: stloc.2
        // sequence point: hidden
        IL_0009: br.s IL_0016
        // loop start (head: IL_0016)
            IL_000b: ldloc.0
            IL_000c: ldarg.0
            IL_000d: ldloc.1
            IL_000e: ldelem.i4
            IL_000f: conv.i8
            IL_0010: add
            IL_0011: stloc.0
            IL_0012: ldloc.1
            IL_0013: ldc.i4.1
            IL_0014: add
            IL_0015: stloc.1

            IL_0016: ldloc.1
            IL_0017: ldloc.2
            IL_0018: blt.s IL_000b
        // end loop

        IL_001a: ret
    } // end of method C::UseCache

    .method private hidebysig static 
        void UseLiteral (
            int32[] dataArray
        ) cil managed 
    {
        // Method begins at RVA 0x20a0
        // Code size 27 (0x1b)
        .maxstack 3
        .locals init (
            [0] int64,
            [1] int32
        )

        IL_0000: ldc.i4.0
        IL_0001: conv.i8
        IL_0002: stloc.0
        IL_0003: ldc.i4.0
        IL_0004: stloc.1
        // sequence point: hidden
        IL_0005: br.s IL_0012
        // loop start (head: IL_0012)
            IL_0007: ldloc.0
            IL_0008: ldarg.0
            IL_0009: ldloc.1
            IL_000a: ldelem.i4
            IL_000b: conv.i8
            IL_000c: add
            IL_000d: stloc.0
            IL_000e: ldloc.1
            IL_000f: ldc.i4.1
            IL_0010: add
            IL_0011: stloc.1

            IL_0012: ldloc.1
            IL_0013: ldc.i4 100000000
            IL_0018: blt.s IL_0007
        // end loop

        IL_001a: ret
    } // end of method C::UseLiteral

    .method public hidebysig specialname rtspecialname 
        instance void .ctor () cil managed 
    {
        // Method begins at RVA 0x20c7
        // Code size 7 (0x7)
        .maxstack 8

        IL_0000: ldarg.0
        IL_0001: call instance void [mscorlib]System.Object::.ctor()
        IL_0006: ret
    } // end of method C::.ctor

} // end of class C

/* JITによるコンパイル後 */
; Desktop CLR v4.7.3324.00 (clr.dll) on amd64.

C..ctor()
    L0000: ret

C.UseProperty(Int32[])
    L0000: xor eax, eax
    L0002: xor edx, edx
    L0004: mov r8d, [rcx+0x8]
    L0008: test r8d, r8d
    L000b: jle L0022
    L000d: movsxd r9, edx
    L0010: mov r9d, [rcx+r9*4+0x10]
    L0015: movsxd r9, r9d
    L0018: add rax, r9
    L001b: inc edx
    L001d: cmp r8d, edx
    L0020: jg L000d
    L0022: ret

C.UseCache(Int32[])
    L0000: xor eax, eax
    L0002: xor edx, edx
    L0004: mov r8d, [rcx+0x8]
    L0008: test r8d, r8d
    L000b: jle L0022
    L000d: movsxd r9, edx
    L0010: mov r9d, [rcx+r9*4+0x10]
    L0015: movsxd r9, r9d
    L0018: add rax, r9
    L001b: inc edx
    L001d: cmp edx, r8d
    L0020: jl L000d
    L0022: ret

C.UseLiteral(Int32[])
    L0000: sub rsp, 0x28
    L0004: xor eax, eax
    L0006: xor edx, edx
    L0008: test rcx, rcx
    L000b: jz L0030
    L000d: cmp dword [rcx+0x8], 0x5f5e100
    L0014: jl L0030
    L0016: movsxd r8, edx
    L0019: mov r8d, [rcx+r8*4+0x10]
    L001e: movsxd r8, r8d
    L0021: add rax, r8
    L0024: inc edx
    L0026: cmp edx, 0x5f5e100
    L002c: jl L0016
    L002e: jmp L004d
    L0030: cmp edx, [rcx+0x8]
    L0033: jae L0052
    L0035: movsxd r8, edx
    L0038: mov r8d, [rcx+r8*4+0x10]
    L003d: movsxd r8, r8d
    L0040: add rax, r8
    L0043: inc edx
    L0045: cmp edx, 0x5f5e100
    L004b: jl L0030
    L004d: add rsp, 0x28
    L0051: ret
    L0052: call 0x7ffdb9ec2660
    L0057: int3

このように、リテラルを用いたループ処理では比較や代入などが何度も行われています。
単純に処理のステップが多いため、リテラルを用いたループ処理はキャッシュを用いたループ処理よりも遅くなっているようです。
基本的にはリテラルの方が早いはずなのですが……分かる方のコメントをお待ちしています。

albireo様のコメントより　※ 2019/04/22 追記
どうやらリテラルの場合は、それが配列の要素数の範囲に収まるかがコンパイル時点では判断出来ないため、
それをループ時にインデックスが配列の範囲外ではないかのチェックを行っている事で速度に差が出てしまっているようです。
これはループに用いる配列を、ループと同じメソッド内で作成しても変わらず、コンパイラはインデックスの範囲外チェックが必要だと判断してしまいました。
上手く回避する方法が見つかれば追記しますが、現状はキャッシュを使用する方法が一番早そうです。

##テストコード

条件式の速度の違いを調べるテストコード
using System;
using System.Diagnostics;

namespace C
{
	class Program
	{
		static void Main (string[] args)
		{
			/* ループ処理に使用する配列を作成する */
			int[] dataArray = new int[100000000];
			for (int i = 0 ; i < 100000000 ; i++)
			{
				dataArray[i] = i;
			}

			/* 10回分の平均速度を求める */
			long sum;
			long[] result = new long[3];
			Stopwatch sw = new Stopwatch();
			for (int loop = 0 ; loop < 10 ; loop++)
			{
				/* 配列のプロパティをそのまま使う */
				sw.Reset();
				sw.Start();
				UseProperty(dataArray);
				sw.Stop();
				result[0] += sw.ElapsedMilliseconds;

				/* 配列のプロパティを変数にキャッシュして使う */
				sw.Reset();
				sw.Start();
				UseCache(dataArray);
				sw.Stop();
				result[1] += sw.ElapsedMilliseconds;

				/* リテラルを使用する */
				sw.Reset();
				sw.Start();
				UseLiteral(dataArray);
				sw.Stop();
				result[2] += sw.ElapsedMilliseconds;
			}
			Console.WriteLine("プロパティ：" + result[0] / 10);
			Console.WriteLine("キャッシュ：" + result[1] / 10);
			Console.WriteLine("　リテラル：" + result[2] / 10);
			Console.ReadKey();
		}

                /* Lengthプロパティを用いたループ処理 */
		static void UseProperty (int[] dataArray)
		{
			long sum = 0;
			for (int i = 0 ; i < dataArray.Length ; i++)
			{
				sum += dataArray[i];
			}
		}

                /* Lengthプロパティをローカル変数にキャッシュしたループ処理 */
		static void UseCache (int[] dataArray)
		{
			long sum = 0;
			for (int i = 0, len = dataArray.Length ; i < len ; i++)
			{
				sum += dataArray[i];
			}
		}

		/* リテラルを用いたループ処理 */
		static void UseLiteral (int[] dataArray)
		{
			long sum = 0;
			for (int i = 0 ; i < 100000000 ; i++)
			{
				sum += dataArray[i];
			}
		}
	}
}

#あとがき
今回は速度の違いについて書きましたが、個人的には「とにかく早ければ良い」という考えは危険だと思っています。
大抵の場合、速いコードほど読みにくいからです（程度の問題ではありますが）。
そして、読みにくいコードというのは得てしてバグの温床になりやすい。
なので、本当に必要な時以外は読みやすいコードを優先した方が良いと思います（これが一番難しい……）。
この記事でも、そこまで読みにくくはならないだろうという程度の小手先しか紹介していません。
本当に速くしたいのならメモリについての知識が必須なので、興味があれば調べてみてください。
あくまでもこの記事はちょっとしたお役立ち知識として参考にしていただけると幸いです。
また、私自身も勉強中の身のため、間違いを見つけたらコメントで指摘していただけるとありがたいです。

12
14
5

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
12
14

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?