За программирование без ветвлений

Современной парадигмой программирования следует считать состояние схожести функционирования аппаратных и программных средств компьютера. На практике это означает отсутствие явного ветвления в алгоритме. Программа переходит из одного состояния в другое как функциональный автомат. Разработан алгоритм сравнения целых чисел без использования команд ветвления. Результат действия метода сравнения дает целое число 0 или 1, в зависимости от значений сравниваемых величин. Это значение можно использовать для скрытого ветвления, путем вызова метода из двумерного массива методов по индексу 0 (нет)или 1 (да).
Трудность в том, что метод закрыт для внешней оболочки и его трудно встроить в общую канву основного метода . Есть ли мысли по поводу реализации этой возможности?

0

Сообщение от B_S_V Трудность в том, что метод закрыт для внешней оболочки и его трудно встроить в общую канву основного метода .

Для кого закрыт? Почему закрыт?

0

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

0

Сообщение от B_S_V Если вызываем отдельный метод, то локальные переменные исходного метода в нем недоступны.

Смотря как определять метод.
А зачем нам локальные переменные исходного метода?

Сообщение от B_S_V Отсутствие ветвлений, т.е явных вызовов if позволяет избежать спекулятивных вычислений, что повышает производительность программы.

Каких именно вычислений позволяет избежать?

0

Сообщение от Shamil1 Смотря как определять метод. А зачем нам локальные переменные исходного метода?

Теряется контекст ситуации ветвления: переменные, метки.

Сообщение от Shamil1 Каких именно вычислений позволяет избежать?

Спекулятивных.

0

Сообщение от B_S_V Теряется контекст ситуации ветвления: переменные, метки.

У нас есть метод, в котором осуществляется ветвление. Зачем методам, которые он вызывает или из которых он вызывается, контекст ситуации ветвления?

Сообщение от B_S_V Спекулятивных.

Что Вы называете "спекулятивными вычислениями" и каким образом использования таблицы переходов позволяет их избежать?

0

Если метод ветвления, абсолютно изолирован от основного метода, то – да, контекст не важен. Бывают ситуации, в вызываемом блоке требуется изменение переменных основного блока. В этом загвоздка.
Что касается спекулятивных вычислений, проверено тестом, программа выполняет не одну ветвь (один метод), а обе ветви. Видно по времени выполнения программы. В конце неправильная ветвь отбрасывается. Это собственно и подвигло на борьбу с ветвлением

0

Проведите тесты, проверьте

0

Сообщение от B_S_V Что касается спекулятивных вычислений, проверено тестом, программа выполняет не одну ветвь (один метод), а обе ветви. Видно по времени выполнения программы.

Программа не выполняет обе ветви.

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

Алгоритм сравнения целых чисел без использования команд ветвления разработан очень давно. Применение этого трюка полезно, когда получаемые 0/1 можно напрямую использовать в дальнейших вычислениях.
Он описан в классической литературе (например, Алгоритмические трюки для программистов) и используется в классических программных продуктах (например, The GNU Multiple Precision Arithmetic Library).

0

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

Вопрос решен. Всем спасибо за обстоятельное обсуждение.

0

Сообщение от B_S_V При альтернативном выполнении двух объемных методов, потери производительности могут быть огромными.

Потери производительности будут только если программист по ошибке явным образом попросит программу выполнить оба метода. С ветвлением это никак не связано.

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

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

В конструкции if (условие) then (блок 1) else (блок 2) end вычисляется только один блок кода.
Если предсказатель переходов угадает, то этот нужный блок кода начнёт вычисляться еще до того, как вычислено условие. Если предсказатель переходов не угадает, то это нужный блок кода начнёт вычисляться сразу после того, как вычислено условие. И именно с этим связаны задержки. Предлагаемый Вами метод решения проблемы не позволяет гарантированно начать вычисление нужного блока кода до того как вычислено условие, поэтому заявленную проблему не решает.

0

Провел тестирование. Абсолютно одинаковый результат, что выполнение через индекс, что ветвление по if. Возможно в программе была ошибка ( код давно утерян).
Соревнование двух подходов можно считать закончившимся ничьей. Если нет особых возражений, конечно.

Добавлено через 2 часа 25 минут
Запись ветвления через индексацию, представляет единое выражение, допускающее использование в качестве отдельного элемента программирования. Например, можно указать в качестве аргумента метода.

func [ (((uint) (((x - y) & 0x80000000) >> 31) + ( (uint) ((y - x) & 0x80000000) >> 31))) ^ 0x00000001] (x,y);

1