Rambler's Top100 Service калинин.ru / программирование / оптимизация /  << 08.08.01 >>

Списки и последовательный доступ

Список как структура для хранения данных известна достаточно широко. Фактически, наверняка в любом курсе программирования ее изучают в том или ином виде. Но то, что обычно усваивает студент (читать: "будущий программист") заключается примерно в следующем:

  • Списки организуются на динамической памяти. Динамическая память, по мнению студента, это то, что можно получить при помощи операторов 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). Поэтому скорость последовательного доступа к элементам массива будет выше, чем доступ к элементам "списка с указателями" даже когда размер структур более размера целого числа.

Кстати сказать, в таких случаях выгодно выравнивать размер структур по размеру кешлайнов, потому что чтение одного кешлайна из оперативной памяти тоже операция неоднородная и начало кешлайна появится в кеше быстрее, чем окончание, на чем тоже можно "сыграть".

Резюме

Таким образом, процессор всегда рассчитывает на последовательный доступ к данным и использование этого факта может сильно ускорить работу программы. Это относится не только к организации списков на массивах (не в случае, когда указатели на следующий элемент заменяются индексами внутри массива, а когда положение элемента в списке определяется его индексом в массиве), но и, например, к обработке двумерных массивов (значительно выгоднее читать массив по возрастанию реальных адресов ячеек).

PS

Кстати сказать, существуют эффективные вариации сортировки слиянием для данных, находящихся в оперативной памяти. Просто именно такой, достаточно простой способ сортировки, позволяет учитывать в алгоритме иерархичность оперативной памяти и легко распараллеливается на несколько процессоров.


Версия для печати


  Рядом в разделе:
Ассемблер x86 против C (22.06.01)
   Весь текст ниже взят из переписки с . Моего тут только несколько строчек, выделенных курсивом и резюме. Текст основан на трех...   >>>>
  Рядом по дате:
Сублимированное мясо (08.09.01)
   Всегда одна из самых бессмысленных тяжестей в снаряжении туристов это консервные банки от тушеного мяса. Честно говоря, если в области покупного...   >>>>
Новые технологии в рекламе (29.07.01)
   Как хорошо, что основной операционной системой, которой я пользуюсь, является малораспространенная среди российских интернетошатающихся FreeBSD. Как хорошо, что браузеры, которые я...   >>>>
  Содержание:
Заглавная страница
Мой блог
Мое резюме
Дайджест
Программирование
   C&C++
Сети
Unix
Алгоритмы
Оптимизация
Соревнования
Отвлеченно
XML
TeX
Просто так
Студенческое
Туризм
  Байки
Фотографии
Комментарии
   Книги
Web-ресурсы
Фильмы
Интернет
Программное обеспечение
Жизнь
Благодарности
Форум
Хронология
 
  В этом разделе:
Списки и последовательный доступ (08.08.01)
   Список как структура для хранения данных известна достаточно широко. Фактически, наверняка в любом курсе программирования ее изучают в том или ином...   >>>>
Ассемблер x86 против C (22.06.01)
   Весь текст ниже взят из переписки с . Моего тут только несколько строчек, выделенных курсивом и резюме. Текст основан на трех...   >>>>
Содержание раздела полностью...
   Примерно в тоже время
Сублимированное мясо (08.09.01)
   Всегда одна из самых бессмысленных тяжестей в снаряжении туристов это консервные банки от тушеного мяса. Честно говоря, если в области покупного...   >>>>
Новые технологии в рекламе (29.07.01)
   Как хорошо, что основной операционной системой, которой я пользуюсь, является малораспространенная среди российских интернетошатающихся FreeBSD. Как хорошо, что браузеры, которые я...   >>>>
Хронология полностью...
   Содержание
Заглавная страница
Мой блог
Мое резюме
Дайджест
Программирование
  C&C++
Сети
Unix
Алгоритмы
Оптимизация
Соревнования
Отвлеченно
XML
TeX
Туризм
  Байки
Фотографии
Комментарии
  Книги
Web-ресурсы
Фильмы
Интернет
Программное обеспечение
Жизнь
Студенческое
Просто так
Благодарности
Форум
Хронология
© 2000-2008, Andrey L. Kalinin
mailto:andrey@kalinin.ru
Rambler's Top100