Kalkulator ONP - C++ vs Delphi

Odpowiedz Nowy wątek
2011-07-31 12:33
0

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 :)

edytowany 2x, ostatnio: maciejmt, 2015-12-23 00:45
A kod cepa jest z debugiem, bez optymalizacji itd czy normalny release testowałeś? Bo aż taka różnica jest po prostu dziwna. - O_o 2011-07-31 17:15
Jak wrzuci obydwie binarki to będzie wszystko widać na tacy :] Jak na razie czekam... - msm 2011-07-31 18:20
Też też bo to ciekawi ciut :> Ciągle wpadają mi do łba dziwaczne przyczyny tego zjawiska :> - O_o 2011-07-31 18:23
Ja głównie liczyłem na przekazywanie każdym wywołaniu przez wartość dużych struktur ale się przeliczyłem... - msm 2011-07-31 18:35

Pozostało 580 znaków

2011-07-31 17:10
msm
0

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?

Pozostało 580 znaków

2011-08-01 00:08
msm
0

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 :/

Pozostało 580 znaków

2011-08-01 00:12
0

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.

edytowany 4x, ostatnio: maciejmt, 2015-12-23 00:45

Pozostało 580 znaków

2011-08-01 01:19
mf
0

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.

edytowany 1x, ostatnio: mf, 2011-08-01 01:23
tak tylko chciałem pokazać różnicę wydajności tej samej koncepcji w dwóch językach. Na siłę nie mam potrzeby tu kombinować :) - maciejmt 2011-08-01 01:31

Pozostało 580 znaków

2011-08-01 03:06
msm
0

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...
wth2.png

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...

  • wth2.png (0,38 MB) - ściągnięć: 118
edytowany 4x, ostatnio: msm, 2011-08-01 14:08
znakiem końca linii w C++ jest '\n' a nie "\r\n" - niezależnie od systemu operacyjnego. - Azarien 2011-08-01 09:37
no tak... Chwilę wcześniej parsowałem trochę danych notepadem++ który przy podstawianiu (przy kodowaniu windows) wymaga \r\n, - msm 2011-08-01 14:07

Pozostało 580 znaków

2011-08-01 09:45
0

@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 23+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ż 32+123,43=132,43.

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


Not Found
The requested URL /wypasiona_sygnaturka.txt was not found in this brain.
-----
Human/1.0.00 (Earth) Server at Poland Port 65535
edytowany 1x, ostatnio: mnbvcX, 2011-08-01 09:51

Pozostało 580 znaków

2011-08-01 13:21
0

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)

edytowany 2x, ostatnio: maciejmt, 2011-08-01 13:28
Planuję jeszcze zająć się tym po co prosiłem o program w delphi czyli analizą różnic między plikami .exe wygenerowanymi przez Delphi (btw. jaki kompilator bo PEiD nie dał rady?) i Gcc. W końcu z czegoś ta różnica tak czy inaczej wynika. Wtedy się okaże czy jest to kwestia faktycznie narzutu C++ czy jednak gdzieś jest subtelna różnica. Osobiście zresztą stawiałbym na to że C++ nie jest przystosowany do wielokrotnej alokacji pamięci - gdyby przepisać do C++ program w C# razem z alokacją na stercie każdej zmiennej lokalnej to działałby wolniej od brainfucka. - msm 2011-08-01 14:22
Co nie zmienia faktu że jak dla mnie twój program nie działa poprawnie, patrz 2 posty wcześniej. - msm 2011-08-01 14:24
zobaczę wieczorem, może z czymś jeszcze się machnąłem. - maciejmt 2011-08-01 14:41

Pozostało 580 znaków

2011-08-01 15:57
0

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.

edytowany 5x, ostatnio: maciejmt, 2015-12-23 00:45

Pozostało 580 znaków

2011-08-01 17:05
Cplus
0

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.

Pozostało 580 znaków

2011-08-01 17:05
msm
0

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.

edytowany 5x, ostatnio: msm, 2011-08-01 17:13

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0