Для получения триального ключа
заполните форму ниже
Team license
Enterprise license
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Запросите информацию о ценах
Новая лицензия
Продление лицензии
--Выберите валюту--
USD
EUR
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Бесплатная лицензия PVS-Studio для специалистов Microsoft MVP
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Для получения лицензии для вашего открытого
проекта заполните, пожалуйста, эту форму
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Мне интересно попробовать плагин на:
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Ваше сообщение отправлено.

Мы ответим вам на


Если вы так и не получили ответ, пожалуйста, проверьте папку
Spam/Junk и нажмите на письме кнопку "Не спам".
Так Вы не пропустите ответы от нашей команды.

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

Неэффективность 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(). Нельзя угадать, что захотят рано или поздно подсунуть вашему алгоритму. Удачи в оптимизации!

Популярные статьи по теме
PVS-Studio: 2 фишки для быстрого старта

Дата: 08 Дек 2022

Автор: Сергей Васильев

В этой заметке расскажу, как легко начать использовать PVS-Studio. Рассмотрим два сценария: когда вы пробуете анализатор впервые и когда внедряете его в проект.
Почему ты делаешь за меня мою работу? Типы людей, которые не пишут в поддержку

Дата: 06 Дек 2022

Автор: Алёна Фоканова

Привлекательное название статьи должно раскрывать то, что будет в ней. Так вот, работа специалистом поддержки клиентов подразумевает появление вопросов к пользователю. Иногда возникает как раз такой:…
Как Apple и другие крупные компании настиг программный баг

Дата: 09 Ноя 2022

Автор: Ульяна Гришина

Сегодня мы отобрали свежие случаи программных ошибок, чтобы вы могли немного отвлечься и, возможно, узнать что-то новенькое. Если вам интересно узнать, как программисту удалось сломать Интернет по вс…
Единороги компании PVS-Studio

Дата: 30 Авг 2022

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

Скорее всего вы перешли на эту статью, заинтересовавшись одним из наших рисунков единорогов. Приятно видеть ваш интерес. Сейчас мы расскажем, почему рисуем этих единорогов, что они означают и чем воо…
Обрабатывать ли в PVS-Studio вывод других инструментов?

Дата: 26 Май 2022

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

Анализатор PVS-Studio умеет "схлопывать" повторяющиеся предупреждения. Предоставляет возможность задать baseline, что позволяет легко внедрять статический анализ в legacy-проекты. Стоит ли предостави…

Комментарии (0)

Следующие комментарии
Unicorn with delicious cookie
Мы используем куки, чтобы пользоваться сайтом было удобно.
Хорошо