Самая быстрая факторная реализация с 64-битным результатом в сборке - PullRequest
Новая
       37

Самая быстрая факторная реализация с 64-битным результатом в сборке

4 голосов
/ 08 июля 2010

Это не домашняя работа, просто то, о чем я думаю.Таким образом, прямые вычисления факториала не совсем быстрые;Запоминание может помочь, но если результат должен соответствовать 32 или 64 битам, то факториал может работать только для входов 0 - 12 и 20 соответственно.Итак ... мы могли бы также использовать справочную таблицу: 

n   n!
0   1       
1   1       
2   2       
3   6       
4   24      
5   120     
6   720     
7   5040        
8   40320       
9   362880      
10  3628800     
11  39916800        
12  479001600       
13  6227020800  2^32=   4294967296
14  87178291200     
15  1.30767E+12     
16  2.09228E+13     
17  3.55687E+14     
18  6.40237E+15     
19  1.21645E+17     
20  2.4329E+18      
        2^64=   1.84467E+19

Итак, предположим, что я хочу иметь встроенную факториальную функцию C ++, которая использует встроенную сборку, с 32-разрядным или 64-разрядным целым числом без знака, ожидаемым какрезультат.Если входное значение либо отрицательное, либо достаточно большое, чтобы вызвать переполнение, выходное значение должно быть равно 0. Как это можно сделать в сборке, чтобы он занимал наименьшее количество циклов?Этот код будет работать на 64-битной архитектуре Intel / AMD.Если это возможно, я заинтересован в улучшении сценария наихудшего случая, поэтому 20! не должен занимать намного больше времени, чем 0! - надеюсь, есть подход бинарного поиска.Надеюсь, есть умный трюк для выполнения if (n == 0 || n == 1) { return 1; }.Кроме того, если выходные данные должны быть 32-разрядными, то я думаю, что инструкции по сборке могут содержать как код, так и данные в них.Мое знание сборки слабое.Пожалуйста, дайте мне знать, если вопрос не имеет большого смысла.

Было бы неплохо иметь возможность использовать функцию в C ++ - делает ее более реалистичной.Если, например, вызов функции стоит дорого, то попытка сохранить 1-2 такта в теле сборки не сильно поможет.

Ответы [ 6 ]

10 голосов
/ 09 июля 2010

Я умело построил таблицу поиска в сборке. На всякий случай, если вы ржавые на вашей сборке, Процедура ожидает, что параметр будет в регистре ecx. Я проверяю, что он находится в диапазоне, затем считываю значения таблицы поиска в регистры eax и edx. Если значение выходит за пределы диапазона, я просто записываю регистры eax и edx вместе с ними (это приводит к их 0). К сожалению, так как это процедура сборки, компилятор не сможет встроить код. Но я уверен, что те немногие циклы, которые я сохранил, написав мою классную процедуру сборки, будут более чем компенсировать любой выигрыш, встроенный. 

factorial:
    xorl    %eax, %eax
    xorl    %edx, %edx
    cmpl    $20, %ecx
    ja  .TOOBIG
    movl    CSWTCH.1(,%ecx,8), %eax
    movl    CSWTCH.1+4(,%ecx,8), %edx
.TOOBIG:

LOOKUP_TABLE:
    .section    .rodata
    .align 32
    .type   CSWTCH.1, @object
    .size   CSWTCH.1, 168
CSWTCH.1:
    .long   1
    .long   0
    .long   1
    .long   0
    .long   2
    .long   0
    .long   6
    .long   0
    .long   24
    .long   0
    .long   120
    .long   0
    .long   720
    .long   0
    .long   5040
    .long   0
    .long   40320
    .long   0
    .long   362880
    .long   0
    .long   3628800
    .long   0
    .long   39916800
    .long   0
    .long   479001600
    .long   0
    .long   1932053504
    .long   1
    .long   1278945280
    .long   20
    .long   2004310016
    .long   304
    .long   2004189184
    .long   4871
    .long   -288522240
    .long   82814
    .long   -898433024
    .long   1490668
    .long   109641728
    .long   28322707
    .long   -2102132736
    .long   566454140

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

static constexpr uint64_t const_factorial(uint32_t i) {
    return (i==0)? 1: (i * const_factorial(i-1));
}

uint64_t factorial(uint32_t i) {
    switch(i) {
        case 0: return const_factorial(0);
        case 1: return const_factorial(1);
        case 2: return const_factorial(2);
        case 3: return const_factorial(3);
        case 4: return const_factorial(4);
        case 5: return const_factorial(5);
        case 6: return const_factorial(6);
        case 7: return const_factorial(7);
        case 8: return const_factorial(8);
        case 9: return const_factorial(9);
        case 10: return const_factorial(10);
        case 11: return const_factorial(11);
        case 12: return const_factorial(12);
        case 13: return const_factorial(13);
        case 14: return const_factorial(14);
        case 15: return const_factorial(15);
        case 16: return const_factorial(16);
        case 17: return const_factorial(17);
        case 18: return const_factorial(18);
        case 19: return const_factorial(19);
        case 20: return const_factorial(20);
        default: return 0;
    }
}

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

5 голосов
/ 08 июля 2010

Прошло много времени с тех пор, как я согнул свои сборочные мышцы, поэтому я просто предложу несколько общих советов.

Поскольку вы заранее точно знаете, сколько и какого размера будут все элементы, просто создайте непрерывный массив значений (жестко запрограммированных или предварительно рассчитанных). После проверки правильности ввода в функцию (<0 или> 12/20) вы можете использовать простую адресацию смещения для получения соответствующего значения. Это будет работать за O (1) раз.

0 голосов
/ 09 июля 2010

Ответ GCC

... который, вероятно, бьет твой, был составлен из: 

uint64_t answers[] = {
    1ULL,
    1ULL,
    2ULL,
    6ULL,
    24ULL,
    ...
    2432902008176640000ULL,
};

uint64_t factorial(unsigned int i) {
    if(i >= sizeof(answers) / sizeof(*answers))
        return 0;
    else
        return answers[i];
}

... и сборка ... 

factorial:
    cmpl    $20, %edi
    movl    $0, %eax
    ja  .L3
    movslq  %edi,%eax
    movq    answers(,%rax,8), %rax
.L3:
    rep
    ret
answers:
    .quad 1
    .quad 1
    ...

... который кажется первым 64-битным ответом ассемблера ...

0 голосов
/ 09 июля 2010

Если вы работаете только с числами от 0 до 19, хеш-таблица или двоичное дерево являются избыточными.Просто создайте unsigned int[20] и запросите индекс: 

const unsigned int FACTORIALS[20] = {1,1,2,6,24,120,etc..};

unsigned int factorial(unsigned int num) {
    if(num >= 0 && num <= 19) {
        return FACTORIALS[num];
    }
    else {
        throw // some sort of exception
    }
}

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

0 голосов
/ 09 июля 2010

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

#include <map>

void main()
{
    std::map<int, BigIntThing> factMap;
    // insert all elements here, probably fancier ways to do this
    factMap.insert( 1 );
    factMap.insert( 1 );
    factMap.insert( 2 );
    // ....
    // to access, say 15!
    BigIntThing factMap[15]; // I think the index is right >_<
}

Вот и все. std::map заказывается, так что если у вашего BigIntThing есть оператор сравнения, все хорошо. Должен быть способ получить это const и / или static и / или global, чтобы скомпилировать его так, как вы хотите.

0 голосов
/ 08 июля 2010

Кто сказал, что ваша сборочная версия все равно будет быстрее, чем версия C ++. Фактически, кто сказал, что это будет даже соответствовать по скорости? Я бы поставил на $ 100, что вам никогда не удастся сделать это так быстро, как это делает компилятор.

...