Здравствуйте, tranzit, Вы писали:

T>в исходной задаче не было функции. Но с учетом тела функции сравни

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

T>обрати внимание на цикл и количество обращений к памяти

По одному обращению на итерацию, и там и там в cmp. А ты сколько насчитал?
И кстати, у тебя нет проверки на входные first==last.

И судя по всему тебя не O3 интересует, а Os:

#include <algorithm>

int *concrete_test(int *first, int *last)
{
    return std::partition_point(first, last, [](int x){ return x > 42; });
}

g++ -std=c++11 -Os -DNDEBUG -Wall -pedantic main.cpp -S && cat main.s

    .file    "main.cpp"
    .text
    .globl    _Z13concrete_testPiS_
    .type    _Z13concrete_testPiS_, @function
_Z13concrete_testPiS_:
.LFB799:
    .cfi_startproc
    subq    %rdi, %rsi
    movq    %rdi, %rax
    sarq    $2, %rsi
.L3:
    testq    %rsi, %rsi
    jle    .L2
    movq    %rsi, %rdx
    sarq    %rdx
    leaq    (%rax,%rdx,4), %rcx
    cmpl    $42, (%rcx)
    jg    .L7
    movq    %rdx, %rsi
    jmp    .L3
.L7:
    subq    %rdx, %rsi
    leaq    4(%rcx), %rax
    decq    %rsi
    jmp    .L3
.L2:
    ret
    .cfi_endproc
.LFE799:
    .size    _Z13concrete_testPiS_, .-_Z13concrete_testPiS_
    .ident    "GCC: (GNU) 6.1.0"
    .section    .note.GNU-stack,"",@progbits

LIVE DEMO

Здравствуйте, tranzit, Вы писали:

T>в исходной задаче не было функции. Но с учетом тела функции сравни

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

T>обрати внимание на цикл и количество обращений к памяти

По одному обращению на итерацию, и там и там в cmp. А ты сколько насчитал?
И кстати, у тебя нет проверки на входные first==last.

И судя по всему тебя не O3 интересует, а что-то типа Os:

#include <algorithm>

int *concrete_test(int *first, int *last)
{
    return std::partition_point(first, last, [](int x){ return x > 42; });
}

g++ -std=c++11 -Os -DNDEBUG -Wall -pedantic main.cpp -S && cat main.s

    .file    "main.cpp"
    .text
    .globl    _Z13concrete_testPiS_
    .type    _Z13concrete_testPiS_, @function
_Z13concrete_testPiS_:
.LFB799:
    .cfi_startproc
    subq    %rdi, %rsi
    movq    %rdi, %rax
    sarq    $2, %rsi
.L3:
    testq    %rsi, %rsi
    jle    .L2
    movq    %rsi, %rdx
    sarq    %rdx
    leaq    (%rax,%rdx,4), %rcx
    cmpl    $42, (%rcx)
    jg    .L7
    movq    %rdx, %rsi
    jmp    .L3
.L7:
    subq    %rdx, %rsi
    leaq    4(%rcx), %rax
    decq    %rsi
    jmp    .L3
.L2:
    ret
    .cfi_endproc
.LFE799:
    .size    _Z13concrete_testPiS_, .-_Z13concrete_testPiS_
    .ident    "GCC: (GNU) 6.1.0"
    .section    .note.GNU-stack,"",@progbits

LIVE DEMO