Kalkulator ONP - C++ vs Delphi

Z ciekawości dla sprawdzenia o ile szybciej będzie działać program napisany w C++(bo tak się mówi że Delphi jest bee), przepisałem parser z Delphi z minimalną funkcjonalnością - parsuje bez nawiasów i funkcji.

800 000 razy w pętli jest parsowane i liczone wyrażenie 2^3+123.43
Czas liczony za pomocą QueryPerformanceCounter
Wyniki: Delphi - 1.2s ; C++ - 4s.

Chciałby ktoś sprawdzić czemu taka duża różnica jest ? (może zrobiłem jakiś kardynalny błąd)
Generalnie przepisałem zamieniając case record na union ; currency na double oraz StrToFloat na atof
Projekt w Code::Blocks (no ale po dodaniu stdafxa na VS bez problemu powinno działać).
Dwie klasy - Stack i RPN, nie ma dużo kodu do oglądania :)

Dziwne że nie wybuchły tu jeszcze płomienie piekielne po tym jak ośmieliłeś się twierdzić że C++ jest wolniejsze od czegokolwiek poza Asemblerem.

Kod się ściąga, niestety w Delphi nigdy nie pisałem a w Pascalu na tyle dawno że nie pamiętam już na tyle dobrze żeby ocenić jakość twojego kodu.
W kodzie C++ nie widzę jakichś oczywistych błędów ale to jeszcze o niczym nie świadczy.

Mógłbyś gdzieś wrzucić binarkę z programem napisanym w Delphi wykonującym to samo zadanie?

Nie chciałbym cię pośpieszać, ale ponawiam prośbę - wrzuć tutaj jeśli możesz binarkę z Delphi. Wynik kompilacji programu w Delphi szybszego od tego który wrzuciłeś.

Żeby się nie okazało że ten mistyczny benchmark w którym Delphi miażdży C++ trzykrotnie nie istnieje :/

Już leci binarka i Src, dziś byłem na wyjeździe i wróciłem godzinkę temu :)
Update 1post (raczej miał być ale się nie da)

Chyba nawet skompilowana w Debug. Konsolowa aplikacja , wynik 1.44s
Odpowiednik w C++ kompilowany w VS z O3 osiągnął chyba najlepiej 2.5s.

Matematyka na klasach nie jest dobrym rozwiązaniem. Moja rada:

Lekkie przyspieszenie C++ uzyskasz eliminując trochę wskaźników na rzecz referencji w argumentach funkcji. A przy okazji warto zmienić koncepcję stosu. Robienie dzieci na rumuńską pandę nie jest wydajne przy obliczeniach (Elem/Item). Zastosować lepiej macierz jednowymiarową i zaalokować od razu więcej pamięci, zamiast robić rozrzuty.

Chyba za późno żebym się tym teraz zajmował bo wychodzą mi cuda...

Najpierw sprawdziłem wynik kodu w C++ - po r.Calc(); dodałem

cout << r.val << "\r\n";

Niech mi ktoś powie gdzie tu jest błąd bo oślepłem?

W wyniku na ekranie ląduje 800000 napisów 2.30214e+097 czyli prawie 10^100...
Ok, czyżby błąd? Dla odmiany sprawdziłem to co się dzieje na niższym poziomie, czyli wartość val tuż przed Clear().
Zakładając little endian dostajemy ciąg 0x40606DC28F5C28F6 który jako 64bitowa liczba zmiennoprzecinkowa zgodna ze standardem IEEE-754 (blah blah blah...) wynosi 131.43. Czyli dobrze. Sprawdzam co się dzieje w Delphi. Znalazłem ciąg 0x0000000000140DFC ... Decymalnie 6.493505e-318 czyli ponad 10^300...
Zakładam najprostszą możliwość czyli że źle ustaliłem lokalizacje w pamięci zmiennej val (IMHO mało prawdopodobne bo czym może być kopiowanie w metodzie clear do pola klasy przekazanej w parametrze z takim samym offsetem jak val w c++ zmiennej o wielkości 2 quadwordów czyli wielkości double...)
Stwierdzam że zajmę się tym później. Wracam do C::B. OK, to musi być przecież powtarzalne. Wczytujemy program wygenerowany przez C::B pod debugger. Pierwsze wykonanie kodu. I co ląduje na ekranie? 131.43...

Najlepsze jest to że to jest w 100% powtarzalne...

edit: Bardzo chaotycznie to wyszło, ale biorąc pod uwagę okoliczności, nic dziwnego.

Podsumowanie:

• Dodanie couta z wyliczoną wartością powoduje że program wypisuje za każdym razem 2.30214e+097
• Wykonanie tego samego programu pod IDĄ powoduje że program wypisuje za każdym razem 131.43
• Delphi nic nie wypisuje bo nie mam kompilatora żeby zmienić kod, ale sprawdzanie pamięci sugeruje że wynik pod debuggerem wynosi za każdym razem 6.493505e-318
• O_o?

PS. mam nadzieję że to tylko efekt jakiejś chwilowej mojej ślepoty, ale nie wiem na czym miałaby polegać skoro tylko uruchamiam program w różny sposób...

@msm: tutaj może siedzieć błąd (RPN.cpp:24-30):

            Item* it = new Item;
            it->ItemType = itArg;
            const char* ex = expr;
            while((*expr >= '0' && *expr <= '9') || (*expr == '.'))
                ++expr;
            memcpy(it->Arg, ex, expr-ex);
            queue.Push(it);

Można sprawdzić w kodzie, że to fragment wrzucający do kolejki znalezioną liczbę. Są tu aż dwa błędy:

• Bardzo poważny: Instrukcja memcpy kopiująca liczbę do pola it->Arg. Rzecz jasna, pole nie jest wyzerowane w żaden sposób przed skopiowaniem, ani potem w żaden sposób nie dodano znaku końca łańcucha znakowego \0 - w takim razie po naszej liczbie znajdują się losowe znaki. Co, gdyby przypadkowo były to dodatkowe cyfry?
• Trochę mniej poważny: program, już widać, nie jest "idiotoodporny". Zaakceptowałby liczbę z kilkoma kropkami, np. 1234.56.78.

Oprócz tego trzeba zauważyć, że 2³+123,43 = 131,43; nie zaś 132,43 wyliczone w programie.
Tak mi się zdaje, że jest to spowodowane dziwnie odwróconą kolejnością parametrów, gdyż 3²+123,43=132,43.

Edit: to może być tylko przypadek, ale dziwnym trafem 2^323,43 ≈ 2,30214 * 10⁹⁷ (pominąłem dodawanie, bo praktycznie nie wpływa na wynik). Dziwna zbieżność zapisu wykładnika z liczbą 123,43.

Faktycznie, zapomniałem o /0
Co do idioto-odporności to nie o to tu chodzi, tak na szybko przepisałem kawałek funkcjonalności w celu porównania :)
Co do niepoprawnego wyniku, to zamieściłem update (powinien być INTO, a nie push w kolejce, małe zamachnięcie się przy pisaniu :P)

Tak jak mnbvcX napisał - problemem był terminator cstringa, a raczej jego brak. Dzięki !
Dla Delphi zrobiłem wypisanie wyniku oraz zbuildowałem dla Release.

Tak więc MSM podaj czas w Delphi, i zbuildowany u Ciebie w CPP. U mnie ostra różnica jest :)
Potem może zobaczę czas wykonania poszczególnych elementów i się znajdzie wąskie gardło w Cpp.

Co się rzuca w oczy to to, że kod nie jest do końca ten sam:

C++:

 if(queue.Top()->ItemType == itVal || queue.Top()->ItemType == itArg)

Delphi:

if FQueue.Top^.ItemType in [itVal, itArg] then

W tym wypadku w wersji C++ masz dodatkowo wyliczenie "queue.Top()->ItemType".
Może to być zoptymalizowane / wyeliminowane automatycznie ale nie musi.
Aby było bardziej dokładnie, powinieneś odłożyć wartość do zmiennej i dopiero ją porównywać.
Ale to raczej nie jest przyczyną tak dużej różnicy.

Chyba jednak to w większości jest alokacja - zmieniłem kod tak żeby używał domyślnych klas C++ (std::queue i std::stack) i czas wykonania spadł do 1.06. Na razie :P
Jakby nie patrzeć to używanie standardowych klas jest bardziej naturalne niż wymyślanie koła od nowa więc myślę że moje rozwiązanie jest bliższe naturalnemu w C++.

Swoją drogą fajne zagadnienie :]

Wrzucam zmieniony kod, mam nadzieję że się nie obrazisz:

#include "../include/RPN.h"
#include <cstring>
#include <cmath>
#include <cstdlib>

using namespace std;

RPN::RPN()
    : stack(), queue(), val(0)
{
}

RPN::~RPN()
{
    //dtor
}

void RPN::InToPost(const char* expr)
{
    while(*expr)
    {
        Item it = Item();
        if(*expr >= '0' && *expr <= '9')
        {
            it.ItemType = itArg;
            const char* ex = expr;
            while((*expr >= '0' && *expr <= '9') || (*expr == '.'))
                ++expr;
            memcpy(it.Arg, ex, expr - ex);
            queue.push(it);
        }
        else
        {
            it.ItemType = itOp;
            it.Op = *expr;
            it.priority = Prior(*expr);

            while(!stack.empty() && it.priority <= stack.top().priority)
            { queue.push(stack.top()); stack.pop(); }

            stack.push(it);
            ++expr;
        }
    }
    while(!stack.empty())
    { queue.push(stack.top()); stack.pop(); }
}

void RPN::Calc()
{
    while(!queue.empty())
    {
        if(queue.front().ItemType == itVal || queue.front().ItemType == itArg)
        { stack.push(queue.front()); queue.pop(); }
        else
        {
            double op2, op1;
            if(stack.top().ItemType == itVal)
                op2 = stack.top().Val;
            else
                op2 = atof(stack.top().Arg);

            stack.pop();

            if(stack.top().ItemType == itVal)
                op1 = stack.top().Val;
            else
                op1 = atof(stack.top().Arg);
            stack.top().ItemType = itVal;

            switch(queue.front().Op)
            {
                case '+':
                {
                    stack.top().Val = op1 + op2;
                    break;
                }

                case '-':
                {
                    stack.top().Val = op1 - op2;
                    break;
                }

                case '*':
                {
                    stack.top().Val = op1 * op2;
                    break;
                }

                case '/':
                {
                    stack.top().Val = op1 / op2;
                    break;
                }

                case '^':
                {
                    stack.top().Val = std::pow(op1, op2);
                    break;
                }
            }

            queue.pop();
        }
    }
    val = stack.top().Val;
}

void RPN::Clear()
{
    val = 0;
    while(!stack.empty()) stack.pop();
    while(!queue.empty()) queue.pop();
}

char RPN::Prior(const char op) const
{
    if(op == '+' || op == '-')
        return 1;
    else if (op == '*' || op == '/')
        return 2;
    else
        return 3;
}

U mnie czas C++ wynosi 1.06123 s. a Delphi 0.98503 s. więc różnica niebezpiecznie dla Ciebie spada :P

luźna uwaga 1: implementacja stosu i kolejki w C++ to WTF -> pop() zwraca void przez co trzeba kombinować ze stack.top(); stack.pop(). Nie ma też czegoś takiego jak clear przez co trzeba kombinować z while(!s.empty())s.pop();

luźna uwaga 2: @Cplus -> jest znacznie większa różnica - w C++

if(*expr >= '0' && *expr <= '9')

w Delphi

TArgSet = ['0'..'9', '.']; if Expr[I] in TArgSet then

luźna uwaga 3: Kod Delphi był przyjemniejszy do statycznej analizy pod disassemblerem (załadowałem na krótko obydwa żeby sprawdzić wyliczaną wartość), ale może wynikało to z tego że była to wersja debug.

luźna uwaga 4: zauważ że jeszcze nic nie optymalizowałem tylko zmieniłem implementację na bardziej prawdopodobną w normalnym życiu.

szybko wyedytuj, bo działasz na starej wersji (bez terminatora cstringa) oraz linijka niżej tym fragmencie ma być queue.INTO(na koniec).
No cóż, nie sądziłem, że własny stos może być tyle wolniejszy(oczywiście w Cpp) :>

Kasowanie w pętli stosu (Clear) to masakra, wywal to.

Użyj zamiast std::stack albo std::vector albo std::list.

No zależy jak na to patrzeć.
Dla dwóch równoważnych kodów, w Delphi biło na głowę :)
Można by sprawdzić jeszcze pod VS albo Intelem, przeróbkę MSMa, o ile to przyspieszy.
Jak będzie mi się chciało, może sprawdzę użycie gotowych kontenerów Delphi.

@maciejmt - queue w stl nie ma metody into(), push wrzuca automatycznie na koniec.
@Cplus - nie jest tak strasznie, w końcu w ONP wszystko ostatecznie jest zużywane. Rozmiar stosu przy usuwaniu jest stały i wynosi 1, rozmiar kolejki jest stały i wynosi 0.
@O_o - zarówno Delphi jak i C++ dałoby się zoptymalizować jeszcze bardzo dużo więc konkurs uważam za nierozstrzygnięty (aczkolwiek Delphi trzeba przyznać że ma na razie przewagę - wrzucę kiedyś ten wątek jeśli ktoś będzie się upierał że C++ zawsze jest najszybszy.
@maciejmint - ale to raczej dlatego że źle podszedłeś do kwestii alokacji pamięci. W C++ alokacja pamięci to dość newralgiczna sprawa. To nie tyle kwestia wydajności języka co jego filozofii (w Javie i C# jest np. odwrotnie i alokacja to najoczywistsza rzecz pod słońcem)

Ostateczne wyniki w celu uporządkowania (Core2, 2.16):
Delphi (release) 1145ms
Delphi (kontenery biblioteczne) 1300ms

C++ (VS 2010, O3, Release, kontenery biblioteczne) - 1406ms
C++ (VS 2010, O3, Release) - 2672ms

C++ (C::B, O3, Release) - 4182ms

Moje wyniki:

• delphi - release - 0.890 s
• cpp - release - wersja udostępniona: 3.6 s
• cpp - release - wersja po skompilowaniu VS 2010 Express: 1.63 s

Sprawdzę jak będzie ze standardowymi kontenerami...

wersja udostępniona dla delphi:

Turbo Delphi 2006 — 893 ms
Free Pascal 2.6.2 — 2632 ms (Release, O3)

wiedziałem że FPC generuje wolniejszy kod od Delphi, ale tutaj to poległ zupełnie.

Zawsze można by oszukać gdzieś i walić wstawki asma ;)

Zmiana wskazywanych przeze mnie wcześniej wyrażeń nic nie dała.

Po testach pod profilerem mogę stwierdzić, że głównym problemem są tu dynamiczne alokacje, które się w kółko wykonują.

W związku z tym zacząłem optymalizować wersję C++ w tym kierunku:

Delphi: 0.890 [s]

C++:
Wersja oryginalna: 1.63 [s]
Wersja ze standardowymi kontenerami (list of pointers): 1.70 [s]
Boost object pool/construct: 1.40 [s]
Boost object pool/malloc: 1.35 [s]
Boost object pool/malloc+list on pool: 1.37 [s]
Boost object pool/list on fast pool: 1.06 [s]

Można jeszcze próbować z std::vector<Item>, ale to już gruntowna przeróbka algorytmu.

Po tych zmianach znowu zajrzałem do profilera i... wyszło, że 50% czasu pożera atof().
Po zamianie na wersję stąd:
http://www.leapsecond.com/tools/fast_atof.c

wynik spadł poniżej wyniku Delphi:
Boost object pool/list on fast pool / specjalne atof: 0.603 [s] (!)

Ta najszybsza wersja jest ze źródłami w załączniku (mam nadzieje że się doda...).

To było ciekawe pytanie :-)

@Cplus - nieźle :)
Na standardowych kontenerach kolejka musiała być na domyślnym deque a stack na vector<Item> - u mnie prawie 2 * szybsze!

Próbowałem jeszcze z inline (patrz symbol STD_INLINE w Stack.h), ale to nic w tym wypadku nie dało.

Cplus ładnie tak mnie denerwować przed spaniem ? !!

Zmieniłem wersję Delphi na identyczną do C++ (Currency i Extended -> Double) oraz wywaliłem IFa przy dzieleniu (w wersji cpp go nie było) oraz przekazywanie wzoru przez const . StrToFloat zamienione na Pascalowe Val .
Osiągnałem ponad 100ms szybciej, a Twój komp jest trochę szybszy widzę więc może dogodni wersję Cpp :)

Cplus ładnie tak mnie denerwować przed spaniem ? !!

Zmieniłem wersję Delphi na identyczną do C++ (Currency i Extended -> Double) oraz wywaliłem IFa przy dzieleniu (w wersji cpp go nie było) oraz przekazywanie wzoru przez const . StrToFloat zamienione na Pascalowe Val .
Osiągnałem ponad 100ms szybciej, a Twój komp jest trochę szybszy widzę więc może dogodni wersję Cpp :)

Rozumiem że chcesz wojny? :]

No sądziłem, że Delphi wygra :)
Lubię Cpp, ale w sercu Borland ...

Żeby było sprawiedliwie, to zrobiłem dokładną wersję tego co było w Cpp (wtedy machnąłem ręką na drobiazgi) :)

Porównałem wersję CPlusa
Moja - 991ms
Cplus - 1138 (ta co była w bin - ja nie mogłem zbuildować)

Chyba Delphi jednak na tronie :>

@maciejmt: dodaj źródła i binarkę, bo zaczniemy płynąć jak nie będzie z czym porównać
@O_o: boosta w tym wypadku nie trzeba instalować chyba, wystarczy rozpakować do jakiegoś katalogu i dodać do ścieżki include
@Azarien: Free Pascal wspierany jest dla x maszyn, dlatego może nie być dokładnie dopasowany do x86, w każdym razie tutaj najważniejsza jest alokacja a Delphi ma ją wyśrubowaną dzięki jednemu maniakowi - Pierre le Riche (FastMM). Facet napisał manager pamięci jako niezależny programista i było to tak dobre że włączyli to do następnych wersji Delphi (z tego co się orientuję, bo dawno nie używałem).

Na tym kompie na którym teraz siedzę:

• najnowsza wersja Delphi: 0.825
• najnowsza wersja C++: 0.89

(znalazłem źródła)

Generalnie to ONP wykorzystuje w pewnym projekcie i się kiedyś starałem aby było jak najszybsze :)
Jeśli chcecie podjąć rękawicę, to wrzucę wersję z nawiasami, unarnym minusem i plusem, seperatorem argumentów funkcji i funkcjami.
Bo tu już nie ma co za bardzo testować...

Tak się rozglądam po sieci i widzę, że w C++ dużo ludzi narzeka na wydajność operacji typu atof().
Można jeszcze zastosować do tego boost::spirit:

http://www.boost.org/doc/libs/1_41_0/libs/spirit/doc/html/spirit/qi/reference/numeric/real.html

Z tego co piszą parsowanie tekstu powinno być nawet 4x szybsze od atof().