Задача с собеседования: продолжение

Поскольку в комментариях ответ нашли аж несколько раз, то сознаюсь — да, идея в том, что второй процессор это не только дополнительные 600 баксов стоимости и 70Вт энергопотребления, но еще и лишние 32Кб L1 кэша данных (а в Sandy Bridge так и лишние 256Кб L2, потому что там L2 тоже на каждое ядро). Так что, хотя в общем случае логично ожидать, что однопроцессорная версия будет быстрее (потому что не надо тратиться на синхронизацию), но если задача достаточно memory intensive (т.е. мы упираемся в скорость доступа к данным), причем фазы P1 и P2 оперируют разными данными, то в двухпроцессорном варианте данные фазы 1 будут горячими в кэше CPU1, а данные фазы 2 горячими в кэше CPU2. Получим эффективный размер L1 в 64Кб. И эффект от такого "увеличения" кэша может оказаться доминирующим, и оправдать даже расходы на синхронизацию.

Но мне стало интересно, смогу ли я этот эффект поймать в реальности. Реальность, как обычно, оказалась чуть сложнее теории, но в поединке мозга и компьютера мозг опять победил: вот этот код при базовых (тщательно подобранных) настройках дает в синхронном режиме (-Dasync=false) (690 +/- 1%) нс/сообщение, а в асинхронном (560 +/- 8%) нс/сообщение.

Хотелось бы в общих чертах понять, о чем говорит иностранецчто там происходит?

Нужно подобрать некоторую условную memory intensive задачу, и разбить ее на две фазы, каждая из которых обращается к своему куску данных. Я взял кусок данных в виде достаточно большого (сопоставимого с размером L1) массива double[]. Сама "фаза обработки сообщения" состоит из нескольких чтений/записей в ячейки этого массива. "Несколько" выбрано равным 128, и эти 128 ячеек выбираются из всего массива по псевдослучайному алгоритму (типа ЛКГ: I = (A*I) mod C). Сначала первая фаза делает это над своим массивом, потом вторая фаза делает ровно то же самое над своим — и так для каждого сообщения, коих легион 1 000 000 в каждом заходе. Да чего я код надиктовываю:

int index = message.index;
for( int i = 0; i < OPS_PER_MESSAGE; i++ ) {
  index = Math.abs( index * offset ) % DATA_SIZE;
  array[index] += amount;
}

---

Интересный вопрос №1: если псевдослучайное скакание по массиву заменить на проходку с фиксированным шагом, то разница в производительности практически пропадает. Скорее даже, с небольшим перевесом, почти на грани погрешности, начинает выигрывать синхронный вариант. Почему так? Интересный вопрос №2: если отставить в сторону рассмотренный вариант — какие еще эффекты могут обеспечить преимущество "распараллеленному" варианту последовательного кода? P.S. Да, кстати — мы (Дойче банк) набираем людей. Кажется, 3-4 вакансии у нас сейчас открыты. Можно прямо мне и писать — а то у меня еще много интересных идей для собеседования есть :)