Kalkulator ONP - C++ vs Delphi

Ok, zawziąłem się i przepisałem cały kod (teraz w sumie kod jest w C, ale formalnie dla celów konkursu stwierdzam że pisałem w C++).

Trochę mi to zajęło... Ale wynik przerósł moje oczekiwania 0_o. Jakieś 4 razy.

Czas wykonania dla 800000 elementów wynosi... 0.239620 sekundy. W wersji Debug.
Na Release wynosi 0.192682, w porywach do 0.17xxxx. Nieźle.

Dziękuję, do widzenia, C99 owns u.

ExtremeRpn.zip

PS. znajdźcie w tym kodzie jakiś błąd bo mi szkoda Delphi.

edit: reupload, znalazłem 'drobny' błąd ale dał się poprawić bez zmiany wydajności

Łał, właśnie obejrzałem ten kod i jestem w szoku bo jest nawet ładny o_O
Spodziewałem się jakiegoś magicznego potwora a tu takie cudeńko.

Ale w dalszym ciągu Delphi nas szokuje bliskością wydajności do normalnie pisanego cepa. A zawsze to niby było takie wolne :)

@O_o - dzięki, starałem się pisać ładny kod. Magicznych potworków tam jest parę tylko są ładnie popakowane w moduły :)

Na przykład:

typedef union
{
	struct
	{
		char operator_type;
		char priority;
		unsigned short int item_type;
	};
	float number;
} rpnItem;

Nawet sam wygląd jest 'fajny' (jest to w sumie niezgodne ze standardem C w związku z czym wymaga w gcc kompilacji z parametrem -fms-extensions. Chodzi o anonimowe unie i struktury które są zresztą tylko kwestią estetyki. No i w C++ są w standardzie).
Ale o co chodzi - wszystkie itemy - czyli operatory i wartości są przechowywane w takiej unii (wielkości 4 bajtów każda). W pamięci wygląda to tak:

/------------------------------------/
/ op_type |  prior  |   item_type    /
/              number                /
/------------------------------------/

Jeśli item_type == 0xFFFF to znaczy że mamy do czynienia z operatorem i możemy używać pól 'operator_type' i 'priority', w przeciwnym wypadku to liczba i korzystamy z pola number.
Na pierwszy rzut oka wydaje się to kiepskim i dość ryzykownym rozwiązaniem - co jeśli numer będzie akurat miał tak ustawione te dwa bajty? Hackiem tutaj jest właśnie zauważenie że nie będzie miał, bo float mający exponent ustawiony na 0xF i niezerową mantystę jest traktowany jako NaN

'Sztuczek' jest jeszczę parę, ale może się już nie będę pogrążał ;)

@msm: niezły wynik, gratuluje!
A możesz zrobić taką wersję, która wyświetla wynik? Bo jak historia uczy to jest najlepszy sprawdzian poprawności programu.
Pod VS 2010 się nie kompiluje, nawet po zmianie typu języka na "C" - wywala się na przypisywaniu struktury:

1>......\c\src\main.c(10): error C2275: 'swHandle' : illegal use of this type as an expression
1> \stopwatch.h(12) : see declaration of 'swHandle'

Za dużo magii w tym jest by heretyczny VS to zjadł :)
A co się stanie z tym trikiem z exponentem na 0xF jeśli coś się zmieni na poziomie binarnym? Np odwrócenie końcówkowości, wtedy by trzeba było obrócić całą unie żeby było tak samo (chyba)

@Cplus - VS jest z tego co pamiętam dość restrykcyjne jeśli chodzi o kod C, sprawdź czy przeniesienie deklaracji swHandle przed jakiekolwiek wyrażenie (na początek funkcji) pomoże.
W dodatku anonimowa struktura raczej nie zadziała... Jeśli chcesz mogę to przepisać tak żeby dało się skompilować w VS.

Mógłbym dać wersję wyświetlającą wynik, ale równie dobrze mogłaby wyglądać tak:

for(int i = 0; i < 800000; i++)
{ printf("%d\n", 131.43); }

Więc jako test poprawności niezbyt by się przydało...
(Edit2: ofc u mnie dobrze wypisuje)

Edit: @O_o - Zamiana little endian <-> big endian niestety będzie zabójcza (tzn z szansy na błąd równej 0 zrobi się 1/0x10000). Wszystko dlatego że struktura musi być dostosowana do pobierania jej wartości przez wskaźniki czyli nie może być odwrócona w pamięci. Możnaby z tym walczyć przez kompilację warunkową albo trzymanie struktury jako 4 bajtowego inta i dobieranie się do elementów przez operacje bitowe ale... po co.
Teoretycznie też jakaś maszyna (w końcu celem projektowym C była przenośność więc na różnych szafach da się go uruchomić) mogłaby stosować niestandardowy zapis liczb zmiennoprzecinkowych ale nie potrafię do tego wymyślić realnej sytuacji.

Popatrzyłem jeszcze w profilera, ciągle masakrycznie dużo zżerało synchronizowanie wątków, których przecież w tym programie nie ma...

W związku z tym poprawiłem trochę definicję listy, teraz wygląda przydługo:

typedef std::list<Item *, boost::fast_pool_allocator<Item *, boost::default_user_allocator_new_delete, boost::details::pool::null_mutex> > StdItemStack;

ale dało to efekt (najnowsze wersje):
Delphi: 0.650 [s]
C: 0.19 [s]
C++: 0.27 [s]

Po tej zmianie wreszcie pod profilerem znaczenie ma kluczowa w tym programie funkcja - pow() (18%).

W załączniku źródła + binarka.

Niezły typ listy... Widzę że boost ma w zanadrzu sporo niezłych sztuczek.
Tak czy inaczej gratuluję :)

Teraz Delphi zostało samo... A nikt się chyba nie kwapi do optymalizowania go.

Ale trzeba przyznać uczciwie że 'normalnie' napisany kod Delphi był praktycznie równy 'normalnemu' (bez profilowania i optymalizacji) kodu C++.

No to były cuda z tym Delphi tutaj :)
Ja męczę tego C#... Mogłem przepisywać kod Cepa a ja głupi zacząłem tłumaczyć z Delphi :( Koszmar :) Sądzę że jak już się skompiluje to i tak coś źle zadziała :/

Nie powiedziałem ostatecznego słowa...
Później zedytuje (nie wiem kiedy bo żniwa :) )

Poddaję się :(. Napisałem proceduralnie, na tablicowych stosach i spadło do jedynie 680ms.

Stringi w Delphi indeksuje się od 1? Bo jak tak to mam ten index co mi ucieka :>

Jej, dużo lepiej tym razem :>
Object reference not set to an instance of an object. ;)

Wo! Dałem && zamiast ||, ciapłem się w przerabianiu in [...]

A teraz dostaje wpiernicz batem za moje heretyczne zamienienie unii na klasy z dziedziczeniem x_x
Unable to cast object of type 'rpncsharp.itOp' to type 'rpncsharp.itVal'.

Łiiii.... Input string was not in a correct format. :/

U mnie:
C++: 161ms
C: 120ms
Delphi: 299ms, pierwsza wersja 670ms
C#: 350ms

Najnowsze wersje programów, moja wersja w C# jest właściwie kalką tego z C tylko na kolekcjach z .NET.
Użyłem także skróconej wersji atof, float.Parse, który bierze pod uwagę ustawienia kulturowe itd jest piekielnie wolny. Teraz najwolniejsze są kolekcje.
Sądzę, że gdyby się przepisało wersję C właściwie znak w znak włącznie z arytmetyką wskaźnikową i kolekcjami na nich, różnice byłyby naprawdę nieduże.

źródło C#: http://pastebin.com/r1R1n5j2

ciekawostka: fakt, trzeba było posiedzieć na tym algorytmem sporo czasu, żeby go zoptymalizować. Ale.. gdy dzisiaj czas programisty jest cenniejszy niż koszt podzespołów.. robi się Parallel.For(0, 800000, (i) => new RPN().Eval("2^3+123.43")); i z 350ms wynik spada nam na czterech rdzeniach do 110ms ;).

        [StructLayout(LayoutKind.Explicit)]
        private struct Item
        {
            [FieldOffset(0)]
            public byte operatorType;
 
            [FieldOffset(1)]
            public byte priority;
 
            [FieldOffset(2)]
            public ushort itemType;
            
            [FieldOffset(0)]
            public float number;
        }

zaraz zaraz, przecież teraz number zakrywa resztę pól łącznie z itemType.

MSM napisał(a)

Mógłbym dać wersję wyświetlającą wynik, ale równie dobrze mogłaby wyglądać tak:

for(int i = 0; i < 800000; i++)
{ printf("%d\n", 131.43); }

Więc jako test poprawności niezbyt by się przydało...
(Edit2: ofc u mnie dobrze wypisuje)

Chodziło mi o to, że każda z wersji (Delphi, C++) wypisuje ostatni wynik - po to żeby potwierdzić że te 800000 liczeń robiło coś sensownego.

Ciakawostka:

if(op == '+' || op == '-')
    return 1;
else if (op == '*' || op == '/')
    return 2;
else
    return 3;

Skoro już optymalizujemy to na całego:

return (op + 5) & 0x44;

'+' = 0x2B  (+ 0x5 & 0x44 = ) 0x00
'-' = 0x2D  (+ 0x5 & 0x44 = ) 0x00
'*' = 0x2A  (+ 0x5 & 0x44 = ) 0x04
'/' = 0x2F  (+ 0x5 & 0x44 = ) 0x04
'^' = 0x5E  (+ 0x5 & 0x44 = ) 0x40

Różnice powinny zamknąć się w 1% ale i tak było warto. ;)

Tak się bawię z wersją Rev'a:

1. Przeniosłem do z Eval do konstruktora

stack = new Stack<Item>();
queue = new Queue<Item>();

A do Eval dałem

stack.Clear();
queue.Clear();

Przy wywołaniu w pętli jest szybsze lecz przy wywołaniu przez Parallel wolniej o_O

Chłopaki,czym dokładnie określiliście ten czas wykonania się?

Dodaje wersję dla Lazarus Pascal - bazująca na wersji Delphi bez ASM (po drobnych przeróbkach).
Jak już ktoś wspomniał - ok. 2x wolniejsze od wersji w Delphi.

Próbowałem to sprofilować, ale pod Lazarusem chyba nie ma tak łatwo jak w Visual C++... (ulubiony GpProfile nie działa - brak INI).

Prawdopodobnie najwolniesze są alokacje pamięci...

To w sumie całkiem dobry test kompilatora i CPU...

OK, zrobiło mi się żal C# więc postanowiłem go też lekko poprawić - w końcu mój ulubiony język :>

Start: 1.13
Wycięcie substringa: 1,03
Atof zmienia index : 0.95 (Wycięcie zbędnej pętli. Tego nie zrobiłem w C!)
Uruchomienie tego kodu jako release (hmm...) : 0.64
Zamiana char.IsDigit() na 2 porównania : 0.62 (różnica potwierdzona kilka razy, zawiodłem się na tobie optymalizatorze...)
Przeniesienie tworzenia stosu i kolejki do konstruktora (były tworzone i alokowane za każdym razem - rev, cóżeś uczynił?) : 0.37
Zamiana stosu na tablicę 0.31 - (do niewiernych - różnica jakby niewielka czyli te kolekcje nie są takie wolne... Zwłaszcza że wykonują dodatkowe sprawdzenie błędów :] )
Kolejka na tablicę (czyli coś czego domyślnie normalna kolejka nie może robić): 0.25
Kurczę, spodobała mi się zabawa, C++ @Cplusa już w tyle :> Spróbujemy dojść bliżej C
Switch na charze na switch na byte: 0.23 (to raczej nie jest przypadkowy wynik, różnica się potwierdza i chyba wiem czemu).
Jeszcze 2 char.IsDigit zmienione na 2 ify - 0.205
Jeszcze tylko troszeczkę :>
Ostatecznie: data.Length zmienione w atof na int len = data.Length - 0.195!
Ech, po ponad 20 minutach nie wymyśliłem żadnej dającej przyśpieszenie optymalizacji (pewnie z godzinę nad tym siedziałem :/ ) więc na razie niech tak będzie.

W sumie to doszedłem (prawie) do poziomu C :P Co prawda to użyłem dodatkowej sztuczki która w C się nie pojawiła ale fakt jest faktem - niskopoziomowcy, strzeżcie się!

PS. Mam jeszcze jeden pomysł na przyśpieszenie ale spróbuję tego później.

Oh my, zapomniałbym kodu wrzucić! http://pastebin.com/JSZshcG8

U mnie zoptymalizowana wersja C# wyciąga 102ms :). Jak dodamy wielowątkowość:

Parallel.For<RPN>(0, 800000,
    () => new RPN(),
    (i, state, rpn) => {
        rpn.Eval("2^3+123.43");
        return rpn;
    },
    (rpn) => { result = rpn.Result; });

29ms
Może akurat w tym przypadku to trochę bez sensu, ale widać, że warto wielowątkowość stosować, a w nowym .NET za pomocą C# możemy coś takiego uzyskać jednym wywołaniem funkcji, możemy bez problemu określić stan początkowy (co by nie tworzyć 800 tys elementów, a 4), końcowy, etc.

W tym szybkim atof() z sieci był jeszcze jeden drobny błąd (brak inicjalizacji) - w załączniku lepsza wersja.
Zmieniłem też to na wersję "naiwną" - tą z C# i użyłem gdzieniegdzie naiwnego atoi(), ale to już niewiele pomogło:
Lazarus Pascal: 1.11 [s]

Delphi: 0.41 [s]
Delphi XE: 0.38 [s]

C++: 0.232 [s]
C: 0.18 [s]

Ten Parallel.For to rzeczywiście ciekawa sprawa, w C++ jest OpenMP i kilka bibliotek jednego-dostawcy (MS, Intel), ale nic tak bardzo uniwersalnego...

A ten żart to w sumie nie załapałem - bo nie znam C#... To jaka jest tak naprawdę tego wydajność?

[edit] - po mikro-optymalizacjach:
C++/VC2010: 0.224 [s]
C++/VC2010: 0.187 [s] - /fp:fast
C++/pgi 11.7: 0.44 [s] - (-w -fast -Mfprelaxed -Msafeptr -Mprefetch -Mnovect -alias=ansi -Mipa=fast,inline --zc_eh -tp barcelona-64 & acml::fastpow)
C++/gcc 4.4.1: 0.47 [s] - (-O3, -fexpensive-optimizations, -s, -ftree-vectorize, -march=amdfam10, -funroll-all-loops, -ffast-math -fomit-frame-pointer)
C++/intel 2011: 0.191 [s] (O3)
C++/Builder XE: 0.86 [s]

Z ciekawości sprawdziłem:
C#: 0.6 [s] - release, v.1
C#: 0.17 [s] - release, v.2

Jak to żart ;P? No wydajność taka, jaką podajemy. W tym momencie faktycznie jest szybciej niż w C, ale gdyby wszystkie optymalizacje kodu były takie same (kod w 90% identyczny) to wydajność byłaby w gruncie rzeczy identyczna albo może i na lekką korzyść C#. Wszak JIT ma potencjalnie większe pole do popisu pod względem optymalizacji niż AOT.

Wydajność jest taka jaką podawałem. Chodzi o to że pisałem to dla za zabawy a nie żeby udowodnić wyższość C# nad resztą świata (bo IMO mimo wszystko C/C++ jednak są szybsze tylko teraz im się nie udało :) ).

Ciekaw jestem na ile te wyniki były realne - i czy czasem C# sobie nie zredukował tych obliczeń do jednorazowego wykonania kalkulatora...

Porównałem większość znanych mi kompilatorów C++ - (patrz strona 5).
Wyniki dowodzą, że nie tylko programista, ale i kompilator ma znaczenie - różnice potrafią być nawet 2x między różnymi kompilatorami i ich ustawieniami (np. dla pgi spadło m. ponad 1s do 0.4 s).

Szkoda, że GCC wypadło tak marnie...

Spróbuję jeszcze z najnowszymi C++ Builder i Delphi - jak mi przyślą klucze...