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