Предсказание ветвлений (лайфхак)
Есть вот такая беда, в командной работе.
- Вася делает полезное, ему нужен Петя. Петя занят, счас доделает, ответит Васе. Вася ждет.
- Петя отвлекся, время потратил, Вася ответ получил, пошел работать — Петя вьезжает обратно в задачу.
- Дальше выясняется что Васе потребуется ответ от соседнего отдела — там думают, ответ завтра.
- Васе непонятно: ждать, переключаться на другое, просто тупить, итп.
Когда Васе дадут ответ, ему надо будет посоветоваться со своим руководителем, например. У которого тоже дела, в моменте не срастется, надо ждать. Еще и подумать бы неплохо.
Классический пинг-понг между не-синхронизированными процессами.
Два оч крутых решения подсмотрел в инженерной среде, сравнительно давно. Одно просто иногда помогает, вторым хорошим даже со студентами делюсь.
Первое — вы будете смеяться, но ГОСТ по эргономике (!) от 1976 года, что ли (!).
Когда компутеры были большими, а мы были маленькими.
Суть там в следующем:
— вычисления — это долго (1976, ну)
— юзер точно будет тупить
— поэтому сначала выведи пользователю все запросы на все данные, заранее
— а потом, пока юзер тупит, спокойно делай свою работу (которая у тебя раньше была)
— сделаешь — обработаешь пользовательский ввод, и пойдешь дальше
Прикольно? Да не то слово. Работает — да.
Применимо — ну, на самом деле не всегда, потому что для выполнения какой-то работы тебе и нужны будут ответы от юзера.
Но сначала оформить в UI всё что требует тупняка, а потом спокойно делать пока то, что тупняка не требует — это хороший паттерн. Ёмкий. Есть над чем подумать.
Второе — здесь референс от умных дядек в железе.
У вас на физическом уровне, унутри кампутера, постоянно сотни и тысячи вычислительных процессов работают в параллель. И даже чего-то ждут. Даже если не ждут, разные операции различаются между собой по времени в разы, а иногда и на порядки.
Например, из своего кеша первого уровня одно вычислительное ядро процессора выполняет команды со скоростью, соизмеримой со световой. Я не шучу: за то время, пока свет идет (1 метр) от монитора до ваших глаз, современный процессор успевает обратиться к кешу L1 до шести раз.
Лазить в общую память — долго и дорого. Лазить проверять какие-то условия — еще дольше. Ждать, пока соседи подготовят блок вычислений, чтобы забрать к себе — очень долго. Ждать, пока там устройства и шина расчехлятся — можно вообще успеть выключиться поспать, батарейки сэкономим. Все примитивы синхронизации — сверки, проверки условий, обмен данными — так или иначе тупняк.
Но хочется работать быстро. Поэтому вычислительное ядро что делает?
Вступает в силу механизм предсказания ветвлений, название которого вынесено в заголовок.
На логической развилке, где надо сходить за данными, выбираем самый вероятный вариант, и начинаем сразу готовить его.
— В худшем случае, если окажется, что решение не верное — вы потратили время впустую, но вы все равно бы его потратили, пока ждали.
— В лучшем, вероятном случае — окажется, что пока ждали, часть работы уже выполнена, время сэкономлено.
Если предположить, что на тупых логических проверках (a=0) распределение тупое и равновероятное, 50/50, то в 50% случаях алгоритм экономит время. В терминах задач, конвейеров и процессором — это дофига выигрыш в производительности. Особенно, когда параллелизма много (например, видеокарты, cell-архитектура, кольцевые шины итд итп).
Продолжать делать, что дали — просто и полезно.
Ждать и спрашивать (и не делать) — сложно и дорого.
Еще раз: если у нас на точке ветвления есть вариант, про который мы знаем, что он самый вероятный — не надо тупить, надо идти и делать его.
Хотя бы до последующих вопросов, развилок и взаимодействий.
Перекликается также с лайфхак-методикой «следующий шаг» — писал здесь — когда вы точно так же, сразу стараетесь подумать на один вопрос вперед, и последующее поведение вместе с ответами спрогнозировать заранее. Меньше бегать с вопросами, меньше тупняка, меньше пинг-понга, все довольны.
Хак «предсказания ветвлений» помогает также прикинуть, как пойдет выполнение плана в реальном мире, если всё принятие решений оставить на самотек, «по дефолту», взять самые очевидные варианты.
Да, очень может быть, что очевидные = неправильные; вы этого пока не знаете. Но уже можете оценить и план, и срок, и требуемые телодвижения — вдруг выяснится, что и делать не надо вовсе. И копали не туда.
Вместе с первым написанным хаком, про тупняк и эргономику, удобно: собрать скопом сразу ряд вопросов, отдать их на изучение всем заинтересованным сторонам — а самим тем временем пилить самый очевидный вариант. Пересмотрите план — не беда, все равно лучше чем сидеть тупить.
Стоит отметить: описанное «предсказание ветвлений» — логический лайфхак, для людей, для иллюстрации подхода.
Для процессоров и железок уже давно придумали гораздо более интересные и плотные штуки — например, SMT + uop, вот тут базово: https://blog.codingconfessions.com/p/simultaneous-multithreading