Forcer GCC à effectuer une déconnexion de boucle des contrôles de taille d'exécution memcpy?

Question

Est-il un moyen fiable pour forcer la GCC (ou n'importe quel compilateur) à facteur d'exécution de la taille des contrôles en memcpy() à l'extérieur d'une boucle (où que la taille n'est pas constante à la compilation, mais constante à l'intérieur de cette boucle), spécialiste de la boucle pour chaque gamme de taille plutôt qu'à plusieurs reprises la vérification de la taille du sein?

C'est un cas de test réduite à partir d'une régression de la performance signalé ici pour une bibliothèque open source conçue pour l'efficacité en mémoire l'analyse de grands ensembles de données. _{(La régression se produit à cause d'un de mes commits...)}

Le code d'origine est en Cython, mais je l'ai réduite à une pure C proxy comme suit:

void take(double * out, double * in,
          int stride_out_0, int stride_out_1,
          int stride_in_0, int stride_in_1,
          int * indexer, int n, int k)
{
    int i, idx, j, k_local;
    k_local = k; /* prevent aliasing */
    for(i = 0; i < n; ++i) {
        idx = indexer[i];
        for(j = 0; j < k_local; ++j)
            out[i * stride_out_0 + j * stride_out_1] =
            in[idx * stride_in_0 + j * stride_in_1];
    }
}

Les progrès sont variables; en général, les tableaux ne sont même pas garanti d'être contiguës (étant donné qu'ils peuvent être non-contigus tranches de grands tableaux). Cependant, pour le cas particulier de c-tableaux contigus, j'ai optimisé le ci-dessus pour les éléments suivants:

void take(double * out, double * in,
          int stride_out_0, int stride_out_1,
          int stride_in_0, int stride_in_1,
          int * indexer, int n, int k)
{
    int i, idx, k_local;
    assert(stride_out_0 == k);
    assert(stride_out_0 == stride_in_0);
    assert(stride_out_1 == 1);
    assert(stride_out_1 == stride_in_1);
    k_local = k; /* prevent aliasing */
    for(i = 0; i < n; ++i) {
        idx = indexer[i];
        memcpy(&out[i * k_local], &in[idx * k_local],
               k_local * sizeof(double));
    }
}

(Les assertions ne sont pas présents dans le code d'origine; au lieu de cela, il vérifie la continuité et l'appelle la version optimisée si possible, et le unoptimized, si ce n'.)

Cette version optimise très bien dans la plupart des cas, depuis l'utilisation normale si pour petite n et de grandes k. Cependant, à l'opposé de cas d'utilisation ne passera (grand n et petit k), et il s'avère que pour le cas particulier de l' n == 10000 et k == 4 (qui ne peut pas être exclu en tant que représentant d'une partie importante d'un hypothétique plan de travail), l' memcpy() version 3.6 x fois plus lent que l'original. C'est, apparemment, principalement en raison du fait qu' k n'est pas constante à la compilation, comme en témoigne le fait que cette prochaine version effectue (ou presque exactement, en fonction des paramètres d'optimisation) ainsi que l'original (ou mieux, parfois), pour le cas particulier de l' k == 4:

    if (k_local == 4) {
        /* this optimizes */
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    } else {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    }

Bien évidemment, il n'est pas pratique pour coder en dur une boucle pour chaque valeur de k, j'ai donc tenté le suivant à la place (comme une première tentative qui pourrait par la suite généralisée, si cela a fonctionné):

    if (k_local >= 0 && k_local <= 4) {
        /* this does not not optimize */
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    } else {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    }

Malheureusement, cette dernière version n'est plus rapide que l'original memcpy() version, qui est un peu décourageant pour ma foi en la GCC est l'optimisation des capacités.

Est il possible que je peux donner plus de "trucs" pour GCC (par tous moyens) qui va l'aider à faire la bonne chose ici? (Et même mieux, il y a des "indices" qui pourrait sûrement le travail à travers les différents compilateurs? Cette bibliothèque est compilée pour différentes cibles.)

Les résultats indiqués sont pour GCC 4.6.3 sur 32 bits Ubuntu avec le "-O2" drapeau, mais j'ai aussi testé GCC 4.7.2 et "-O3" versions avec similaire (mais pas identique) des résultats. J'ai posté mon harnais de test pour LiveWorkspace, mais les horaires sont de ma propre machine à l'aide de l' time(1) commande (je ne sais pas quelle est la fiabilité de LiveWorkspace horaires.)

EDIT: j'ai aussi considéré comme juste, la fixation d'un "nombre magique" pour certains, la taille minimale d'appeler memcpy() , et que j'ai pu trouver une telle valeur avec des tests répétés, mais je ne suis pas sûr de savoir comment généraliser les résultats de ma recherche serait à travers les différents compilateurs/plates-formes. Est-il une règle de base que je pourrais utiliser ici?

En OUTRE EDIT: Réalisé l' k_local variables sont plutôt inutile dans ce cas, effectivement, puisque aucun aliasing est possible; il a été réduit à partir de quelques expériences, j'ai couru partout où c'est possible (k global) et j'ai oublié je l'ai changé. Il suffit de les ignorer cette partie.

MODIFIER la BALISE: Réalisé que je peux aussi utiliser C++ dans des versions plus récentes de Cython, de sorte que le marquage de C++ dans le cas où il ya quelque chose qui peut aider à partir de C++...

Montage FINAL: À la place (pour l'instant) de descendre de l'assemblée spécialisée memcpy(), la suite semble être la meilleure solution empirique pour ma machine locale:

    int i, idx, j;
    double * subout, * subin;
    assert(stride_out_1 == 1);
    assert(stride_out_1 == stride_in_1);
    if (k < 32 /* i.e. 256 bytes: magic! */) {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            subout = &out[i * stride_out_0];
            subin = &in[idx * stride_in_0];
            for(j = 0; j < k; ++j)
                subout[j] = subin[j];
        }
    } else {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            subout = &out[i * stride_out_0];
            subin = &in[idx * stride_in_0];
            memcpy(subout, subin, k * sizeof(double));
        }
    }

Il utilise un "nombre magique" pour décider de l'appel d' memcpy() ou pas, mais toujours optimise le cas pour les petits tableaux qui sont connus pour être contiguës (donc c'est plus rapide que l'original, dans la plupart des cas, étant donné que l'original ne fait pas une telle hypothèse).

Answer 1

En fin de compte, la question à portée de main est l'un de demander à l'optimiseur hypothèses à propos de l'exécution comportement en fonction de multiples variables. Alors qu'il est possible de fournir à l'optimiseur de certains au moment de la compilation conseils via l'utilisation de "const" et "registre" des déclarations sur les variables clés, en fin de compte, vous êtes en fonction sur l'optimiseur de faire beaucoup d'hypothèses. En outre, alors que le memcpy() peut très bien être intrinsèque, il n'est pas garanti et même si/quand il est, la mise en œuvre(s) peut varier assez largement.

Si l'objectif est d'atteindre une performance maximale, parfois vous avez juste à ne pas s'appuyer sur la technologie pour comprendre, pour vous, au lieu de le faire directement. Les meilleurs conseils pour que cette situation est l'utilisation de l'assembleur en ligne pour résoudre le problème. Cela vous permet d'éviter tous les pièges d'une "boîte noire" de la solution de compliments de l'heuristique du compilateur et de l'optimiseur et à finitely état de votre intention. Le principal avantage de l'utilisation de l'assembleur en ligne est la capacité à éviter tout pousse/pops et étrangers "généralisation" de code dans la solution du problème de copie de mémoire et la capacité de prendre avantage direct du processeur, la capacité de résoudre le problème. Le côté est de l'entretien, mais étant donné que vous avez vraiment besoin seulement de répondre à Intel et AMD pour couvrir l'essentiel du marché, il n'est pas insurmontable.

Je pourrais ajouter aussi que cette solution pourrait bien vous permettre de profiter de multiples coeurs/threads et/ou d'un GPU si/si disponible pour effectuer la copie en parallèle et vraiment obtenir un gain de performance. Alors que le temps de latence pourrait être plus élevé, le débit serait très probablement beaucoup plus élevé, ainsi. Si, par exemple, vous pourriez profiter d'un GPU lorsqu'il est présent, on pourrait lancer un noyau par copie et de copie des milliers d'éléments en une seule opération.

L'alternative à cela dépend du compilateur/optimiseur de faire les meilleures estimations pour vous, utilisez le "const" et "registre", déclaration, où vous pouvez offrir le compilateur conseils et de l'utilisation des numéros de magie à la direction générale basée sur la "meilleure solution" chemins... cependant, cela est va être exceptionnellement compilateur/dépend du système et de votre kilométrage peut varier largement d'une plate-forme/environnement à l'autre.

Answer 2

SSE/AVX et l'Alignement

Si vous êtes, par exemple, un moderne-ish processeur Intel puis l'utilisation de l'ESS ou d'instructions AVX est une option. Bien que n'étant pas spécifiquement sur GCC, voir cette Si vous êtes intéressé et rincer avec cache je pense que Intel faire une version de leur suite de compilateurs pour Linux ainsi que Windows, et je pense qu'il est livré avec sa propre suite de bibliothèques.

Il y a aussi ce post.

Threads (eek)

J'ai eu exactement ce genre de problème assez récemment, un memcpy() prend trop de temps. Dans mon exemple, il a été un grand memcpy() (1MByte ou donc) plutôt que beaucoup de plus petits, comme vous êtes en train de faire.

J'ai obtenu un très bon kilométrage par l'écriture de mon propre multi-thread memcpy (), où les fils étaient persistants et a "chargé" avec une part de l'emploi par un appel de ma propre pmemcpy() fonction. La persistance de threads signifiait que la surcharge était assez faible. J'ai eu un x4 amélioration pour les 4 cœurs.

Donc si il était possible de briser vos boucles vers le bas dans un bon nombre de threads (je suis allé pour un par disponible de base), et vous avez le luxe de quelques-uns de rechange cœurs sur votre machine, vous pourriez obtenir un avantage similaire.

Ce que le temps réel de la foule - DMA

Juste en aparté, j'ai le plaisir de jouer avec quelques-uns assez exotique OpenVPX matériel. En gros, c'est un tas de planches dans une grosse boîte avec un high speed serial RapidIO interconnexion entre eux. Chaque commission dispose d'un moteur DMA que les données des disques à travers le sRIO à une autre carte mémoire.

Le vendeur je suis allé à est assez habile à la façon de maximiser l'utilisation de l'UC. Le bit intelligente, c'est que les DMA les moteurs sont assez intelligents - ils peuvent être programmés pour faire des choses comme la matrice des transformations à la volée, la bande de l'exploitation minière, des choses comme vous essayez de le faire, etc. Et parce que c'est une pièce séparée de matériel le CPU n'est pas lié dans le temps, de sorte que peut être en train de faire quelque chose d'autre.

Par exemple, si vous faites quelque chose comme le Radar à Ouverture Synthétique traitement tu finis toujours par faire une grosse matrice de transformation. La beauté est que la transformation elle-même prend pas de PROCESSEUR de temps, il vous suffit de déplacer les données vers un autre conseil d'administration et il arrive déjà transformé.

De toute façon, ayant l'avantage de ce genre de chose qui fait vraiment un souhait que les Processeurs Intel (et d'autres) ont à bord des DMA de moteurs capables de la mémoire de travail-mémoire au lieu de simplement la mémoire de la périphérie. Qui permettrait de faire des tâches comme la vôtre vraiment rapide.

Answer 3

Je pense que la meilleure façon est d'expérimenter et de trouver les conditions optimales de valeur de k pour basculer entre l'algorithme original (avec une boucle) et votre algorithme optimisé à l'aide de memcpy. L'optimal "k" varient selon les types de processeurs, mais ne devrait pas être radicalement différents; essentiellement, c'est à propos de la surcharge de l'appel de memcpy, les frais généraux dans memcpy lui-même dans le choix de l'algorithme optimal (basé sur la taille, l'alignement, etc.) contre la "naïve" de l'algorithme avec une boucle.

memcpy est intrinsèque dans gcc, oui, mais il ne veut pas faire de la magie. Ce qu'il fait est que si la taille de l'argument est connu au moment de la compilation et de la petite-ish (je ne sais pas quel est le seuil de l'est), alors GCC va remplacer l'appel à la fonction memcpy avec le code en ligne. Si la taille de l'argument n'est pas connu au moment de la compilation, un appel à une fonction de la bibliothèque memcpy le sera toujours.