Предвыборка кода

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

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

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

Способы реализации предвыборки кода

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

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

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

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

Аппаратные решения, упрощающие программную конвейеризацию

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

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

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

Программная конвейеризация

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

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

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

Пул строк

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

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

2) Ленивые присваивания строк
Обычно строка — это объект большого размера, требующий для своей работы выделения большого блока памяти. Данная оптимизация выделяет память под строки только при надобности, позволяя нескольким переменным указывать на одну цепочку символов. Только если одна из переменных меняет своё содержимое, строка копируется.

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

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;

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

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

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

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

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