Список как структура для хранения
данных известна достаточно широко. Фактически, наверняка в любом курсе
программирования ее изучают в том или ином виде. Но то, что обычно усваивает
студент (читать: "будущий программист") заключается примерно в следующем:
Списки организуются на динамической
памяти. Динамическая память, по мнению студента, это то, что можно получить при
помощи операторов new и удалить dispose.
Списки организуются при помощи
одного указателя на голову списка и, включенных в каждый элемент, указателей на
следующий элемент списка. Точнее, может присутствовать указатель и на предыдущий
элемент, а также указатель на хвост списка, это не суть важно.
Кроме этого, средний студент часто
путает список с очередью: все дело в том, что обычно на лабораторных работах
дается задание реализовать очередь, выбрав для ее внутреннего устройства список.
На самом деле, очередь это "нечто", что позволяет поместить туда элемент и
получить его согласно правилу FIFO ("First In, First Out" --- "Первый вошел,
первый вышел").
Тем не менее, я не хотел обижать
студентов, совсем нет. Просто очень часто, если практически не постоянно можно
увидеть один и тот же подход: организацию списков при помощи указателей.
Проблема заключается в том, что такая реализация списков не единственна и
достаточно часто не эффективна.
Допустим, программист реализует
некую структуру данных, основываясь на хеш-таблице, при этом коллизии решаются
списками элементов. Что может сделать программист, имеющий стереотипы наподобие
предыдущих? Что-нибудь в духе:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
struct hash_list
{
int key;
hash_list* next;
};
#define HASH_TABLE_SIZE 511
hash_list*
hash[HASH_TABLE_SIZE];
#define COUNT 1000000
struct {
unsigned int iterations;
} stat;
int main()
{
unsigned int i, j;
int k;
hash_list* ptr, *prev_ptr;
bzero((char*)hash,
sizeof(hash));
bzero((char*)&stat,
sizeof(stat));
srandom(time(NULL));
for(i = 0; i < COUNT; i++)
{
k = random() & 8191;
prev_ptr = NULL;
for(ptr = hash[k%HASH_TABLE_SIZE];
ptr && ptr->key != k;
prev_ptr = ptr, ptr = ptr->next,
stat.iterations++)
;
if(!ptr)
{
if(prev_ptr)
{
prev_ptr->next =
(hash_list*)calloc(1, sizeof(hash_list));
prev_ptr->next->key = k;
}
else
{
hash[k%HASH_TABLE_SIZE] =
(hash_list*)calloc(1, sizeof(hash_list));
hash[k%HASH_TABLE_SIZE]->key =
k;
}
}
}
printf("Iterations: %u\n",
stat.iterations);
}
Что же тут неправильного? Ничего.
Все сделано, вроде бы, достаточно логично. Тем не менее, показательно сделать
несколько запусков и полюбоваться результатами (для измерения затраченного
времени буду использовать команду bash time):
alk:~$ g++ -O5 t1.cpp -o t1
alk:~$ time t1
Iterations: 7485181
real 0m0.559s
user 0m0.549s
sys 0m0.001s
alk:~$ time t1
Iterations: 7485586
real 0m0.556s
user 0m0.555s
sys 0m0.001s
alk:~$ time t1
Iterations: 7486098
real 0m0.558s
user 0m0.549s
sys 0m0.001s
alk:~$ time t1
Iterations: 7480581
real 0m0.556s
user 0m0.548s
sys 0m0.000s
На самом деле, единственное что
можно поставить в упрек написанной выше программе, это расход на каждый элемент
(целое число) два раза больше оперативной памяти, чем надо --- еще столько же
тратится на указатель для организации списка. Несложно придумать реализацию
подобного списка на массиве, когда указатели не нужны:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
struct hash_item
{
int* keys;
size_t alloc;
size_t used;
};
#define HASH_TABLE_SIZE 511
#define HASH_ALLOC_DELTA 16
hash_item hash[HASH_TABLE_SIZE];
#define COUNT 1000000
struct {
unsigned int iterations;
} stat;
int main()
{
unsigned int i, j;
int k;
hash_item* ptr;
bzero((char*)hash,
sizeof(hash));
bzero((char*)&stat,
sizeof(stat));
srandom(time(NULL));
for(i = 0; i < COUNT; i++)
{
k = random() & 8191;
ptr = hash +
(k%HASH_TABLE_SIZE);
for(j = 0; j < ptr->used
&& ptr->keys[j] != k;
j++, stat.iterations++)
;
if(j >= ptr->used)
{
if(ptr->used ==
ptr->alloc)
{
int* temp = ptr->keys;
ptr->keys =
(int*)calloc(ptr->alloc += HASH_ALLOC_DELTA,
sizeof(int));
if(ptr->used)
{
memcpy(ptr->keys, temp,
ptr->used*sizeof(int));
free(temp);
}
}
ptr->keys[ptr->used++] =
k;
}
}
printf("Iterations: %u\n",
stat.iterations);
}
Выглядит на первый взгляд несколько
сомнительно: ведь преимущества обычных списков с указателями заключаются как раз
в том, что общее количество выделенных элементов будет равно нужному, а при
вставке нового элемента не требуется модификация всего остального списка. В
данном же случае, количество выделенных элементов, размер которых, правда,
меньше предыдущего в два раза, всегда кратно 16, а изменение списка влечет за
собой копирование всех данных из старой области памяти в новую.
Тем не менее, надо попробовать еще
раз запустить тест:
alk:~$ g++ -O5 t2.cpp -o t2
alk:~$ time t2
Iterations: 7478165
real 0m0.296s
user 0m0.296s
sys 0m0.000s
alk:~$ time t2
Iterations: 7477196
real 0m0.296s
user 0m0.296s
sys 0m0.000s
alk:~$ time t2
Iterations: 7489060
real 0m0.296s
user 0m0.295s
sys 0m0.000s
alk:~$ time t2
Iterations: 7492167
real 0m0.298s
user 0m0.282s
sys 0m0.008s
Если вас не удивили полученные
числа, то читать дальше вам будет совершенно неинтересно.
Стоит отметить, что общее количество
сравнений практически одинаково в обоих случаях. Разница в затраченном времени
между вторым и первым вариантом программы достаточно просто объяснима, для этого
достаточно представлять себе в общих чертах устройство современных
микропроцессоров.
Все дело в том, что память не
является чем-то однородным, более того, память образует иерархию по своей
скорости, например: регистры процессора, кеш первого уровня, кеш второго уровня,
оперативная память, жесткие диски... несмотря на то, что каждый "вид" памяти
предназначен, по сути, для одного и того же --- хранения данных --- скорость
доступа может сильно отличаться.
Когда процессор желает что-то
прочитать из оперативной памяти, эти данные "оседают" в кешах, доступ к которым
быстрее, и если через некоторое время (пока запись еще не была удалена из кешей)
процессор вновь обратится к тому же адресу, что и раньше, то обращения к
относительно медленной оперативной памяти не будет. Кроме того, кеш разбит на
области фиксированного размера (линии, в случае обычного Пентиума --- 32 байта),
и именно такими блоками происходит чтение данных из оперативной памяти. Таким
образом, если, как во втором случае, происходит чтение последовательного массива
целых чисел, то считывая один элемент, в кеш попадут как минимум 8 элементов
этого массива и все они больше не будут требовать обращений к оперативной памяти
в ближайшее время.
В случае же "с указателями",
невозможно предсказать какой элемент будет следующим в списке, потому что он
зависит от содержимого внутри прочитанной области данных (указателя) и, скорее
всего, следующий элемент не попадет в кеш. Поэтому итерация по списку будет
требовать еще столько операции чтения из оперативной памяти, сколько будет в
списке элементов.
Кроме того, современные умные
микропроцессоры, или не менее умные оптимизаторы, умеют делать предварительное
чтение данных в кеш. То есть, если читается блок в кеш, то пока процессор с ним
работает, можно прочитать в кеш следующий блок памяти в расчете на
последовательный доступ к данным (prefetch). Поэтому скорость последовательного
доступа к элементам массива будет выше, чем доступ к элементам "списка с
указателями" даже когда размер структур более размера целого числа.
Кстати сказать, в таких случаях
выгодно выравнивать размер структур по размеру кешлайнов, потому что чтение
одного кешлайна из оперативной памяти тоже операция неоднородная и начало
кешлайна появится в кеше быстрее, чем окончание, на чем тоже можно "сыграть".
Резюме
Таким образом, процессор всегда
рассчитывает на последовательный доступ к данным и использование этого факта
может сильно ускорить работу программы. Это относится не только к организации
списков на массивах (не в случае, когда указатели на следующий элемент
заменяются индексами внутри массива, а когда положение элемента в списке
определяется его индексом в массиве), но и, например, к обработке двумерных
массивов (значительно выгоднее читать массив по возрастанию реальных адресов
ячеек).
|