Algorytmy i książki

Kiedy w 1969 roku zaczynałem programować, to nawet komputery mainframe od IBM-a mogły mieć jedynie 1 MB pamięci głównej i dwa lub trzy napędy dyskowe mierzone w setkach megabajtów z wielościeżkowymi taśmami uzupełniającymi pamięć masową. Jakikolwiek rodzaj przetwarzania równoległego zwykle kładł nacisk na utrzymanie potrzebnych danych w głównej pamięci i trzeba było próbować przenosić gotowe dane na „stabilną pamięć masową”, czyli dysk lub taśmę magnetyczną.

Niektóre z pierwszym komputerów IBM, na których programowałem, korzystały z systemu operacyjnego MFT (Multiple Fixed Tasking), który posiadał do 16 „partycji” w pamięci. Każda z nich posiadała stały rozmiar ustawiany przy konfiguracji systemu.

Kiedy operatorzy uruchamiali zadanie, JCL (Job Control Language) określał, jak wiele pamięci będzie potrzebował, i zadanie było ustawiane we fragmencie pamięci o wystarczającej przestrzeni. Jeśli twórca JCL-a podał zbyt duży kawałek, oznaczało to, że pamięć była marnowana. Zbyt mały z kolei sprawiał, że program mógł się nie zakończyć, a nawet nie uruchomić.

Później system został zmieniony na MVT (Multiprogramming with a Variable number of Tasks), który pozwalał programiście (gdyż to on zwykle generował JCL-e) na określanie dokładnego rozmiaru jednego z 16 możliwych kawałków. Problemem MVT było to, że mógł tworzyć serie małych, niemożliwych do użycia dziur w głównej pamięci fizycznej systemu. Kiedy kilka mniejszych dziur łączyło się razem, można było uruchomić większy program, co jest raczej prymitywnym sposobem na sprzątanie.

Jeśli brzmi to trochę skomplikowanie, a może i niewiarygodnie w czasach pamięci wirtualnej na żądanie, to dorzucę jeszcze jedną informację. Przestrzeń adresowa mainframe’ów IBM-a była oryginalnie w 24 bitach (zamiast 32 lub 64), co oznaczało, że programy mogły adresować maksymalnie 16 milionów bajtów pamięci głównej naraz.

Oczywiście, chociaż maszyny te były według dzisiejszych standardów niesamowicie powolne i logicznie niewielkie, to dla nas to była „magia”, kiedy je programowaliśmy.

W każdym razie przywiązywaliśmy dużo uwagi zapotrzebowaniu na pamięć dla każdego kawałka danych oraz temu, jak wiele obliczeń będzie kosztowało każde działanie. Czasami, w dłuższej perspektywie, odbijało się to na nas negatywnie, na przykład w przypadku głośnego problemu roku 2000, gdyż wydawało nam się, że dwie, a nie cztery cyfry wystarczą do zapisania roku.

Wiele osób może pamiętać, że kiedy zbliżaliśmy się do roku 2000, zaczęto panikować odnośnie tego, co się stanie o północy 31 grudnia 1999 r., kiedy zmieni się stulecie. Na szczęście ludzie zaczęli myśleć o tym wystarczająco wcześniej i problem został zlikwidowany.

Kilka lat wcześniej wyszła seria książek pod Donalda E. Knutha pod tytułem Sztuka programowania. Tom 3, Sortowanie i wyszukiwanie, wydany został w 1973 roku, kiedy zaczynałem programowanie na mainframe’ach IBM-a, chwilę przed rozpoczęciem studiów magisterskich z informatyki.

Algorytmy w tej książce starannie wyjaśniały różne metody sortowania i wyszukiwania oraz w jaki sposób korzystają one z poziomów pamięci – od dysków po rejestry procesora i wszystko pomiędzy (główna pamięć, pamięć buforująca). Książka wskazywała, że przy ograniczeniu do 24-bitowej przestrzeni adresowej (często 16-bitowej lub mniejszej na minikomputerach) tablice mieszające i techniki wyszukiwania z nich korzystające często były nieefektywne ze względu na liczbę zderzeń.

Jednak, łącząc wiedzę o efektywności danego algorytmu, rozmiarze sortowanych danych i architekturze maszyny, możemy uniknąć drastycznych konsekwencji.

Miałem kiedyś program, który sortował 1206 wierszy o długości 32 bajtów. Pracował na komputerze PDP-11/70 (z 64 KB przestrzeni adresowej) z systemem operacyjnym RSTS/E. Ukończenie sortowania zajęło mu 10.5 godziny. Wykorzystywał sortowanie bąbelkowe i jeśli wszystkie dane przechowywane by były w pamięci głównej, nie byłoby tak źle, ale niestety korzystał z wirtualnej tablicy, która była implementowana na dysku. Program wykonał ponad 13 milionów porównań i 700.000 odczytów z dysku.

Przepisanie programu tak, aby korzystał z sortowania przez utworzenie kopca i łączenie sortowań tak jak w książce Knutha rozbiło 1.206 wierszy na siedem plików po 173 wiersze i każdy z nich mógł być przechowywany i sortowany w pamięci głównej. Na koniec połączyłem siedem posortowanych plików, razem otrzymując ostateczny wynik. Czas tej operacji został zredukowany do 3 minut (z 10,5 godziny).

Knuth to nie jest jedyny dobry autor piszący o algorytmach, ale głębia jego analizy sprawia, że książki te są wiecznie żywe, w przeciwieństwie do innych popularnych wydawnictw o komputerach.

Jon „maddog” Hall jest autorem, wykładowcą, informatykiem i jednym z pionierów Wolnego Oprogramowania. Od 1994 roku, kiedy po raz pierwszy spotkał Linusa Torvaldsa i ułatwił przeniesienie jądra na systemy 64-bitowe, pozostaje orędownikiem Linuksa. Obecnie jest prezesem Linux International®.