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

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

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

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

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

** На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Ваше сообщение отправлено.

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


Если вы так и не получили ответ, пожалуйста, проверьте папку
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 оказался внимательнее, чем три с половиной программиста

Дата: 22 Окт 2018

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

PVS-Studio, как и другие статические анализаторы кода, часто выдаёт ложные срабатывания. Но не стоит спешить считать странные срабатывания ложными. Это короткая история о том, как PVS-Studio вновь ок…
Характеристики анализатора PVS-Studio на примере EFL Core Libraries, 10-15% ложных срабатываний

Дата: 31 Июл 2017

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

После большой статьи про проверку операционной системы Tizen мне было задано много вопросов о проценте ложных срабатываний и о плотности ошибок (сколько ошибок PVS-Studio выявляет на 1000 строк кода)…
PVS-Studio ROI

Дата: 30 Янв 2019

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

Время от времени нам задают вопрос, какую пользу в денежном эквиваленте получит компания от использования анализатора PVS-Studio. Мы решили оформить ответ в виде статьи и привести таблицы, которые по…
Любите статический анализ кода!

Дата: 16 Окт 2017

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

Я в шоке от возможностей статического анализа кода, хотя сам участвую в разработке инструмента PVS-Studio. На днях я был искренне удивлён тому, что анализатор оказался умнее и внимательнее меня.
Как и почему статические анализаторы борются с ложными срабатываниями

Дата: 20 Мар 2017

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

В своей предыдущей статье я писал, что мне не нравится подход, при котором статические анализаторы кода оцениваются с помощью синтетических тестов. В статье приводился пример, воспринимаемый анализат…
Статический анализ как часть процесса разработки Unreal Engine

Дата: 27 Июн 2017

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

Проект Unreal Engine развивается - добавляется новый код и изменятся уже написанный. Неизбежное следствие развития проекта - появление в коде новых ошибок, которые желательно выявлять как можно раньш…
PVS-Studio для Java

Дата: 17 Янв 2019

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

В седьмой версии статического анализатора PVS-Studio мы добавили поддержку языка Java. Пришло время немного рассказать, как мы начинали делать поддержку языка Java, что у нас получилось и какие дальн…
Эффект последней строки

Дата: 31 Май 2014

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

Я изучил множество ошибок, возникающих в результате копирования кода. И утверждаю, что чаще всего ошибки допускают в последнем фрагменте однотипного кода. Ранее я не встречал в книгах описания этого …
Главный вопрос программирования, рефакторинга и всего такого

Дата: 14 Апр 2016

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

Вы угадали, ответ - "42". Здесь приводится 42 рекомендации по программированию, которые помогут избежать множества ошибок, сэкономить время и нервы. Автором рекомендаций выступает Андрей Карпов - тех…
Бесплатный PVS-Studio для тех, кто развивает открытые проекты

Дата: 22 Дек 2018

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

В канун празднования нового 2019 года команда PVS-Studio решила сделать приятный подарок всем контрибьюторам open-source проектов, хостящихся на GitHub, GitLab или Bitbucket. Им предоставляется возмо…

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

Следующие комментарии

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