.NET 3.5, Java, Visual Studio 2008 C++ - prędkość działania na tablicach

Testy były robione na 64 bitowej Viście. Testy C++ na Visual Studio 2008 SP1. Testy C# na Visual Studio 2008 SP1 (.NET 3.5). Testy Javy na JRE 1.6.0 (IDE to Netbeans). Wszystkie programy kompilowałem w Release (o ile była taka możliwość). Wszystkie programy były uruchamiane samodzielnie, nie z IDE. Java i C++ nie wykazywały spowolnienia podczas uruchamiania z IDE. C# w pierwszym teście dwie pierwsze metody potrafił wykonać 4 razy wolniej. Mając na myśli C++ mam na myśli język niezarządzalny, bez Garbage Collectora. Dla precyzyjnego pomiaru czasu w C++ wykorzystałem klasę CPreciseTimer. C#, .NET 3.5, kompilator do kodu pośredniego, kompilator kodu pośredniego do maszynowego - mam nadzieję, że wiadomo jakie są różnicę, bo dalej nie będę taki precyzyjny (chyba już nawet w tytule postu nie jestem). Podobnie zresztą można powiedzieć o Javie. W przypadku C++ testy były robione podczas kompilacji na 32 i 64 bity. To samo tyczy się C#. Tutaj kod pośredni wyglądał identycznie (przynajmniej dla pierwszego testu), różnica brała się pewnie podczas kompilacji kodu pośredniego. W Javie kompilacja jest chyba zawsze na 32 bity. Podczas testów wyłączałem oszczędzanie energii polegające na spowolnieniu częstotliwości procesora kiedy nic się nie dzieje. Dostęp do dużej tablicy Test polega na stworzeniu wielkiej tablicy, zapełnieniu ją losowymi wartościami i zsumowaniu ich w prostej pętli. Tablica składa się z 100 milionów intów. Tablica jest na tyle duża by pominąć efekt pamięci cache procesora na jej przetwarzanie. Java:

public class ArraySpeedTest1
{
    private int[] big_array;

    public ArraySpeedTest1()
    {
        big_array = new int[1000*1000*100];
        java.util.Random r = new java.util.Random();
        for (int i = 0; i < big_array.length; i++)
            big_array[i] = r.nextInt(5);
    }

    private int SpeedTest1()
    {
        int r = 0;

        for (int i = 0; i < big_array.length; i++)
            r += big_array[i];

        return r;
    }

    private int SpeedTest2()
    {
        int r = 0;

        for (int n : big_array)
            r += n;

        return r;
    }

    public void Test()
    {
        long t = System.nanoTime();
        int r = SpeedTest1();
        t = System.nanoTime() - t;
        System.out.println(String.format("SpeedTest1, sum: %d, time: %d [ms]", r, t / 1000000));

        t = System.nanoTime();
        r = SpeedTest2();
        t = System.nanoTime() - t;
        System.out.println(String.format("SpeedTest2, sum: %d, time: %d [ms]", r, t / 1000000));
    }
}

Wynik: SpeedTest1, sum: 199998357, time: 244 [ms] SpeedTest2, sum: 199998357, time: 168 [ms] C++:

class ArraySpeedTest1
{
    private: int BIG_ARRAY_LENGTH;
    private: int* big_array;

    public: ArraySpeedTest1()
    {
        BIG_ARRAY_LENGTH = 1000*1000*100;

        big_array = new int[BIG_ARRAY_LENGTH];

        srand((unsigned)time(NULL));
        for (int i=0; i<BIG_ARRAY_LENGTH; i++)
            big_array[i] = rand() % 4;
    }

    public: ~ArraySpeedTest1()
    {
        delete big_array;
    }

    private: int SpeedTest1()
    {
        int r = 0;
        int* p = big_array;
        for (int i=0; i<BIG_ARRAY_LENGTH; i++)
            r += *p++;
        return r;
    }

    private: int SpeedTest2()
    {
        int r = 0;
        for (int i=0; i<BIG_ARRAY_LENGTH; i++)
            r = r + big_array[i];
        return r;
    }

    public: void Test()
    {
        CPreciseTimer* timer = new CPreciseTimer();
        timer->StartTimer();
        int r = SpeedTest1();
        timer->StopTimer();
        std::cout << "SpeedTest1, sum: " << r << ", time: " << timer->GetTime() / 1000 << "[ms]\r\n";
        delete timer;

        timer = new CPreciseTimer();
        timer->StartTimer();
        r = SpeedTest2();
        timer->StopTimer();
        std::cout << "SpeedTest2, sum: " << r << ", time: " << timer->GetTime() / 1000 << "[ms]\r\n";
        delete timer;
    }
};

Wyniki: 32 bity: SpeedTest1, sum: 449948271, time: 82[ms] SpeedTest2, sum: 449948271, time: 82[ms] 64 bity: SpeedTest1, sum: 449948271, time: 82[ms] SpeedTest2, sum: 449948271, time: 82[ms] C#:

public class ArraySpeedTest1
{
    private int[] big_array = new int[1000 * 1000 * 100];

    public ArraySpeedTest1()
    {
        Random r = new Random();
        for (int i = 0; i < big_array.Length; i++)
            big_array[i] = r.Next(5);
    }

    private int SpeedTest1()
    {
        int r = 0;

        for (int i = 0; i < big_array.Length; i++)
            r += big_array[i];

        return r;
    }

    private int SpeedTest2()
    {
        int r = 0;

        foreach (int n in big_array)
            r += n;

        return r;
    }

    private int SpeedTest3()
    {
        return big_array.Sum();
    }

    public void Test()
    {
        Action<Func<int>, string> d = (f, s) =>
        {
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            int r = f();
            sw.Stop();
            System.Console.WriteLine("{0}, sum: {1}, time: {2} [ms]", s, r, sw.ElapsedMilliseconds);
        };

        d(SpeedTest1, "SpeedTest1");
        d(SpeedTest2, "SpeedTest2");
        d(SpeedTest3, "SpeedTest3");
    }
}

Wyniki 32 bity: SpeedTest1, sum: 199995106, time: 111 [ms] SpeedTest2, sum: 199995106, time: 105 [ms] SpeedTest3, sum: 199995106, time: 1064 [ms] 64 bity: SpeedTest1, sum: 199981552, time: 130 [ms] SpeedTest2, sum: 199981552, time: 134 [ms] SpeedTest3, sum: 199981552, time: 1028 [ms] Komentarz: W C# kod 32 bitowy jest wykonywany szybciej niż kod 64 bitowy. W C++ nie widać różnicy w prędkości pomiędzy kodem 64 bitowym, a 32 bitowym. Wygląda na to, że optymalizacja dla 64 bitowego kodu nie jest najlepsza dla C#. Co do różnic w prędkości widzimy, że kod najszybciej wykonuje się w C++ (obie wersje tak samo szybkie). Dalej jest C#. A na końcu Java (co ciekawe wersja z wykorzystaniem enumeracji jest wyraźnie szybsza). Dla C# wersja z wykorzystaniem LINQ choć ma najelegantszy kod to jest najwolniejsza. Dla C++ widzimy, że ręczna zabawa na wskaźnikach nie zawsze daje efekty. Możemy uśrednić wyniki: C++: 85 [ms], C#: 115[ms], Java: 200[ms] Wielokrotny dostęp do małej tablicy Ilość sumowanych wartości jest taka sama, tylko, że zamiast sumować tablice 100 milionów elementów, sumujemy 100 tysięcy razy tablice 1000 elementów. Dzięki temu korzystamy w pełni z pamięci cache procesora. Java:

public class ArraySpeedTest2
{
    private int OUTER_LOOP;
    private int[] big_array;

    public ArraySpeedTest2()
    {
        OUTER_LOOP = 1000*100;
        big_array = new int[1000];
        java.util.Random r = new java.util.Random();
        for (int i = 0; i < big_array.length; i++)
            big_array[i] = r.nextInt(5);
    }

    private int SpeedTest1()
    {
        int r = 0;

        for (int j=0; j<OUTER_LOOP; j++)
            for (int i = 0; i < big_array.length; i++)
                r += big_array[i];

        return r;
    }

    private int SpeedTest2()
    {
        int r = 0;

        for (int j=0; j<OUTER_LOOP; j++)
            for (int n : big_array)
                r += n;

        return r;
    }

    public void Test()
    {
        long t = System.nanoTime();
        int r = SpeedTest1();
        t = System.nanoTime() - t;
        System.out.println(String.format("SpeedTest1, sum: %d, time: %d [ms]", r, t / 1000000));

        t = System.nanoTime();
        r = SpeedTest2();
        t = System.nanoTime() - t;
        System.out.println(String.format("SpeedTest2, sum: %d, time: %d [ms]", r, t / 1000000));
    }
}

Wyniki: SpeedTest1, sum: 201900000, time: 224 [ms] SpeedTest2, sum: 201900000, time: 136 [ms] C++:

class ArraySpeedTest2
{
    private: int OUTER_LOOP;
    private: int BIG_ARRAY_LENGTH;
    private: int* big_array;

    public: ArraySpeedTest2()
    {
        OUTER_LOOP = 1000*100;
        BIG_ARRAY_LENGTH = 1000;

        big_array = new int[BIG_ARRAY_LENGTH];

        srand((unsigned)time(NULL));
        for (int i=0; i<BIG_ARRAY_LENGTH; i++)
            big_array[i] = rand() % 4;
    }

    public: ~ArraySpeedTest2()
    {
        delete big_array;
    }

    private: int SpeedTest1()
    {
        int r = 0;
        
        int* p;
        for (int j=0; j<OUTER_LOOP; j++)
        {
            p = big_array;
            for (int i=0; i<BIG_ARRAY_LENGTH; i++)
                r += *p++;
        }
        return r;
    }

    private: int SpeedTest2()
    {
        int r = 0;
        for (int j=0; j<OUTER_LOOP; j++)
            for (int i=0; i<BIG_ARRAY_LENGTH; i++)
                r = r + big_array[i];
        return r;
    }

    public: void Test()
    {
        CPreciseTimer* timer = new CPreciseTimer();
        timer->StartTimer();
        int r = SpeedTest1();
        timer->StopTimer();
        std::cout << "SpeedTest1, sum: " << r << ", time: " << timer->GetTime() / 1000 << "[ms]\r\n";
        delete timer;

        timer = new CPreciseTimer();
        timer->StartTimer();
        r = SpeedTest2();
        timer->StopTimer();
        std::cout << "SpeedTest2, sum: " << r << ", time: " << timer->GetTime() / 1000 << "[ms]\r\n";
        delete timer;
    }
};

Wyniki: 32 bity: SpeedTest1, sum: 155800000, time: 45[ms] SpeedTest2, sum: 155800000, time: 45[ms] 64 bity: SpeedTest1, sum: 155800000, time: 45[ms] SpeedTest2, sum: 155800000, time: 45[ms] C#:

public class ArraySpeedTest2
{
    private int OUTER_LOOP = 1000 * 100;
    private int[] big_array = new int[1000];

    public ArraySpeedTest2()
    {
        Random r = new Random();
        for (int i = 0; i < big_array.Length; i++)
            big_array[i] = r.Next(5);
    }

    private int SpeedTest1()
    {
        int r = 0;

        for (int j = 0; j < OUTER_LOOP; j++)
            for (int i = 0; i < big_array.Length; i++)
                r += big_array[i];

        return r;
    }

    private int SpeedTest2()
    {
        int r = 0;

        for (int j = 0; j < OUTER_LOOP; j++)
            foreach (int n in big_array)
                r += n;

        return r;
    }

    private int SpeedTest3()
    {
        int r = 0;

        for (int j = 0; j < OUTER_LOOP; j++)
            r += big_array.Sum();

        return r;
    }

    public void Test()
    {
        Action<Func<int>, string> d = (f, s) =>
        {
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            int r = f();
            sw.Stop();
            System.Console.WriteLine("{0}, sum: {1}, time: {2} [ms]", s, r, sw.ElapsedMilliseconds);
        };

        d(SpeedTest1, "SpeedTest1");
        d(SpeedTest2, "SpeedTest2");
        d(SpeedTest3, "SpeedTest3");
    }
}

Wyniki: 32 bity: SpeedTest1, sum: 195800000, time: 93 [ms] SpeedTest2, sum: 195800000, time: 90 [ms] SpeedTest3, sum: 195800000, time: 1051 [ms] 64 bity: SpeedTest1, sum: 200200000, time: 117 [ms] SpeedTest2, sum: 200200000, time: 116 [ms] SpeedTest3, sum: 200200000, time: 1013 [ms] Widzimy, że kod w C++ przyspieszył dwukrotnie, zaś kod w C# i w Javie przyspieszył nieznacznie. Wynika to prawdopodobnie z ilości instrukcji procesora na pojedyńczą pętle. Kiedy cała pętla zaczyna korzystać z pamięci cache, do której dostęp jest szybszy niż do pamięci zewnętrznej, to kod w C++, który ma najmniej instrukcji na pętle zaczyna działać najszybciej. Prawdopodobnie jest tak, że w C++ dla pierwszego testu to procesor czeka na dane z pamięci, a wykonywanie kodu stoi. W C# i Javie nie widzimy tak wielkiego przyspieszenia, gdyż pomimo dostępu do pamięci cache procesor i tak ma dużo rozkazów do przetworzenia. Możemy uśrednić wyniki: C++: 45 () [ms], C#: 90[ms], Java: 170[ms]. Te same testy uruchomione na domowym komputerze dla C++ i C# przyspieszyły do 30 [ms] i 60 [ms]. Stosunek przyspieszenia jest idealnie proporcjonalny do prędkości zegara procesora. Dla porównania wersja pierwsza działająca na dużej tablicy w ogóle nie przyspieszyła. Widzimy, że kiedy dane są w pamięci cache liczy się tylko prędkość procesora. W pierwszym przypadku prawdopodobnie znaczenie ma prędkość pamięci (u mnie w obu przypadkach taka sama patrząc na indeks szybkości liczony przez Viste). Kod w C++ wykonał się w drugim przypadku w 45 [ms]. Prędkość procesora to 2,26 [GHz]. W tym czasie przetworzył 100M elementów tablicy. Ile elementów tablicy przetworzył by w sekundę? - 2222M. Czyli możemy powiedzieć, że efektywna częstotliwość przetwarzania tablicy to 2,22 [GHz]. A taka pętla to na pewno jest kilka instrukcji procesora. Tutaj widać jak działają współczesne procesory, jak potrafią optymalizować wykonanie kodu. I widać (może trochę mniej), jak skomplikowanym zagadnieniem jest optymalizacja kodu pod współczesne procesory - czym na niższy poziom schodzimy tym efekty naszego niby-przyspieszania mogą być coraz bardziej zaskakujące. Potrzebna jest tutaj dokładna wiedza jak działa procesor niestety...