Самый быстрый способ вычислить порядок величины в сборке x86

12

Задача проста: написать сборку, которая вычисляет порядок целого числа, используя как можно меньше тактов.

  • Порядок величины определяется как log10, нет log2.
  • Диапазон допустимых значений: 0до , включительно. Поведение для ввода за пределами этого диапазона не определено.1012
  • Значения должны быть округлены до ближайшего целого, за исключением того, что при заданном входном значении 0выходные данные должны быть 0. (Вы можете считать это лучшим представлением отрицательной бесконечности, которое возможно в целых числах без знака).
  • Должна быть сборка х86.
  • Целое число должно быть во время выполнения значения, а не статическое / инлайн целого числа. Поэтому мы не знаем, что это во время компиляции.
  • Предположим, что у вас уже есть целое число, загруженное в регистр. (Но для ясности включите установку значения в регистр в ответ).
  • Невозможно вызвать какие-либо внешние библиотеки или функции.
  • Бесплатно использовать любые доступные инструкции в документации Intel .
  • Нет C.
  • Любая из ~ 7 архитектур Intel Core является приемлемой (перечислены на стр. 10 ). В идеале Nehalem (Intel Core i7).

Победившим ответом является тот, который использует наименьшее возможное количество тактов. То есть он может иметь наибольшее количество операций в секунду. С краткими сведениями о цикле часов можно ознакомиться здесь: http://www.agner.org/optimize/instruction_tables.pdf . Расчет тактов может произойти после публикации ответа.

math fastest-algorithm assembly Лэнс Поллард
источник
Разрешены ли 'FYL2X' и другие инструкции FPU?
Цифровая травма
1
Должен ли результат быть целым числом? Если так, как это должно быть округлено?
Цифровая травма
3
Таким образом, вход и выход являются целыми числами, да? Но входное значение может достигать 10 ^ 12, поэтому оно слишком велико для 32-битного целого. Итак, мы принимаем 64-битное целочисленное значение?
Пол Р
3
Критерий выигрыша основан на максимальном или среднем количестве циклов? И если это среднее, каково распределение входов?
Runer112
2
Какой процессор предназначен? В связанном документе перечислены более 20 различных процессов (AMD, Intel и др.), И время ожидания значительно варьируется.
Цифровая травма

Ответы:

8

7 циклов, постоянное время

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

    .intel_syntax noprefix
    .globl  main
main:
    mov rdi, 1000000000000              #;your value here
    bsr rax, rdi
    movzx   eax, BYTE PTR maxdigits[1+rax]
    cmp rdi, QWORD PTR powers[0+eax*8]
    sbb al, 0
    ret
maxdigits:
    .byte   0
    .byte   0
    .byte   0
    .byte   0
    .byte   1
    .byte   1
    .byte   1
    .byte   2
    .byte   2
    .byte   2
    .byte   3
    .byte   3
    .byte   3
    .byte   3
    .byte   4
    .byte   4
    .byte   4
    .byte   5
    .byte   5
    .byte   5
    .byte   6
    .byte   6
    .byte   6
    .byte   6
    .byte   7
    .byte   7
    .byte   7
    .byte   8
    .byte   8
    .byte   8
    .byte   9
    .byte   9
    .byte   9
    .byte   9
    .byte   10
    .byte   10
    .byte   10
    .byte   11
    .byte   11
    .byte   11
    .byte   12
powers:
    .quad   0
    .quad   10
    .quad   100
    .quad   1000
    .quad   10000
    .quad   100000
    .quad   1000000
    .quad   10000000
    .quad   100000000
    .quad   1000000000
    .quad   10000000000
    .quad   100000000000
    .quad   1000000000000

Компилируется в GCC 4.6.3 для Ubuntu и возвращает значение в коде выхода.

Я не уверен, что интерпретирую эту таблицу циклов для любого современного процессора, но, используя метод @ DigitalTrauma на процессоре Nehalim, я получаю 7 ?

ins        uOps Latency
---        -    - 
BSR r,r  : 1    3
MOVZX r,m: 1    -
CMP m,r/i: 1    1 
SBB r,r/i: 2    2
AShelly
источник
О - видел DigitalTrauma после того, как я начал писать свой. Похожие идеи. Используя его методологию подсчета, я думаю, что получить 3,1,1,1 = 6 для BSR, MOV, CMP, SBB
AShelly
Да, я думаю, что ваш бьет мой. Просто покажу а) я не программист на ассемблере и б) сборку лучше оставить нам, простым смертным ;-)
Digital Trauma
The integer must be a runtime value, not a static/inline integer. So we don't know what it is at compile time.
кот
1
правильно, а в следующей строке написано: «Предположим, что у вас уже есть целое число, загруженное в регистр (но для ясности включите установку значения в регистр в ответе»). Что я и сделал.
AShelly
замените movzx eax на mov al. Верхние 24 бита eax уже будут равны нулю, поэтому zx является избыточным (и дорогим).
Питер Ферри
6

Наилучший случай 8 циклов, наихудший случай 12 циклов

Поскольку это не ясно в вопросе, я основываю это на задержках Ivy Bridge.

Подход здесь состоит в том, чтобы использовать bsr(обратное сканирование битов) инструкцию как log2 () бедного человека. Результат используется в качестве индекса в таблице переходов, которая содержит записи для битов от 0 до 42. Я предполагаю, что, учитывая, что операция с 64-битными данными неявно требуется, тогда использование bsrинструкции в порядке.

В лучшем случае входные данные с помощью таблицы переходов могут отображать bsrрезультат непосредственно на величину. Например, для входных данных в диапазоне 32-63, bsrрезультат будет 5, который отображается на величину 1. В этом случае путь инструкции:

Instruction    Latency

bsrq                 3
jmp                  2
movl                 1
jmp                  2

total                8

В наихудших входных данных bsrрезультат будет отображаться с двумя возможными значениями, поэтому элемент с перемычкой делает еще одну дополнительную cmpпроверку , чтобы определить, является ли входное значение> 10 n . Например, для входов в диапазоне 64-127 bsrрезультат будет 6. Соответствующая запись с перемычкой затем проверяет, является ли вход> 100, и соответственно устанавливает величину выхода.

В дополнение к пути наихудшего случая у нас есть дополнительная инструкция mov для загрузки непосредственного 64-битного значения для использования в cmp, так что путь инструкции наихудшего случая:

Instruction    Latency

bsrq                 3
jmp                  2
movabsq              1
cmpq                 1
ja                   2
movl                 1
jmp                  2

total               12

Вот код:

    /* Input is loaded in %rdi */
    bsrq    %rdi, %rax
    jmp *jumptable(,%rax,8)
.m0:
    movl    $0, %ecx
    jmp .end
.m0_1:
    cmpq    $9, %rdi
    ja  .m1
    movl    $0, %ecx
    jmp .end
.m1:
    movl    $1, %ecx
    jmp .end
.m1_2:
    cmpq    $99, %rdi
    ja  .m2
    movl    $1, %ecx
    jmp .end
.m2:
    movl    $2, %ecx
    jmp .end
.m2_3:
    cmpq    $999, %rdi
    ja  .m3
    movl    $2, %ecx
    jmp .end
.m3:
    movl    $3, %ecx
    jmp .end
.m3_4:
    cmpq    $9999, %rdi
    ja  .m4
    movl    $3, %ecx
    jmp .end
.m4:
    movl    $4, %ecx
    jmp .end
.m4_5:
    cmpq    $99999, %rdi
    ja  .m5
    movl    $4, %ecx
    jmp .end
.m5:
    movl    $5, %ecx
    jmp .end
.m5_6:
    cmpq    $999999, %rdi
    ja  .m6
    movl    $5, %ecx
    jmp .end
.m6:
    movl    $6, %ecx
    jmp .end
.m6_7:
    cmpq    $9999999, %rdi
    ja  .m7
    movl    $6, %ecx
    jmp .end
.m7:
    movl    $7, %ecx
    jmp .end
.m7_8:
    cmpq    $99999999, %rdi
    ja  .m8
    movl    $7, %ecx
    jmp .end
.m8:
    movl    $8, %ecx
    jmp .end
.m8_9:
    cmpq    $999999999, %rdi
    ja  .m9
    movl    $8, %ecx
    jmp .end
.m9:
    movl    $9, %ecx
    jmp .end
.m9_10:
    movabsq $9999999999, %rax
    cmpq    %rax, %rdi
    ja  .m10
    movl    $9, %ecx
    jmp .end
.m10:
    movl    $10, %ecx
    jmp .end
.m10_11:
    movabsq $99999999999, %rax
    cmpq    %rax, %rdi
    ja  .m11
    movl    $10, %ecx
    jmp .end
.m11:
    movl    $11, %ecx
    jmp .end
.m11_12:
    movabsq $999999999999, %rax
    cmpq    %rax, %rdi
    ja  .m12
    movl    $11, %ecx
    jmp .end
.m12:
    movl    $12, %ecx
    jmp .end

jumptable:
    .quad   .m0
    .quad   .m0
    .quad   .m0
    .quad   .m0_1
    .quad   .m1
    .quad   .m1
    .quad   .m1_2
    .quad   .m2
    .quad   .m2
    .quad   .m2_3
    .quad   .m3
    .quad   .m3
    .quad   .m3
    .quad   .m3_4
    .quad   .m4
    .quad   .m4
    .quad   .m4_5
    .quad   .m5
    .quad   .m5
    .quad   .m5_6
    .quad   .m6
    .quad   .m6
    .quad   .m6
    .quad   .m6_7
    .quad   .m7
    .quad   .m7
    .quad   .m7_8
    .quad   .m8
    .quad   .m8
    .quad   .m8_9
    .quad   .m9
    .quad   .m9
    .quad   .m9
    .quad   .m9_10
    .quad   .m10
    .quad   .m10
    .quad   .m10_11
    .quad   .m11
    .quad   .m11
    .quad   .m11_12
    .quad   .m12
    .quad   .m12
    .quad   .m12

.end:
/* output is given in %ecx */

В основном это было сгенерировано из вывода ассемблера gcc для написанного мной кода на языке C для проверки концепции . Обратите внимание, что код C использует вычислимое goto для реализации таблицы переходов. Он также использует __builtin_clzll()встроенный gcc, который компилируется в bsrинструкцию (плюс an xor).

Я рассмотрел несколько решений, прежде чем прийти к этому:

  • FYL2Xрассчитать натуральный логарифм, затем FMULпо необходимой константе. Это, вероятно, выиграло бы это, если бы это был конкурс [tag: инструкция: гольф]. Но FYL2Xимеет время ожидания 90-106 для Ivy Bridge.

  • Жестко закодированный бинарный поиск. Это на самом деле может быть конкурентоспособным - я оставлю это кому-то другому для реализации :).

  • Полная таблица результатов поиска. Это, я уверен, теоретически самый быстрый, но потребует таблицы поиска в 1 ТБ - пока не практично - возможно, через несколько лет, если закон Мура будет продолжать действовать.

Цифровая травма
источник
При необходимости я могу рассчитать среднюю задержку для всех разрешенных входных данных.
Цифровая травма
jmpи jccне имеют задержки, только затраты на пропускную способность. Предсказание ветвлений + спекулятивное выполнение означают, что управляющие зависимости не являются частью цепочек зависимостей данных.
Питер Кордес