Как устройство Вареного пудинга работает?

объяснение в Журнале доктора Dobb является лучшим, который я нашел по теме.

Этот являющийся моим АГА момент:

for (i = 0; i < len; ++i) {
    HAL_IO_PORT = *pSource++;
}

становится:

int n = len / 8;
for (i = 0; i < n; ++i) {
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
}

n = len % 8;
for (i = 0; i < n; ++i) {
    HAL_IO_PORT = *pSource++;
}

становится:

int n = (len + 8 - 1) / 8;
switch (len % 8) {
    case 0: do { HAL_IO_PORT = *pSource++;
    case 7: HAL_IO_PORT = *pSource++;
    case 6: HAL_IO_PORT = *pSource++;
    case 5: HAL_IO_PORT = *pSource++;
    case 4: HAL_IO_PORT = *pSource++;
    case 3: HAL_IO_PORT = *pSource++;
    case 2: HAL_IO_PORT = *pSource++;
    case 1: HAL_IO_PORT = *pSource++;
               } while (--n > 0);
}

Точка устройства вареных пудингов должна сократить количество сравнений, сделанных в трудной memcpy реализации.

предположим Вы хотите скопировать байты 'количества' от до b, прямой подход должен сделать следующее:

  do {                      
      *a = *b++;            
  } while (--count > 0);

, Сколько раз необходимо сравнить количество, чтобы видеть, является ли это вышеупомянутый 0? времена 'количества'.

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

Теперь предполагают, что Вы хотите скопировать 20 байтов с помощью устройства вареных пудингов, в каком количестве сравнений Вы нуждались бы? Только 3, так как Вы копируете восемь байтов за один раз кроме <забастовка> в последний раз сначала та, где Вы копируете всего 4.

ОБНОВЛЕННЫЙ: Вы не должны делать 8 comparisons/case-in-switch операторов, но это разумно компромисс между функциональным размером и скоростью.

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

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

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

Хотя я не на 100% уверен, что Вы просите, здесь идет...

проблема, что адреса устройства Вареного пудинга являются одним из раскручивания цикла (как Вы будете несомненно видеть на Wiki, связывают Вас отправленный). То, к чему это в основном приравнивается, является оптимизацией эффективности во время выполнения по объему потребляемой памяти. Устройство вареного пудинга имеет дело с последовательным копированием, а не просто любой старой проблемой, но является классическим примером того, как оптимизации могут быть сделаны путем сокращения количества раз, что сравнение должно быть сделано в цикле.

, Поскольку альтернативный пример, который может помочь понять, предполагает, что у Вас есть массив объектов, которые Вы хотите циклично выполнить и добавить 1 к ним каждый раз... обычно, Вы могли бы использовать для цикла и цикла приблизительно 100 раз. Это кажется довольно логичным и, это... однако, оптимизация может быть сделана путем раскручивания цикла (очевидно, не слишком далеко..., или Вы не можете также просто использовать цикл).

Так постоянный клиент для цикла:

for(int i = 0; i < 100; i++)
{
    myArray[i] += 1;
}

становится

for(int i = 0; i < 100; i+10)
{
    myArray[i] += 1;
    myArray[i+1] += 1;
    myArray[i+2] += 1;
    myArray[i+3] += 1;
    myArray[i+4] += 1;
    myArray[i+5] += 1;
    myArray[i+6] += 1;
    myArray[i+7] += 1;
    myArray[i+8] += 1;
    myArray[i+9] += 1;
}

, Что делает устройство Вареного пудинга, реализовывают эту идею, в C, но (как Вы видели на Wiki) с последовательными копиями. То, что Вы видите выше с раскрученным примером, является 10 сравнениями по сравнению с 100 в оригинале - это составляет несовершеннолетнего, но возможно значительный, оптимизация.

Когда я прочитал это в первый раз, я автоматически отформатировал его в это

void dsend(char* to, char* from, count) {
    int n = (count + 7) / 8;
    switch (count % 8) {
        case 0: do {
                *to = *from++;
                case 7: *to = *from++;
                case 6: *to = *from++;
                case 5: *to = *from++;
                case 4: *to = *from++;
                case 3: *to = *from++;
                case 2: *to = *from++;
                case 1: *to = *from++;
            } while (--n > 0);
    }
}

и понятия не имел, что происходит.

Возможно, не тогда, когда этот вопрос задавался, но теперь В Википедии есть очень хорошее объяснение

Устройство является допустимым, разрешенным C на основании двух атрибутов в C:

• Смягченная спецификация оператора switch в определение языка. На момент изобретения устройства это было первое издание языка программирования C, которое требует только, чтобы управляемый оператор переключателя был синтаксически допустимым (составным) оператором, в котором метки case могут стоять перед любым подоператором. В сочетании с тем фактом, что в отсутствие оператора break поток управления будет переходить от оператора, управляемого одной меткой case, к оператору, управляемому следующей меткой, это означает, что код определяет последовательность количества копий из последовательные исходные адреса к отображаемому в памяти выходному порту.
• Возможность легально прыгнуть в середину цикла в C.