Eu tenho uma única linha de código, que consome 25% - 30% do tempo de execução do meu aplicativo. É um comparador menor que um std :: set (o conjunto é implementado com uma Red-Black-Tree). É chamado cerca de 180 milhões de vezes em 28 segundos.

struct Entry {
  const float _cost;
  const long _id;

  // some other vars

    Entry(float cost, float id) : _cost(cost), _id(id) {
    } 
};



template<class T>
struct lt_entry: public binary_function <T, T, bool>
{
    bool operator()(const T &l, const T &r) const
    {
        // Most readable shape
        if(l._cost != r._cost) {
            return r._cost < l._cost;
        } else {
            return l._id < r._id;
        }
    }
};

As entradas devem ser classificadas por custo e se o custo é o mesmo pelo seu id. Eu tenho muitas inserções para cada extração do mínimo. Eu pensei em usar o Fibonacci-Heaps, mas me disseram que eles são teoricamente bons, mas sofrem de altas constantes e são muito complicados de implementar. E como a inserção está em O (log (n)), o aumento do tempo de execução é quase constante com n grande. Então eu acho que está tudo bem em ficar com o set.

Para melhorar o desempenho, tentei expressá-lo em diferentes formas:

return l._cost < r._cost || r._cost > l._cost || l._id < r._id;

return l._cost < r._cost || (l._cost == r._cost && l._id < r._id);

Até isso:

typedef union {
    float _f;
    int _i;
} flint;

//...

flint diff;
diff._f = (l._cost - r._cost);
return (diff._i && diff._i >> 31) || l._id < r._id;

Mas o compilador já parece bastante inteligente, porque não consegui melhorar o tempo de execução.

Eu também pensei sobre o SSE, mas esse problema não é muito aplicável para o SSE ...

A montagem parece um pouco assim:

movss  (%rbx),%xmm1
mov    $0x1,%r8d
movss  0x20(%rdx),%xmm0
ucomiss %xmm1,%xmm0
ja     0x410600 <_ZNSt8_Rb_tree[..]+96>
ucomiss %xmm0,%xmm1
jp     0x4105fd <_ZNSt8_Rb_[..]_+93>
jne    0x4105fd <_ZNSt8_Rb_[..]_+93>
mov    0x28(%rdx),%rax
cmp    %rax,0x8(%rbx)
jb     0x410600 <_ZNSt8_Rb_[..]_+96>
xor    %r8d,%r8d

Eu tenho uma experiência muito pequena com a linguagem assembly, mas não muito.

Eu pensei que seria o melhor (apenas?) Ponto para espremer algum desempenho, mas vale realmente a pena o esforço? Você consegue ver alguns atalhos que poderiam economizar alguns ciclos?

A plataforma em que o código será executado é um Ubuntu 12 com o gcc 4.6 (-stl = c ++ 0x) em uma máquina Intel de muitos núcleos. Apenas as bibliotecas disponíveis são boost, openmp e tbb. O benchmark de 30 segundos foi realizado no meu laptop antigo de 4 anos (core 2 duo).

Eu estou realmente presa nessa, parece tão simples, mas leva muito tempo. Eu tenho esmagado minha cabeça desde os dias pensando como eu poderia melhorar esta linha ...

Você pode me dar uma sugestão de como melhorar essa parte ou ela já está no seu melhor?

EDIT 1: Depois de usar a sugestão de Jerry consegui uma aceleração de ~ 4,5 segundos. EDIT 2: Depois de tentar impulsionar Fibonacci heaps a comparação foi para 174 milhões de chamadas para o menor que a função.