Неэффективность last() в реальном мире

09 Фев 2009

Автор: Андрей Карпов

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

Началось все с жалобы, что статический анализатор Viva64 зависает при анализе одного из проектов, а вернее на одном из файлов проекта. Анализ показал, что на самом деле не зависает, а очень даже усердно работает. Очень усердно и очень долго. Я думаю даже он успешно его сможет проанализировать, часов так через 5-10 :). Но это стало ясно уже потом и естественно такое поведение можно считать ошибкой.

Честно говоря, в начале меня подобное поведение сильно удивило. Анализатор Viva64 работает весьма быстро. И среднее время анализа одного файла занимает всего несколько секунд. И время его работы значительно меньше, чем тратится на предварительное препроцессирование файлов. Препроцессирование выполняется за счет компилятора Visual C++ и здесь мы убыстрить процесс пока никак не можем. Поэтому, грубо говоря, время проверки проекта близко к времени препроцессирования всех файлов. И вдруг обнаруживается такая огромная неэффективность в алгоритме анализа!

Расследования показали, что зависание происходит на файле, который содержит некие ресурсы из библиотеки Qt. А именно массив "static const unsigned char qt_resource_data[]", размером... размер массива не знаю, но знаю что это самый большой массив, который я видел в своей жизни. Выглядит он так:

static const unsigned char qt_resource_data[] = {
  0x0,0x0,0x0,0xc5,
  0x51,
  0x46,0x72,0x61,0x6d,0x65,0x20,0x7b,
  0xd,0xa,0x20,0x20,0x20,0x20,0x6d,0x69,0x6e,
  0x2d,0x77,0x69,0x64,0x74,0x68,0x3a,0x20,
  0x36,0x70,0x78,0x3b,0xd,0xa,0x20,0x20,
  0x20,0x20,0x6d,0x69,0x6e,0x2d,0x68,0x65,
  0x69,0x67,0x68,0x74,0x3a,0x20,0x36,0x30,
  . . .

Занимает этот массив в файле около 9 мегабайт. Много, но это не повод анализатору так плохо себя вести.

Проблема оказалась в уже упомянутой функции last(). Анализатор Viva64 построен на библиотеке VivaCore. А VivaCore построена в свою очередь на библиотеке OpenC++, от которой она унаследовала представление данных в виде деревьев и списков. Кстати, обработка данных в OpenC++ (и VivaCore) весьма напоминает lisp программу. Имеется множество функций вида Eq, Car, Cdr, First, Rest, Second, Nth, List и так далее.

И есть функция last(), которая используется при создании списка элементов для инициализации массива. В псевдокоде это выглядит так:

while (еще есть элементы)
{
  Ptree *e = взять очередной элемент;
  Ptree *last = Last(eList);
  last->SetCdr(Cons(e, 0));
}

Общий смысл - берем очередной элемент массива и добавляем его в хвост списка. Чтобы найти хвост для простоты используется функцию last(). Автор OpenC++ явно не предполагал, что алгоритму будет подсунута инициализация массива из миллионов элементов. На маленьких массивах все замечательно, но время подобного алгоритма растет пропорционально квадрату количества элементов (а, если быть точным - треугольному числу: 0.5 * n * (n + 1) , где n - количество элементов).

Простейшая оптимизация, заключающаяся в хранении указателя на последний элемент списка, (что позволяет не вызывать функцию last()) сотворила буквально чудо. Обработка файла, которая ранее занимала больше 3 часов (больше 3 часов я ждать не вытерпел :), стала занимать несколько секунд.

Что сказать - будьте аккуратнее, прежде чем использовать функции подобные last(). Нельзя угадать, что захотят рано или поздно подсунуть вашему алгоритму. Удачи в оптимизации!