Nie ma czegoś takiego jak najszybszy kod

Oryginalny post: There Ain't No Such Thing as the Fastest Code

Autor: Jeff Atwood

Uradowałem się, gdy zobaczyłem, że James Hague wybrał książkę The Zen of Assembly Language Programming jako jedną z pięciu, godnych zapamiętania książek o programowaniu. Całkowicie się z tym zgadzam. Nawet jeśli podczas swojej zawodowej kariery nie planujesz nawet liznąć asemblera, to ta książka jest i tak fantastyczna oraz całkowicie godna polecenia. Byłem zwykłym programistą Visual Basica w momencie, gdy natrafiłem na tę książkę (razem z The Zen of Code Optimization), zacząłem czytać ją dla zabawy i ledwie mogłem się od niej oderwać. Jest tak dobra.

Abrash nie tylko jest wpływową postacią wśród inżynierów oprogramowania, ale również jednym z najlepszych technicznych pisarzy, jakiego jesteś w stanie znaleźć. To dlatego jest on jednym z moich programistycznych bohaterów, zaraz obok Steve'a McConnell'a.

Jego książka Graphics Programming Black Book jest świetna w podobny sposób i pokrywa tak rozległe tematy, że tytuł staje się trochę niewłaściwy. Najlepsze jest to, że dzięki uprzejmości Dr. Dobb's jest ona dostępna w sieci, więc można ją wypróbować samemu.

Michael Abrash Graphics Programming Black Book

Wiem, co sobie myślisz. "Ta książka jest o grafice. I o asemblerze. Dodatkowo, jest z 1996 roku, co w komputerowych latach oznaczałoby 1928. Jako programista, nie jestem nią zainteresowany." Przyznaj to. Tak właśnie. Ale wiesz, co zamierzasz zrobić? Zamierzasz i tak ją przeklikać, i trochę poczytać. Tak jak na studiach, tematyka zajęć nie jest istotna, jeśli wykładowca jest znakomitym nauczycielem. A dokładnie takim nauczycielem jest Abrash.

Abrash jest światowej sławy programistą oraz pisarzem technicznym, ale również nie wstydzi się wyjaśniać zagrożenia oraz niebezpieczeństwa związane z naszą profesją, włączając w to największy problem ze wszystkich — ten, który siedzi za klawiaturą. Pozwól mi, iż zilustruję to za pomocą jednego z moich ulubionych paragrafów Abrasha, z 16 rozdziału książki Graphics Programming Black Book.

Nie tak dawno temu, Terje Mathisen, którego przedstawiłem wcześniej w książce, napisał bardzo szybki program zliczający wyrazy, a następnie umieścił go w serwisie BIX. Kiedy mówię, że był szybki, to mam na myśli szybki; ten kod był rewelacyjnie zoptymalizowany. Mówimy tu o kodzie najwyższej jakości.

Kiedy temat optymalizacji został poruszony na jednej z konferencji BIX, to został również wspomniany program Terje'a, i ogłosił on następującą wiadomość: "Rzucam wyzwanie społeczności BIX (a w szczególności mabrashowi!), abyście znacznie przyspieszyli mój program. Wynik w wysokości 5% uznaję za dobry." Oczywistym wnioskiem było to, że "ten kod był tak szybki, jak to tylko możliwe."

Oczywiście nie był; nie ma czegoś takiego jak najszybszy kod.

[sztuczki asemblera i użyteczne podejścia optymalizacyjne w skrócie — zobacz PDFa, jeśli chcesz więcej]

Największą barierą optymalizacyjną jaką napotkał Terje było to, iż myślał, że posiadał najszybszy możliwy kod. Kiedy już otworzył się na możliwość, że istnieją szybsze podejścia, i spojrzał poza to konkretne podejście, które tak ostrożnie optymalizował, to był w stanie stworzyć kod, który był o wiele szybszy. Zauważ nieodpowiedniość chęci Terje'a, aby uznać 5% przyspieszenie za znaczące w świetle jego późniejszego niemal dwukrotnego zwiększenia wydajności.

W tym samym rozdziale, Pan Abrash nawiązuje do podobnej anegdoty opartej na programie do zliczania słów. Był on opublikowany jako wyzwanie w jego sekcji "Pushing the Envelope":

Wyzwanie zostało zapoczątkowane przez artykuł dotyczący liczenia wyrazów w dokumencie, napisany przez Davida Gerrolda; David przedstawił też w międzyczasie kila całkiem interesujących problemów optymalizacyjnych. Zaprogramował wszystko w Pascalu zaznaczając przy tym, że wersja w asemblerze prawdopodobnie byłaby szybsza, ale jego wersja pascalowa działała poprawnie i była wystarczająco szybka dla niego.

Jednakże nie była wystarczająco szybka dla mnie. Logicznym punktem startowym do przyspieszania programu do liczenia wyrazów wydawał się być oryginalny kod pascalowy Davida, ale jako iż lepiej się czuję w C, więc stworzyłem luźną aproksymację programu Davida przetłumaczoną na C.

Mike kontynuował to, w czym jest najlepszy — zoptymalizował program do liczenia wyrazów w kodzie asemblera i wyjaśnił przy okazji w sposób opanowany i wysoce elokwentny. Efekty jego pracy są następujące:

konwersja do C 4.6 sekundy
konwersja do C oraz asemblera 2.4 sekundy
konwersja do C oraz asemblera z tabelą podglądu 1.6 sekundy

Następnie opublikował on swój program jako wyzwanie dla czytelników PC Techniques — czy ten program do zliczania słów napisany w zoptymalizowanym asemblerze, autorstwa uznanego przez branżę eksperta w dziedzinie optymalizacji asemblera, może być uczyniony jeszcze szybszym? Cóż, podejrzewam, iż możesz zgadnąć co nastąpiło potem.

Tak więc jak plasowali się uczestnicy tego konkretnego wyzwania? Więcej niż jeden twierdził, iż trzykrotnie przyspieszył mój asemblerowy kod zliczający wyrazy. Biorąc pod uwagę trzykrotne przyspieszenie w stosunku do kodu C, które zrealizowałem, to mamy do czynienia niemal z przyspieszeniem o rząd wielkości. Oczywiście masz prawo do swojej opinii, ale ja uważam, że rząd wielkości jest znaczący.

Prawdę mówiąc, nie oczekiwałem trzykrotnego przyspieszenia; dwukrotne, to było to, co miałem na myśli. Co z kolei pokazuje, iż każdy kod może zostać przyspieszony bardziej, niż tego oczekujesz, jeśli odpowiednio długo i z odpowiednio wielu perspektyw się nad nim zastanowisz.

Jak to powiedział Mike, nie ma czegoś takiego, jak najszybszy kod. Jeśli uważasz, że jest, to prawdopodobnie Ty jesteś barierą stojącą na drodze ku lepszej wydajności, a nie kod.

Data publikacji oryginału: 19 lutego, 2008

9 komentarze:

godlark pisze...

Artykuł fajny, wiem co ma na myśli autor.
Jednak zdecydowanie brakuje mi przykładu jak ten kod został przyśpieszony, chociażby głupich odnośników do kodu.

sprae pisze...

Ciekawe który mocarz wymyślił ten boczny panel z linkami do podstron zasłaniając tekst.

szmergiell pisze...

sprae, a myślałem, że tylko mi przeszkadza ten panel.

Marek Stój pisze...

Panowie sprae i szmergiell: można było maila skrobnąć do nas i coś byśmy zaradzili, a nie tak w komentarzach - nie jesteśmy w stanie przeczytać wszystkich Waszych wypowiedzi, gdyż jest ich baaardzo dużo ;)

Jakich używacie rozdzielczości, że ten pasek nachodzi na treść?

stark pisze...

pewnie mniejszych niż 1280x800, bo w takiej rozdziałce jest ok ;)

Anonimowy pisze...

Nawet tego paska nie zauważyłem w mojej rozdzielczości 1680 x 1050 ;) Kto ma większą rozdzielczość - parafrazując za treścią tego artykułu?

rafek pisze...

@Anonimowy: Top3 rozdzielczości ekranów czytelników dB wg Google Analytics jest następujące: 1280x800, 1280x1024, 1680x1050

Anonimowy pisze...

Rozdzielczość 1920x1200, oglądam przeważnie na połowie ekranu (czyli 960), pasek nachodzi na komentarze.

szmergiell pisze...

1024x768

Prześlij komentarz

Related Posts with Thumbnails