Быстро генерирование «последовательность треугольника»: избежать mispredictions

Question

Я заинтересован в вычислении последовательности ^{треугольника 1}, который является последовательностью пара (i, j): (0, 0), (1, 0), (1, 1), (2, 0), (2, 1) ... которые итерация, хотя все пары (i, j) с тем ограничением, что i >= j. Интересна и такая же последовательность, но с ограничением i> j.

Эти последовательности представляют собой, среди прочих вещей, все способы, чтобы выбрать 2 (возможно, одинаковые) элементы из множества п-элемента (для последовательности по ), или индексы нижних triagular элементов матрица . Последовательность значений только для i составляет A003056 в OEIS, а j - A002262. Эта последовательность часто возникает в комбинаторных алгоритмах, где их производительность может быть критической.

Простой, но ветвистый способ генерации следующего значения в последовательности:

if (i == j) { 
    j = 0; 
    i++; 
    } else { 
    j++; 
    }  
} 

Однако, это страдает от многих mispredicts при расчете начальных элементов последовательности, при проверке состояния (i == j) - целом один неверный прогноз каждый раз, когда i увеличивается. По мере увеличения последовательности число ошибочных прогнозов становится ниже, так как i увеличивается с с уменьшенной частотой, поэтому ветвь j++ доминирует и хорошо предсказывается. Тем не менее, некоторые типы комбинаторного поиска многократно перебирают по небольшим терминам в последовательности, поэтому я ищу подход без ветвей или какой-то другой подход, который страдает меньшим количеством ошибочных прогнозов.

Для многих применений порядок последовательностей не так важен, поэтому получение значений в порядке differnet, чем указано выше, является допустимым, если оно приводит к лучшим решениям. Например, j может рассчитывать, а не вверх: (0, 0), (1, 1), (1, 0), (2, 2), (2, 1), ....

---

Я также заинтересован в зная, что правильное название для этой последовательности (возможно, так что я сделать больше прав на этот вопрос). Я просто вроде «треугольная последовательность».

Здесь, версия i >= j представляет суб-мультинаборы (повторение разрешено), в то время как i > j вариант представляет собой нормальные подмножества (нет повторения).

Здесь, версия i >= j включает в главной диагонали, в то время как i > j вариант исключает ее.

Answer 1

Вот две ветви свободных подходов, которые не используют любые дорогостоящие вычисления. Первый из них использует сравнение и логическое И:

const bool eq = i == j; 
i += eq; 
j = (j + 1) & (eq - 1); 

Второй вариант использует сравнение и умножение:

const bool eq = i == j; 
i += eq; 
j = (j + 1) * (1 - eq); 

В теории «умножение» вариант должен быть медленнее, чем «логический» один, но измерения показывают очень мало разницы ,

Оба подхода приведут к нераспределенному коду только для процессоров, которые позволяют проводить разветвленные сравнения (например, x86). Кроме того, эти подходы предполагают реализацию с использованием языка, где результаты условных выражений могут быть легко преобразованы в целые числа (например, C/C++, где «ложные» сравнения преобразуются в нулевые целые числа, а «истинные» - целые числа, равные « 1").

Единственная проблема с этими подходами - производительность. Они могли бы теоретически опередить разветвленный код, но только тогда, когда очень часто происходят ошибочные прогнозы. Простой тест, в котором нет другой работы помимо генерации «последовательности треугольников» (см. Его на ideone), показывает жалкую скорость неправильного предсказания, и поэтому оба нераспространенных метода примерно в 3 раза медленнее, чем разветвленные. Объяснение простое: для более длинных последовательностей должно быть не слишком много неверных прогнозов; как и для более коротких, современные процессоры имеют очень хорошие отраслевые предсказатели, которые почти никогда не сбой в случае коротких структур ветвления; поэтому у нас не так много ошибочных прогнозов, разветвленный код почти всегда выполняет только 2 команды (ср., increment), в то время как нераспространяемый код выполняет как активные, так и принудительные «ветви» плюс некоторые инструкции, характерные для нераспространяемого подхода.

---

В случае, если вы хотите repeatedly iterate over the small terms in the sequence, вероятно, другой подход был бы предпочтительнее. Вы вычисляете последовательность только один раз, затем многократно читаете ее из памяти.

Answer 2

Это кажется таким простым, что я уверен, что пропустил много ...но вы не только ищете вложенный цикл, как это (псевдокод)

for(i=0, i<4, i++) 
    for(j=0, j<i+1, j++) 
     print(i,j) 

Answer 3

Вы можете вывести из J I:

...set val... 
old_j = j; 
j = (j + 1) % (i + 1); 
if (i == old_j) { 
    i++; 
} 
...loop if more... 

И далее вывести я приращение от^и тока я:

...set val... 
old_j = j; 
j = (j + 1) % (i + 1); 
i = i + (i/old_j); 
...loop if more... 

(не могу проверить это на данный момент ... Пожалуйста, ознакомьтесь с)

Answer 4

В Python мы можем выразить это так:

i, j = i + (i == j), (j + 1) * (i != j) 

, но оказывается, на уровне около миллиона итераций или так, на моей машине, в следующем, более долго наматывается, ленивый код оценки составляет около 20% быстрее:

from itertools import count, repeat 

def gen_i(): 
    """ A003056 """ 
    for x in count(0): # infinitely counts up 
     yield from repeat(x, x + 1) # replication 

def gen_j(): 
    """ A002262 """ 
    for x in count(0): # infinitely counts up 
     yield from range(x + 1) # count up to (including) x 

sequence = zip(gen_i(), gen_j()) 

for _ in range(1000000): 
    i, j = next(sequence) 

В приведенном выше коде, gen_i(), gen_j(), count(), repeat() и zip() все генераторы (и range() итератор), так sequence продолжается т o вызов в код по требованию, поскольку требуются новые (i, j) пары. Я предполагаю, что реализация range() и repeat() прекращается с неправильным прогнозом.

Простой необязательно также быстрый (т. Е. Рассмотрите все ненужные добавления нуля и умножения на единицу в компактной форме.)

Итак, что более важно, быстро генерируя последовательность или избегая неверных предсказаний?