Эффективность 2 векторов по сравнению с вектором структур

Question

Я работаю над проектом на C++, где мне нужно искать через вектор, игнорирующий те, которые уже были посещены. Если кто-то посетил, я установил его соответствующее посещение в 1 и проигнорировал его. Какое решение выполняется быстрее?

Решение 1:

vector<string> stringsToVisit; 
vector<int> stringVisited; 

for (int i = 0; i < stringToVisit.size(); ++i) { 
    if (stringVisited[i] == 0) { 
     string current = stringsToVisit[i]; 
     ...Do Stuff... 
     stringVisited[i] = 1; 
    } 
} 

или

Решение 2:

struct StringInfo { 
    string myString; 
    int visited = 0; 
} 

vector<StringInfo> stringsToVisit; 

for (int i = 0; i < stringsToVisit.size(); ++i) { 
    if (stringsToVisit[i].visited == 0) { 
     string current = stringsToVisit[i].myString; 
     ...Do Stuff... 
     stringsToVisit[i].visited = 1; 
    } 
} 

Answer 1

Решение 1 быстрее, чем решение 2, потому что, когда компилятор решает stringVisited [я] просто имеет для добавления смещения (i) к базовому адресу (stringVisited), во втором решении также необходимо добавить смещение члена struct (visit).

Answer 2

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

Тем не менее, вот мой ответ:

time complexity обоих растворов O (п), так что мы говорим только о постоянной фактор оптимизации здесь.

Решение 1 требует поиска двух разных блоков памяти: stringsToVisit [i] и stringVisited [i] в ​​каждом цикле. Это не подходит для CPU caches, по сравнению с решением 2, каждая итерация цикла обращается к одной структуре, хранящейся в смежных местах в памяти. Таким образом, решение 2 будет работать лучше.

Решение 2 потребует более сложного поиска косвенной памяти, чем решение 1 для доступа к свойству visited структуры: (base address of stringsToVisit) + (index) * (struct size) + (displacement in struct). Тем не менее, этот вид поиска хорошо вписывается в основную архитектуру процессоров SIB (scale-index-base), поэтому он будет компилироваться только с одной инструкцией по сборке, поэтому не будет много медлительности, если таковая вообще есть. Стоит отметить, что оптимизирующий компилятор может заметить, что вы последовательно получаете доступ к памяти и выполняете оптимизацию, чтобы полностью не использовать адресацию SIB.

Следовательно, решение 2, скорее всего, будет быстрее.

Answer 3

Как отмечает Бернард, сложность времени и памяти обоих предлагаемых решений идентична, и немного более сложная адресация, требуемая вторым решением, не замедлит работу современных процессоров. Но я не согласен с его предложением о том, что «Решение 2 скорее всего будет быстрее». Мы действительно недостаточно знаем, чтобы даже сказать, что теоретически это должно быть быстрее, и, за исключением, возможно, нескольких дегенеративных ситуаций, разница в фактической производительности, вероятно, будет неизмеримой.

Первая итерация цикла, скорее всего, будет медленнее. Кэш холодный, и для первого решения требуется две строки кэша для хранения первых элементов, а для второго - только один. Но после этого оба решения делают прямой линейный обход. У CPU не будет проблем с предварительной загрузкой дополнительных строк кеша, поэтому в большинстве ситуаций эти первоначальные дополнительные накладные расходы вряд ли будут иметь большое значение.

С другой стороны, вы записываете данные в этом цикле, поэтому некоторые из линий кэша, к которым вы обращаетесь, также становятся помеченными грязными (что означает, что их данные должны быть записаны обратно в общий кэш или основную память в конечном итоге, и они очиститься от других кеш-ядер).В решении 1, в зависимости от sizeof(string) и sizeof(int), только 5-25% строк кэша становятся грязными. Решение 2, однако, каждый триллер, поэтому он может использовать большую пропускную способность памяти.

Так, некоторые вещи, которые могут сделать раствор-быстрее, являются:

• Список строк обрабатываемым чрезвычайно короток
• ...Do Stuff... является (достаточно очень сложен, так что строки кэша, удерживающие данных очиститься из кэша L1)

некоторых вещей, которые могут сделать раствор 1 или более быстрым, чем решение 2:

• Списка строк Обрабатываемый умеренный до большого
• ...Do Stuff... не очень сложен, поэтому кэш остается теплым
• Программы многопоточный, а другой поток хочет читать данные из stringsToVisit одновременно.

Суть в том, что это, вероятно, не имеет значения.