Jak korzystać z Lookup Table?

Zastosowania tablic w C - wszystkie wpisy

• Tablice wskaźników na funkcje
• Maszyny stanów na tablicach
• Tablice przyspieszające wyszukiwanie elementów
• Jak korzystać z Lookup Table?

Pod wpływem doskonałej książki Code Complete autorstwa Steve’a McConella postanowiłem napisać o zastosowaniach tablic w C. Nie chodzi mi tu oczywiście o podstawy, składnię itp. Chociaż jak to w C, nawet tutaj znalazłoby się kilka niuansów. Mam zamiar zająć się bardziej zaawansowanymi tematami takimi jak lookup table, hash table, maszyny stanów, czy polimorfizm na tablicach wskaźników na funkcje. Wyszło tego sporo, dlatego podzieliłem tekst na kilka wpisów. Na pierwszy ogień idą Lookup Table.

Czym jest Lookup Table?

Lookup table (LUT) to technika zwiększająca szybkość wykonywania programu kosztem zużycia pamięci RAM albo ROM w zależności od tego, czy wpisy w tablicy można edytować podczas działania programu. Polega na zapisaniu w pamięci tablic z wynikami obliczeń dla poszczególnych wartości. Dzięki temu obliczenia zajmujące wiele instrukcji procesora zastępujemy jednym odczytem z tablicy.

Typowe zastosowania

Chyba najczęściej wykorzystywanym zastosowaniem LUT w embedded jest CRC. Zamiast wykonać obliczenia, przechowujemy obliczone CRC dla 256 bajtów. Technika jest na tyle popularna, że w internecie możemy łatwo znaleźć skrypty generujące nam tablice dla dowolnych wielomianów CRC. Moja ulubiona strona do generowania CRC to Sunshine. Więcej o obliczaniu CRC w osobnym wpisie.

Innym typowym zastosowaniem są funkcje trygonometryczne. Wystarczy przechowywać wartości dla przedziału . Z ćwiartki sinusa możemy łatwo wygenerować wartość dla dowolnego kąta. Dla wartości pomiędzy kolejnymi indeksami tablicy możemy zastosować interpolację.

Dobrym kandydatem na LUT są odczyty z sensorów, które chcemy przekonwertować na wartości fizyczne. W jednym z poprzednich wpisów użyłem tej techniki do obliczania odległości od ściany na podstawie odczytu z ADC w robocie Micromouse.

Innym zastosowaniem Lookup Table bardzo powszechnym w systemach embedded jest obsługa wyświetlaczy. Mamy tutaj duże pole do popisu. W tablicach przechowujemy czcionki, teksty, czy całe struktury menu albo nawet animacje.

Zastępowanie logiki warunkowej

LUT mogą zastępować nie tylko obliczenia, ale również skomplikowaną logikę warunkową. Dobrym przykładem mogą być tu działania na datach jak konwersja dnia od początku roku na format dzień/miesiąc/rok:

enum
{
	YEAR_TYPE_NORMAL,
	YEAR_TYPE_LEAP,
	YEAR_TYPE_MAX,
};

enum
{
	MONTH_JAN = 1,
	MONTH_FEB,
	MONTH_MAR,
	MONTH_APR,
	MONTH_MAY,
	MONTH_JUN,
	MONTH_JUL,
	MONTH_AUG,
	MONTH_SEP,
	MONTH_OCT,
	MONTH_NOV,
	MONTH_DEC,
	MONTH_MAX,
};

struct date_format_day_month_s
{
	day_t day;
	month_t month;
};

const day_t DAY_ERROR = -1;
const month_t MONTH_ERROR = -1;
const struct date_format_day_month_s DAY_MONTH_ERROR = {DAY_ERROR, MONTH_ERROR};

const struct date_format_day_month_s day_nr_to_day_month[YEAR_TYPE_MAX][] =
{
	{
		{1, MONTH_JAN},
		{2, MONTH_JAN},
		...
		{31, MONTH_JAN},
		{1, MONTH_FEB},
		...
		{28, MONTH_FEB},
		{1, MONTH_MAR},
		...
		{31, MONTH_DEC},
		DAY_MONTH_ERROR
	},
	
	{
		{1, MONTH_JAN},
		{2, MONTH_JAN},
		...
		{31, MONTH_JAN},
		{1, MONTH_FEB},
		...
		{29, MONTH_FEB},
		{1, MONTH_MAR},
		...
		{31, MONTH_DEC}
	},
};

Jeżeli chcemy wykonać konwersję, wystarczy wtedy wykonać prosty odczyt z tablicy:

const struct date_format_day_month_s day_month = day_nr_to_day_month[YEAR_TYPE_NORMAL][day_nr];

Konwersja dat to częste zadanie na rozmowach rekrutacyjnych do rozwiązania przy tablicy, bo pokazuje jak kandydat ogarnia ify. Lookup table mogą Wam tutaj oszczędzić dużo trudu. Oczywiście pod warunkiem, że nie będziecie musieli wypisać ręcznie wszystkich wartości tablicy 😀

Kwestie implementacyjne

Lookup Table w większości przypadków powinniśmy implementować jako tablice const, żeby obronić się przed przypadkowym nadpisaniem. Zwyklepowinniśmy przechowywać takie tablice w pamięci nieulotnej. Na niektórych procesorach i kompilatorach musimy w tym celu dodać przy deklaracji jakiś specjalny atrybut jak np. PROGMEM w AVR.

Do generowania LUT warto wykorzystywać automatyczne skrypty np. napisane w Pythonie. W tym celu najpierw robimy ręcznie prototyp, żeby wybrać odpowiednią strukturę danych, a potem generujemy dane automatycznie. Dzięki temu oszczędzamy wiele czasu podczas edycji i uodporniamy się na błędy copy/paste.

Czasami potrzebujemy większej elastyczności i chcemy generować LUT w runtime. Możemy wtedy uzależnić generowane dane od jakiś danych podawanych przez użytkownika. Obliczanie elementów tablicy podczas działania programu nosi nazwę Memoization. Technika ta jest wykorzystywana np. do rozwiązywania problemów programowania dynamicznego. Warto po wypełnieniu takiej tablicy przekazać ją do procedur obsługujących dostęp jako const, żeby obronić się przed próbami zapisu. Niestety w przypadku dangling pointera dane i tak zostaną nadpisane.

Tablice powinny być szczegółem implementacyjnym opakowanym w odpowiednie API. Na zewnątrz powinniśmy udostępniać funkcje zupełnie nie zdradzające istnienia pod spodem tablicy. Dzięki temu mamy dowolność późniejszej zmiany implementacji.

Na nowoczesnych procesorach o częstotliwościach taktowania rzędu GHz dostęp do pamięci jest dużo wolniejszy niż wykonywanie instrukcji. Dlatego wykorzystuje się cache. Na takim procesorze może okazać się, że nawet skomplikowane obliczenia mogą być szybsze niż prosty odczyt z tablicy ze względu na możliwy cache miss. Dlatego jak w przypadku każdej optymalizacji musimy mierzyć czasy i podejmować decyzje w oparciu o twarde dane, a nie dlatego, że coś nam się wydaje.

Podsumowanie

Lookup Table to prosta w użyciu technika mogąca dać wielkie korzyści. Zarówno pod względem optymalizacji, jak i czytelności kodu. Niestety zwykle jej nie używamy. I problemem nie jest tu brak wiedzy. Po prostu jako programiści mamy nawyk rozwiązywania problemów za pomocą algorytmów i często nawet nie pomyślimy, że zamiast tego możemy po prostu zapisać wszystkie możliwe wyniki do tablicy. Oczywiście nic nie stoi na przeszkodzie, żeby uprzednio napisaną sekwencję ifów zrefaktorować do Lookup Table, kiedy już dochodzimy do problemów z czytelnością.

W następnym wpisie zajmę się tablicami indeksowanymi i hashowaniem. W planie są jeszcze maszyny stanu i tablice wskaźników na funkcje. Jeżeli chcecie przeczytać o jakiś innych zastosowaniach tablic, dajcie znać w komentarzach.

Dodatkowe materiały

Efficient C tips – użycie LUT

Zastosowania tablic w C - Nawigacja