Производительность C и Go

В этой статье мы исследуем различия, сходства и варианты использования C и Go, двух самых популярных языков программирования в мире. C — один из самых широко используемых языков программирования всех времен. Go — это язык программирования с открытым исходным кодом, который упрощает создание простого, надежного и эффективного программного обеспечения. Начните с этого быстрого сравнения двух, а затем посмотрите, как они складываются, когда дело доходит до удобочитаемости, скорости, простоты обучения и многого другого.

В этой статье мы реализуем параллельную версию алгоритма задачи коммивояжёра (TSP), описанного в главе 6 книги Питера Пачеко «Введение в параллельное программирование», используя языки Go и C. Эта задача направлена на определение кратчайшего маршрута для путешествия через ряд городов. (побывав в каждом из них только один раз), возвращаясь в родной город. Это NP-сложная задача оптимизации, вдохновленная потребностью продавцов доставлять товар в несколько мест (городов) по кратчайшему пути, сокращая время в пути и возможные затраты на транспортировку и топливо.

Обе системы начинают с процесса 0, чтобы прочитать экземпляр и передать его всем остальным. Все процессы должны повторить начало поиска в ширину, а затем посвятить себя исследованию поддерева. Наша программа должна статически разделить работу между процессами с глобальными обновлениями лучшего маршрута. Чтобы сравнить производительность реализованного алгоритма, мы измеряем время выполнения для 2 или 4 потоков в каждом процессе. В конце мы используем известные сценарии TSP для сравнения производительности реализаций. Важно отметить, что в этой статье производительность C и Go сравнивается с конкретным алгоритмом. Это не то, как следует проводить тестирование производительности.

Go (также известный как Golang) был разработан инженерами Google, которым нужен был язык, предлагающий эффективность C++, но более простой в изучении, написании, чтении и развертывании. Горутины языка упрощают разработчикам создание приложений, в полной мере использующих преимущества параллелизма, таких как крупные веб-сайты электронной коммерции, за счет одновременного развертывания рабочих нагрузок на нескольких ядрах ЦП. Другими словами, идеально подходит для параллельных вычислительных сред.

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

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

Теперь у нас есть наш первый подпуть. Он содержит ровно одну вершину и не содержит ребер. Этот путь может быть расширен всеми соседями последнего посещенного узла (пока единственного). Теперь мы создаем не более n-1 новых кандидатов. Для всех них мы можем снова вычислить окончательную нижнюю границу. Единственная разница в том, что на данный момент у нас есть узел, где мы знаем выходной вес, и узел, где мы точно знаем входной вес.

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

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

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

В целом реализация пошла по пути, предложенному Питером Пачеко в справочнике. Только несколько частей были изменены. Один из них находится в начале алгоритма, когда процесс 0 должен отправить проблемные данные другим. Мы решили эту проблему немного другим способом. Вместо того, чтобы отправлять всю матрицу графа другим процессам и повторять поиск по ширине для создания задач в каждом из них, мы решили выполнить этот поиск и разделение в начальном процессе. После генерации каждого стека задач для каждого процесса основной процесс отправляет только сгенерированные стеки, а остальные процессы уже начинают работать поверх стека вскоре после получения их в готовом виде. Эти процессы взаимодействуют через MPI, и внутри каждого процесса мы используем потоки через pthreads. Между этими потоками у нас происходит динамическая балансировка работы по описанной в книге стратегии.

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

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

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

На некоторых веб-страницах есть хорошо известные тестовые файлы для TSP. Мы используем один из этих сайтов для нашего тестирования. Мы заметили, что при тестировании сценариев с большим количеством экземпляров на их устранение очень быстро уходит очень много времени. В качестве отправной точки мы использовали сценарий с 5 городами, а затем расширили его до 15 городов, чтобы рассмотреть несколько более сложный сценарий. Как видно из приведенных ниже результатов, реализация на Go дала лучший результат, чем на C.

Наша первая реализация на Go была в 3 раза хуже по производительности алгоритма, чем на C. При быстром поиске можно найти анализы, оправдывающие эту разницу особенностями сборки мусора таких языков, как Go. Этот анализ очень поверхностный. Сборка мусора обычно занимает очень небольшой процент от общего времени выполнения, также есть некоторые косвенные и связанные вещи. Языки сбора мусора стараются быть языками, безопасными для памяти, поэтому они также, как правило, имеют проверки границ массива, когда компилятор не может доказать, что их можно опустить. Они также, как правило, не допускают большого количества интеллектуальных приведений и не допускают арифметических указателей.

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