Оптимизация процесса тестирования по С с использованием эвристического анализа тестового покрытия кода (1187409), страница 3
Текст из файла (страница 3)
При внесении изменений в одну часть продуктаразработчик предполагает, что благодаря системе интерфейсов иразделению кода, а также опираясь на доказанную предыдущей тестовойитерациейвалидность кода, он может с высокой вероятностьюпротестировать их валидность запустив лишь соответствующую им частьтестов. Данный подход существенно ускоряет разработку, однаковероятность валидной проверки кода теперь опирается не только накачество тестов, но и на знание конкретным человеком набора тестов,требуемых к запуску. Выигрыш времени также варьируется от того, вкакой части были внесены изменения - в случае правки редкоиспользуемого периферийного метода, для проверки может бытьдостаточно менее десяти тестов, с учетом только что написанных. Однакоизменения в сильно связном коде могут потребовать запуска большинстватестов для подтверждения валидности.3.3.
Причина выбора пути оптимизацииВ случае работы с крупным проектом, в котором задействовано множествоперсонала, серьезное вмешательство в код связано с огромными рисками.Команда разработки, фактически, останавливает работу над новымфункционаломинепривноситсущественногоулучшенияпроизводительности - а это именно то, что требуется продукту, чтобыпродолжать жить. Даже если менеджмент готов пойти на подобный риск,персонал, зачастую, оказывается не готов к подобным изменениям. При16рефакторинге проявляются скрытые проблемы и противоречия втребованиях, к которым клиенты уже привыкли как к данности неожидают их переработки.
В итоге старые проблемы вынужденнопереходят в новый код, забирая с собой, в том числе, и громоздкие тесты.Конечно же, описанные выше проблемы ни в коем случае не ставят крестна идее рефакторинга и улучшении кодовой базы. Они лишь призваныпоказать, что небольшой группе разработчиков не под силу решитьпроблему оптимизации тестирования путем работы с самим кодом.Именно поэтому была выбрана стратегия, подразумевающая полноеотсутствие взаимодействия с кодовой базой. Будет произведена оценкасуществующего набора тестов, какие части кода они затрагивают, а вдальнейшем, без участия человека, будет запускаться оптимальное ихподмножество. Непосредственно часть, затрагивающая проект будетсведена к минимуму на финальном этапе встраивания оптимизации всистему контроля внесения изменений в код.174.
Автоматизация процесса тестированияПроцесс тестирования программного обеспечения, при котором основныефункции и шаги теста, такие как запуск, инициализация, выполнение,анализ и выдача результата, производятся автоматически с помощьюинструментов для автоматизированного тестирования. В свою очередь,инструмент для автоматизированного тестирования — это программноеобеспечение, посредством которого осуществляется создание, отладка,выполнение и анализ результатов прогона тест-скриптов (Test Scripts —это наборы инструкций для автоматической проверки определенной частипрограммного обеспечения).
Рассмотрим популярный инструментарийtravis-ci. Проект непрерывной интеграции в нем является конфигурациейдля сервера-исполнителя. По требованию системы создается задача натестирование, которая помещается в очередь. При обработке задачи серверприменяет относящуюся к ней конфигурацию, после чего запускаеттестовые скрипты и, в зависимости от результата и настроек системы,производит различные действия.
Например, провал сборки при наличииошибок в тестах и т.п.Такие системы внедряются для того, чтобы утилизировать тестынепосредственно в процессе разработки. Рассмотрим в качестве примерапопулярный сервис github, предоставляющий интерфейс над VCS git.Пользователь может настроить свой репозиторий таким образом, чтобыпри запросе на объединение ветвей (pull request) автоматическизапускались тесты, чтобы удостовериться, что ошибки не попадут в[14]основную ветвь, а также что общий процент покрытия кода не снизился.185. Исследуемый метод оптимизации5.1.
Постановка задачиНа вход дается результат работы утилиты анализа покрытия в форматеxml, и, опционально, внесенные изменения. Необходимо разработатьалгоритм, который позволит максимально проверить код за отведенноеему время, при этом результат работы алгоритма должен бытьоптимизирован. Информация о тестах и их соответствии коду хранитсяотдельно в виде метаданных о текущем состоянии кодовой базы.Метаданные должны итеративно накапливаться и попадать на вход приследующем запуске утилиты.Применение оптимизации должнопозволить проводить полный запуск тестов с меньшей частотой и длябольшего количества изменений за раз.5.2. Абстрактный методДля начала, распишем все возможные варианты работы алгоритмаоптимизации в зависимости от входных данных.Что может произойти с кодом с точки зрения алгоритма?Во-первых, код и тесты могли остаться без изменений.
В таком случаенеобходимо вычислить и запустить набор наиболее оптимальных тестов,способных покрыть за отведенное время наибольшее количество строккода.Во-вторых, могли быть внесены изменения только в код. В таком случаенеобходимо в первую очередь протестировать их, для чего требуетсяопределить, какими тестами, вероятно, покрывается данный участок.Добавим их в обязательные для запуска, после чего выберем изоставшихся наиболее оптимальные.В-третьих, могли быть внесены изменения в сами тесты. Запустимизмененные тесты, чтобы получить новую статистику покрытия,19исключим их из рассмотрения, после чего переходим к проверке,описанной выше.Из описанной схемы видно, что необходимо конкретизировать дваалгоритма - выбор “дорогих” тестов и выбор тестов, покрывающихизменения. Необходимо также уточнить некоторые прикладные моменты.5.2.1.
Провал тестаТесты создаются для того, чтобы знать, что пошло не так в программе.Естественно, они будут проваливаться. В таком случае результатыпокрытия данного теста учитываться в будущем не должны.5.2.2. Типы изменений кодаСуществует три типа изменений - модификация строк, удаление строк идобавление строк, и на каждые тип алгоритм должен реагироватьпо-своему. Данные случаи будут рассмотрены позднее.205.2.3. Типы изменений тестовВ данном случае все намного проще. В случае удаления теста мы такжеудаляем данные о нем. Случаи модификации и добавления тестов неотличаются для алгоритма между собой - в обоих вариантах необходимоих запустить.5.3. Алгоритм выбора “дорогих” тестовДанный алгоритм работает только с тестами и информацией об ихпокрытии и времени работы. Изменения не учитываются.5.3.1.
Постановка задачиДан набор тестов { ti , ci }, а также T - время, отведенное на тестирование.Необходимо выбрать набор тестов таким образом, чтобы их суммарноепокрытие ∩ci было максимальным, а общее время исполнения быломеньше, чем T .5.3.2. РешениеВ первую очередь исключим тесты, время работы которых больше, чем T .К сожалению, насколько бы тест ни был эффективен, мы не можемзапустить его, если он не укладывается в базовые требования по времени.Введем функцию веса теста - m(t, c) = c/t . Отсортируем тесты поубыванию значения соответствующей им функции. Теперь необходимоизбавиться от пересечения покрытий.Будем последовательно брать наиболее эффективные тесты и отсекать ихчасти покрытия от всех менее эффективных.
В итоге каждой части кодабудет соответствовать тот тест, который проходит ее наиболее быстро.Визуально этот способ можно продемонстрировать примером ниже. Какмы видим, первый тест, будучи наиболее быстрым, вытеснил собой тесты2 и 3.21#include<stdio.h>123-->1intmain(){doublenumber;printf("Enter a number: ");scanf("%lf",&number);if(number <=0.0){if(number ==0.0)printf("You entered 0.");elseprintf("You entered a negative number.");}elseprintf("You entered a positive number.");3return0;}123-->1231-->1123-->1123-->1123-->121-->11 -->12 -->23 -->123-->1После данных манипуляций нам потребуется обновленный критерийвыбора.
Формально задача теперь записывается так.T , {ti , ci }1N →{k 1 , ..., k n } : max∑{k 1 , ..., k n }где ci : c1 = c1 , ck = ckci ,∑{k 1 , ..., k n }ti ≤T ,k−1∩∩1 ciДанная задача является примером классической “Задачи о рюкзаке”(Knapsack Problem) и решается методом динамического программированияза O(N ×T ) .
В данном случае ценой для предметов будут служитьуникальные покрытия, а весом - время исполнения.5.3.3. Метод динамического программирования[22]Разберем подробнее решение задачи о рюкзаке.Пусть A(k, s) естьмаксимальная стоимость предметов, которых можно уложить в рюкзак22вместимости s , если можно использовать только первые k предметов, тоесть {n1 , ..., nk } , назовем этот набор допустимых предметов для A(k, s) .A(k, 0) = 0A(0, s) = 0Найдем A(k, s) . Возможны 2 варианта:1. Если предметkне попал в рюкзак.
ТогдаA(k, s)равномаксимальной стоимости рюкзака с такой же вместимостью инаборомдопустимыхпредметов{n1 , ..., nk−1 } ,тоестьA(k, s) = A(k − 1, s)2. Еслиkпопал в рюкзак. Тогда A(k, s) равно максимальнойстоимости рюкзака, где вес s уменьшаем на вес k − ого предмета инабор допустимых предметов {n1 , ..., nk−1 } плюс стоимость k , тоесть A(k − 1, s − wk ) + pkТо есть: A(k, s) = max( A(k − 1, s), A(k − 1, s − wk ) + pk )Стоимость искомого набора равна A(N , W ) , так как нужно найтимаксимальную стоимость рюкзака, где все предметы допустимы ивместимость рюкзака W .Восстановим набор предметов, входящих в рюкзак.
Будем определять,входит ли ni предмет в искомый набор. Начинаем с элемента A(i, W ) , гдеi = N w = W ,. Для этого сравниваем A(i, w) со следующими значениями:1. Максимальная стоимость рюкзака с такой же вместимостью инабором допустимых предметов {n1 , ..., ni−1 } , то есть A(i − 1, w)2. Максимальная стоимость рюкзака с вместимостью на wi меньше инабором допустимых предметов {n1 , ..., ni−1 } плюс стоимость, тоесть A(i − 1, w − wi ) + pi23Заметим, что при построении A мы выбирали максимум из этих значенийи записывали в A(i, w) .
Тогда будем сравнивать A(i, w) c A(i − 1, w) , еслиравны, тогда ni не входит в искомый набор, иначе входит.5.3.4. Реализация метода динамического программированияБудем считать, что все веса нормализованы.defknapsack_solution(N ,W,w):A=[[0for_ inrange(W )]for_ inrange(N)]fork inrange(N):fors inrange(W):ifs >=w[k]:A[k][s]=max(A[k-1][s],A[k-1][s-w[k]]+p[k])else:A[k][s]=A[k-1][s]answer =list()defget_best(k,s):ifA[k][s]==0:returnifA[k-1][s]==A[k][s]:get_best(k-1,s)else:get_best(k-1,s -w[k])answer.append(k)get_best(N,W)returnanswer5.4.
Алгоритм для работы с изменениямиТеперь необходимо рассмотреть алгоритм, который был бы применим дляработы с изменениями в коде. В первую очередь заметим, что никакиеоптимизации не будут иметь смысла, если непосредственно изменения небудут протестированы. Однако мы вынуждены работать с ограничениемпо времени. Таким образом, не всегда получится полностью проверить всевозможные ошибки, особенно с учетом того, что тесты не являютсяистиной в последней инстанции.24Алгоритм будет простым - определим, к каким областям покрытияотносятся изменения, после чего, используя описанный выше алгоритм,выберем столько затронутых тестов, сколько получится запустить, непревышая данный лимит времени.5.4.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
