Загадочного указатель связанной многопоточности замедление

Question

фон: Так что я работаю на Raytracer .. для моей конструкции схемы пространственного разделения, я изначально имел некоторый код, как это:

if (msize <= 2) { // create a leaf node 
    Model **models = new Model*[msize]; 
    for (uint i=0; i<msize; ++i) 
     models[i] = &mlist[i]; 
    *arrayPtr = Node(models, msize); // class Node contains a copy of models 
    ... increment arrayPtr ... 
    return; 
} 

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

Тогда я понял, что эй, нет причин для меня добавить этот дополнительный уровень косвенности; если я правильно устрою свои модели, я могу получить узлы листа, чтобы указать на большой массив моделей. Модели, прилегающие друг к другу в большом массиве, будут принадлежать данному листовому узлу, поэтому листья будут содержать указатели на модели. Поэтому я сделал это и протестировал его, оставив все остальное неизменным.

Теперь можно было бы подумать, что это, очевидно, ускорит программу. Ну, это ускоряет однопоточную версию (примерно на 10%), но она замедляет многопоточность (примерно на 15%! Это довольно важно, если вы делаете большую оптимизацию.) Я вполне уверен потеря на том, как справиться с этим - я думал, что косвенность была плохая, я думал, что сокращение использования памяти было хорошим, особенно для многопоточности .. нет никакой записи для листового узла или Модели, все записи выполняются в отдельной структуре данных ,

Любые указатели/рекомендации по анализу проблемы были бы замечательными.

Некоторые статистические данные: cachegrind сообщает мне, что для подхода с двойной привязкой имеется меньше ошибок ref/cache misss, но больше не хватает данных refs/cache. Разница не такая большая, хотя для обоих.

Edit: В соответствии с просьбой, структура данных, что меня интересует:

class Node { 
    ushort type; 
    union { 
     ushort axisID; 
     ushort childrenSize; 
    }; 
    union { 
     Model **models; 
     Node *rightChild; 
    }; 
    float leftPlane, rightPlane; 
    ... public methods and stuff ... 
} 

Я в принципе изменить Model **models к Model *models, а затем я получаю скорость купания. Класс Model сам содержит указатель на два абстрактных класса, Shape и Material. Все классы, упомянутые здесь, выделены блоком, за исключением Material, так как в данный момент я просто использую один.

Answer 1

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

Answer 2

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

Answer 3

Другой опросил вопрос о том, происходит ли замедление от добавленной косвенности или изменения в том, как вы распределяете struct Model. Поскольку теперь вы выделяете структуры Model как смежную область памяти, возможно, что смежные структуры могут совместно использовать одну и ту же линию кэша. Если ваши потоки одновременно обращаются к смежным структурам, они будут бороться за доступ. Один доступ для чтения останавливается для цикла шины, ожидая другого.

Что такое sizeof(class Model)? Вы можете попытаться расширить его с помощью фиктивных переменных до тех пор, пока класс не станет размером с вашей линией кэша.

Другая возможность заключается в том, что вы изменили выравнивание переменных-членов, к которым вы обращаетесь. Если ваш sizeof(class Model) не кратен размеру вашего компьютера (например, 8-байтов), тогда у массива таких объектов будут некоторые элементы, соответствующие размеру слова, а некоторые нет. Misalignment вызывает двойную выборку на шине памяти, поскольку блок выборки считывает машинные слова из выровненных мест памяти и компонует адресное значение из этих двух наборов.