Programowanie C++ - praktyka i szybki kod

C++ w praktyce:

Wejście do katalogu kodów źródłowych Trochę o optymalizacji kodu w C++ Moje biblioteki (C++) w jednym archiwum

Uwagi wstępne

Przykładowe pliki źródłowe testowane są głównie kompilatorami:

• pod Windows XP Pro: Microsoft Visual C++ 6.0, Visual C++ 7.1 .NET 2003 (oba komercyjne)
• pod Linuxem: gcc 3.3.3 (g++) (darmowy)
• pod Beos: gcc 2.95 (g++)
• pod Linuxem: KAI KCC 4.0-d1 (KCC) (trial, już nie sprzedawany)
• pod Windows 2000: Borland/Inprise 5.6 (bcc32) (darmowy 5.5 jest z linii komend)
• pod Windows 2000: Open Watcom 1.3 (wcl386) (darmowy)
• pod Windows XP Pro: Dev-C++ z MINGW (gcc 3.4.2) (darmowy)
• pod Windows XP Pro: MINGW Developer Studio 2.05 (gcc 3.4.2) (darmowy)
• pod Windows XP Pro: DJGPP (gcc 3.23) (darmowy)
• pod Windows XP Pro: Cygwin (gcc 3.3.3) (darmowy)
• pod Windows XP Pro i Windows CE 2002: eMbedded Visual 3.0 (darmowy)
• pod Windows XP Pro i Windows CE 2003: eMbedded Visual 4.0 (darmowy)
• pod Windows XP Pro: Digital Mars 8.43 (dmc) (darmowy, dawniej Symantec C++)
• pod Windows XP Pro: Intel C++ 8.1 (icl) (trial)
• pod Windows XP Pro: Metrowerks CodeWarrior 8.0 (IDE 5.0.1305) (trial)
• pod Compaq Tru64 Unix: cxx
• pod Redhat 64bit: Intel 8.1 i gcc 3.3.3
• Weryfikowane przez Compuware (NuMega) DevPartner Studio Professional 7.10,
  Gimpel PCLint 8,
  Parasoft C++Test 2.2,
  Borland Together 6.10 Tool/Audit
  

i z rzadka na innych kompilatorach C++: gcc 2.7.2.f1, 2.8.0, 2.8.1, 2.91.6 egcs 1.1.1, 1.1.2, Digital C++ (SunOS, cxx), Visual C++ 4.0, 5.0. Kompatybilność z gcc niemal zawsze implikuje kompatybilność ze środowiskiem DJGPP/Cygwin/MINGW. Wszystkie testy przy najwyższych poziomach ostrzeżeń kompilatorów:

• --pedantic -ansi -Wall dla gcc
• /W4 dla kompilatorów Microsoftu
• /GS dodatkowo dla .NET C++
• -wx dla Watcom
• /Ge /GS /Op- /GR- /GX- /Wall /Wport /Qpc32 /Za dla Intela

i w zgodzie z aktualnym standardem języka: International Standard ISO/IEC 14882-1998(E) Programming languages - C++.
Dla przenaszalności nie używam typename, domyślnych argumentów wzorców. Dla wydajności unikam domyślnych argumentów funkcji, zliczania odniesień (ten wynalazek jest dla programistów systemowych którzy nie potrafią przekazywać argumentów przez referencje, a każdemu dodaje mały narzut czasowy), unikam w miarę możliwości wirtualiów. Nie używam RTTI, dynamic_cast<> świadczących częściej o złym projekcie niż dobrym implementatorze (są wyjątki). Utrzymuję wszystkie konwencje STL, dla łatwego przyswajania sobie kodu przez innych. Omijam iteratory. W zamian używam inteligentnych wskaźników (z kontrolą zakresu w czasie odpluskwiania!). Wyjątków używam tylko wyjątkowo rzadko i po zdefiniowaniu odpowiednich makr (_USE_ARRAY_EXCEPTIONS w l3_arrex.h). Wyłączenie obsługi wyjątków w kompilatorze pozostawia mój kod praktycznie tak samo bezpiecznym i równie użytecznym (a szybszym!). Kod ten jest 'exception safe' - gwarantowany brak wycieków zasobów w obecności wyjątków rzucanych przez typy parametryczne wzorców kontenerów.

Pozostają jeszcze do zbadania kompilatory: Comeau. Szczególnie ciekaw jestem testów na nietypowych platformach (48 bitowych?). Póki co .NET wykrywa problemy z przenośnością na 64 bity i się nie skarżył, a części kodu na 64 bitach uruchamiane były. Gdyby ktoś dla własnej ciekawości chciał tego dokonać osobiście proponuję skompilować i uruchomić l3_test.h z mojej biblioteki. W razie niezgodności powinny wyskoczyć jakieś brzydkie asercje (jest ich w moim kodzie mnóstwo).

Uwaga!

• W przypadku kompilacji pod MSVC++ 4.0 i gcc 2.7.2 kompilator nie akceptuje typu bool. W celu bezbolesnej kompilacji należy dopisać następujący kod:
  
  typedef char bool;
const bool true=1, false=0;
  
  Możesz go także zdefiniować jako znacznie większy int. Nie używaj do tego makr - w razie błędów w kodzie mogą dawać mylące komunikaty. Pamiętaj: Microsoftowy BOOL ma trzy wartości: TRUE, FALSE i -1 , więc nie jest zamiennikiem dla bool. -1 to kod błędu, zwracany gdy funkcja normalnie zwracająca BOOL nie może poprawnie zakończyć działania. Jest to więc typ Troolowski a nie Boolowski.
  
  
• Gdy brak obsługi specyfikatora explicit, zdefiniuj go jako pusty symbol:
  
  #define explicit
  
  
• Używam static_cast, const_cast i reinterpret_cast gdyż są czytelniejsze, łatwiejsze do znalezienia w kodzie, sprawdzane co do klasyfikacji rzutowania w czasie kompilacji i tym samym samokomentujące dla innych programistów. Na dodatek mają jednorodną składnię postaci static_cast<double>(value). Gdy zbyt stary Watcom ich nie akceptuje, użyj klas z pliku l3_port.h, które dodatkowo pod eMbedded Visual 3 zdefiniują asercje, przekierują cout, cerr, stdin i stdout do pliku, dodadzą fstream, tamże możesz _"podmienić" basearray i autoarray na std::vector i porównać czas kompilacji, kod wynikowy i jego wydajność (a także się upewnić że masz przenośny kod i nie jesteś uwiązany do moich tablic).
  

Często przydzielam ponad 64kb pamięci i zakładam że int jest co najmniej 32 bitowy (może być większy, pierwsze testy na 64 bitowym DECAlpha całkowicie bezproblemowe). Często używam wzorców. Pliki biblioteczne są maksymalnie niezależne, np. nie używają wspólnego pliku idiotycznych, nieprzenaszalnych definicji i rzadko włączają się wzajemnie. Ze względów wydajności programów nie używam wyjątków, klas i funkcji wirtualnych, stosuję parametry domyślne jedynie do naprawdę dużych funkcji. Wszystko to co programuję pomyślane jest jako szybsze od ewentualnej konkurencji. Wydajność programów jest głównym celem mojej twórczości, a nie kwiecistość stylu programowania i trywialne komentarze plus noty prawne w kodzie źródłowym, ani tym bardziej ikonki, myszki i buczki na każdym kroku.


Wszystkie programy publikowane na tej stronie napisałem osobiście, rzadko z użyciem koncepcji i algorytmów osób trzecich (co zaznaczono). Kody źródłowe i programy zamieszczone są tutaj w celach edukacyjno-poznawczych i w celu pochwalenia się moimi zdolnościami. Kody źródłowe chodzą i są dobrze napisane, lecz ich całość nie stanowi produktu i nie zobowiązuję się do opisywania co się w nich dzieje i dlaczego dla tych, którzy czegoś nie doczytali, jest to więc raczej zbiór użytecznych przykładów jak problemy można rozwiązywać. Kod ten jest chroniony prawem autorskim i nadużycie tych praw w celu osiągnięcia korzyści materialnych będzie ścigane i karane w maksymalnym zakresie przewidzianym przez prawo. All trademarks are trademarks and are owned by their owners.

Polecana bibliografia

Zainteresowanych i zielonych odsyłam do następujących książek, które były kamieniami milowymi w mojej programistycznej edukacji:

• Kernighan, Ritchie _"Język C" (2nd ed.)
• Stroustrup _"Język C++" (5-ta ed.)
• Meyers _"Język C++ bardziej efektywny"
• Sutter _"Exceptional C++"
• Lippman _"Model obiektu w C++"
• Murray _"C++ Strategia i taktyka"
• Plauger _"Biblioteka standardowa C++"
• Knuth _"The art of computer programming"
• Sedgewick _"Algorithms in C++ p1-4"
• Press, Teukolsky, Vetterling, Flannery _"Numerical Recipes in C" (2nd ed.)
• Müllges, Uhlig _"Numerical Algorithms with C"
• Foley, van Dam, Feiner, Hughes _"Computer graphics: Principles and practice in C" (2nd ed.)
• Nelson, Gailly _"The data compresion book" (2nd ed.)
• Petzold _"Programowanie Windows"

Proszę mnie nie pytać gdzie je znaleźć.

Większość pozostałych publikacji (szczególnie tzw. biblie) to mniejsze lub większe wyciągi z tych właśnie pozycji.

Struktury danych i algorytmy

Dlaczego są lepsze sposoby na STL?

• Można zrobić wiele dobrego z uźyciem makra NDEBUG i assert tworząc bezpieczne STL.
• Można uniknąć dziedziczenia i notorycznych alokatorów aby przyśpieszyć kompilację i czasem znacząco czas wykonania.
• Można obstawić asercjami wszystkie argumenty standardowych funkcji, w szczególności konstruktorów. Grunt to znaleźć błąd i znaleźć go wcześnie!
• Można badać asercjami dostęp za granicami tablic.
• Można zabronić asercjami operacji pop dla pustych kontenerów.
• Można zabronić asercjami operacji push dla przepełnionych kontenerów.
• Nieudany przydział pamięci można od razu pokazać, nie każąc łapać wyjątków daleko w kodzie.
• Można użyć 'agresywnych destruktorów': w destruktorze zaśmiecamy dawną zawartość usuwanego obiektu. Już nikt go nie użyje przez pomyłkę za pośrednictwem starego adresu/wskaźnika.
• Można zaśmiecać wartości tablic przy ich tworzeniu a nie wypełniać w większości zerami. W ten sposób czytane lecz uprzednio nie zainicjowane pozycje zostaną łatwo wykryte.
• Zamiast chorych iteratorów można użyć inteligentnych wskaźników o mniejszym narzucie w czasie wykonania i z pełnymi asercjami co do zakresu i porównania.
• można dodać operację setsize() lub newsize() która zmieniałaby wielkość kontenera zapominając jego poprzednią zawartość (tak szybciej i często przydatne).
• Można w końcu postawić na 'standardowe' tablice dwuwymiarowe eliminując kupę bzdurnego kodu i błędów.

I można przy tym zachować stary kod! Uwaga od eksperta (to ja, rzecz jasna): sposób zaprojektowania iteratorów w STL wyklucza napisanie dla nich kontroli zbyt dużego zakresu. Nie doczekają się Państwo nigdy stosownej biblioteki... Moja idea polega na używaniu własnych kontenerów, przenaszalnych i maksymalnie wydajnych z identyczną semantyką życia, nazwami metod i operatorami jak w Standard Template Library. Oznacza to łatwiejszą naukę i łatwiejsze łapanie błędów tak wcześnie jak to możliwe. Nazwy kontenerów są różne niż w STL i uzewnętrzniają nieco bardziej ich wewnętrzną implementację. Możliwe jest jednoczesne używanie moich własnych kontenerów i STL. Aby zrezygnować z używania biblioteki wystarczy kilkadziesiąt linii kodu w którym należy wyprowadzić klasy basearray od std::vector itd. według odpowiedników, zobacz l3_port.h.
Co ciekawe, pod eMbedded Visual 3.0 nie ma iostream i fstream, szczęśliwie dostarczam własną mini-implementację opartą na stdio. eMbedded Visual 3.0 nie ma też STL ale to jak można się domyślić nie jest dla mnie problemem bo właśnie masz przed sobą w 90% kompatybilny i bardziej przenośny zamiennik.

• l3_array.h (bezpieczniej niż std::vector i szybciej niż std:valarray) - bezpieczne tablice, poinformuje o przekroczeniu zakresu, pamięć nie _"cieknie".
  
• l3_arr2d.h (brak konkurenta w całym STL!) - bezpieczne tablice 2D, indeksowane (x,y) i w stylu C [x][y], kontrola zakresu i iteratory.
  
• l3_arrex.h - definicje opcjonalnie używanych wyjątków do bezpiecznych tablic.
  
• l3_mat.h - macierz kwadratowa i rzadka z rozkładem LU: rozwiązują macierzowe Ax=b, a także układ równań liniowych np. dla 400 niewiadomych, wyznacznik macierzy (determinant), wskaźnik uwarunkowania macierzy (condition), iteracyjne poprawianie rozwiązania, funkcje podające błąd rozwiązania, bardzo przyśpieszone rozwiązywanie dla macierzy rzadkich...
  
• l3_mat3.h - macierz trójdiagonalna, macierz symetryczna trójdiagonalna i macierz cyklicznie trójdiagonalna z rozkładami LU Gaussa lub LDL^(T) Choleskiego dla macierzy symetrycznej, testowanie rozwiązań, statystyka zawartości.
  
• l3_mat5.h - macierz pięciodiagonalna (pentadiagonalna) - rozkład LU.
  
• l3_poly.h - wielomian dowolnego stopnia, liczy pochodne i wartość w punkcie (schematem Hornera).
  
• l3_stack.h (bezpieczniej niż std::stack) - bezpieczny stos (LIFO) (STL w ogóle nie nadąża). Moje struktury danych znacznie przewyższają wszystkie STL, ponieważ posiadają kompletną ochronę naruszenia zakresów (za pomocą assert). Jednym słowem nie da się nieświadomie zdjąć czegoś z pustego stosu/kolejki.
  
• l3_queue.h (bezpieczniej niż std::queue lub std::deque) - bezpieczna kolejka (FIFO), przemysłowo szybka, na tablicach (STL i Sedgewick się chowa).
  
• l3_heap.h (bezpieczniej niż std::priority_queue) - sterta (kolejka priorytetowa), można nią sortować nawet z pesymistyczną złożonością Nlog₂N, lepszą niż quick sort! Prosty sposób na zrobienie krótkiego słownika na podstawie danego tekstu.
• l3_qlist.h- szybka lista podwójnie linkowana, na tablicach: do 100x szybsza od wskaźnikowej (np. tej z STL...).
  
• l3_ptr.h - SmartPointer - inteligentny wskaźnik z kontrolą zakresu, już nigdy więcej pisania po pamięci 'o jeden bajt za daleko'. MemTester czyli tester klas-kontenerów: tak czuły na wysypania jak się da; idealny obiekt reprezentatywny.
  
• l3_str.h - TextString, przenaszalny! Nie martwisz się już więcej czy twój kompilator posiada standardową ponoć klasę 'string'.
  
• l3_rand.h - godny zaufania generator liczb losowych, oparty na ran2 (Numerical Recipies in C 2nd Edition) lub bardzo ostatnio modnym Mersenne Twister, rozkład normalny (Gaussa) metodą biegunową.
  
• l3_vec.h - w pełni wyposażony wektor 3D.
  
• l3_wire.h - grafika 3D we współrzędnych homogenicznych (por. Foley), dla obiektów konturowych (wire frame objects).
  
• l3_sort.h - różne algorytmy sortujące, wiele szybszych od standardowego qsort().
  
• l3_files.h - filename wildcarding, listowanie wielu plików jak np. w DOSie ('plik*.txt').
  
• l3_tool.h - krótkie często używane funkcje.
  
• l3_time.h - profilowanie funkcji, pomiar czasu, estymacja czasu trwania operacji, progresywnie wzrastająca _"siła działania" klawisza itp.
  
• l3_date.h - Rzeczywista Data: będzie działać do roku 2038... A pamiętać może miliony lat.
  
• l3_comp.h - liczby zespolone, części re i im na bazie double lub Rational lub czegokolwiek.
  
• l3_mem.h - przyśpieszanie zarządzania pamięcią, bloki pamięci.
  
• l3_opgl.h - OpenGL lub MESA, prosty interfejs pozwala na naprzemienne użycie obu bibliotek, przenaszalna grafika.
  

Symulacje w fizyce

• l3_spin.h - zespół n spinów góra/dół ustawi się na żądanie.
• l3_ising.h - kwadratowa płaszczyzna w modelu Isinga zapełniona spinami bez zewnętrznego pola magnetycznego czeka na osiągnięcie równowagi.
• l3_obj.h - galaktyka i punkt materialny + algorytmy ewolucji z czasem... Nic tylko animować ruch planet.
• l3_diff.h - Płaszczyzna dwuwymiarowa z operatorami liczącymi pochodne cząstkowe metodą róźnicową (finite difference).
  
• l3_spar.h - Cząstki rozmyte (smoothed particles) czyli sposób na symulowanie ciał stałych za pomocą średniej (ok. 1000) ilości cząstek o zadanych oddziaływaniach między nimi, wiele zaawansowanych algorytmów ewolucji w czasie dla różniczkowych równań Newtona.
  
• l3_rad.h - radialna funkcja falowa w polu potencjalnym, liczymy przekroje czynne na zderzenie i annihilację...

Metody numeryczne

• bignum.zip - klasa liczb nieskończonej (!) dokładności, wielomian i ułamek.
• plot.cpp - rozwiązanie uproszczone, lecz zdecydowanie szalone.
• inter.cpp - interpolacja wielomianowa Hermite'a.
  
• gaussdet.cpp - rozkład LU macierzy: eliminacja Gaussa (double pivoting) i wyznacznik (nowsza wersja: patrz l3_mat.h, tamże dużo szybciej lecz single pivoting), gaussdet jest bardziej poglądowy.
  
• liniter.cpp - iteracyjna metoda Jakobiego rozwiązywania równań liniowych (macierzowo Ax=b).
  
• eigvecja.cpp - iteracyjna metoda Jakobiego znajdowania wartości i wektorów własnych macierzy.
  
• polyroot.cpp - szukanie miejsc zerowych wielomianów (Bairstow, Newton).
  

Algorytmy

• l3_sort.h - kilkanaście smakowitych algorytmów sortujących, kilka błyskawicznych.
• sortlab.cpp - laboratorium testujące sortowanie.
• sortresu.txt - porównanie algorytmów.

Grafika i symulacje

• l3_opgl.h - Są to definicje upraszczające użycie OpenGL, dostępnej z pakietem MSVC++ i nie tylko...
• feigen.exe - badanie przekształcenia logistycznego - bifurkacje Feigenbauma.
• throw.exe - symulacja rzutu ukośnego w polu grawitacyjnym ziemi, także z oporami.

Wybiórczy przegląd

• feigen.exe - badanie przekształcenia logistycznego: x_n+1 = kx_n(1-x_n) dla k z przedziału (3...4) dostarcza efektowny chaos. Na początku ustalam x₁ na dowolne z zakresu (0, 1) i obliczam np. x₁₀₀. Dla pewnych k x_dużo dąży do określonej liczby, dla innych k powstają chaotyczne, zależne od konkretnego komputera wyniki. Odkładając na osi OX parametr k, na osi OY końcową wartość x₁₀₀ i jednocześnie następne x₁₀₁, x₁₀₂, ..., x₂₀₀ otrzymujemy diagram bifurkacji Feigenbauma. Klawisze myszy wybierają obszar do powiększenia. 'q' powiększa obszar. 'w' niezależnie od wybranego obszaru zmniejsza wykres o stały czynnik. Na środku diagramu mamy wykres wykładnika Lapunowa, ujemna wartość oznacza przyciągający (stabilny) obszar odwzorowania, dodatnia - chaotyczny. Pomaga to w zauważeniu wysp stabilności pośród chaosu. Owe wyspy są naprawdę gęsto rozmieszczone...
• l3_file.h - prawdziwym problemem w małych programach jest odczytanie z dysku wszystkich plików ze ścieżki podanej tak '\*' lub tak '../dir/*.bat' lub tak 'a:\dir\'. Ta biblioteka rozwiązuje czasochłonny w testach problem korzystając z nieprzenaszalnych (niestety) funkcji pod MSVC 5.0. Na szczęście pod UNIXem problem ma dużo mniejsze znaczenie (można czytać w programie wszystko ze stdin, a uruchamaiać go tak: 'cat xfiles*.zi? | moje'.
• l3_tool.h - czyli różne elementarne i przenaszalne narzędzia, które powinny być w standardowych bibliotekach a ich tam nie widać, np. funkcja obcinająca liczbę do zadanego zakresu oraz inteligentna zmienna, pamiętająca swoją starą wartość, pomocna także do obsługi parametrów zmienianych klawiaturą: nigdy nie przekroczy zadango zakresu, oraz posiada funkcje z rodziny Dynamic...() które umożliwiają progresywne zwiększanie i zmniejszanie jej wartości coraz większymi skokami. Efekt ten użyłem w throw.cpp.
• w2i.zip - Win2Iso text converter - przerabia pliki HTML ze standardu Win1250 na ISO, dzięki czemu polskie litery na Twoich stronach pojawią się na przeglądarkach niemicrosoftowych. W przeciwieństwie do setek podobnych programów, ten nie dołącza swoich tekstów 'copyright' itd. a na dodatek dołączyłem kod źródłowy. Ponadto program zamienia napotkany ciąg znaków 'charset=windows-1250" ' na 'charset=iso-8859-2" '. Plik do konwertowania podaje się jako parametr wywołania w linii komend.
• throw.exe - jest to symulacja rzutu ukośnego w polu grawitacyjnym ziemi (F_y=-const), w przypadku braku oporu powietrza lub oporze powietrza zależnym jak -const*v (czyli duże ciało, względnie mała prędkość i bez turbulencji) lub -const*v² (czyli mniejsce ciało, lub szybsze i turbulencja). Obsługa: kursorami ustaw "armatkę" , [a], [z] ustawiają prędkość początkową, [s] strzela i zatrzymuje symulację. W dowolnej chwili [d] zmienia charakter oporu powietrza. Jasność punktu zależy od prędkości piłki, natomiast sam czas symulacji jest liniowy (lecz stałe fizyczne i czas nie są w żaden realny sposób przeskalowane). [r] wyświetla zależność zasięgu rzutu od kąta podniesienia (dla kątów -90...90 stopni od poziomu), przy prędkości zadanej dla armatki, im ciemniejsza linia tym tłumienie zależy od wyższej potęgi. Aktualny kąt podniesienia jest pokazany pionową linią na tym wykresie. Więc aby "strzelić" najdalej, należy wybrać przez [d] charakter tłumienia, i tak dobrać kąt, by pionowa linia kąta rzutu pokrywała się z maksimum zasięgu dla danego tłumienia (patrz na strzałki!). Zapraszam do zabawy.
  Dość ciekawy jest fakt użycia znanej biblioteki OpenGL. Plik źródłowy throw.cpp załączyłem. W celu kompilacji pod MSVC 4.0 i wyższym (konieczne Win95 wyprodukowane po 1996r z powodu OpenGL) należy:
  • 'New project': console application
  • 'Add to project': throw.cpp,
  • 'Build/Rebuild All'
  • jest mnóstwo błędów, więc ustawiamy opcje linkera: 'Alt-F7:Link tab', i dopisujemy te biblioteki: "glaux.lib opengl32.lib glu32.lib" oraz ew. dodatkowo (polecam) w polu linii komend linkera "/subsystem:windows" i "/entry:mainCRTStartup"
  • 'Build/Rebuild All'
  • 'Build/Run' i gotowe (mam nadzieję)
  Najzabawniejsze, że ten program jest całkowicie przenaszalny na UNIXy! Tyle, że OpenGl na linuxa jest tylko komercyjne, a GLUT nadaje się, lecz trzeba zmienić nazwy wielu funkcji z 'aux*' na 'glut*', 'gl*' na 'glut*' i nazwy funkcji otwierających okno na jakieś inne.
• koch.exe - można wydrukować, skopiować do schowka i pobawić się z krzywą Kocha. Można ją także budować na nietypowych, wyciągniętych trójkątach (spróbuj parametr wzrostu = 11 !).
• bignum.zip - jak policzyć liczbę e (Eulera ~ 2.71) lub Pi (~3.14) lub cokolwiek baaardzo ważnego z dokładnością do 100 (a może nawet do 10000) miejsc po przecinku? Czasem pakietem Mathematica, Maple, Reduce, a czasem za pomocą języka C++. Wystarczy zdefiniować: klasę liczba (dowolnej dokładności), następnie wszystkie operatory (w zasadzie wystarczy z dziesięć) i już. A 20KB kodu źródłowego i przykład jest w tym pliku. Kod jest już agresywnie optymalizowany na prędkość i wygląda na wystarczający niezrozumiały by nadawał się do publikacji. Ze względu na mój niskopoziomowy styl C++, przepisanie go na asembler przyniesie zyski <=30% (serio, już próbowałem), a wstawka asemblerowa w środku dużej funkcji (np. CalcAddOn) źle wpływa na pracę każdego kompilatora optymalizującego i wynik szybkościowy na początku przepisywania na asembler bywa z początku znacznie gorszy! Przetestowana kompilacja pod linuxem, przy agresywnej optymalizacji do 30% szybciej niż pod Win95. Obecna wersja działa szybciej niż jakikolwiek znany mi pakiet matematyczny do obliczeń dokładnych (oczywiście w ramach tego, co BIGNUM potrafi, a nie potrafi np. dobrze dzielić. Ale tylko dlatego, że się za to jeszcze nie wziąłem i nikomu to nie było potrzebne).
• part.zip - obliczanie partycji liczby naturalnej. Są tamże wyniki obliczeń, kody źródłowe i inne.
• mmx.zip - plik ASCII ze spisem instrukcji MMX i przykładem zastosowania. A oto, jak dodać dwie tablice 64 liczb każda typu unsigned char (a i b) przechowując wynik w tablicy c pod MSVC 5.0:
  
  unsigned char *a, *b, *c;
unsigned char *oa=a, *ob=b, *oc=c; //pamiętanie wskaźników, 3 cykle
__asm emms //~17 cykli
for(char i=0; i<8; i++, a+=8, b+=8, c+=8)
{
    __asm{
    movq mm0, qword ptr a //1 cykl
    paddusb mm0, qword ptr b //1 cykl
    movq qword ptr c, mm0 }//1 cykl
}
a=oa; b=ob; c=oc; //przywracanie wskaźników, 3 cykle

  A oto równoważny kod w czystym C:
  
  unsigned char *a, *b, *c, *oa=a, *ob=b, *oc=c;
for(char i=0; i<64; i++)
    *c++=*a++ + *b++;
a=oa; b=ob; c=oc;

  Czyli z użyciem MMX na 8 obrabianych bajtów przypada 3 cykle na operacje i 3 na zwiększanie wskaźników (razem 6 cykli x 8 porcji + 17 cykli emms + 6 na przywrócenie starych wskaźników = 71 cykli).
  To samo z użyciem zwykłego kodu: na każdy obrabiany bajt 3 cykle i 3 na zwięksanie wskaźników (razem 6 cykli * 64 porcje + 6 na przywrócenie starych wskaźników = 387 cykli). Teoretycznie 5 razy szybciej, lecz ten wynik powinien się pogorszyć do ok 3 x z uwagi na superskalarność procesorów wobec rejestrów ogólnego przeznaczenia (ale przyjdą czasy, gdy będzie kilka równoległych potoków dla MMX, a wtedy...). Uwaga: nie wliczałem też czasu porównań i inkrementacji licznika (a przecież w zwykłym kodzie było takich operacji 8 razy więcej niż w MMX).
  I ostatecznie: do wyniku MMX trzeba dodać 8 porównań i 8 inkrementacji (16 cykli), a do zwykłego kodu 64 porównania i 64 inkrementacje... Ale w rzeczywistości ta różnica nie byłaby dodana, bo sprytny programista rozwinąłby pętlę tak:
  
  unsigned char *a, *b, *c, *oa=a, *ob=b, *oc=c;
for(char i=0; i<8; i++)
{
    *c++=*a++ + *b++;
    *c++=*a++ + *b++;
    *c++=*a++ + *b++;
    *c++=*a++ + *b++;
    *c++=*a++ + *b++;
    *c++=*a++ + *b++;
    *c++=*a++ + *b++;
    *c++=*a++ + *b++;
}
a=oa; b=ob; c=oc;

  
  I finalnie ilość porównań jest taka sama. A teraz przykład, jak oficjalnie nie należy pisać w C++, ale jak trzeba gdy się spieszymy. Zakładamy tu ostro, by istniał typ __int32 - 32 bitowy. Do dzieła, rozwijając dwukrotnie pętlę:
  
  unsigned char *a, *b, *c, *oa=a, *ob=b, *oc=c;
__int32 *ptra=(*__int32)a, *ptrb=(*__int32)b, *ptrc=(*__int32)c;
/*
A co mi tam - w końcu chyba te unsigned chary siedzą w pamięci po kolei?
No to dodajemy czwórkami, bo dodanie wartości 32 bitowych zajmuje na procesorach
np. pentium tyle samo co dodanie dwóch 8 bitowych - tylko jeden cykl!
Uwaga: jeśli będzie przeniesienie przy dodawaniu - nie wolno tak czynić
i tylko odpowiednia instrukcja MMX może być ratunkiem.
*/
for(char i=0; i<8; i++)
{
    *ptrc++=*ptra++ + *ptrb++;
    *ptrc++=*ptra++ + *ptrb++;
}
a=oa; b=ob; c=oc;

  
  Oczywiście najlepiej byłoby na procesorze Intel Merced zrobić tak:
  
  unsigned char *a, *b, *c;
__int64 *ptra=(*__int64)a, *ptrb=(*__int64)b, *ptrc=(*__int64)c;
for(char i=0; i<4; i++)
{
    *ptrc++=*ptra++ + *ptrb++;
    *ptrc++=*ptra++ + *ptrb++;
}

  Przy czym na UNIXach można zamiast '__int64' napisać 'long long'. Powyższy kod można kompilować nawet na procesorze 32 bitowym, ale kwestia wydajności z jaką kompilator C++ udaje maszynkę 64 bitową jest nierozstrzygnięta - lecz ogólnie opłaca się stosować technikę 64 bitową, bo takie procesory już będą chociażby w domach lada dzień.
  
  Oto wyniki po wliczeniu ilości porównań:
  • Merced 2x unrolled, 64bit required: = 51
  • MMX: 71+16 = 87
  • C 2x unrolled, 32bit required: = 99
  • C 8x unrolled loop: 387+16 = 403
  • typical C: 387+128 = 515
  
  Jak widać 8-krotne rozwinięcie pętli daje kod 1-403/515 = 20% szybszy, co jest czasami nie do pogardzenia. Co ważne, ze względu na superskalarność procesorów, w typowych zastosowaniach na AMDK6 ten rozwinięty kod dla długich pętli (dodajemy ok. 4096 bajtów) jest ok. 35% szybszy od zwykłego kodu C. Uwaga: według wszelkich moich dociekań kompilator MSVC++ 5.0 praktycznie nie rozwija pętli, natomiast gcc 2.7.3 robi to po podaniu opcji -O3 lub -funroll-loops, a rozwija prawie wszystkie po podaniu -funroll-all-loops. Ta ostatnia opcja może ponoć (man gcc) obniżyć wydajność przy niektórych algorytmach, ale ja zauważyłem, że właśnie dopiero po podaniu tej ostatniej opcji przyśpieszenie jest zauważalne. Poza tym, dobry kompilator pod windows jest pojęciem czysto wirtualnym, więc jeśli się spieszysz, to rozwijaj kod źródłowy.
  
• lib3.zip - to bardzo użyteczne biblioteki struktur danych. Są zaimplementowane z naciskiem na wydajność. Jest tu lista, zbiór, kolejka, stos, tablica, sterta, buforowany generator liczb losowych. Wyglądają na bardzo wartościowe (skromnie mówiąc). Tablica i ciąg znaków jest jednak optymalizowany na bezpieczeństwo, gdyż optymalizacja tych klas na szybkość sprowadza się do nieimplementowania ich w ogóle jako klas, tylko użycia podstawowych typów wskaźnikowych. Powyższe archiwum jest w całości zawarte w cpp.zip.
• knight.cpp - czy można konikiem szachowym odwiedzić wszystkie pola na zadanej wymiarami planszy? Klasyczny, króciutki algorytm z nawrotami, jest niestety niestabilny (z jednego pola planszy 8x8 wynik jest w 1s, lecz z innego może być (i bywa) do 5.5 godziny).
• l3_sort.h - spora biblioteka algorytmów sortujących, oraz sortlab.cpp czyli laboratorium testujące wydajność tych algorytmów. Szczególnie polecam! Na deser: sortresu.txt to wynik pracy laboratorium dla najważniejszych algorytmów sortujących.
• permut.cpp - wakacje na Permutach czyli program wyświetlający permutacje (wszystkie i _"po kolei", do tego naprawdę szybko). Zastosowania są szerokie: do łamania haseł linuxowych (a nuż ktoś użył permutacji liter swojego loginu, nazwy serwera... Łamać należy oczywiście z uwzględnieniem dodatkowych metod rekombinacji haseł!). Mnie przydaje się to do liczenia wyznacznika i do wielu brutalnych metod odgadywania rozwiązań przy bardzo małej ilości danych, bo złożoność obliczeniowa rzecz jasna wynosi O(n!).
• det.cpp - skoro umiemy permutować, to możemy obliczać wyznaczniki korzystając z permutacyjnej definicji wyznacznika. Metoda wyznaczania minorów po kolei oznaczałaby dużo kopiowań po pamięci, a tu algorytm jest względnie prosty.
• gaussdet.cpp - jednak znając rozkład P*A=L*U macierzy A (rozkład LU - LU decomposition) możemy liczyć wyznacznik ze złożonością obliczeniową O(n³) zamiast O(n!) z definicji permutacyjnej... Co więcej, rozkład LU może się przydać do rozwiązywania układu równań liniowych i szukania macierzy odwrotnej przy O(n³). Jest to więc zalecana metoda numerycznych zabaw z macierzami. Do poważnych zastosowań zalecam klasę GaussLU_Once i GaussLU_NarrowMulti z l3_mat.h.
• inter.cpp - interpolacja wielomianowa Hermite'a z uwzględnieniem pochodnych dowolnego rzędu, dane wejściowe: TablicaArgumentówX={12, 12, 12, 15, 15, 16} TablicaWartościIPochodnychY={0, 0, 0, 1, 2, 3} oznaczają, że 2 pochodna, a także 1 oraz wartość w punkcie X=12 są zerowe, pierwsza pochodna dla X=15 wynosi 1, wartość w X=15 wynosi 2, wartość dla X=16 wartość wynosi 3. Trzeba pilnować kolejności niemalejących argumentów, oraz kolejności: {n-ta pochodna, ..., 1-sza pochodna, wartość, następne dane}.
• liniter.cpp - rozwiązywanie układów równań liniowych (Ax=b) metodą iteracyjną Jakobiego. Alternatywą jest użycie eliminacji gaussa - patrz gaussdet.cpp.
• part1.cpp i part2.cpp - partycja liczby naturalnej, czyli obliczanie, na ile sposobów można za pomocą sumy liczb naturalnych rozpisać inną liczbę naturalną. Wersja 2 pokazuje sukces tzw. programowania dynamicznego (podwyniki są sprytnie tablicowane co drastycznie zmniejsza ilość wywołań rekurencyjnych, w efekcie program part2.cpp działa ok. 10⁵ razy szybciej od part1.cpp). Niestety partition(121) jest większe niż największy int na maszynce 32 bitowej. Używając reprezentacji liczb dowolnie dużych (bignum.zip) program part3.cpp znajdzie partycję nawet dla 800. I jest odpowiednio powolny. Jest za to part4.cpp który można kompilować pod Linuxem, używa zgodnie z sugestią dr Z. Kozy typu 'long long' (signed 64 bit integer), co jest raczej nieprzenaszalne ale działa klawo nawet na i486 (chociaż on nie ma nawet takich szerokich rejestrów!). Ten typ pod innymi kompilatorami może się nazywać hyper lub __int64. W przypadku mnożenia (~11...127 cykli procesora) najszybszy jest typ 1 bajtowy char (czas wykonania T=1), potem praktycznie równie ze sobą szybkie (z dokł. do kilku procent) typy short (2 bajty, T=1.2) oraz int (4 bajty, T=1.2), __int64 ma T=3.1 i jest emulowany software'owo na etapie kompilacji (na procesorach 32 bitowych, czyli praktycznie wszyskich: Intele wszystkie aż do Merceda wyłącznie). Można liczyć partycję(405) otrzymując poprawny wynik już w 2.5s na AMDK6-233. Jest też wersja pod MSVC 5.0: part5.cpp która działa tak samo, lecz z powodu źle napisanych przez Microsoft klas (źle przeciążyli cout<<), używa supertajnej funkcji _i64toa... part6.cpp - to już chyba ostatnia wersja po optymalizacjach... Całość jest również zebrana w archiwum part.zip
• plot.cpp - jak nabazgrać na ekranie Windows95 bez otwierania okna?

kbosak@box43.pl