Jak przyspieszyć działanie programu?

Napisałem aplikację, która szuka optymalnego rozwiązania za pomocą algorytmy ewolucyjnego dla złożonego problemu.

Jednak aplikacja puszczona liczy wszystko przez ok. 100 min. A trzeba wyniki pozbierać dla wielu rożnych dobranych parametrów. Znacie jakieś sposoby by przyspieszyć działanie programu. W menedżerze zadań program uruchomiony zabiera 5%-6% pamięci i 25%-30% procesora, więc widać że z mocy komputera możnaby jeszcze sporo wyciągnąć. W czym problem?

To że kod można zoptymalizować to wiem, ale po walkach godzinnych z błędami wolałbym tam już nie grzebać. Z kodu jedynie wiem na 100% że trochę zabiera czasu serializacja do memoryStream i deserializacja, w ten sposób klonuję obiekty. Wiem że lepiej to można zrobić ale obiekt ma trochę referencji, które mają referencję itd. i sporo roboty by przy ręcznym pisaniu metody kopiującej zeszło czasu.

1. Procenty w wykorzystaniu procesora. Chodzi tutaj o rdzenie, masz pewnie procesor 4 rdzeniowy a Twój algorytm wykorzystuje tylko jedne wątek. Nie przeskoczysz tego, chyba że go zrównoleglisz. Są specjalne algorytmy ewolucyjne równoległe (np wyspowe), można również zrównoleglać liczenie funkcji fitness.
2. Co do optymalizacji samego algorytmu. Piszesz że klonujesz obiekty bo mają dużo referencji. Pisząc obiekt masz na myśli osobnika populacji? Jeśli tak to zastanów się nad prostszą reprezentacją genotypu, w algorytmach takich chodzi właśnie o to żeby była jak najprostsza, zazwyczaj jakaś tablica intów czy coś. Dzięki temu masz szybkie operatory krzyżowania/mutacji.

najlepiej poczytaj to: http://msdn.microsoft.com/en-us/library/ff963552.aspx
w algorytmie ewolucyjnym jest wiele pętli, w których iteracje są niezależne od siebie, a to rozwiązanie uwolni cię od samodzielnego kombinowania z wątkami i aplikacja sama będzie się skalować w zależności od tego ile rdzeni ma system, na którym działa aplikacja.

Mam 2 rdzenie.
Boję się że jak wrzucę tam pracę na wątkach to się wszystko rozwali, bo już takie jazdy miewałem z wątkami, że strach.
Problem jest trochę skomplikowany i wszystko jest powiązane, ciężko to inaczej zrobić niż po prostu powiązanymi ze sobą obiektami, aczkolwiek przy krzyżowaniu i mutacji robię z tego prostą w miarę reprezentację genową. Jednak z samej reprezentacji genowej nie obliczysz fkcji fitness itd. Wierzcie mi że kod jest bardzo zawiły niestety. Miał być o wiele prostszy ale wyniki były błędne więc zacząłem na szybko rzeźbić byleby działało no i takie są efekty.

Co do niezależnych iteracji to widocznie coś źle zrobiłem, bo jeśli program nie pójdzie "po kolei" to nie wyjdzie z tego nic dobrego. Wszystko jeszcze komplikuje fakt, że na raz jest puszczonych wiele populacji i potem wynikami są średnie, dodatkowo co generację rysowane są na bieżąco wykresy.

Wasyl0 napisał(a):

Boję się że jak wrzucę tam pracę na wątkach to się wszystko rozwali, bo już takie jazdy miewałem z wątkami, że strach.

Nie masz testów?

Akurat użycie parallel loops jest najbardziej bezbolesną formą pracy z wątkami.

dodatkowo co generację rysowane są na bieżąco wykresy.

Gdzie rysowane? Bo to też może być wąskie gardło.

Generalnie, to nikt Ci nie wywróży, czemu Twój program działa wolno. Zbadaj go profilerem, to się dowiesz.

Połowę czasu zabiera wielokrotne wykonanie serializacji i deserializacji w celu utworzenia obiektu-klona. Może jest jakiś sposób aby działało te parę linijek szybciej lub zastąpić je czymś innym? Ręczne robienie metod głębokiego klonowania niezbyt mi się uśmiecha.

 MemoryStream stream = new MemoryStream();
            IFormatter formatter = new BinaryFormatter();
            formatter.Serialize(stream, this);


            IFormatter formatter2 = new BinaryFormatter();
            stream.Seek(0, SeekOrigin.Begin);
            object o2 = formatter2.Deserialize(stream); 

class Osobnik : ICloneable
    {
        public object Clone()
        {
            MemoryStream stream = new MemoryStream();
            IFormatter formatter = new BinaryFormatter();
            formatter.Serialize(stream, this);


            IFormatter formatter2 = new BinaryFormatter();
            stream.Seek(0, SeekOrigin.Begin);
            object o2 = formatter2.Deserialize(stream);

            return o2;
        }
...
 

Wasyl0 napisał(a):

Ręczne robienie metod głębokiego klonowania niezbyt mi się uśmiecha.

Klasa Osobnik jest aż tak bardzo skomplikowana? Bo może jednak warto to zrobić ręcznie, serializacja jest przyjemna, ale trochę waży.

A w jakim celu w ogóle klonujesz te obiekty? Może to nie jest potrzebne.

Inna rzecz, że programowanie obiektowe jest fajne, nawet bardzo fajne, ale matematykę lepiej (a na pewno szybciej) robi się na macierzach i wektorach.

klasa Osobnik ma kilka list w których są referencje, w których są znowu listy z obiektami.

Czemu klonuję?:
Powiedzmy że robimy selekcję osobników turniejową.
Z populacji np. 100, losujemy dziesiątkę losową i najlepszego przenosimy do nowej populacji i tak wykonujemy tą operację 100 razy bo rozmiar populacji nie może się zmieniać. Wiadome że bardzo dobry osobnik prawdopodobnie zostanie wybrany kilka razy do nowej populacji. I nie może to być oczywiście ta sama referencja, bo poźniej jakbyśmy go zmutowali, to okazałoby się że zmutowało się przy okazji mnówstwo innych osobników z populacji.

Obiektowo do tego podszedłem ponieważ problem jest też dosyć "obiektowy" optymalizacja produkcji z harmonogramowanie i przydzielaniem pracowników o różnych umiejętnościach do maszyn produkcyjnych z tym że każda maszyna może wykonać kilka programów, a do produkcji danego produktu trzeba użyć wielu różnych programów, maszyny są różne też z różnym czasem wykonania programów, dodatkowo przestrojenie każdej maszyny na inną opcję programową też zajmuje czas. To tak w skrócie.

Wasyl0 napisał(a):

klasa Osobnik ma kilka list w których są referencje, w których są znowu listy z obiektami.

Dziwne, zawsze wydawało mi się, że Osobnik powinien być dość prostą klasą i zawierać jedną tablicę liczb (genów).

W każdym razie, skoro tak jest, to musi być wolne. Możesz spróbować użyć refleksji zamiast serializacji, tutaj jest ciekawy wpis i przykład raczej wydajnego kodu: http://theinstructionlimit.com/fast-net-reflection

Obiektowo do tego podszedłem ponieważ problem jest też dosyć "obiektowy"

Każdy problem jest obiektowy. Ale to nie znaczy, że rozwiązanie go obiektowo będzie wydajne. A Ty chyba wpadłeś w obiektową pułapkę.

To zastosowanie refleksji jest ciekawe, ale nie mogę znaleźć dokładnie kawałka jak mógłbym to zrobić.

Chodzi o metodę trzecią i mamy taki kod w formsie za to odpowiedzialny:

LogTestStarted("DynamicMethod + Delegate, Cached");

            for (int i = 0; i < outerLoops; i++)
            {
                var serializer = new Serializer(new CachedReflector());
                for (int j = 0; j < innerLoops; j++)
                    lastDeserialized = serializer.Deserialize<Entity>(lastSerialized = serializer.Serialize(entity));
            }

            SerializedObject temp = null;

            LogTestCompleted();

            lastReserialized = (new Serializer(new CachedReflector())).Serialize(lastDeserialized);

Oczywiście te pętle to tylko po to żeby czas zwiększyć, ale nie mogę tego przełożyć do swojego programu po dołączeniu tej biblioteki.

No na moje oko to wystarczy wziąć ten kod, tylko zamiast Entity użyć Osobnik, no i tak jak piszesz poprawić pętlę.

No niestety, ale pomimo siedzenia nad kodem i próbach nie można tego użyć ot tak do swojego przykładu. Prostą klasę łyknie, ale taką z powiązaniami, nie i sypie wyjątkiem.

Poprawiam, nie chce za bardzo radzić sobie nawet z prostymi moimi klasami ;D

Prędkość znacząco podniosłem.
Użycie Clone w niektórych miejscach nie było potrzebne co o połowę przyspieszyło program. Miejsce w którym wykonuje się mój Clone() za pomocą serializacji dalej jest najdłużej wykonującą się częścią ale kod, jest i tak już zadowalająco szybki.

Do tego dodałem Parallel.For, który prawie niezauważalnie zwiększył szybkość. Ale użyłem go w niewielu miejscach, bo jednak kolejność wykonania kroków pętli jest istotna w większości przypadków.

Inną ciekawą sprawą jest, że jeśli kompiluję projekt z przeznaczeniem na platformę x64 program jest zauważalnie wolniejszy, więc kompiluję dla x86, chociaż procesor i system jest x64.
Oczywiście też kompiluję w trybie release, zawsze to mała optymalizacja będzie miała miejsce.

Chciałbym się spytać was o jeszcze jedną ciekawą sprawę.

Testowałem szybkość wykonywania się za pomocą zwykłego fora i parallel.
Co dziwne taki, krótki kod daje dziwne wyniki bo czasem czas jest ujemny. ???

List<Osobnik> lista = new List<Osobnik>();
            int a =DateTime.Now.Millisecond;
            Parallel.For(0, licznoscPopulacji, i =>
            {
                List<Osobnik> listaTurniejowa = new List<Osobnik>();

                for (int j = 0; j < wielkoscTurnieju; j++)
                {
                    listaTurniejowa.Add(osobniki[Manager.rnd.Next(osobniki.Count)]);
                }

                lista.Add((Osobnik)ZnajdzMax(listaTurniejowa).Clone());
            });
            
            Console.WriteLine(DateTime.Now.Millisecond - a);

Mierz czas za pomocą Stopwatch, a nie DateTime.

Inną ciekawą sprawą jest, że jeśli kompiluję projekt z przeznaczeniem na platformę x64 program jest zauważalnie wolniejszy, więc kompiluję dla x86, chociaż procesor i system jest x64.
To jest prawda, że .Net pod x64 jest wolny, pracują nad tym. W następnej wersji będzie nowy JIT.

Póki co najlepiej ustawiać x86, albo, w nowszych Visualach, nową opcję "prefer 32-bit".