4
votes

Fonction optimisée pour la constante de compilation

Supposons que j'ai une fonction de calcul de longueur vectorielle, qui a un paramètre supplémentaire inc (cela indique la distance entre les éléments voisins). Une implémentation simple serait:

calcLength(v, size, 1); // this should end up calcLength(v, size, Constant<1>());
calcLength(v, size, inc); // this should end up calcLength(v, size, Var(int));

Maintenant, calcLength peut être appelé avec deux types de paramètres inc : quand inc est connu au moment de la compilation, et quand il ne l'est pas. J'aimerais avoir une version optimisée de calcLength pour les valeurs courantes de compilation de inc (comme 1).

Donc, j'aurais quelque chose comme ceci:

int inc = <some_value>;
calcLength(v, size, Var(inc)); // inc is a non-compile-time constant here, less possibilities of compiler optimization

Donc, ceci peut être utilisé:

calcLength(v, size, Constant<1>()); // inc is a compile-time constant 1 here, calcLength can be vectorized

ou

template <int C>
struct Constant {
    static constexpr int value() {
        return C;
    }
};

struct Var {
    int v;

    constexpr Var(int p_v) : v(p_v) { }

    constexpr int value() const {
        return v;
    }
};

template <typename INC>
float calcLength(const float *v, int size, INC inc) {
        float l = 0;

        for (int i=0; i<size*inc.value(); i += inc.value()) {
            l += v[i]*v[i];
        }
        return sqrt(l);
    }
}

Ma question est la suivante: serait-il possible d'une manière ou d'une autre de conserver l'interface d'origine, et de mettre automatiquement Constant / Var , en fonction du type (compiler -time constante ou non) de inc?

float calcLength(const float *v, int size, int inc) {
    float l = 0;

    for (int i=0; i<size*inc; i += inc) {
        l += v[i]*v[i];
    }
    return sqrt(l);
}

Remarque: ceci est un exemple simple. Dans mon problème actuel, j'ai plusieurs fonctions comme calcLength , et elles sont volumineuses, je ne veux pas que le compilateur les intègre.


Note2: je suis ouvert à différentes approches également. En gros, j'aimerais avoir une solution qui remplisse ces conditions:

  • l'algorithme est spécifié une fois (très probablement dans une fonction de modèle)
  • si je spécifie 1 comme inc , une fonction spéciale instanciée et le code sera probablement vectorisé
  • si inc n'est pas une constante de compilation, une fonction générale est appelée
  • sinon (constante de compilation non-1): peu importe la fonction appelée


18 commentaires

AFAIK, à moins que la fonction entière ne soit constexpr , passer une constante de temps de compilation ne vous rapporte rien. Une chose que vous pouvez faire est de faire de la constante un paramètre de modèle non type. Ensuite, la valeur sera connue au moment de la compilation et le compilateur peut optimiser en conséquence.


@NathanOliver: d'après ce que je vois, c'est ce que je fais dans la question. Avec une différence: pour permettre les deux types de inc , il a un paramètre de modèle de type. Mais le résultat est le même.


Recherchez-vous if constexpr ?


Je veux dire une fonction comme template float calcLength (const float * v, int size) {utiliser inc ici comme valeur de compilation} .


@NathanOliver: votre suggestion a le même résultat que ma solution, si Constant est utilisé comme inc .


Avez-vous des repères conformes à votre conjoncture sur les «meilleures optimisations»? Je peux imaginer des cas hypothétiques si inc% 8 == 0 ou inc% 16 == 0, mais je ne serais pas sûr qu'il puisse être vectorisé beaucoup mieux.


@Dmitry: dans mon cas, si inc est connu à la compilation, ce sera 1 99% du temps. Et bien sûr, il peut être beaucoup mieux optimisé. Il a une énorme différence de vitesse.


@geza Je pense que "avez-vous des benchmarks" signifie "poster votre benchmark afin que je puisse vérifier que ma solution fonctionne".


@anatolyg: J'ai des repères, mais pas pour ce cas simple. Mais en réalité, cette question n'a pas besoin de référence. C'est plus une question de langue. En gros, j'aimerais avoir une fonction, qui peut être automatiquement compilée pour la constante de compilation. Mon code fonctionne, mais je n'aime pas la spécification manuelle Constant / Var . J'aimerais que ce soit automatique.


Vous avez donc la preuve que cette approche est en fait meilleure pour votre architecture que de simplement rendre la fonction en ligne et de laisser l'optimiseur s'en soucier? Ce serait bon d'expliquer ou du moins de le mentionner dans la question.


@aschepler: J'ai mentionné dans la question que j'avais plusieurs fonctions, et elles sont énormes. Je suis absolument sûr que le compilateur ne les intégrera pas en raison de leur taille. J'aurais besoin d'utiliser une fonction forceinline . Mais je ne veux pas, car la taille du code compilé sera beaucoup plus grande. Ce serait une erreur d'intégrer ces fonctions sur n'importe quelle architecture actuelle.


@JesperJuhl: Je ne sais pas comment je peux utiliser if constexpr dans mon problème, donc probablement pas.


Mais si inc n'est pas une constante de compilation mais avec la valeur 1 , quelle fonction doit être appelée? C'est OK, pour vous, si cela s'appelle la version Constant<1> ?


@ max66: en gros ce n'est jamais le cas. Mais je pense que je vois pourquoi vous demandez ceci: je pourrais ajouter une petite fonction de wrapper en ligne, qui vérifie pour 1. Je n'aime pas vraiment cette solution, car elle ajoute un if inutile pour le cas constant de non-compilation. Si c'est la seule solution, je continuerai à utiliser Constant / Var .


std :: integral_constant , mais cela ne semble pas avoir été efficace: godbolt.org/z/YuSK0L


Maintenant que j'ai activé les optimisations, les deux versions ont été calculées au moment de la compilation: godbolt.org/z/-s1xNS


Si la portabilité ne vous dérange pas trop, __builtin_constant_p est un excellent outil pour ce type d'optimisation.


Si vous utilisez GCC, comme @MarcGlisse l'a suggéré, __builtin_constant_p fonctionnerait, mais si les conditions sont toujours à l'exécution cet exemple ...


3 Réponses :


0
votes

C ++ ne permet pas de détecter si un paramètre de fonction fourni est une expression constante ou non, vous ne pouvez donc pas différencier automatiquement les littéraux fournis et les valeurs d'exécution.

Si le paramètre doit être un paramètre de fonction, et que vous ne souhaitez pas changer la façon dont il est appelé dans les deux cas, alors le seul levier dont vous disposez ici est le type du paramètre : vos suggestions pour Constante <1> () vs Var (inc) sont plutôt bonnes à cet égard.


0 commentaires

2
votes

Si l'objectif ici est simplement d'optimiser, plutôt que d'activer l'utilisation dans un contexte de compilation, vous pouvez donner au compilateur des indications sur votre intention:

// give the compiler a hint that it can optimize `f` with knowledge of `cond`
template<typename Func>
auto optimize_for(bool cond, Func&& f) {
    if (cond) {
        return std::forward<Func>(f)();
    }
    else {
        return std::forward<Func>(f)();
    }
}

float calcLength(const float *v, int size, int inc) {
    return optimize_for(inc == 1, [&]{
        float l = 0;
        for (int i=0; i<size*inc; i += inc) {
            l += v[i]*v[i];
        }
        return sqrt(l);
    });
}

Depuis godbolt , vous pouvez voir que calcLength_inner a été instancié deux fois, avec et sans la propagation constante.

Ceci est une astuce C (et est largement utilisée dans numpy), mais vous pouvez écrire un simple wrapper pour le rendre plus facile à utiliser en c ++:

static float calcLength_inner(const float *v, int size, int inc) {
    float l = 0;

    for (int i=0; i<size*inc; i += inc) {
        l += v[i]*v[i];
    }
    return sqrt(l);
}

float calcLength(const float *v, int size, int inc) {
    if (inc == 1) {
        return calcLength_inner(v, size, inc);  // compiler knows inc == 1 here, and will optimize
    }
    else {
        return calcLength_inner(v, size, inc);
    }
}


2 commentaires

Bonne prise sur le retour manquant, corrigé


Lien Godbolt ajouté



0
votes

Option 1: Faites confiance à votre compilateur (c'est-à-dire ne rien faire)

Les compilateurs peuvent-ils faire ce que vous voulez sans que vous leviez le petit doigt (eh bien, vous devez activer les compilations optimisées, mais cela va sans dire).

Les compilateurs peuvent créer ce qu'on appelle des "clones de fonction", qui font ce que vous voulez. Une fonction de clonage est une copie d'une fonction utilisée pour la propagation constante, c'est-à-dire l'assemblage résultant d'une fonction appelée avec des arguments constants. J'ai trouvé peu de documentation sur cette fonctionnalité, donc c'est à vous si vous voulez vous y fier.

Le compilateur peut totalement intégrer cette fonction, ce qui pourrait faire de votre problème un non-problème (vous pouvez l'aider en en le définissant en ligne dans un en-tête, en utilisant lto et / ou en utilisant des attributs spécifiques au compilateur comme __attribute__((always_inline)))

Maintenant, je ne prêche pas de laisser le compilateur faire son emploi. Bien que les optimisations du compilateur soient incroyables ces temps-ci et que la règle de base soit de faire confiance à l'optimiseur, il y a des situations où vous devez intervenir manuellement. Je dis juste d'en être conscient et d'en tenir compte. Oh, et comme toujours mesurer, mesurer, mesurer quand il s'agit de performances, n'utilisez pas votre instinct "Je sens ici que j'ai besoin d'optimiser".

Option 2: Deux surcharges

calcLength(v, size, inc); // ok
calcLength<1>(v, size);   // ok
calcLength(v, size, 1);   // nope

L'inconvénient ici est la duplication de code, ofc. Aussi peu de précautions doivent être prises sur le site d'appel:

float calcLength(const float *v, int size, int inc) {
    float l = 0;

    for (int i=0; i<size*inc; i += inc) {
        l += v[i]*v[i];
    }
    return sqrt(l);
}

template <int Inc>
float calcLength(const float *v, int size) {
    float l = 0;

    for (int i=0; i<size*inc; i += inc) {
        l += v[i]*v[i];
    }
    return sqrt(l);
}

Option 3: Votre version

Votre version est correcte.

h1>


1 commentaires

@geza proposition géniale, mais il semble qu'elle nécessite encore un travail considérable.