К предыдущему посту про разделение труда

В английском языке есть слово bangalored. «Отбангалорить» — значит уволить и перенести позицию в страну с более дешёвой рабочей силой. Этот термин возник в IT сфере США в 2000-х после лопнувшего пузыря доткомов. После кризиса многие компании сокращали расходы и отдавали работу на аутсорс в страны, где работникам можно платить ветку миску риса. ‎Одним из центров притяжения новых рабочих мест стал город Бангалор на юге Индии.

Недавно Google уволила сотрудников из команд Flutter, Dart и Python. По словам бывшего сотрудника, замена была найдена в Мюнхене из-за более дешёвого найма. Кстати, советую почитать его тред. Интересно, как работники на западе реагируют на сокращения.

В 2022 году я грёб в аутсорс компании. Мы работали на проекте Fujitsu. После февральских событий, они решили прекратить сотрудничество с разработчиками из России и нашли нам замену в Бангалоре и Пуне. То есть, нас буквально отбангалорили 😂 Как и сотрудники Google, мы проводили обучение тех, кто нас заменит. В том году я весь октябрь провёл в Индии, обучая свою замену. Фото, кстати, от туда.

К чему это всё и какой можно сделать вывод? Неважно, кто ты: работник MAANG-компании или гребец на галерах. Нужно быть готовым к тому, что бизнес решит тебя отбангалорить, поскольку это всегда происходит внезапно.

🖥 О последовательном доступе к данным и кэше ЦПУ

В прошлое воскресенье на LeetCode в качестве челленджа была задачка Largest Local Values in a Matrix. Несмотря на уровень Easy, она демонстрирует важность последовательного доступа к данным.

Суть задачи

Дана матрица MxM. Нужно найти максимальные значения во всех матрицах 3x3, которые получаются из исходной матрицы. Решение от LeetCode реализовано так (рис. 1):

1. Берётся матрица 3x3.
2. Последовательно обходятся элементы матрицы в поисках максимума.
3. goto п.1.

Что не так с решением?

Например, что столбцы [9, 6, 2] и [8, 2, 6] относятся к матрицам 0 и 1, и будут обработаны несколько раз. Оптимальный алгоритм вернёт правильное решение, обработав каждый столбец и строку лишь 1 раз. Реализовать такой алгоритм можно 2 способами:

1. Обход по столбцам слева направо, сверху вниз (рис. 2).
2. Обход по строкам сверху вниз, слева направо.

Что быстрее? Кажется, что обход по столбцам. Да, но не всегда.

Причём тут последовательный доступ и кэш ЦПУ?

Реализация кэша ЦПУ основана на концепции локальности данных. При обращении к данным высока вероятность, что:

1. Вскоре к данным обратятся снова. Поэтому-то они и сохраняются в кэш.
2. Могут обратиться и к соседним данным. Поэтому кэширование происходит блоками определённого размера (cache line) и в кэш попадают не только запрашиваемые данные, но и соседние байты памяти.

В общем случае, если поведение программы не укладывается в концепцию выше, то производительность снижается. Например, для алгоритма с обходом по строкам, при размере матрицы 2000+ элементов, количество промахов кэша увеличивается многократно (рис. 3), что приводит к ухудшению производительности (рис. 4). Объясняется это непоследовательным доступом. В кэш попадают ненужные даные, ведь используется только 3 элемента из строки.

Но интересно то, что обход по строкам быстрее, если матрица небольшая (рис. 5). В таком случае, в кэш попадает практически вся матрица. А найти max значение 3-х элементов одной строки быстрее, чем 3-х элементов из разных строк.