В блоге beeline cloud мы делились историями и мнениями разработчиков — как программист-самоучка выучил 30 языков программирования, в каких случаях парное программирование не работает и почему некоторые проекты угасают, когда из компании уходит тимлид разработки. Сегодня поговорим о том, как изучать азы информатики при помощи Stack Overflow, даже если ваше образование не связано с компьютерными технологиями. Вот интересный перевод.

Мое основное образование далеко от ИТ. Но приблизительно в 2016 году я придумал, как изучать основы информатики при помощи Stack Overflow. Так у меня появилось увлекательное хобби. В свободное время я проглядываю сайт в поисках вопросов, получивших наибольшее количество голосов.

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

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

Одному из вопросов, набравшему наибольшее количество голосов на Stack Overflow (сейчас это порядка 24 миллионов «плюсов»!), я хочу посвятить эту статью.

Первое знакомство

Наткнувшись на этот вопрос, я не поверил своим глазам. Поначалу даже решил, что неправильно его понял.

Все ясно, подумал я, — очередной вопрос со звездочкой, типичный для интервью в FAAMG.

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

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

// !!! With this, the next loop runs faster.
   std::sort(data, data + arraySize);

   // Test
   clock_t start = clock();
   long long sum = 0;
   for (unsigned i = 0; i < 100000; ++i)
   {
       for (unsigned c = 0; c < arraySize; ++c)
       {   // Primary loop.
           if (data[c] >= 128)
               sum += data[c];
       }
   }

Поэтому с восприятием кода у меня сложностей не возникло. Но, тем не менее, сам код не вписывался ни в одну из привычных для меня моделей.

Пришлось прочесть его трижды, подавляя в себе желание прокрутить страницу, чтобы узнать ответ. Но что‑то все равно ускользало от моего понимания. Что это за обработка массива такая? Перебор элемент за элементом? Очень похоже на обычный поиск, и при этом не самый быстрый.

Лишь через какое‑то время я понял, что вижу совсем иной вид поиска, и уж точно не двоичный. Каждый элемент здесь обрабатывался особым O(N) порядком. Циклы не зависели от математических предположений программиста, таких как:

if value < maxElement/2
  search for value in (0...maxElement/2 - 1)
else
  search for value in (maxElement/2...maxElement)

Что же позволило ускорить обработку отсортированного массива?

Краткий ответ на вопрос

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

Лучшим ответом на него было сравнение с железнодорожным узлом. Прежде чем читать дальше, запомните основы этой аналогии:

Узел = инструкция сравнения (оператор If)

Ветвь = результат выполнения инструкции JUMP или ее разновидности

(поток управления if-else/while)

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

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

• Если бы он был оракулом, поезду никогда бы не пришлось останавливаться.

• Но если пророчества дадут осечку, машинисту придется прекратить движение и дать задний ход.

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

При обработке массива, содержащего сравнение (if currentElement <= or == or ≥ value), процессор использует хитрый трюк.

Допустим, цикл выполняется N раз. На каждой k-итерации (0 < k < N-1) обработки массива он будет пытаться «вспомнить», что происходило в прошлых итерациях от 0 до k-1. Использование данных зависит от сложности устройства процессора, поэтому пока оставим это в стороне.

Если условие (например, currentElement == value) было истинным в большинстве из k-1 раз, предполагается, что оно будет истинным и в k-n раз. И наоборот.

Исходя из того, что значения счетчика определенно будут меньше 30 (на основании предыдущих, таких как 17, 18, 19...), зачем дожидаться 20 (или 21, 22 или 23)?

Нужно просто руководствоваться тем, что они меньше 30.

Что же все-таки из себя представляет Branch predictor — модуль предсказания переходов (прогнозирования ветвлений)

И если он настолько хорош, то что с ним до сих пор не так?

«Бутылочное горлышко» фон Неймана

Процессор выполняет инструкции. Под этими словами подразумеваются все совершаемые им вычисления (c = a + b) и сравнения (i == 100). Но это лишь малая часть его работы. Тем не менее, именно о ней мы сейчас поговорим.

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

• Выборка: извлекаются инструкции и операнды (a, b, c, +, = или процессорный эквивалент инструкции IF).

• Декодирование: преобразование адресов памяти соответствующих пространств, поскольку ЦП выполняет несколько программ в множестве контекстов.

• Выполнение: знакомо нам как оператор языка программирования (например, c = a + b).

• Обратная запись: изменение памяти данных/программ полученным результатом, например, заполнение переменной C значением A + B.

Объединение этих четырех этапов известно как 4-этапный цикл команд процессора.

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

Другими словами, выполнение одной ассемблерной команды занимает не менее чем N (>1) тактовых циклов процессора, где N представляет собой длину конвейера команд.

Разумеется, это всего лишь крайне упрощенное объяснение. Диаграмма 4-этапного конвейера команд (N=4) приведена ниже.

Так выглядит 5-этапный (N=5) вариант конвейера команд:

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

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

Почти все из них нам знакомы:

• Кэш процессора

• Разделение кэша между памятью данных и памятью программ

• Система на чипе — линейка продуктов M1 компании Apple является ее потомком

За исключением модуля предсказания переходов (branch predictor).

Как работает предсказатель переходов

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

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

В памяти предиктора сохраняется история выбора пути выполнения во время итерации внутри цикла for/ while.

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

В цикле, содержащем 100 итераций внутри отсортированного массива, путь IF используется первые 51 раз, а путь ELSE — последние 49 раз.

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

Каждый раз при выполнении оператора IF результат TRUE приведет к фазе EXECUTE пути IF. Переход будет осуществлен без ожидания фаз FETCH и DECODE (инструкций ветвления IF).

Так будет продолжаться до 51-й итерации, то есть до тех пор, пока предварительно выбранный набор инструкций предиктора ветвлений не совпадет с оценкой оператора IF. Другими словами, предсказатель перехода будет оперировать готовыми исполняемыми инструкциями ещё до того, как ЦП узнает, что IF выдал TRUE.

При выполнении 52-й итерации результатом IF будет FALSE. Процессор будет знать, что его предварительно выбранному набору инструкций необходима корректировка. Соответственно будет потрачено время на выборку и декодирование набора инструкций ELSE. Затем он продолжит работу с этим набором (выполняя EXECUTE без FETCH и DECODE) вплоть до 100-й итерации.

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

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

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

Для лучшего восприятия ниже приведена блок‑схема, взятая из технического блога. Ее логика ничем не отличается от того, как работает кэш.

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

Заключение

Что же все-таки означает высокий рейтинг вопросов или ответов на Stack Overflow? И чем объяснить огромную популярность этого онлайн-ресурса?

В настоящее время Chat GPT создал серьезную альтернативу классическим форумам. В этих условиях рейтинг оценки Stack Overflow можно назвать несколько спорным. Он по-прежнему останется онлайн-свидетельством солидарности сообщества разработчиков, но не их компетенции в программировании.

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

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

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

beeline cloud — secure cloud provider. Разрабатываем облачные решения, чтобы вы предоставляли клиентам лучшие сервисы.