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

Формулировка задачи:

Решил поделится своим небольшим опытом по оптимизации вычислений на 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):

                    Листинг программы
                
 
                            
                        
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 потока, т.к. больше для моего ЦП -нет смысла:

                    Листинг программы
                
 
                            
                        
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)

                    Листинг программы
                
 
                            
                        
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. АССЕМБЛЕР... здесь мои знания заканчиваются... Что скажут ОТЦЫ, есть ли дальнейшая оптимизация? В блоге.

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

textual
                            Листинг программы 
                        
z = Int(x * 1.2599)