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

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

Бесплатная лицензия 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 вывод других инструментов?

Дата: 26 Май 2022

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

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

Дата: 24 Май 2022

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

Количество багов в нашей коллекции перевалило за отметку 15000. Именно такое количество ошибок обнаружила команда PVS-Studio в различных открытых проектах. Особенно интересно, что это всего лишь побо…
Комментарии в коде как вид искусства

Дата: 04 Май 2022

Автор: Сергей Хренов

Приветствую всех программистов, а также сочувствующих. Кто из нас хотя бы раз в жизни не оставлял комментарии в коде? Был ли это ваш код, а может, чужой? Что за комментарии вы написали: полезные или …
Visual Studio 2022 стильно и свежо. История о её поддержке в PVS-Studio

Дата: 15 Фев 2022

Автор: Николай Миронов

Кажется, анонс Visual Studio 2022 был только недавно, и вот она уже вышла. Это означало ровно одно – поддержать данную IDE нужно в ближайшем релизе PVS-Studio. О том, с какими сложностями пришлось ст…
Лучшие срабатывания статического анализатора

Дата: 29 Окт 2021

Автор: Максим Звягинцев

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

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

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