Разбиение цикла на блоки

Loop tiling - оптимизирующее преобразование, призванное сделать исполнение некоторых типов циклов более эффективным.

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

Пример: умножение матрицы на вектор
for (i = 0; i < N; i++)
     for (j = 0; j < N; j++)
         c[i] = c[i] + a[i, j] * b[j];
        
После разбиения цикла на блоки 2 × 2:
for (i = 0; i < N; i += 2)
     for (j = 0; j < N; j += 2)
         for (ii = i; ii < min(i+2, N); ii++)
             for (jj = j; jj < min(j+2, N); jj++)
                 c[ii] = c[ii] + a[ii, jj] * b[ii];

Размотка цикла 

Размотка цикла — техника оптимизации компьютерных программ, состоящая в искусственном увеличении количества инструкций, исполняемых в течение одной итерации цикла. Позволяет во многих случаях увеличить количество параллельно исполняемых блоков инструкций и более интенсивно использовать регистры процессора, кэш данных и исполнительных устройств.

Пример, код:
int i;
for ( i = 1; i < n; i++) {
    a[i] = (i % b[i]);
}

преобразуется в:
int i;
for (i = 1; i < n - 3; i += 4) {
    a[i] = (i % b[i]);
    a[i + 1] = ((i + 1) % b[i + 1]);
    a[i + 2] = ((i + 2) % b[i + 2]);
    a[i + 3] = ((i + 3) % b[i + 3]);
}

Размыкание цикла

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

Пример преобразования:
for (i = 0; i < 1000; i++) {
    x[i] += y[i];
  
    if (w)
        y[i] = 0;
}

Условие внутри тела цикла мешает его распараллеливанию. После размыкания оно принимает следующий вид:
if (w) {
    for (i = 0; i < 1000; i++) {
        x[i] += y[i];
        y[i] = 0;
    }
}
else {
    for (i = 0; i < 1000; i++)
        x[i] += y[i];
}

Распределение регистров

Распределение регистров – это процесс оптимизации использования регистров процессора в программной реализации вычислительных процессов.

Это распределение является одним из методов оптимизации производительности кода. Состоит из нескольких шагов:
1. Анализ исходного кода, позволяющий определить переменные, которые используются наиболее часто.
2. Распределение регистров таким образом, чтобы переменные, которые используются наиболее часто, сохранялись в регистрах.
3. Создание кода с использованием этих регистров.

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

Методы снижения стоимости операций:

1. Автоматизация - внедрение автоматизированных систем и процессов может значительно сократить время и затраты на выполнение задач.

2. Оптимизация процессов производства - анализ и оптимизация процессов производства позволяют поднять эффективность работы и снизить затраты.

3. Инновации - внедрение новых технологий и методов, которые улучшают процессы, может позволить снизить затраты.

4. Управление запасами - оптимизация управления запасами позволяет снизить затраты на их хранение и обработку.

5. Управление процессом закупок - управление процессом закупок и работа с поставщиками позволяют сэкономить на затратах и получить лучшие условия поставки.

6. Улучшение качества работы персонала - постоянное повышение уровня квалификации и мотивация персонала позволяют повысить эффективность работы и снизить вероятность ошибок и изменений в производственных процессах.

Применение хвостовой рекурсии

Хвостовая рекурсия часто применяется в программах на функциональных языках программирования. Многие вычисления на таких языках естественно выражать в виде рекурсивных функций, а возможность автоматической замены транслятором хвостовой рекурсии на итерацию означает, что по вычислительной эффективности она равна эквивалентному коду, записанному в итеративном виде.

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

Что такое недостижимый код?

Недостижимый код - это код в программе, который никогда не будет выполнен в процессе ее работы.

Пример:
int foo(int a) {
int b;
b = a << 2;
return b;
b = 47; // Недостижимый код
return 0; // Недостижимый код
}

Причины возникновения недостижимого кода

Существование недостижимого кода может быть обусловлено разными факторами, например:

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

Инкапсуляция в ООП

Инкапсуляция является одним из основных принципов ООп, который обеспечивает сокрытие деталей реализации объекта и предоставление интерфейса для взаимодействия с ним.

Этот подход упрощает использование объектов и является одним из способов защиты данных от различных изменений из-за ошибок в других частях программы.

Определение свойств и методов с модификаторами доступа private, protected или public – один из способов обеспечения инкапсуляции. Это позволяет установить уровни доступа к объектам и их методам, определяя, кто и как может обращаться к свойствам классов.

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

Что такое интерфейс?

Интерфейс в ООП – это абстрактный класс, который определяет набор методов без их реализации. Он дает возможность определить некоторый стандарт поведения для классов, которые помимо уже определенных методов могут иметь свои собственные и реализовывать этот интерфейс.

Используя интерфейсы, можно определить, как объекты могут обмениваться данными и какие операции они могут выполнять. Это упрощает процесс разработки и позволяет создавать более гибкие и расширяемые системы.

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

Конструктор и функциональное программирование

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

В функциональном программировании конструктор является частью алгебраического типа данных (ADT), который определяет структуру объекта, состоящего из группы значений. Конструкторы могут быть записаны с помощью ключевого слова data, type или newtype, а типы данных могут быть объединены с помощью оператора |, который определяет алгебраический тип.

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

Контейнер

контейнер(container) - это объект, который хранит и управляет коллекцией других объектов(элементов). В объектно-ориентированных языках программирования контейнеры обычно реализованы как классы или шаблоны классов.

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

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

Непрозрачный указатель

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

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

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

Метод в ООП

Метод в объектно-ориентированном программировании — это функция или процедура, принадлежащая какому-то классу или объекту.

Их различают на:
- простые методы, которые имеют доступ к данным объекта (конкретного экземпляра данного класса),
- статические методы, которые не имеют доступа к данным объекта, и для их использования не нужно создавать экземпляры (данного класса).

Методы предоставляют интерфейс, при помощи которого осуществляется доступ к данным объекта некоторого класса, тем самым, обеспечивая инкапсуляцию данных.

В зависимости от того, какой уровень доступа предоставляет тот или иной метод, выделяют:
- открытый (public) интерфейс — общий интерфейс для всех пользователей данного класса;
- защищённый (protected) интерфейс — внутренний интерфейс для всех наследников данного класса;
- закрытый (private) интерфейс — интерфейс, доступный только изнутри данного класса.

Абстрактный метод

Абстрактный метод  — в ООП метод класса, реализация для которого отсутствует. Класс, содержащий абстрактные методы, также принято называть абстрактным.

Абстрактные методы зачастую путают с виртуальными. Абстрактный метод подлежит определению в классах-наследниках, поэтому его можно отнести к виртуальным, но не каждый виртуальный метод является абстрактным.

Абстрактный метод ничего не делает, но определяет параметры и возвращаемое значение.

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

Пример на с++:
// Чистая (пустая) виртуальная функция.
virtual void Abstr ( void ) = 0;

Тип-произведение в программирование

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

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

Кроме того, тип-произведение может использоваться для передачи значений между функциями.

Также может быть использовано для создания таких структур данных, как списки, очереди и деревья.

Виртуальный метод

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

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

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

Динамическое связывание

Техника вызова виртуальных методов называется ещё «динамическим связыванием». Имеется в виду, что имя метода, использованное в программе, связывается с адресом входа конкретного метода динамически, а не статически, так как в момент компиляции, в общем случае, невозможно определить, какая из существующих реализаций метода будет вызвана.

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

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

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

Геттер

Getter - это метод класса, который используется для получения значения закрытого поля класса. Он позволяет получить доступ к закрытому полю класса, но не позволяет изменить его.

Пример:
class Car {
private:
    int speed;
public:
    int getSpeed() const { // геттер
        return speed;
    }
};

В этом примере getSpeed() - это геттер, который возвращает значение переменной speed, объявленной как закрытая в классе Car.

Сеттер

Setters - это метод класса, который используется для установки значения приватного члена класса.

Пример:
class Car {
private:
    int speed;
public:
    void setSpeed(int newSpeed) { // сеттер
        speed = newSpeed;
    }
};

Деструктор

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

Деструктор не требует явного вызова и вызывается автоматически при удалении объекта (через оператор delete или при выходе объекта из области видимости). Он не возвращает значения, не принимает параметров и не может перегружаться.

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