.net framework｜Memeplexes

[PR]

2024年04月27日

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

Linq vs List vs T[] vs ポインタ　パフォーマンス対決

一番早いのはどれ?

Deep Learningが十分に重い事がわかったので、パフォーマンスを追求してみます。
LinqのSumメソッドとList<T>、T[]の手続き的な合計を比較してみます。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

public struct Synapse
{
    public Neuron SourceNeuron;
    public SymmetricConnection Connection;
}

public class SymmetricConnection
{
    public double Weight;
    public double DeltaWeight;
    public Neuron VisibleNeuron;
    public Neuron HiddenNeuron;

    public void Learn(double learningRate)
    {
        this.DeltaWeight +=
            learningRate * VisibleNeuron.Value * HiddenNeuron.Probability;
    }

    public void EndLearning()
    {
        this.Weight += this.DeltaWeight;
        this.DeltaWeight = 0;
    }

    public static double[][] CreateRandomWeights(Random random, int visibleNeuronCount, int hiddenNeuronCount)
    {
        var result = createJaggedArray<double>(visibleNeuronCount, hiddenNeuronCount);

        double a = 1.0 / visibleNeuronCount;

        for (int i = 0; i < visibleNeuronCount; i++)
        {
            for (int j = 0; j < hiddenNeuronCount; j++)
            {
                result[i][j] = uniform(random, -a, a);
            }
        }

        return result;
    }

    private static T[][] createJaggedArray<T>(int visibleNeuronCount, int hiddenNeuronCount)
    {
        var result = new T[visibleNeuronCount][];

        for (int i = 0; i < visibleNeuronCount; i++)
        {
            result[i] = new T[hiddenNeuronCount];
        }

        return result;
    }

    private static double uniform(Random random, double min, double max)
    {
        return random.NextDouble() * (max - min) + min;
    }

    public static SymmetricConnection[][] CreateConnections(double[][] weights, Neuron[] visibleNeurons, Neuron[] hiddenNeurons)
    {
        var result = createJaggedArray<SymmetricConnection>(visibleNeurons.Length, hiddenNeurons.Length);

        for (int i = 0; i < visibleNeurons.Length; i++)
        {
            for (int j = 0; j < hiddenNeurons.Length; j++)
            {
                SymmetricConnection connection = new SymmetricConnection();
                connection.Weight = weights[i][j];
                connection.VisibleNeuron = visibleNeurons[i];
                connection.HiddenNeuron = hiddenNeurons[j];
                result[i][j] = connection;
            }
        }

        return result;
    }
}

public class Neuron
{
    public double Value;
    public double Probability;
    public double Bias;
    public double DeltaBias;
    public List<Synapse> Synapses = new List<Synapse>();
    private Synapse[] SynapseArray;
    public Random Random;

    public void UpdateByLinq()
    {
        this.Probability = sigmoid(GetInputFromSourceNeuronsByLinq() + Bias);
        this.Value = nextBool(Random, this.Probability) ? 1 : 0;
    }

    private double GetInputFromSourceNeuronsByLinq()
    {
        return Synapses.Sum(s => s.Connection.Weight * s.SourceNeuron.Value);
    }

    public void UpdateByList()
    {
        this.Probability = sigmoid(GetInputFromSourceNeuronsByList() + Bias);
        this.Value = nextBool(Random, this.Probability) ? 1 : 0;
    }

    private double GetInputFromSourceNeuronsByList()
    {
        double result = 0;

        for (int i = 0; i < SynapseArray.Length; i++)
        {
            var s = Synapses[i];
            result += s.Connection.Weight * s.SourceNeuron.Value;
        }

        return result;
    }

    public void UpdateBySynapseArray()
    {
        this.Probability = sigmoid(GetInputFromSourceNeuronsBySynapseArray() + Bias);
        this.Value = nextBool(Random, this.Probability) ? 1 : 0;
    }

    private double GetInputFromSourceNeuronsBySynapseArray()
    {
        double result = 0;

        for (int i = 0; i < SynapseArray.Length; i++)
        {
            var s = SynapseArray[i];
            result += s.Connection.Weight * s.SourceNeuron.Value;
        }

        return result;
    }

    public static Neuron[] CreateNeurons(double[] biases)
    {
        Neuron[] result = new Neuron[biases.Length];

        for (int i = 0; i < result.Length; i++)
        {
            result[i] = new Neuron { Bias = biases[i] };
        }

        return result;
    }

    public static void WireConnections(SymmetricConnection[][] connections)
    {
        foreach (var connectionRow in connections)
        {
            foreach (var connection in connectionRow)
            {
                Synapse hiddenConnection = new Synapse();
                hiddenConnection.Connection = connection;
                hiddenConnection.SourceNeuron = connection.VisibleNeuron;
                connection.HiddenNeuron.Synapses.Add(hiddenConnection);

                Synapse visibleConnection = new Synapse();
                visibleConnection.Connection = connection;
                visibleConnection.SourceNeuron = connection.HiddenNeuron;
                connection.VisibleNeuron.Synapses.Add(visibleConnection);
            }
        }
    }

    public void UpdateSynapseArray()
    {
        this.SynapseArray = Synapses.ToArray();
    }

    private static double sigmoid(double x)
    {
        return 1.0 / (1.0 + Math.Exp(-x));
    }

    private static bool nextBool(Random random, double rate)
    {
        if (rate < 0 || 1 < rate) return false;
        return random.NextDouble() < rate;
    }
}

class Program
{
    static void Main(string[] args)
    {
        var visibleNeurons = Neuron.CreateNeurons(Enumerable.Range(0, 100).Select(i => (double)i).ToArray());
        var hiddenNeurons = Neuron.CreateNeurons(Enumerable.Range(0, 1000).Select(i => (double)i).ToArray());
        var connections = SymmetricConnection.CreateConnections(
            SymmetricConnection.CreateRandomWeights(new Random(0), visibleNeurons.Length, hiddenNeurons.Length),
            visibleNeurons,
            hiddenNeurons
            );
        Neuron.WireConnections(connections);
        var random = new Random(0);

        foreach (var neuron in hiddenNeurons)
        {
            neuron.Random = new Random(random.Next());
            neuron.UpdateSynapseArray();
        }

        foreach (var neuron in visibleNeurons)
        {
            neuron.Random = new Random(random.Next());
            neuron.UpdateSynapseArray();
        }

        int loopCount = 1000;

        Stopwatch stopwatch = new Stopwatch();

        stopwatch.Start();

        for (int i = 0; i < loopCount; i++)
        {
            foreach (var neuron in visibleNeurons)
            {
                neuron.UpdateByLinq();
            }
        }

        stopwatch.Stop();

        Console.WriteLine("Linq : " + stopwatch.Elapsed.TotalMilliseconds);
        GC.Collect();

        stopwatch.Restart();

        for (int i = 0; i < loopCount; i++)
        {
            foreach (var neuron in visibleNeurons)
            {
                neuron.UpdateByList();
            }
        }

        stopwatch.Stop();

        Console.WriteLine("List : " + stopwatch.Elapsed.TotalMilliseconds);
        GC.Collect();

        stopwatch.Restart();

        for (int i = 0; i < loopCount; i++)
        {
            foreach (var neuron in visibleNeurons)
            {
                neuron.UpdateBySynapseArray();
            }
        }

        stopwatch.Stop();

        Console.WriteLine("Array : " + stopwatch.Elapsed.TotalMilliseconds);
    }
}

結果はこちら：

Linq : 8770.8684
List : 1424.852
Array : 1097.6195

単なる合計

Linqは便利ですがやはり遅いですね。
私のDeep Learningのコードでは実はここがボトルネックになっています。
ここではLinqは使えませんね。

せっかくなので、ポインタも使ってみることにしました。

using System;
using System.Diagnostics;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static unsafe void Main(string[] args)
    {
        int loopCount = 10000;
        List<float> numberList = Enumerable.Range(0, 10000).Select(i => (float)i).ToList();
        float[] numberArray = numberList.ToArray();
        Stopwatch stopwatch = new Stopwatch();

        float resultLinq = 0;
        stopwatch.Start();


        for (int i = 0; i < loopCount; i++)
        {
            resultLinq += numberList.Sum(number => number * number);
        }

        stopwatch.Stop();

        Console.WriteLine("Linq : " + stopwatch.Elapsed.TotalMilliseconds);
        Console.WriteLine("\t" + resultLinq);
        GC.Collect();

        float resultList = 0;
        stopwatch.Restart();


        for (int i = 0; i < loopCount; i++)
        {
            float result = 0;

            for (int index = 0; index < loopCount; index++)
            {
                float number = numberList[index];
                result += number * number;
            }

            resultList += result;
        }

        stopwatch.Stop();

        Console.WriteLine("List : " + stopwatch.Elapsed.TotalMilliseconds);
        Console.WriteLine("\t" + resultList);
        GC.Collect();

        float resultArray = 0;
        stopwatch.Restart();

        for (int i = 0; i < loopCount; i++)
        {
            float result = 0;

            for (int index = 0; index < loopCount; index++)
            {
                float number = numberArray[index];
                result += number * number;
            }

            resultArray += result;
        }

        stopwatch.Stop();

        Console.WriteLine("Array : " + stopwatch.Elapsed.TotalMilliseconds);
        Console.WriteLine("\t" + resultArray);
        GC.Collect();

        float resultPointer = 0;
        stopwatch.Restart();

        for (int i = 0; i < loopCount; i++)
        {
            float result = 0;

            fixed (float* numberPointer = numberArray)
            {
                for (int index = 0; index < loopCount; index++)
                {
                    float number = numberPointer[index];
                    result += number * number;
                }
            }

            resultPointer += result;
        }

        Console.WriteLine("Pointer : " + stopwatch.Elapsed.TotalMilliseconds);
        Console.WriteLine("\t" + resultPointer);
        GC.Collect();
    }
}

実行結果はこうなります：

Linq : 5386.1902
        3.333105E+15
List : 1051.6524
        3.333105E+15
Array : 1047.8888
        3.333105E+15
Pointer : 1099.8356
        3.333105E+15

やはりLinqは重いです。
しかし思ったほどポインタは速くなりませんね。
きっとコンパイラの中で最適化されているのでしょう。

[0回]

Parallel.ForEachの使い方

Parallel.ForEach()の使い方をまとめようと思います。
Parallel.ForEach()はデータを並列に処理するときに使います。
参考：Parallel Aggregation

ふつうのforeachを使う

まずは、普通のforeachを使った場合。
Parallel.ForEach()を使わなかった場合どうなるかです。

using System;
using System.Linq;
using System.Diagnostics;

class Program
{
    static void Main(string[] args)
    {
        var numbers = Enumerable.Range(0, 100000000).ToArray();
        ulong sum = 0;

        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();

        foreach (var number in numbers)
        {
            sum += (ulong)number;
        }
        

        stopwatch.Stop();
        Console.WriteLine("sum : " + sum);
        Console.WriteLine(stopwatch.Elapsed.TotalMilliseconds + "ms");
        Console.ReadLine();
    }
}

実行結果はこうなります。

sum : 4999999950000000
449.1242ms

私の環境では実行時間は0.5秒くらいですね。

Parallel.ForEachを使う（エラー！）

error!

using System;
using System.Linq;
using System.Diagnostics;
using System.Threading.Tasks;

class Program
{
    static void Main(string[] args)
    {
        var numbers = Enumerable.Range(0, 100000000).ToArray();
        ulong sum = 0;

        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();

        Parallel.ForEach(
            numbers,
            number =>
        {
            sum += (ulong)number;
        });

        stopwatch.Stop();
        Console.WriteLine("sum : " + sum);
        Console.WriteLine(stopwatch.Elapsed.TotalMilliseconds + "ms");
        Console.ReadLine();
    }
}

実行結果はこうなります。

sum : 1852281973816843
1711.2386ms

！
遅くなってる！？
なんという事でしょうか並列実行したのに実行時間が増えています。
私の環境には8コアあるというのにです。
おそらくこれはオーバーヘッドのためです。
Parallel.ForEachは気軽には使えないということでしょうか…。

そしてなによりも計算結果が間違っています。
ひどいですね。
これは複数のスレッドが一度にひとつの変数sumを読み書きしたせいでしょう。

lockで計算結果を正す

では計算結果を正しくするにはどうすればいいのでしょう？
sumを読み書きできるのはひとつのスレッドだけということにすればいいのです。
これにはlockを使います。

using System;
using System.Linq;
using System.Diagnostics;
using System.Threading.Tasks;

class Program
{
    static void Main(string[] args)
    {
        var numbers = Enumerable.Range(0, 100000000).ToArray();
        ulong sum = 0;

        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();

        Parallel.ForEach(
            numbers,
            number =>
        {
            lock (numbers)
            {
                sum += (ulong)number;
            }
        });

        stopwatch.Stop();
        Console.WriteLine("sum : " + sum);
        Console.WriteLine(stopwatch.Elapsed.TotalMilliseconds + "ms");
        Console.ReadLine();
    }
}

sum : 4999999950000000
9717.7726ms

結果は正しくなりました。
しかし更に遅くなっています。
約１０秒です。

スレッドローカルデータを使う

このままではあまりにも遅いので何とかしましょう。
lockを毎回使っているのを何とかするのです。
lockは重いそうですからね。

そこで１スレッドにあるulongの変数を用意して、そこに（lockを使わず）足しあわせ、
最後にlockを使って足し合わせます。

using System;
using System.Linq;
using System.Diagnostics;
using System.Threading.Tasks;

class Program
{
    static void Main(string[] args)
    {
        var numbers = Enumerable.Range(0, 100000000).ToArray();
        ulong sum = 0;

        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();

        Parallel.ForEach(
            numbers,
            () => (ulong)0,
            (number, state, localSum) =>
            {
                return localSum + (uint)number;
            },
            threadLocalSum =>
            {
                lock (numbers)
                {
                    sum += threadLocalSum;
                }
            });

        stopwatch.Stop();
        Console.WriteLine("sum : " + sum);
        Console.WriteLine(stopwatch.Elapsed.TotalMilliseconds + "ms");
        Console.ReadLine();
    }
}

実行結果はこうなります。

sum : 4999999950000000
580.938ms

実行時間がさっきよりは短くなりました。
しかし相変わらず普通のforeachよりは遅いです。
グラフにすると次のようになります。

繰り返し回数が1の時異常にパフォーマンスが低くなっているのが謎です。
あと並列のほうが遅いのも変ですね。

結論

今回試したケースではParallel.ForEachよりforeachのほうが速いです…

Parallel.ForEachのほうが速くなるケース

しかしそれだけでは結論として物足りないので、Parallel.ForEachの方が早くなるプログラムを作ってみました。
もっとも私の環境ではという条件付きですが…。

using System;
using System.Linq;
using System.Diagnostics;
using System.Threading.Tasks;

class Program
{
    const int iteration = 1000;
    const int numbers2Count = 10000;

    static void Main(string[] args)
    {
        var numbers = Enumerable.Range(0, iteration);

        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();

        var sum = serialSum(numbers);
        //var sum = parallelSum(numbers);

        stopwatch.Stop();
        Console.WriteLine("sum : " + sum);
        Console.WriteLine(stopwatch.Elapsed.TotalMilliseconds + "ms");
        Console.ReadLine();
    }

    private static ulong serialSum(System.Collections.Generic.IEnumerable<int> numbers)
    {
        ulong sum = 0;

        foreach (var number in numbers)
        {
            var numbers2 = Enumerable.Range(0, numbers2Count);
            sum += (ulong)numbers2.Sum();
        }

        return sum;
    }

    private static ulong parallelSum(System.Collections.Generic.IEnumerable<int> numbers)
    {
        ulong sum = 0;

        Parallel.ForEach(
            numbers,
            () => (ulong)0,
            (number, state, threadLocalSum) =>
            {
                return threadLocalSum + (ulong)Enumerable.Range(0, numbers2Count).Sum();
            },
            threadLocalSum =>
            {
                lock (numbers)
                {
                    sum += threadLocalSum;
                }
            });

        return sum;
    }
}

serialSum() : 83.5064ms
parallelSum() : 52.2337ms

なんとか並列処理のほうが速くなりました！
もしかしてデータ数がある程度少なく、１つあたりの処理が重いほうがParallel.ForEachは速くなるのでしょうか？？（←後の実験で半分否定されました。データ数はあまり関係ないようです。）
さらなる実験が必要とされそうです。

するとこうなりました：

最初に時間がかかりまくっているのが謎ですが、それ以降はきちんと理にかなったグラフになっていますね。

[1回]

04/21/2012 訂正：自己解決しました
有益なコメントも頂きました
詳しくはこちら

.netな動的言語については詳しくないのですが
（というかほとんど全然知らないのですが）、
複数のサイトによると（Dynamically Compiling C#、IronPythonの特徴）
IronPythonは属性をどうも使えないらしいです。

で、どうやらその理由が動的言語であることに由来するらしいのです。
本当かは判断できませんが・・・。

とすると、もしかしてIronSchemeでも属性が使えないのでしょうか？
ぱっと見たところ、属性を付与する命令というか方法はないように見えます（一日中調べました）。

属性が使えないことの何が嫌かというと、もちろん
（上で引用した記事にも書いてあるように）
WCFが上手く使えないということもあるのでしょうが、
WPFも使えないのではないかということです。
ウィンドウを表示してワイワイ賑やかになれないということです。

WPFはSTAThreadで動きます。
なのでMainメソッドにSTAThread属性を与えてやらなければ
InvalidOperationExceptionをスローして強制終了です。
そして動的言語では属性を与えられない（のでしょうか？）。
つまり動的言語は全てWPFを使えないことになってしまうのでしょうか？
（いやでも、ググるとIronPythonでWPFを使っている例が見つかりますね。あれ・・・？？）

ちなみに、こんなコードを書いてクラッシュしました：

(import (rnrs) (ironscheme clr))

(clr-reference PresentationFramework)
(clr-reference PresentationCore)
(clr-reference System.Xaml)
(clr-reference WindowsBase)

(clr-using System.Windows)

;[System.STAThread] might be needed.

(define app (clr-new Application))
(clr-call Application Run app (clr-new Window))

で、こちらがエラーです：

Unhandled CLR exception during evaluation:
CLR Exception: System.InvalidOperationException
System.InvalidOperationException: The calling thread must be STA, because many U
I components require this.
   at System.Windows.Input.InputManager..ctor()
   at System.Windows.Input.InputManager.GetCurrentInputManagerImpl()
   at System.Windows.Input.KeyboardNavigation..ctor()
   at System.Windows.FrameworkElement.EnsureFrameworkServices()
   at System.Windows.FrameworkElement..ctor()
   at System.Windows.Controls.Control..ctor()
   at System.Windows.Window..ctor()
   at eval-core(003).$2()
   at #.psyntax.expander::compile-r6rs-top-level#anon#1#2$2505(CodeContext $cont
ext)
   at #.ironscheme.exceptions::dynamic-wind(Object in, Object proc, Object out)
   at #.psyntax.main::load-port#1$2552(CodeContext $context)
   at #.ironscheme.exceptions::dynamic-wind(Object in, Object proc, Object out)
   at IronScheme.Runtime.Builtins.CallWithCurrentContinuation(Object fc1)
   at IronScheme.Runtime.R6RS.Exceptions.WithClrExceptionHandler(Object handler,
 Object thunk)

どなたかご存じの方に教えていただきたいです！

04/21/2012 訂正 : 自己解決しました
有益なコメントも頂きました
詳しくはこちら

[0回]