Форум программистов, компьютерный форум, киберфорум
bedvit
Войти
Регистрация
Восстановить пароль
Рейтинг: 3.67. Голосов: 3.

Оптимизация производительности C#.NET (Алгоритм, Многопоточность, Debug, Release, .Net Core, .Net Native, С++)

Запись от bedvit размещена 26.03.2017 в 13:35
Обновил(-а) bedvit 12.04.2017 в 23:51

Решил поделится своим небольшим опытом по оптимизации вычислений на C#.NET.
НЕ профи, палками не кидать, конструктив приветствуется!
Тестом будет служить время вычисления всех переменных в заданном диапазоне (до 100000) в уравнении x^3 + y^3 = z^3 - 1
Симметричные решения по x и y не учитываем, т.е. из вариантов х=6,у=8,z=9 и х=8,у=6,z=9 - берем один (любой).
Оборудование/Софт:
Кликните здесь для просмотра всего текста
Тип ЦП QuadCore AMD Phenom II X4 Black Edition 955, 3200 MHz (16 x 200)
Системная плата Asus M4A89GTD Pro (2 PCI, 1 PCI-E x1, 1 PCI-E x4, 2 PCI-E x16, 4 DDR3 DIMM, Audio, Video, Gigabit LAN, IEEE-1394)
Чипсет системной платы AMD 890GX, AMD K10
Системная память 8192 МБ (DDR3-1333 DDR3 SDRAM)
Софт Win10x64, Excel2016x64, Visual Studio 2017

ШАГ1. Все кажется просто, берем и перебором ищем значения. Здесь сразу же упираемся в большое количество итераций - время выполнение неприлично большое.

Поэтому ШАГ2 - Оптимизируем алгоритм, создаем массив из степеней Z, переберем значения х, у, обрезаем ненужные итерации, оставляем только один вариант x,y и обрезаем итерации на суммах x^3 + y^3 > z^3. Здесь (код) пальма первенства справедливо принадлежит m-ch - опять неприлично долго в VBA более 10 мин.

ШАГ3. Берем этот алгоритм, переносим на C# и делим потоки, благо это задача хорошо и равномерно параллелится.
Код (Сборка Debug x64):
Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
using System;
using System.Collections.Generic;
using System.Threading;
 
//поиск переменных для решения уравнения x^3 + y^3 = z^3 - 1
class Program
{
    static long n; static long k = 0;
    static long[] a;
 
    static void Main(string[] args)
    {
        var threads = new List<Thread>();
 
        for (int i = 2; i <= 9; i++)
        {
            int k = i;
            threads.Add(new Thread(() => func(k)));
        }
 
        Console.Write("Задайте диапазон расчета переменных, до..., нажмите Enter: ");
        n = Convert.ToInt64(Console.ReadLine());
        a = new long[n + 1];
 
        DateTime dold = DateTime.Now;
 
        for (long i = 1; i <= n; i++)
        {
            a[i] = (long)Math.Pow(i, 3);
        }
 
        threads.ForEach(t => t.Start());
        threads.ForEach(t => t.Join()); //ждем выполнения всех потоков
 
        TimeSpan sp = DateTime.Now - dold;
        Console.WriteLine(sp);
        Console.Write("Программа завершена. Нажмите Enter для выхода...");
        Console.ReadLine();
    }
 
    static void func(long start)
    {
        // здесь код, который будет выполняться в отдельном потоке
        for (long x = start; x <= (long)Math.Pow(((a[n]) - 1) / 2, 1.0 / 3.0); x = x + 8)//на 8 потоков
        {
            for (long y = x; y <= (long)Math.Pow(((a[n]) - 1 - a[x]), 1.0 / 3.0); y++)
            {
                long z3 = a[x] + a[y] + 1;
                long z = (long)(Math.Pow(z3, 1.0 / 3.0) + 0.5);
 
                if (a[z] == z3)
                {
                    k = ++k;
                    Console.WriteLine(k + "   " + x + "   " + y + "   " + z);
                }
            }
        }
    }
}

Время выполнения чуть более 4 минут (по ссылке выше есть так же расчет и на Freebasic). Пока прохладно.

ШАГ4. В C# (как проверено и не только в C#) расчет корня 3 степени медленнее, чем прямой перебор в массиве с некоторой хитростью (т.к. он отсортирован и перебор всегда ведется от меньшего к большему, или наоборот, легко запоминать последнюю найденную позицию и искать начиная с неё в след. цикле). Эта мысль меня посетила и была сразу реализована. Код (Сборка Debug x64) - делю на 4 потока, т.к. больше для моего ЦП -нет смысла:
Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
using System;
using System.Collections.Generic;
using System.Threading;
using System.Diagnostics;
 
namespace ConsoleApplication1
{
    //поиск переменных для решения уравнения x^3 + y^3 = z^3 - 1
    class Program
    {
        static long n; static long k = 0; static long[] a;
        static long threadsN = 4;  //задать 4 потоков
 
        static void Main(string[] args)
        {
            var threads = new List<Thread>();
            for (int i = 1; i <= threadsN; i++)
            {
                int k = i;
                threads.Add(new Thread(() => func(k)));
            }
 
            Console.Write("Задайте диапазон расчета переменных, до..., нажмите Enter: ");
            n = Convert.ToInt64(Console.ReadLine());
            a = new long[n + 1];
 
            //DateTime dold = DateTime.Now;
            Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
            for (long i = 1; i <= n; i++) a[i] = (i * i * i); // Math.Pow не использовал из-за ошибок округления
 
            threads.ForEach(t => t.Start());//стартуем потоки
            threads.ForEach(t => t.Join()); //ждем выполнения всех потоков
 
            sw.Stop();
            //Console.WriteLine(sp);
            Console.WriteLine("Время вычисления: {0}", sw.Elapsed);
            Console.Write("Программа завершена. Нажмите Enter для выхода...");
            Console.ReadLine();
        }
 
        static void func(long start)
        {
            // здесь код, который будет выполняться в отдельном потоке
            long m = n;
            for (long x = start; x <= (long)Math.Pow(((a[n]) - 1) / 2, 1.0 / 3.0); x = x + threadsN)//на 4 потоков
            {
                long s = 1;
                while (a[m] > (a[n]) - 1 - a[x]) m--;
 
                for (long y = x; y <= m; y++)
                {
                    long z3 = a[x] + a[y] + 1;
                    while ((a[s]) <= z3)
                    {
                        if (a[s] == z3)
                        {
                            k++;
                            Console.WriteLine(k + "   " + x + "   " + y + "   " + s);
                        }
                        s++;
                    }
                }
            }
        }
    }
}

Время выполнения - 41 сек. Уже теплее.

ШАГ5. Как же я забыл про Release, срочно исправляюсь - Сборка Release x64.
За счет оптимизации при компилировании получаем время выполнения - 17 секунд. Уже тепло.
Появляются мысли про оптимизацию цикла (в сети множество советов и примеров), т.к. для вычисления требуется несколько миллиардов итераций. Думаю.

ШАГ6. Почитав про .Net Core, решил попробовать.
Новый проект - Консольное приложение .Net Core - вставляем предыдущий код и ...
Время выполнения - 10,5 сек.
Здесь мне кажется, что сделан максимум на C#.

ШАГ7. Решил добить тему и погуглить.
Есть интересный зверь net native, подробно писать здесь не буду. Кратко: В Windows 10 универсальные Windows-приложения на управляемых языках (C#, VB) проходят в магазине процедуру компиляции в машинный код с использованием .NET Native.
Поэтому: создать проект-пустое приложение (универсальное приложение Windows)(UWP).
Создаем button, textBox (на кнопку код, в textBox - переменные).
Здесь нас поджидает проблемы с Threading.
Переходим на Task, двигаем дальше.
Код (Сборка Release x64)
Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
using System;
using System.Collections.Generic;
using Windows.UI.Xaml;
using Windows.UI.Xaml.Controls;
using System.Threading.Tasks;
using System.Diagnostics;
 
namespace App1
{
    public sealed partial class MainPage : Page
    {
        static long n; static long k = 0; static long[] a; static string str = "";
        static long TaskN = 4;  //задать 4 task
 
        public MainPage()
        {
            this.InitializeComponent();
        }
            private void Button_Click(object sender, RoutedEventArgs e)
        {
            n = 100000;
            a = new long[n + 1];
            Stopwatch sw = Stopwatch.StartNew();
 
            for (long i = 1; i <= n; i++) a[i] = (i * i * i); // Math.Pow не использовал из-за ошибок округления
 
            var task = new List<Task>();
            for (int i = 1; i <= TaskN; i++)
            {
                int k = i;
                task.Add(new Task(() => func(k)));
            }
            task.ForEach(t => t.Start());//стартуем task
            task.ForEach(t => t.Wait()); //ждем выполнения всех task
            sw.Stop();
            button.Content = sw.Elapsed.TotalSeconds;
            textBox.Text = str;
        }
 
        static void func(long start)
        {
            // здесь код, который будет выполняться в отдельном task
            long m = n;
            
            for (long x = start; x <= (long)Math.Pow(((a[n]) - 1) / 2, 1.0 / 3.0); x=x+TaskN) //на 4 task
            {
                long s = 1;
                while (a[m] > (a[n]) - 1 - a[x]) m--;
 
                for (long y = x; y <= m; y++)
                {
 
                    long z3 = a[x] + a[y] + 1;
                    while ((a[s]) <= z3)
                    {
                        if (a[s] == z3)
                        {
                            k++;
                            str = str + Environment.NewLine + (k + "   " + x + "   " + y + "   " + s);
                        }
                        s++;
                    }
                }
            }
        }
    }
}

Время выполнения 7,5 сек.
Без вывода строки 5 сек.(подумать со строкой)

ШАГ8. АССЕМБЛЕР(?)... здесь мои знания заканчиваются...

...удалось оптимизировать далее при обсуждении на форуме...

ШАГ8. Убрать проверку индексов массива (unsafe - Небезопасный код).
Время выполнения 3,9 сек.

ШАГ9. Переписать программу на С++
Оптимизированная версия (без ассемблерных вставок, но может они и не нужны при хорошей оптимизации, компилятор выдаст что-то похожее).
Время выполнения 3,76 сек. Прирост на 4-20% в зависимости от конфигурации ПК (сборка х64).
Вложения
Тип файла: rar C++(x^3+y^3=z^3-1).rar (190.5 Кб, 145 просмотров)
Тип файла: rar C#(x^3+y^3=z^3-1).rar (3.2 Кб, 146 просмотров)
Размещено в VB, C#.NET, С++
Показов 925 Комментарии 2
Всего комментариев 2
Комментарии
  1. Старый комментарий
    Аватар для bedvit
    Обсуждения в теме:
    https://www.cyberforum.ru/csha... st10258822
    Запись от bedvit размещена 26.03.2017 в 13:42 bedvit вне форума
  2. Старый комментарий
    Аватар для bedvit
    Переписал код на С++
    https://www.cyberforum.ru/cpp-... st10304017
    Запись от bedvit размещена 12.04.2017 в 19:35 bedvit вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.