В 1978 году вышел третий том монографии Дональда Кнута «Искусство программирования», где автор рассматривает алгоритмы сортировки и поиска. Помимо самих алгоритмов описаны аппаратные характеристики компьютера и их влияние на производительность при работе с алгоритмами.
В 2024 году мы с вами возьмём классические алгоритмы сортировки и посмотрим, как работает современный многоядерный процессор при сортировке нескольких массивов на одном и нескольких логических ядрах. Мы напишем приложение с графическим интерфейсом (GUI) на фреймворке Qt, обойдем глобальную блокировку интерпретатора (GIL), воспользуемся несколькими потоками, на один из которых переложим выполнение асинхронного цикла событий, и распараллелим этот поток для реализации параллельных вычислений.
Предисловие
Перед тем, как мы с вами начнем писать приложения, я вам изложу необходимую теоретическую базу максимально доступным языком для того, чтобы в процессе написания вы понимали, что мы делаем. В статье речь идет о центральном процессоре компьютера – CPU.
Обзор технических характеристик современного процессора
Давайте перейдем к техническим характеристикам процессора AMD Ryzen 7 7700
Первая важнейшая характеристика – это базовая частота процессора. Существует такое понятие «операции, ограниченные быстродействием процессора». Счетные и вычислительные задачи – это классические примеры таких операций. С аппаратной точки зрения: чем выше частота процессора, тем выше скорость выполнения инструкций и вычислений. С программной точки зрения – необходимо выбирать алгоритмы вычисления, которые выполняются за минимальное процессорное время. Обратите внимание, что у процессора существует турбо-режим – автоматическое увеличение частоты включается для скорейшего выполнения длительной счетной и вычислительной операции.
Вторая важнейшая характеристика – это количество ядер. В нашем случае их 8. Здесь речь идёт о физических ядрах, которые находятся под крышкой процессора. Каждое физическое ядро обычно способно обрабатывать инструкции и данные независимо от других ядер, что позволяет параллельно выполнять несколько задач.
Но помимо физических ядер существует другая характеристика – максимальное число потоков. К сожалению, термин «поток» - это крайне неудачное название для логического ядра процессора. Потоки в Python (thread) и логические ядра процессора представляют собой разные концепции. Логические ядра (мы не будем далее использовать термин «потоки») представляют собой виртуальные вычислительные единицы, созданные для увеличения параллелизма выполнения инструкций. Они могут использовать ресурсы физического ядра процессора для исполнения задач, что позволяет повысить общую производительность процессора.
Механизм работы логических ядер процессора
Представьте себе два класса школы: в классе 6А один ученик, а в классе 6Б – 12 учеников. Каждому классу надо решить 12 задач. Один ученик в любом классе решает такую задачу 2 минуты. Сколько будет решать эти задачи класс 6А? Ответ: 12 * 2 = 24 минуты. А сколько эти задачи будет решать класс 6Б? Если учитель даст одновременно каждому ученику по 1 задаче, то все ученики вместе решат задачи за 2 минуты. Результаты: класс 6А: 24 минуты, класс 6Б: 2 минуты. Конечно, это очень грубо, так как есть множество погрешностей – раздать задания, собрать готовые решения. В любом случае, ключевым здесь является то, что класс из 12 учеников эффективнее класса с 1 учеником. С одним огромным НО! Это поведение учителя! Я надеюсь, что вы поняли, что ученики – это логические ядра процессора, а учитель – это интерпретатор Python. И интерпретатор Python не раздает одновременно всем ученикам сразу задания. Он вначале даст первому ученику задание и подождет, пока тот решит (уже 2 минуты). Когда этот ученик решит задание, учитель даст второму ученику задание и будет ждать, пока тот решит. И так далее. В итоге мы ничего не выигрываем, а такое поведение обусловлено наличием глобальной блокировки интерпретатора (GIL).
Глобальная блокировка интерпретатора Python
Глобальная блокировка интерпретатора (GIL) Python - это блокировка, которая не дает Python-процессу исполнять более одной команды байт-кода в каждый момент времени. Но не так все плохо. В Python есть способы обхода GIL. Но в начале разберемся с терминами.
Процесс - работающее приложение, которому выделена область памяти, недоступная другим приложениям. Многопроцессность – это использование двух или более процессоров в одной операционной системе. В Python родительский процесс может создать один или более дочерних процессов, которыми управляет, а затем распределяет работу между ними. Причем у каждого дочернего процесса будет своя GIL.
Поток - это облегченный процесс, наименьшая единица выполнения, которая может выполняться операционной системой. У потоков нет своей памяти, они используются памятью создавшего их процесса. Когда у нас несколько потоков – это называется «многопоточностью», при этом существует главный поток и дополнительные потоки. На одном логическом ядре процессора может исполняться несколько потоков Python. Это возможно благодаря механизму планирования операционной системы, который разделяет процессорное время между различными потоками.
Конкурентность и параллелизм
Для того, чтобы понять, как учитель раздает всем ученикам задания одновременно, а они их одновременно выполняют, мы должны четко понимать такие термины как «конкурентность» и «параллелизм».
Конкурентность относится к способности системы обрабатывать несколько задач одновременно. Приведу конкретный пример: учитель дал задание первому ученику, он начал его выполнять. Пока он делает задание, учитель дал задание второму ученику и тот начал его выполнять. А пока первый и второй ученики выполняют задания, учитель дал третьему ученику задания и так далее. В конце учитель также собирает задания с учеников, кто первый закончил её выполнять.
Параллелизм, с другой стороны, фактически представляет собой одновременное выполнение нескольких задач за счет использования множества ресурсов, таких
как многопроцессорные системы или распределенные вычисления. Параллелизм
позволяет задачам выполняться одновременно и реально ускоряет обработку.
Приведу пример: ученики сидят в классе и одновременно выполняют задачи.
Конкурентность относится к взаимодействию с большим количеством вещей одновременно. Параллелизм относится к выполнению большого количества вещей одновременно.
Инструментом для реализации конкурентности является асинхронное программирование, которое позволяет системе эффективно обрабатывать несколько задач одновременно или переключаться между задачами без блокировки.
С другой стороны, для создания параллелизма используются как многопоточность (одновременное выполнение нескольких потоков в рамках одного процесса), так и многопроцессность (одновременное выполнение нескольких процессов). Оба эти подхода способствуют реальной параллельной обработке задач на многопроцессорной или многоядерной системе.
И еще одно важное понятие – корутина (сопрограмма) в asyncio представляет собой функцию, которая может быть приостановлена и возобновлена, а также взаимодействовать с другими корутинами. В языке Python корутины обозначаются ключевым словом async def. Корутины позволяют писать асинхронный код, который может эффективно управлять множеством параллельных задач без блокировки. Они широко используются в асинхронном программировании на основе asyncio.
Не расстраивайтесь
Если вы мало, что поняли, из текста выше – это нормально. Это довольно сложные темы, а параллельное программирование считается высшим пилотажем и изучается на последнем курсе вуза по IT-специальности. Чтобы все это понять, необходима постоянная практика и повторение, и в один день к вам придёт понимание этих терминов.
Теорию я изложил, давайте немного отдохнем, порисуем. А потом начнем программировать.
Что мы создаем?
Мы создаем приложение с графическим интерфейсом, которое будет вычислять время работы процессора на одном и на нескольких логических ядрах при сортировке заданного количества массивов выбранным алгоритмом сортировки. То есть выбираем режим одного логического ядра, нескольких логических ядер, выбираем количество массивов, которые будут отсортированы, количество чисел в одном массиве. Выбираем алгоритм и нажимаем «Начать тестирование». Спустя некоторое время мы получим результаты тестирования в различных режимах.
UX/UI
Так как наше приложение имеет графический интерфейс, мы должны создать дизайн макет. Прежде всего надо учитывать UX (user experience). Целью UX-дизайна является создание позитивного и значимого опыта для пользователей при использовании приложения. Основная задача UX-дизайна — обеспечить, чтобы приложение было интуитивно понятно, удобено в использовании и полезено для своей целевой аудитории. А UI (User Interface) - это интерфейс, через который пользователь взаимодействует с приложением. Мы воспользуемся любимой программой всех дизайнеров Figma.
Qt Designer
Для создания графического интерфейса будем использовать один из самых популярных фреймворков языка программирования C++ - Qt. Так как мы с вами работаем на Python, мы будем пользоваться Python-библиотекой для использования Qt – PySide6. После установки в виртуальное окружение в папке PySide6 есть приложение Qt Designer, которое нам позволяет быстро создавать графические интерфейсы с помощью функции drag and drop.
После того, как у нас создан графический интерфейс, файл с ним необходимо сохранить с расширением *ui, а далее с помощью обычного терминала конвертировать его в Python-код с помощью команды:
pyside6-uic design.ui -o design.pyОбходим глобальные блокировки интерпретатора
С GIL мы столкнёмся, когда в графическом интерфейсе нажмём кнопку запустить и начнет выполняться длительная вычислительная задача – сортировка. Помним, что блокировка не дает Python-процессу исполнять более одной команды байт-кода в каждый момент времени.
В фреймворке Qt действует система сигналов и слотов, то есть виджет (кнопка, поле ввода) может посылать сигналы, содержащие информацию о событии, а другие компоненты могут принимать эти сигналы посредством специальных функций – слотов. А откуда берётся это событие? В Qt существует цикл событий QEventLoop и именно он будет заблокирован на время выполнения длительной вычислительной операции. То есть, мы не сможем нажать кнопку «Отмена» - пока вычислительная операция не закончится, графический интерфейс будет заморожен. И операционная система может подумать, что приложение не отвечает и предложить принудительно его закрыть.
Поэтому давайте поступим так: так как блокируется операция ввода-вывода мы будем использовать многопоточность. У нас в главном процессе будет работать графический интерфейс со своим циклом событий QEventLoop, а в дополнительном потоке мы реализуем асинхронный цикл событий, в котором мы будем выполнять вычислительные задачи.
import asyncio
from asyncio import AbstractEventLoop
import sys
from threading import Thread
from PySide6.QtWidgets import QApplication
from ui import PythonCPUBenchmark
class ThreadedEventLoop(Thread):
"""Class for async event loop."""
def __init__(self, loop: AbstractEventLoop) -> None:
super().__init__()
self._loop = loop
self.daemon: bool = True
def run(self) -> None:
self._loop.run_forever()
if __name__ == '__main__':
loop = asyncio.new_event_loop()
asyncio_thread = ThreadedEventLoop(loop)
asyncio_thread.start()
app = QApplication(sys.argv)
window = PythonCPUBenchmark(loop)
window.show()
sys.exit(app.exec())
У вас может возникнуть вопрос, что такое self.daemon = True? Для библиотеки threading требуется правильное прерывание. Используются демоны - это специальный вид потоков, предназначенный для выполнения длительных фоновых задач. Они не мешают приложению завершиться.
Когда пользователь нажимает кнопку «Начать тестирование» (зеленый треугольник), мы передаем циклу событий asyncio корутину, выполняющую сортировку. У asyncio есть функция, которая ничего не блокирует и написана с точки зрения потокобезопасности, call_soon_threadsafe. Эта функция принимает функцию Python (не корутину) и потокобезопасным образом планирует её выполнение на следующей итерации цикла событий.
Следующий момент, функция - asyncio.run_coroutine_threadsafe принимает корутину потокобезопасным образом подает её для выполнения и сразу же возвращает будущий объект, который позволит получить доступ к результату корутины.
Реализуем параллельные вычисления
Задача состоит в том, что нам надо производить сортировку от 1 до 10 массивов по одному и тому же алгоритму на одном или нескольких логических ядрах процессора.
В Python можно разбить поток выполнения на несколько процессов с помощью модуля multiprocessing. Этот модуль предоставляет функциональность для создания процессов, которые могут выполняться параллельно. Каждый процесс имеет своё собственное пространство памяти, что делает его отдельным и изолированным от других процессов. Разделение потока выполнения на несколько процессов может быть полезно для распределения вычислений по нескольким ядрам процессора или для решения проблемы GIL.
Но multiprocessing годится для простых случаев, но не годятся, если нужно получать возвращенное функцией значение или обрабатывать результаты по мере готовности. Для этого используются пулы процессов. Конкретно для нашей задачи нам надо быстро переходить от процессов к потокам и назад. Для этого существует стандартный модуль concurrent.futures со своим классом Executor. У этого класса есть 2 конкретные реализации: ProcessPoolExecutor и ThreadPoolExecutor. Решением нашей задачи будет выбор ProcessPoolExecutor, так как мы решаем вычислительную задачу.
Посмотреть полный код
Перед анализом результатов тестирования вы можете ознакомиться с полным кодом приложения – код приложения в свободном доступе в репозитории на моём профиле на GitHub.
Тестирование
Итак, мы с вами протестируем процессор в режиме работы одного логического ядра (я назвал это «Однопроцессность») и максимального числа логических ядер («Многопроцессность»). В начале мы протестируем на 1 массиве, потом на 5 массивах, а затем на 10 массивах. Для медленных алгоритмов сортировки в одном массиве у нас будет 30 тысяч чисел. Для алгоритмов быстрой сортировки в одном массиве у нас будет 1 миллионов чисел.
Для чистоты эксперимента мы отключим турбо-режим, чтобы в процессе тестирования у нас не произошло автоматическое увеличение частоты процессора. Между тестами на разных ядрах мы будем давать отдохнуть процессору 3 секунды. Для идентичности массивов мы установим у модуля псевдослучайных чисел random зерно random.seed(1).
Медленные алгоритмы сортировки
Сортировка вставками
Как и ожидалось, для одного массива однопроцессность – это тоже самое, что многопроцессность. У нас используется только одно логическое ядро. Поэтому различие результатов совершенно незначительное. На 5 массивах разница уже почти в 4 раза. Многопроцессность выигрывает, причем заметно. Но абсолютную победу многопроцессности видно на 10 массивах. Здесь разница в 7,6 раз.
Сортировка выбором
Обратите внимание, что сортировка выбором работает быстрее, чем сортировка вставками при всех тех же входных условиях. И абсолютно такие же отношения по скорости выполнения в однопроцессности и многопроцессности.
Сортировка пузырьком
Сортировка пузырьком – самый медленный алгоритм среди медленных алгоритмов сортировки в нашем эксперименте. Также и отношения между временами при однопроцессности и многопроцессности хуже для 5 массивов – в 3,8 раз. Для 10 массивов результаты по-прежнему отличные.
Быстрые алгоритмы сортировки
Мы увеличиваем количество данных в массивах, потому что массив из 100 тыс. чисел для быстрых алгоритмов сортировки не считается длительной вычислительной задачи. Мы будем получать, что однопроцессность будет работать лучше чем многопроцессность.
Сортировка подсчётом
Вот, казалось бы, что мы нашли идеальный алгоритм сортировки. Но не спешите радоваться! Алгоритм сортировки подсчетом является самым быстрым среди остальных алгоритмов сортировки, когда необходимо отсортировать большое количество элементов из ограниченного диапазона целых чисел. Этот алгоритм имеет линейную временную сложность, что делает его эффективным в таких случаях.
Быстрая сортировка
На сортировке 10 массивов по 1 млн. чисел в каждом параллельно разница во времени по сравнению с синхронным режимом на одном логическом ядре составляет всего 3 раза, что немного.
Сортировка слиянием
Алгоритм сортировки слиянием заметно проигрывает другим быстрым алгоритмам в нашем эксперименте, зато на сортировке 10 массивов по 1 млн. чисел в каждом параллельно разница во времени по сравнению с синхронным режимом на одном логическом ядре составляет 6,8 раз, что неплохо.
Выводы
Для медленных алгоритмов сортировки и быстрых алгоритмов сортировки задача является длительной при разных условиях: например, массив, в котором 10 тысяч целых чисел для медленных алгоритмов сортировки является длительной, а для быстрых алгоритмов сортировки НЕ является длительной.
Для недлительных вычислительных задач скорость выполнения синхронного кода на одном логическом ядре процессора превосходит скорость выполнения на нескольких логических ядрах.
для длительных вычислительных задач с большим количеством входящих массивов скорость выполнения задачи на нескольких логических ядрах процессора превосходит скорость выполнения на одном логическом ядре в несколько раз.
