2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Найти среднее (С++)
Сообщение14.01.2019, 16:22 


27/08/16
9426
Legioner93 в сообщении #1368219 писал(а):
Пузырёк вручную и выводим второй элемент

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

 Профиль  
                  
 
 Найти среднее
Сообщение14.01.2019, 16:27 
Аватара пользователя


10/10/18
739
At Home
photon в сообщении #1368643 писал(а):
...
У меня нет возможности инструментально всё это выполнить-проверить, но даже такие ныне старые, как VC5 и VC6 (по моим воспоминаниям), справлялись со всем. У меня в проектах даже специально ассемблерные листинги были включены в проект и я это всегда смотрел-сравнивал (и Randall Hyde Great Debate и подобное читал).

1) Для бОльшей наглядности сложения можно заменить на |.
===
Это не имеет значения, всё это вместе с умножениями оптимизируется. Плюс считаю естественнее (в статье Википедии "Позиционная система счисления" стоит сумма). Кстати, с плюсом компилятору будет легче выяснить, всё ли есть в switch.

2) Статический анализатор может обругать такой код, сказав, что не все пути имеют return. Чтобы его удовлетворить, можно добавить поле default или воткнуть return за switch-ем.
===
Он должен (сколь помню) разобраться, что там всё перечислено. У вас есть возможность если, посмотрите с разными оптимизациями.

3) Нулевое возвращаемое значение является вполне корректным для данной функции - не очень красиво писать его в return без какой-либо дополнительной обработки, даже если программа туда никогда не зайдет. Кстати, а зачем выписывать варианты, которые не могут случиться?
===
И для красоты-симметрии и для помощи анализатору (2) и для "ровности" кода -- посмотрите в асме, что выходит при разных изменениях.

Если б мог, я бы всё это и сам посмотрел -- интересно же.

Онлайн-компиляторы асм выдают? Надо бы посмотреть, но с планшета это сложновато (и JS выключен почти всегда у меня).

-- 14.01.2019, 17:02 --

Используется синтаксис C++
int mid( int a, int b, int c )
{
  switch( (a<b)*4 + (b<c)*2 + (a<c)*1 )
  {
  case 0: return b; // 000: a>b, b>c, a>c
  case 1: return 0; // 001: a>b, b>c, a<c: cannot be
  case 2: return c; // 010: a>b, b<c, a>c
  case 3: return a; // 011: a>b, b<c, a<c
  case 4: return a; // 100: a<b, b>c, a>c
  case 5: return c; // 101: a<b, b>c, a<c
  case 6: return 0; // 110: a<b, b<c, a>c: cannot be
  case 7: return b; // 111: a<b, b<c, a<c
  }
}
...симметрично относительно центральной горизонтали (между 3 и 4).

Можно воспользоваться этой симметричностью:
Используется синтаксис C++
int mid( int a, int b, int c )
{
  switch( ((b<c)^(a<b))*2 + ((a<c)^(a<b))*1 )
  {
  case 0: return b;
  case 1: return 0;
  case 2: return c;
  case 3: return a;
  }
}


-- 14.01.2019, 17:20 --

Дальше можно воспользоваться и тем, что один результат не используется (схлопываем "0" и "c"):
Используется синтаксис C++
int mid( int a, int b, int c )
{
  switch( ((b<c)^(a<b)) + ((a<c)^(a<b)) )
  {
  case 0: return b;
  case 1: return c;
  case 2: return a;
  }
}

 Профиль  
                  
 
 Найти среднее (С++)
Сообщение14.01.2019, 18:02 
Аватара пользователя


10/10/18
739
At Home
Нашёл онлайн с асмом.

В первом варианте условных переходов нет, switch "решён" (x86-64 gcc 8.2 -O):
код: [ скачать ] [ спрятать ]
Используется синтаксис ASM
; mid(int, int, int):

        cmp     edi, esi
        setl    al
        movzx   eax, al
        cmp     esi, edx
        setl    cl
        movzx   ecx, cl
        add     ecx, ecx
        lea     ecx, [rcx+rax*4]
        cmp     edi, edx
        setl    al
        movzx   eax, al
        add     ecx, eax
        mov     ecx, ecx
        jmp     [QWORD PTR .L6[0+rcx*8]]
.L6:
        .quad   .L5
        .quad   .L7
        .quad   .L13
        .quad   .L10
        .quad   .L9
        .quad   .L13
        .quad   .L7
        .quad   .L5
.L7:
        mov     eax, 0
        ret
.L10:
        mov     eax, edi
        ret
.L9:
        mov     eax, edi
        ret
.L5:
        mov     eax, esi
        ret
.L13:
        mov     eax, edx
        ret

 Профиль  
                  
 
 Re: Найти среднее (С++)
Сообщение14.01.2019, 18:17 


27/08/16
9426
SergeCpp в сообщении #1368687 писал(а):
В первом варианте условных переходов нет, switch "решён".
Зато есть принципиально тут непредсказуемый переход по таблице по индексу. :mrgreen:

-- 14.01.2019, 18:27 --

Вот один из вариантов без переходов:

Используется синтаксис C++
int mid( int a, int b, int c )
{
    return -(b <= a && a <= c)  & a
        | -(a <= b && b <= c) & b
        | -(a <= c && c <= b) & c;
}


-- 14.01.2019, 18:41 --

SergeCpp в сообщении #1368687 писал(а):
Нашёл онлайн с асмом.


Самый быстрый вариант для этого компилятора (если я нигде не ошибся):

код: [ скачать ] [ спрятать ]
Используется синтаксис C++
inline void sortX(int& a, int& b)
{
    int x = -(a > b) & (a ^ b);
    a ^= x;
    b ^= x;
}

inline void sort(int& a, int& b)
{
    if (a > b)
    {
        int oldB = b;
        b = a;
        a = oldB;
    }
}

int mid( int a, int b, int c )
{
    sortX(a, b);
    sort(b, c);
    sort(a, b);
    return b;
}


код: [ скачать ] [ спрятать ]
Используется синтаксис ASM
        cmp     edi, esi
        setg    cl
        movzx   ecx, cl
        neg     ecx
        mov     eax, edi
        xor     eax, esi
        and     ecx, eax
        xor     esi, ecx
        cmp     esi, edx
        cmovg   esi, edx
        xor     ecx, edi
        cmp     ecx, esi
        mov     eax, esi
        cmovge  eax, ecx
        ret


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

UPD: ещё немного сократил выражения

 Профиль  
                  
 
 Оптимизатор
Сообщение14.01.2019, 18:55 
Аватара пользователя


10/10/18
739
At Home
Называется оптимизирующий компилятор 21 века...
Используется синтаксис ASM
        mov     ecx, ecx
...
.L10:
        mov     eax, edi
        ret
.L9:
        mov     eax, edi
        ret

 Профиль  
                  
 
 Re: Найти среднее (С++)
Сообщение14.01.2019, 19:05 


05/09/12
2587
Чет жестко :-) О0? С сохранением дебаг-информации для брейкпоинтов? Тогда еще может быть.

 Профиль  
                  
 
 Re: Найти среднее (С++)
Сообщение14.01.2019, 19:18 


27/08/16
9426
В варианте с тремя обычными sort (без sortX) в моём коде gcc зачем-то оставляет короткий условный переход, из-за чего и приходится извращаться с sortX. А вот x86-64 clang 7.0.0 компилирует его в следующий ассемблерный код:

Используется синтаксис ASM
        cmp     edi, esi
        mov     eax, edi
        cmovg   eax, esi
        cmovge  esi, edi
        cmp     esi, edx
        cmovg   esi, edx
        cmp     eax, esi
        cmovge  esi, eax
        mov     eax, esi
        ret
 


Но победитель, безусловно, ARM64 gcc 8.2:
Используется синтаксис ASM
        cmp     w0, w1
        csel    w3, w0, w1, le
        csel    w1, w1, w0, le
        cmp     w1, w2
        csel    w1, w1, w2, le
        cmp     w3, w1
        csel    w0, w3, w1, ge
        ret
 


UPD Пузырёк в обратную сторону экономит на x86-64 clang 7.0.0 ещё одну команду:

код: [ скачать ] [ спрятать ]
Используется синтаксис C++
inline void sort(int& a, int& b)
{
    if (a > b)
    {
        int oldB = b;
        b = a;
        a = oldB;
    }
}

int mid(int a, int b, int c)
{
    sort(b, c);
    sort(a, b);
    sort(b, c);
    return b;
}
 


Используется синтаксис ASM
        cmp     esi, edx
        mov     eax, esi
        cmovg   eax, edx
        cmovge  edx, esi
        cmp     eax, edi
        cmovl   eax, edi
        cmp     eax, edx
        cmovg   eax, edx
        ret
 

 Профиль  
                  
 
 Оптимизатор
Сообщение14.01.2019, 20:03 
Аватара пользователя


10/10/18
739
At Home
_Ivana в сообщении #1368701 писал(а):
... О0? С сохранением дебаг-информации для брейкпоинтов? Тогда еще может быть.
Если вы про моё замечание по моему примеру, то там "O", что есть "O1" и по документации и по проверке (добавить единичку или нолик и сравнить).
3.10 Options That Control Optimization

-- 14.01.2019, 20:05 --

realeugene в сообщении #1368707 писал(а):
...
Да, это хороший пример. Кстати, а может он есть в книге?

 Профиль  
                  
 
 Re: Найти среднее (С++)
Сообщение15.01.2019, 15:16 


27/08/16
9426
realeugene в сообщении #1368692 писал(а):
Вот один из вариантов без переходов:
Этот вариант ошибочный: условия неполные. Пожалуй, с пузырьком будет быстрее всего в любом случае.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу Пред.  1, 2

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group