1

我有一个小程序，我正在尝试提高其性能。该程序非常简单，主要基于单个递归函数。然而，它背后的数据集非常大 - 需要大约 6,000,000,000 次递归，运行大约需要 4-6 小时，具体取决于机器。没有只处理数据的 I/O，我花了很多时间优化代码并设法找到了大约 60% 的改进。

我现在想看的是多线程代码，以便它利用主机中的所有内核。但是，我尝试使用线程、任务和 Parellel 库的位，但我一直找不到任何不会以负面方式影响性能的东西。

为了让您了解我正在查看的代码类型：

class Program
{
    static void Main(string[] args)
    {
        RecursiveFunction(0);
        Console.ReadLine();
    }
    static void RecursiveFunction(int currentLevel)
    {
        DoWork(currentLevel);

        if (currentLevel < 1000)
            for (int i = 0; i < (currentLevel % 6) + 1; i++)
                RecursiveFunction(currentLevel + 1);
    }
    static void DoWork(int currentLevel)
    {
        Thread.Sleep(42);
    }
}

如您所见，函数的每次运行都不会花费很长时间，因此为每次递归创建线程的成本是不值得的。递归的每个分支都可以有不同的长度，而无法知道每个分支将有多长，因此在特定级别的线程不是正确的方法。

有没有人有什么建议？

4

3 回答 3

2

在树的上层使用并行性。那里的每次调用都需要几分钟到几小时，因此线程的开销非常小。

使用这些Parallel.For*方法并行执行循环。

在递归树的较低层使用正常的顺序循环。

以导致几千次并行循环迭代的方式选择截止级别。

于 2013-01-04T19:54:04.980 回答
0

您始终可以使用下面的代码链接您的任务，并让任务调度程序安排您的工作。

class Program
    {
        private static int MaxLevel = 1000;
        static void Main(string[] args)
        {
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();

            Task mainTask = ParallelRecursiveFunction(0);
            mainTask.Wait();
            stopwatch.Stop();
            Console.WriteLine("Total time of parallel execution  : {0}", stopwatch.ElapsedMilliseconds);


            Console.WriteLine("Press Enter to execute the operation sequentially");
            Console.WriteLine();
            Console.ReadLine();
            stopwatch.Reset();
            stopwatch.Start();

            SequentialRecursiveFunction(0);

            stopwatch.Stop();

            Console.WriteLine("Total time of sequential execution: {0}",stopwatch.ElapsedMilliseconds);
            Console.ReadLine();
        }

        private static void SequentialRecursiveFunction(int currentLevel)
        {
            if (currentLevel >= MaxLevel)
                return;
            DoWork(currentLevel);

            SequentialRecursiveFunction(currentLevel +1);
        }

        public static Task ParallelRecursiveFunction(int currentLevel)
        {
            if (currentLevel >= MaxLevel)
                return _completedTask;
            Task t1 = Task.Factory.StartNew(() => DoWork(currentLevel));

            Task<Task> t2 = Task.Factory.StartNew(() => ParallelRecursiveFunction(currentLevel + 1));

            return Task.Factory.ContinueWhenAll(new Task[] { t1, t2.Unwrap() }, Task.WaitAll);

        }
        private static Task _completedTask = ((Func<Task>)(() =>
        {
            var tcs = new TaskCompletionSource<object>();
            tcs.SetResult(null);
            return tcs.Task;
        }))();

        static void DoWork(int currentLevel)
        {
            Console.WriteLine("Do work at level {0}", currentLevel);

            Thread.Sleep(42);

        }
    }

我测试了我的并行代码运行速度比顺序算法快大约 4 倍（= 我机器上的处理器数量）。

请让我知道你的想法。

干杯。

于 2013-01-05T12:17:37.270 回答
0

在不了解应用程序的情况下很难发表评论。

对于相同的 level 值，递归函数被多次调用。你能收获之前运行的结果对于相同的 level 值吗？...我猜不是，您可能对副作用而不是运行结果感兴趣。

您是否尝试过使用 .NET 4.5 (VS 2012) TAP ？使用 async / await，Tasks，您可以尝试使用 Task.ContinueWith 来链接具有相同（级别 % CORE_COUNT ）的递归调用。这可能有助于平衡所有任务以及所有核心的负载。 MSDN：链接多个任务。

我希望你能回复对你有用的策略。

于 2013-01-04T18:44:08.883 回答