Файл code.c содержит решение задачи на языке Си.
В программе реализованы:
- Структура container - для удобного хранения массивов и их длины
- Функция для ввода массива из файла
void array_input(struct container *array, char *file_name);
- Функция для вывода массива из файла
void array_output(struct container *array, char *file_name);
- Функция для формирования нового массива из положительных чисел заданного массива
struct container construct_new_array(struct container *array);
- Функция для генерации массива на основе рандома
void random_array(struct container *array, size_t size)
- Функция для освобождения динамической памяти в массивах (container)
void free_memory(struct container *array)
Память для массивов выделяется динамически. Если не получилось выделить достаточное количество памяти для хранения какого-либо из массивов, то программа выводит сообщение об ошибке и завершает свое выполнение.
Для получения исполняемого файла в терминале выполняем команду:
gcc code.c -o code
Передача аргументов в программу осуществляется через командную строку. Для корректной работы программы необходимо передать имя файла с входными данными в качестве первого аргумента, а также имя файла для вывода данных в качестве второго аргумента.
Пример запуска исполняемого файла:
./code input.txt output.txt
В программе предоставлена опция сгенерировать входной массив, не считывая его из входного файла. Для этого надо прописать опцию --rand и следом за ней указать размер генерируемого массива. Если размер массива не указан, то размер генерируемого массива равен 1000 по умолчанию.
Сгенерированный массив выводится в файл, указанный в качестве файла с входными данными, то есть указанный в качестве первого аргумента при запуске программы (для того, чтобы у пользователя был доступ к сгенерированному массиву и для генерации рандомных тестов, что расширяет возможности тестирования).
Пример запуска программы с генерацией рандомного массива:
./code input.txt output.txt --rand
В данном случае программа сгенерирует массив размером 1000 и выведет его в input.txt. В файл output.txt будет выведен массив, состоящий из положительных чисел сгенерированного массива.
./code input.txt output.txt --rand 200
В данном случае программа сгенерирует массив размером 200 и выведет его в input.txt. В файл output.txt будет выведен массив, состоящий из положительных чисел сгенерированного массива.
Также предусмотрена возможность замера времени исполнения той части программы, которая выполняет вычисления (имеется в виду та часть кода, которая генерирует массив B из положительных чисел массива A). При замере времени этот блок зацикливается 500 раз, чтобы сделать разницу во времени нагляднее.
Для замера времени нужно при запуске программы добавить опцию --time. Результат замера времени будет выведен в консоль.
Пример запуска программы с замером времени:
./code input.txt output.txt --time
Рандомную генерацию массива и замеры времени можно совмещать:
./code input.txt output.txt --rand 5000 --time
С помощью gcc получим программу на языке ассемблера из нашего решения на языке Си. Для этого введем в терминал следующую команду:
gcc -O0 -Wall -masm=intel -S -fno-asynchronous-unwind-tables -fcf-protection=none code.c -o code.s
За счет использования вышеперечисленных аргументов командной строки наша программа станет более компактной, так как будут убраны лишние макросы.
В файле code.s содержится программа на языке ассемблера, полученная с помощью команды, приведенной выше, с комментариями, поясняющими эквивалентное представление кода в программе на языке Си (code.c), а также передачу фактических параметров и перенос возвращаемого результата при вызове функций.
Для получения исполняемого файла из ассемблерной программы необходимо выполнить в терминале команду.
gcc code.s -o asm_code
Исполняемый файл из ассемблерной программы запускается точно так же, как и исполняемый файл, полученный из программы на Си. Более подробная инфорация о формате команды для запуска программы содержится в разделе "Запуск исполняемого файла".
В папке refactored содержатся ассемблерные файлы, полученные после рефакторинга ассемблерной программы за счет максимального использования регистров процессора (с комментариями о данных, которые хранятся в регистрах).
При рефакторинге были замечены следующие стандартные ситуации с неэффективным использованием регистров:
- При передаче аргументов в функцию аргументы сначала рассчитываются на регистрах rax, rdx, а затем уже передаются в регистры rdi, rsi. Удобней сразу делать все необходимые вычисления на регистрах rdi, rsi.
Пример:
mov rdx, QWORD PTR -96[rbp] # rdx = output
lea rax, -32[rbp] # rax = &b
mov rsi, rdx
mov rdi, rax
call array_output # вызов функции
Рефакторинг:
mov rsi, QWORD PTR -96[rbp] # rsi = output
lea rdi, -32[rbp] # rdi = &b
call array_output # вызов функции
- Когда регистр используется для вспомогательных вычислений, каждый раз это вспомогательное значение рассчитывается заново, хотя иногда его можно переиспользовать и не считать заново. Пример:
mov rax, QWORD PTR -24[rbp] # rax = array
mov QWORD PTR 8[rax], 20 # array->capacity = 20
mov rax, QWORD PTR -24[rbp]
mov QWORD PTR [rax], 0 # array->len = 0
Рефакторинг:
mov rax, QWORD PTR -24[rbp] # rax = array
mov QWORD PTR 8[rax], 20 # array->capacity = 20
mov QWORD PTR [rax], 0 # array->len = 0
- Локальные перемнные хранятся на стеке, даже если их спокойно можно было бы хранить в регистре процессора.
При рефакторинге программа была разбита на две единицы компиляции:
- input_output.s, в которой находятся функции ввода и вывода массивов из файлов
- main.s, в которой находится все остальное
Для получения исполняемого файла необходимо запустить команду
gcc input_output.s main.s -o optimized
Все тесты лежат в папке testing/tests
Результаты тестирования программы на СИ лежат в папке testing/results/c
Результаты тестирования программы на ассемблере (code.s) лежат в папке testing/results/asm
Результаты тестирования оптимизированной программы на ассемблере лежат в папке testing/results/optimized
В папке testing также находятся два скрипта на питоне, которые автоматизируют создание тестов и тестирования
Получив исполняемый файл asm_code из программы на ассемблере, созданной комплилятором, мы три раза (для статистики) прогоним его следующим тестом:
./asm_code input.txt output.txt --rand 1000000 --time
Получились следующие результаты:
-
Process time:2.718014 seconds
-
Process time:2.613697 seconds
-
Process time:2.599745 seconds
В среднем, тест на массив размером 10^6 уходит 2.64 секунды (напомним, что программа повторяется 500 раз)
Повторим этот же эксперимент, но с исполняемым файлом из модифицированной ассемблерной программы.
./optimized ../input.txt ../output.txt --rand 1000000 --time
Получились следующие результаты:
- Process time:1.837195 seconds
- Process time:1.768235 seconds
- Process time:1.764434 seconds
Итого, теперь среднее значение составляет 1.79 секунд.