Размещено на http://www.allbest.ru/

УДК 004.9:681.3

Управляемый стек в программах на языке Си

Самохвалов А.Б.



Аннотация

программный фрейм язык код

Рассмотрена проблема обеспечения надёжности программного кода в отношении безопасности исключений и раннего выхода из процедур и фреймов, написанных на языке Си. Предложен способ реализации управляемого стека на языке Си и представлены результаты его тестирования. Для создания корректного, гибкого программного кода, надёжного управления ресурсами и обеспечения высокоуровневой программной логики разработка программ должна опираться на принцип симметрии. В языке C++ принцип симметрии обеспечивается детерминированным деструктором, а в языке Си это достигается путём применения идиомы (паттерна) управляемого стека. Благодаря управляемому стеку программы на Си становятся устойчивыми к раннему выходу из процедур и фреймов, в том числе, и по причине исключительных ситуаций. В предложенной реализации используется объектно-ориентированный подход и динамическая информация о типе. Результаты тестирования показывают возможность достижения высокой производительности программ на Си с применением управляемого стека. Исследование представляет интерес для разработки и рефакторинга программного кода на языке Си, а также и для других языков программирования.

Ключевые слова: С, C++, язык программирования, управляемый стек, ресурсы, симметрия, исключения, идиомы, паттерны.



Abstract

The problem of programming code reliability regarding exception safety and early procedure and frame exit in C language is considered. The way of managed stack implementation in C language and its testing results are presented. In order to provide correct, flexible programming code, reliable resource management and high-level logic procuring the software development should be based on the principle of symmetry. In C++ language the principle of symmetry is guaranteed by determinated destructor while in C language it is attained by the using of managed stack idiom (pattern). Due to managed stack the programs in C language become robust to early exit from procedures and frames, including by the cause of exceptions. The object-oriented approach and dynamic type information are used in proposed implementation. The testing results show the possibility to attain high performance of the programs in C with the usage of managed stack. The research would be interesting for program code development and refactoring not only in C language but also for other programming languages.

Keywords: C, C++, programming language, managed stack, resources, symmetry, exceptions, idiom, pattern.



Несмотря на то, что языки Си и C++ часто упоминают совместно (например, как “C/C++”), предоставляемые ими по умолчанию возможности и вытекающие из этого приёмы программирования кардинальным образом отличаются. Дело не только в том, что C++ - объектно-ориентированный, самое главное, что отличает C++ от языка Си и многих других языков программирования - это то, что в нём изначально, на уровне правил самого языка заложен принцип детерминированного деструктора. Детерминированный деструктор - это гарантия того, что для каждого объекта, созданного в стеке, будет вызван деструктор и только один раз при выходе из области видимости (фрейма стека), причём вызов деструкторов происходит в обратной последовательности по отношению к порядку создания объектов. Детерминированный деструктор является ничем иным, как проявлением принципа симметрии, его грамотное использование значительно повышает качество программного кода. Напротив, нарушение принципа симметрии в программировании делает программу громоздкой, запутанной, возрастает количество ошибок, что снижает надёжность программного обеспечения. Возникает вопрос, можно ли писать надёжные программы на языке Си в том же стиле, как это принято на языке C++, т.е. воспроизвести средствами языка Си детерминированный деструктор? Да, это возможно, но для этого нужно реализовать на языке Си идиому (паттерн) управляемого стека.

1. Принцип симметрии при разработке программного обеспечения

Симметрия или принцип баланса - один из важнейших принципов, лежащий в основе природных явлений, науки и искусства. В программировании симметрия проявляется как подчинённые действия. В общем случае каждому действию есть подчинённое ему - т.е. такое, которое обязательно должно быть выполнено после первого вне зависимости от пути выполнения программы. Если обозначать «открывающие» действия как X1, а подчинённые им как X2, то программу можно условно записать как:



A1

B1

C1

…

C2

B2

A2

Это и есть принцип симметрии в программировании. Всякое нарушение симметрии означает нарушение корректности работы программы, что приводит либо к нарушению целостности данных, либо к утечке ресурсов.

Устойчивость кода к раннему выходу - это важнейший показатель, обеспечивающий надёжность кода. Большинство языков программирования допускает ранний выход из процедур (оператор return) и из циклов (операторы break и continue). Организация кода должна гарантировать, что ранний выход не нарушит симметрию, т.е. все подчинённые действия будут выполнены. Для этого код разделяют на три части:

1. Инициализация переменных и получение ресурсов.

2. Работа с переменными и ресурсами.

3. Выполнение всех завершающих действий с переменными и освобождение ресурсов.

Объектно-ориентированный подход состоит в том, что инициализирующее действие находится в конструкторе объекта, а завершающее подчинённое - в деструкторе (идиома RAII в C++).

Безопасность исключений - это также проблема обеспечения симметрии программного кода при генерировании исключений [1, 2]. Исключение - это разновидность раннего выхода; в языках, поддерживающих исключения, всякий вызов функции или процедуры может привести к генерированию исключения, а, значит, к выходу из вызывающей процедуры и переходу в обработчик. Обеспечить вызов деструкторов при исключении можно только при наличии детерминированного деструктора (как в C++) или сборщика мусора (как в большинстве объектно-ориентированных языков). Однако, если сборщик мусора не гарантирует обратной последовательности вызова деструкторов для объектов, созданных в стеке, то он не обеспечивает симметрию, что требует дополнительных усилий по организации кода.

Фактичекски, требуется не просто сборщик, мусора, а управляемый стек.

Управляемый стек выполняет функции сборщика мусора, но не только: он также обеспечивает детерминированный порядок вызова деструкторов - в последовательности, обратной последовательности создания объектов (очередь FILO).

Для чего нужно реализовывать управляемый стек на языке Си? Для этого могут быть следующие причины:

- не для всех платформ имеется надёжный компилятор C++ и удобная среда разработки для него, что вынуждает применять язык Си вместо C++;

- работа с унаследованным кодом на Си;

- отработка приёмов применения управляемого стека для других языков (язык Си как средство универсального представления идиом и паттернов программирования).

2. Экспериментальная реализация управляемого стека на языке Си

Экспериментальная реализация управляемого стека на языке Си включает следующие основные понятия и элементы.

Под «классом» понимается структура данных и набор функций (процедур) для работы с ней. Отличие «класса» от просто структуры данных в том, что для класса обязательно выполнение определённых действий при инициализации (конструктор) и уничтожении (деструктор) объекта. Также определяются конструктор копирования и оператор присваивания, если для класса эти действия не запрещены. Таким образом, здесь применены те же принципы, что и в C++. Далее есть отличия, связанные с тем, что реализация выполняется на языке Си и в нём нет встроенной поддержки классов и автоматических переменных. Объекты классов находятся под управлением стека, иначе говоря, принадлежат управляемому стеку. Чуть ниже мы рассмотрим особенности его реализации.

Обсуждаемые далее примеры тестовых приложений можно получить по ссылке https://yadi.sk/d/OYul07FLxuqmT.

Динамическая информация о типе - обязательный элемент каждого объекта. Реализована динамическая информация аналогично реализации полиморфных классов на C++. Первым членом данных каждого объекта является указатель на статический константный блок памяти, содержащий информацию о типе - структуру TypeInfo. Эта структура включает следующие поля:

- размер объекта в байтах;

- указатель на функцию - конструктор (без дополнительных параметров, т.е. конструктор «по умолчанию») для объектов данного класса со следующий сигнатурой:

BOOL(*pfnConstructDefault_)(void* const pObject);

- указатель на функцию - конструктор копирования со следующей сигнатурой:

BOOL(*pfnConstructCopy_)(void* const pObject, const void* const pObject_Other);

- указатель на функцию - оператор присваивания:

BOOL(*pfnAssign_)(void* const pObject, const void* const pObject_Other);

- указатель на функцию - деструктор:

void(*pfnDestruct_)(void* const pObject);

Отметим, что конструкторы и оператор присваивания возвращают тип BOOL (TRUE, FALSE), т.е. программа должна быть способна корректно обработать ситуацию, когда вызов этих процедур заканчивается неуспешно, и продолжить своё выполнение. В отличие от них, деструктор возвращает тип void; соответственно, предполагается, что деструктор не может завершиться неуспешно; если в ходе выполнения деструктора обнаруживается, что он не может быть успешно завершён, то программа целиком должна быть завершена с сообщением об ошибке, поскольку либо состояние её данных далее некорректно, либо произошла утечка ресурса (то же правило действует в C++).

Использование структуры TypeInfo практически означает, что каждый класс имеет виртуальные конструктор, конструктор копирования, оператор присваивания и деструктор. В этом отличие от C++, где конструкторы не могут быть виртуальными. Виртуальные конструкторы означают, что здесь используется паттерн «фабрика классов (объектов)».

Реализация класса «строка» служит хорошей иллюстрацией класса, опирающегося на управляемый стек. Структура данных для объектов класса «строка» следующая:

typedef struct _StringA

{

const TypeInfo* pTypeInfo_; // указатель на статическую информацию о типе

char* pBuff_; // буфер для хранения символов строки, завершающийся `\0'

} StringA;

Для класса StringA предусматриваются конструктор по умолчанию:

BOOL StringA_Construct(StringA* const this)

{

this->pTypeInfo_ = &typeInfo_StringA; // статическая информация о типе

this->pBuff_ = NULL;

return TRUE;

}

Конструктор копирования (объект this создаётся как копия объекта other):

BOOL StringA_Assign_StringA(StringA* const this, const StringA* const other);

Аналогично - копирующее присваивание:

BOOL StringA_Assign_StringA(StringA* const this, const StringA* const other);

Деструктор:

void StringA_Destruct(StringA* const this)

{

free(this->pBuff_);

this->pBuff_ = NULL;

}

Статическая информация о типе представлена экземпляром структуры TypeInfo с именем typeInfo_StringA, единственным глобальным объектом для всех объектов класса StringA.

Инициализация статической информации о типе для класса StringA выполняется следующим образом с использованием перечисленных выше процедур:

void StringA_InitTypeInfo()

{

typeInfo_StringA.sizeBytes_ = sizeof(StringA);

typeInfo_StringA.pfnConstructDefault_ = StringA_Construct;

typeInfo_StringA.pfnConstructCopy_ = StringA_Construct_Copy;

typeInfo_StringA.pfnAssign_ = StringA_Assign_StringA;

typeInfo_StringA.pfnDestruct_ = StringA_Destruct;

}

Для единообразного получения информации о типе для класса StringA предусмотрена функция

const TypeInfo* StringA_GetTypeInfo()

{

return &typeInfo_StringA;

}

Аналогично классу StringA реализуются и другие классы, предназначенные для использования в управляемом стеке.

Реализация обобщённых коллекций, очевидно, также опирается на информацию о типе. Для этого в состав объекта «коллекция» дополнительно вводится указатель на структуру TypeInfo для хранимых элементов коллекции. Например, динамический массив (аналогичный классу vector стандартной библиотеки C++) представлен следующей структурой:

typedef struct _Vector

{

const TypeInfo* pTypeInfo_; // информация о типе для класса Vector

const TypeInfo* pTypeInfo_Elem_; // информация о типе для элементов вектора

BYTE* pBuff_; // буфер для размещения элементов

UINT totalBufferSizeBytes_; // полный размер буфера в байтах

UINT nElems_; /* кол-во элементов, находящихся в буфере (остальной объём резервируется */

} Vector;

Реализация управляемого стека выполнена следующим образом. В стек помещаются элементы трёх типов:

- маркер начала процедуры;

- маркер начала внутреннего фрейма;

- объект.

Соответственно, структура элемента стека:

typedef struct _StackM_Elem

{

eStackM_Elem_Type type_; // тип элемента (маркер, объект)

void* pObject_; // указатель на объект в динамич. памяти (NULL для маркеров)

} StackM_Elem;

Как видно из структуры StackM_Elem, память для объекта, принадлежащего управляемому стеку, выделяется в области динамической памяти (вызов malloc); в самом стеке хранится только указатель на объект.

Объекты, размещённые в стеке, принадлежат соответствующей процедуре; дополнительно они могут принадлежать одному или нескольким внутренним фреймам, вложенным в процедуру и друг в друга (области видимости).

В структуре стека также предусматриваются поля для хранения информации о текущей ошибке (исключении).

Структура стека StackM выглядит таким образом:

typedef struct _StackM

{

BOOL bError_; // флаг, показывающей наличие ошибки (исключения)

wchar_t arErrMsg_[1024]; // буфер для описания ошибки (исключения)

StackM_Elem* pBuffer_; // буфер стека

UINT buffCapacity_Elems_; /* максимальная ёмкость буфера стека (кол-во элементов) */

UINT nElems_; // текущее кол-во элементов в буфере стека

} StackM;

Объект помещается в стек либо путём копирования (вызывается зарегистрированный в TypeInfo конструктор копирования для этого объекта), либо объект непосредственно создаётся на вершине стека (вызывается конструктор по умолчанию).

При помещении объекта в стек возвращается указатель на него для непосредственного локального использования и дескриптор для безопасной передачи в другие процедуры. Дескриптор, фактически - это индекс элемента стека StackM_Elem, ссылающегося на объект.

Организация кода, использующего управляемый стек подчиняется набору правил:

1. Каждой процедуре, использующей управляемый стек («пользовательская процедура»), передаётся указатель на него (StackM* const pStackM) в качестве первого аргумента.

2. При входе в пользовательскую процедуру в стек помещается маркер начала процедуры, для этого используется макрос PROC_BEGIN, определённый как:

#define PROC_BEGIN { StackM_EnterProc(pStackM)

3. В завершении кода пользовательской процедуры вызывается функция свёртки стека вплоть до начала покидаемой процедуры. Для этого определены два макроса, соответственно, для завершения процедуры с возвратом значения и без него:

#define PROC_END_RET(RetVal) StackM_ExitProc(pStackM); return RetVal; }

#define PROC_END StackM_ExitProc(pStackM); }

4. Ранний выход из пользовательской процедуры, как и выход в её конце, сопровождается свёрткой стека с вызовом деструкторов для всех созданных к этому времени локальных стековых объектов. Для этого определены макросы:

#define PROC_RETURN { StackM_ExitProc(pStackM); return; }

#define PROC_RETURN_RET(RetVal) { StackM_ExitProc(pStackM); return RetVal; }

5. Аналогично процедурам, вход вложенный фрейм означает запись маркера в стек, а выход - свёртку с удалением локальных стековых объектов:

#define FRAME_BEGIN { StackM_EnterFrame(pStackM);

#define FRAME_END StackM_ExitFrame(pStackM); }

6. Ранний выход из циклов с помощью операторов break и continue также означает свёртку фрейма:

#define FRAME_BREAK { StackM_ExitFrame(pStackM); break; }

#define FRAME_CONTINUE { StackM_ExitFrame(pStackM); continue; }

Пример оформления процедуры (показаны основные конструкции):

BOOL MyProc(StackM* const pStackM, /* другие аргументы */)

PROC_BEGIN // начало процедуры

// …

// Создание объекта в управляемом стеке:

StringA* const pStr1 = StringA_ConstructOnStack(pStackM).pStringA_;

// Вызов под-программы:

if (! SubProc1(pStackM, /* другие аргументы */))

PROC_RETURN_RET(FALSE) // ранний выход из процедуры

// …

// Цикл:

while (/*…*/)

FRAME_BEGIN // начало вложенного фрейма (тело цикла)

// …

if (! SubProc2(pStackM, /* другие аргументы */))

PROC_RETURN_RET(FALSE) // ранний выход из процедуры

if (/* условие */)

FRAME_BREAK // выход из фрейма и цикла

// …

if (/* условие */)

FRAME_CONTINUE // выход из фрейма, возврат к началу цикла

// …

FRAME_BEGIN // начало вложенного фрейма (2-ой уровень вложения)

// …

FRAME_END // конец вложенного фрейма (2-ой уровень вложения)

FRAME_END // конец вложенного фрейма (тело цикла)

// …

PROC_END_RET(TRUE) // конец процедуры

Процедуры, как правило, возвращают значение BOOL (TRUE, FALSE). Это позволяет проверять результат вызова каждой процедуры и, в случае отрицательного результата (исключения), прерывать выполнение вызывающей процедуры (ситуация наличия ошибки или исключения). Информация об причине исключения сохраняется в специальном поле объекта «управляемый стек».

Как видно из изложенных правил, любой выход из процедуры или вложенного фрейма сопровождается свёрткой стека, т.е. удалением всех объектов, покидающих область видимости, с соответствующим вызовом их деструкторов. Использование вспомогательных макросов означает, что в процедурах, использующих управляемый стек, фигурные скобки { } не пишутся (их заменяют макросы). Ошибки при расстановке макросов входа/выхода в процедуры и фреймы частично выявляются статически при компиляции кода, оставшиеся - динамически при выполнении программы, для чего в процедурах работы со стеком предусмотрены соответствующие проверки.

3. Тестирование

Для тестирования была взята задача, состоящая из следующих этапов:

- чтение строк из входного файла;

- обработка строк: многократное повторение цикла, когда из входного набора строк по определённым правилам формируется набор строк с меньшим количеством элементов; результирующий набор принимается вновь за исходный и операция продолжается до тех пор, пока в результирующем наборе останется не более двух строк;

- запись результата в выходной файл.

Тестирование производилось на ноутбуке ASUS TP500LN, процессор Intel® Core™ i7-4510U CPU @2.00 GHz 2.60 GHz, ОЗУ 8,0 Гб. Операционная система: Microsoft Windows 8.1, 64-разрадная. Разработка кода и компиляция в среде Visual C++ 2015, оптимизация кода в соответствии с параметрами по умолчанию.

В целях сравнительного анализа тестовая задача была реализована следующими способами (каждый способ в виде отдельной программы):

- реализация на C++ (базовый вариант);

- реализация на «классическом» Си;

- реализация на Си с управляемым стеком (1 вариант - без оптимизации);

- реализация на Си с управляемым стеком (2 вариант - «средняя оптимизация»);

- реализация на Си с управляемым стеком (3 вариант - «глубокая оптимизация»).

Различие между вариантами реализации на Си с управляемым стеком следующие.

Первый вариант реализации написан без какой бы то ни было оптимизации, примерно с теми же идиоматическими конструкциями, какие применяются на C++, в особенности в отношении создания временных переменных в стеке и работы с коллекциями типа «вектор» (динамический массив). Отличие, конечно же, в том, что в C++ управляемый стек создаётся автоматически компилятором, а на Си - самим программистом. Соответственно, компилятор C++ имеет большие возможности оптимизации.

Второй вариант по сравнению с первым оптимизирован:

- если размер объекта не превышает фиксированный лимит в 32 байта, то объект размещается в самом элементе стека, а не в динамической памяти;

- при добавлении объекта в вектор вместо копирования применяется конструктор по умолчанию, это исключает добавление временного объекта в стек;

- предусмотрены резервные объёмы в буферах строк;

- из наиболее нагруженного цикла удалена лишняя временная переменная, помещаемая в управляемый стек;

- фреймы, не использующие управляемый стек для размещения внутренних переменных, не регистрируются в стеке (т.е. реализованы обычным образом, как в классическом Си).

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

Третий вариант реализации ещё дополнительно оптимизирован по сравнению с вторым: вместо обобщённого вектора (динамического массива) для хранения и обработки строк применён специализированный, аналогичной тому, который использован в реализации на классическом Си.

Результаты тестирования показаны на Рис. 1.

Рисунок 1 - Результаты тестирования

По результатам тестирования реализация на C++ и классическом Си показали примерно одинаковое время выполнения, хотя всё-таки небольшое (всего на несколько процентов) преимущество «классического» Си по скорости прослеживается. Но это связано, скорее, с особенностями реализации - при написании на Си оптимизация получается естественным образом, поскольку используются низкоуровневые конструкции (и при этом, как правило, страдает надёжность).

Теперь перейдём к реализациям на Си с управляемым стеком. Первый вариант реализации с управляемым стеком показал значительное уменьшение производительности по сравнению с реализациями на C++ и «классическом» Си, второй оказался лучше, а третий практически не отличался от реализации на C++. Большая потеря производительности в первом случае связана, очевидно, с большим количеством локальных объектов, создаваемых и удаляемых из управляемого стека; при этом используется динамическая информация о типе и динамические проверки корректности операций, что не может не сказаться на производительности. Производительность, однако, в нашем исследовании не является самоцелью, поскольку критичные по производительности участки кода всегда невелики по отношению к общему объёму кода приложения и могут быть отдельно оптимизированы вплоть до ассемблера. Гораздо важнее общая надёжность кода и корректность в управлении ресурсами, а именно этому служит применение управляемого стека.

Оптимизация кода в приложении на Си с управляемым стеком, как видно из приведённых примеров, имеет следующие направления:

- оптимизация высокоуровневых конструкций, использующих управляемый стек; как пример - вынос локальной переменной (объекта) за пределы тела цикла;

- отказ от регистрации в управляемом стеке тех процедур и внутренних фреймов, в которых не требуется создавать объекты в управляемом стеке;

- инкапсуляция низкоуровневого кода, не использующего управляемый стек, в методах объектов, принадлежащих управляемому стеку; как пример - класс StrArray, инкапсулирующий указатели на строки из третьего варианта реализации.



Заключение

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

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



Список информационных источников

[1] Bjarne Stroustrup. Exception Safety: Concepts and Techniques [Электронный ресурс]. URL: http://www.stroustrup.com/except.pdf (дата обращения: 01.11.2016).

[2] MSDN. How to: Design for Exception Safety [Электронный ресурс]. URL: https://msdn.microsoft.com/en-us/library/hh279653.aspx (дата обращения: 01.11.2016).

Размещено на Allbest.ru