optimization javascript - Améliorer les performances INSERT par seconde de SQLite?




example js (9)

Optimiser SQLite est délicat. Les performances d'insertion en bloc d'une application C peuvent varier de 85 insertions par seconde à plus de 96 000 insertions par seconde!

Contexte: Nous utilisons SQLite dans le cadre d’une application de bureau. Nous avons de grandes quantités de données de configuration stockées dans des fichiers XML qui sont analysés et chargés dans une base de données SQLite pour un traitement ultérieur lors de l'initialisation de l'application. SQLite est idéal pour cette situation car il est rapide, il ne nécessite aucune configuration spécialisée et la base de données est stockée sur le disque dans un fichier unique.

Raison: Au début, j'étais déçu de la performance que je voyais. Il s'avère que les performances de SQLite peuvent varier considérablement (à la fois pour les insertions en bloc et pour les sélections) en fonction de la configuration de la base de données et de la manière dont vous utilisez l'API. Ce n’était pas une mince affaire de savoir quelles étaient toutes les options et techniques, j’ai donc jugé prudent de créer cette entrée du wiki de la communauté afin de partager les résultats avec les lecteurs de afin d’épargner aux autres le problème des mêmes enquêtes.

L'expérience: Plutôt que de simplement parler de conseils de performance au sens général ( "Utilisez une transaction!" ), J'ai jugé préférable d'écrire du code C et de mesurer l'impact de diverses options. Nous allons commencer avec quelques données simples:

  • Un fichier texte délimité par une tabulation de 28 Mo (environ 865 000 enregistrements) du calendrier de transport complet pour la ville de Toronto
  • Ma machine de test est un P4 à 3,60 GHz sous Windows XP.
  • Le code est compilé avec Visual C ++ 2005 en tant que "version" avec "optimisation complète" (/ Ox) et code rapide favorable (/ Ot).
  • J'utilise SQLite "Amalgamation", compilé directement dans mon application de test. La version de SQLite que j'ai est un peu plus ancienne (3.6.7), mais je suppose que ces résultats seront comparables à ceux de la dernière version (laissez un commentaire si vous pensez le contraire).

Ecrivons du code!

Le code: Un simple programme en C qui lit le fichier texte ligne par ligne, divise la chaîne en valeurs et insère ensuite les données dans une base de données SQLite. Dans cette version "baseline" du code, la base de données est créée, mais nous n'insérerons pas de données:

/*************************************************************
    Baseline code to experiment with SQLite performance.

    Input data is a 28 MB TAB-delimited text file of the
    complete Toronto Transit System schedule/route info
    from http://www.toronto.ca/open/datasets/ttc-routes/

**************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include "sqlite3.h"

#define INPUTDATA "C:\\TTC_schedule_scheduleitem_10-27-2009.txt"
#define DATABASE "c:\\TTC_schedule_scheduleitem_10-27-2009.sqlite"
#define TABLE "CREATE TABLE IF NOT EXISTS TTC (id INTEGER PRIMARY KEY, Route_ID TEXT, Branch_Code TEXT, Version INTEGER, Stop INTEGER, Vehicle_Index INTEGER, Day Integer, Time TEXT)"
#define BUFFER_SIZE 256

int main(int argc, char **argv) {

    sqlite3 * db;
    sqlite3_stmt * stmt;
    char * sErrMsg = 0;
    char * tail = 0;
    int nRetCode;
    int n = 0;

    clock_t cStartClock;

    FILE * pFile;
    char sInputBuf [BUFFER_SIZE] = "\0";

    char * sRT = 0;  /* Route */
    char * sBR = 0;  /* Branch */
    char * sVR = 0;  /* Version */
    char * sST = 0;  /* Stop Number */
    char * sVI = 0;  /* Vehicle */
    char * sDT = 0;  /* Date */
    char * sTM = 0;  /* Time */

    char sSQL [BUFFER_SIZE] = "\0";

    /*********************************************/
    /* Open the Database and create the Schema */
    sqlite3_open(DATABASE, &db);
    sqlite3_exec(db, TABLE, NULL, NULL, &sErrMsg);

    /*********************************************/
    /* Open input file and import into Database*/
    cStartClock = clock();

    pFile = fopen (INPUTDATA,"r");
    while (!feof(pFile)) {

        fgets (sInputBuf, BUFFER_SIZE, pFile);

        sRT = strtok (sInputBuf, "\t");     /* Get Route */
        sBR = strtok (NULL, "\t");            /* Get Branch */
        sVR = strtok (NULL, "\t");            /* Get Version */
        sST = strtok (NULL, "\t");            /* Get Stop Number */
        sVI = strtok (NULL, "\t");            /* Get Vehicle */
        sDT = strtok (NULL, "\t");            /* Get Date */
        sTM = strtok (NULL, "\t");            /* Get Time */

        /* ACTUAL INSERT WILL GO HERE */

        n++;
    }
    fclose (pFile);

    printf("Imported %d records in %4.2f seconds\n", n, (clock() - cStartClock) / (double)CLOCKS_PER_SEC);

    sqlite3_close(db);
    return 0;
}

Le contrôle"

L'exécution du code en l'état n'effectue pas d'opération de base de données, mais cela nous donnera une idée de la rapidité des opérations d'E / S et de traitement de chaînes de fichiers C bruts.

864913 enregistrements importés en 0.94 secondes

Génial! Nous pouvons faire 920 000 insertions par seconde, à condition de ne pas en faire: -)

Le "pire scénario"

Nous allons générer la chaîne SQL en utilisant les valeurs lues dans le fichier et appeler cette opération SQL en utilisant sqlite3_exec:

sprintf(sSQL, "INSERT INTO TTC VALUES (NULL, '%s', '%s', '%s', '%s', '%s', '%s', '%s')", sRT, sBR, sVR, sST, sVI, sDT, sTM);
sqlite3_exec(db, sSQL, NULL, NULL, &sErrMsg);

Cela va être lent car le code SQL sera compilé dans le code VDBE pour chaque insertion et chaque insertion aura lieu dans sa propre transaction. À quelle vitesse?

Importé 864913 enregistrements en 9933.61 secondes

Beurk! 2 heures et 45 minutes! C'est seulement 85 insertions par seconde.

Utiliser une transaction

Par défaut, SQLite évaluera chaque instruction INSERT / UPDATE dans une transaction unique. Si vous effectuez un grand nombre d’insertions, il est conseillé d’envelopper votre opération dans une transaction:

sqlite3_exec(db, "BEGIN TRANSACTION", NULL, NULL, &sErrMsg);

pFile = fopen (INPUTDATA,"r");
while (!feof(pFile)) {

    ...

}
fclose (pFile);

sqlite3_exec(db, "END TRANSACTION", NULL, NULL, &sErrMsg);

864913 enregistrements importés en 38.03 secondes

C'est mieux. Le simple fait de regrouper toutes nos plaquettes en une seule transaction a amélioré notre performance à 23 000 plaquettes par seconde.

Utiliser une déclaration préparée

L'utilisation d'une transaction était une énorme amélioration, mais recompiler l'instruction SQL pour chaque insertion n'a pas de sens si nous utilisons le même SQL over-and-over. Utilisons sqlite3_prepare_v2 pour compiler notre instruction SQL une fois, puis lions nos paramètres à cette instruction à l'aide de sqlite3_bind_text :

/* Open input file and import into the database */
cStartClock = clock();

sprintf(sSQL, "INSERT INTO TTC VALUES (NULL, @RT, @BR, @VR, @ST, @VI, @DT, @TM)");
sqlite3_prepare_v2(db,  sSQL, BUFFER_SIZE, &stmt, &tail);

sqlite3_exec(db, "BEGIN TRANSACTION", NULL, NULL, &sErrMsg);

pFile = fopen (INPUTDATA,"r");
while (!feof(pFile)) {

    fgets (sInputBuf, BUFFER_SIZE, pFile);

    sRT = strtok (sInputBuf, "\t");   /* Get Route */
    sBR = strtok (NULL, "\t");        /* Get Branch */
    sVR = strtok (NULL, "\t");        /* Get Version */
    sST = strtok (NULL, "\t");        /* Get Stop Number */
    sVI = strtok (NULL, "\t");        /* Get Vehicle */
    sDT = strtok (NULL, "\t");        /* Get Date */
    sTM = strtok (NULL, "\t");        /* Get Time */

    sqlite3_bind_text(stmt, 1, sRT, -1, SQLITE_TRANSIENT);
    sqlite3_bind_text(stmt, 2, sBR, -1, SQLITE_TRANSIENT);
    sqlite3_bind_text(stmt, 3, sVR, -1, SQLITE_TRANSIENT);
    sqlite3_bind_text(stmt, 4, sST, -1, SQLITE_TRANSIENT);
    sqlite3_bind_text(stmt, 5, sVI, -1, SQLITE_TRANSIENT);
    sqlite3_bind_text(stmt, 6, sDT, -1, SQLITE_TRANSIENT);
    sqlite3_bind_text(stmt, 7, sTM, -1, SQLITE_TRANSIENT);

    sqlite3_step(stmt);

    sqlite3_clear_bindings(stmt);
    sqlite3_reset(stmt);

    n++;
}
fclose (pFile);

sqlite3_exec(db, "END TRANSACTION", NULL, NULL, &sErrMsg);

printf("Imported %d records in %4.2f seconds\n", n, (clock() - cStartClock) / (double)CLOCKS_PER_SEC);

sqlite3_finalize(stmt);
sqlite3_close(db);

return 0;

Importé 864913 enregistrements en 16.27 secondes

Agréable! Il y a un peu plus de code (n'oubliez pas d'appeler sqlite3_clear_bindings et sqlite3_reset ), mais nous avons plus que doublé notre performance, à 53 000 insertions par seconde.

PRAGMA synchrone = OFF

Par défaut, SQLite s'interrompt après avoir émis une commande d'écriture au niveau du système d'exploitation. Cela garantit que les données sont écrites sur le disque. En définissant synchronous = OFF , nous demandons à SQLite de simplement transférer les données au système d'exploitation pour l'écriture, puis de continuer. Il est possible que le fichier de base de données soit corrompu si l'ordinateur subissait un crash catastrophique (ou une panne de courant) avant que les données ne soient écrites sur le plateau:

/* Open the database and create the schema */
sqlite3_open(DATABASE, &db);
sqlite3_exec(db, TABLE, NULL, NULL, &sErrMsg);
sqlite3_exec(db, "PRAGMA synchronous = OFF", NULL, NULL, &sErrMsg);

Importé 864913 enregistrements en 12.41 secondes

Les améliorations sont maintenant moins importantes, mais nous avons atteint 69 600 insertions par seconde.

PRAGMA journal_mode = MEMORY

Envisagez de stocker le journal d'annulation en mémoire en évaluant PRAGMA journal_mode = MEMORY . Votre transaction sera plus rapide, mais si vous perdez le courant ou si votre programme se bloque pendant une transaction, votre base de données pourrait être corrompue avec une transaction partiellement complétée:

/* Open the database and create the schema */
sqlite3_open(DATABASE, &db);
sqlite3_exec(db, TABLE, NULL, NULL, &sErrMsg);
sqlite3_exec(db, "PRAGMA journal_mode = MEMORY", NULL, NULL, &sErrMsg);

864913 enregistrements importés en 13,50 secondes

Un peu plus lent que l'optimisation précédente à 64 000 insertions par seconde.

PRAGMA synchrone = OFF et PRAGMA journal_mode = MEMORY

Combinons les deux optimisations précédentes. C'est un peu plus risqué (en cas de crash), mais nous importons simplement des données (sans gérer de banque):

/* Open the database and create the schema */
sqlite3_open(DATABASE, &db);
sqlite3_exec(db, TABLE, NULL, NULL, &sErrMsg);
sqlite3_exec(db, "PRAGMA synchronous = OFF", NULL, NULL, &sErrMsg);
sqlite3_exec(db, "PRAGMA journal_mode = MEMORY", NULL, NULL, &sErrMsg);

Importé 864913 enregistrements en 12.00 secondes

Fantastique! Nous sommes en mesure de faire 72 000 insertions par seconde.

Utilisation d'une base de données en mémoire

Juste pour le plaisir, bâtissons sur toutes les optimisations précédentes et redéfinissons le nom de fichier de la base de données afin que nous travaillions entièrement en RAM:

#define DATABASE ":memory:"

864913 enregistrements importés en 10.94 secondes

Ce n'est pas très pratique de stocker notre base de données dans la RAM, mais il est impressionnant de pouvoir effectuer 79 000 insertions par seconde.

Refactoring Code C

Bien qu’il ne s’agisse pas d’une amélioration SQLite, je n’aime pas les opérations d’affectation supplémentaires char* dans la boucle while. Refactorisons rapidement ce code pour passer le résultat de strtok() directement dans sqlite3_bind_text() , et laissons le compilateur essayer d'accélérer les choses:

pFile = fopen (INPUTDATA,"r");
while (!feof(pFile)) {

    fgets (sInputBuf, BUFFER_SIZE, pFile);

    sqlite3_bind_text(stmt, 1, strtok (sInputBuf, "\t"), -1, SQLITE_TRANSIENT); /* Get Route */
    sqlite3_bind_text(stmt, 2, strtok (NULL, "\t"), -1, SQLITE_TRANSIENT);    /* Get Branch */
    sqlite3_bind_text(stmt, 3, strtok (NULL, "\t"), -1, SQLITE_TRANSIENT);    /* Get Version */
    sqlite3_bind_text(stmt, 4, strtok (NULL, "\t"), -1, SQLITE_TRANSIENT);    /* Get Stop Number */
    sqlite3_bind_text(stmt, 5, strtok (NULL, "\t"), -1, SQLITE_TRANSIENT);    /* Get Vehicle */
    sqlite3_bind_text(stmt, 6, strtok (NULL, "\t"), -1, SQLITE_TRANSIENT);    /* Get Date */
    sqlite3_bind_text(stmt, 7, strtok (NULL, "\t"), -1, SQLITE_TRANSIENT);    /* Get Time */

    sqlite3_step(stmt);        /* Execute the SQL Statement */
    sqlite3_clear_bindings(stmt);    /* Clear bindings */
    sqlite3_reset(stmt);        /* Reset VDBE */

    n++;
}
fclose (pFile);

Remarque: Nous revenons à utiliser un fichier de base de données réel. Les bases de données en mémoire sont rapides, mais pas nécessairement pratiques

864913 enregistrements importés en 8.94 secondes

Un léger remaniement du code de traitement de chaîne utilisé dans notre liaison de paramètres nous a permis d’effectuer 96 700 insertions par seconde. Je pense qu'il est prudent de dire que c'est beaucoup rapide . Lorsque nous commencerons à modifier d’autres variables (taille de la page, création d’index, etc.), ce sera notre référence.

Résumé (jusqu'à présent)

J'espère que tu es toujours avec moi! La raison pour laquelle nous avons commencé dans cette voie est que les performances des insertions en masse varient énormément avec SQLite et que les modifications à apporter pour accélérer nos opérations ne sont pas toujours évidentes. En utilisant le même compilateur (et les mêmes options), la même version de SQLite et les mêmes données, nous avons optimisé notre code et notre utilisation de SQLite pour passer d'un scénario du pire scénario de 85 insertions par seconde à plus de 96 000 insertions par seconde!

CREATE INDEX puis INSERT vs. INSERT puis CREATE INDEX

Avant de commencer à mesurer les performances de SELECT , nous savons que nous allons créer des index. L'une des réponses ci-dessous suggère que, lors de l'insertion en bloc, il est plus rapide de créer l'index une fois les données insérées (par opposition à la création de l'index en premier lieu à l'insertion des données). Essayons:

Créer un index puis insérer des données

sqlite3_exec(db, "CREATE  INDEX 'TTC_Stop_Index' ON 'TTC' ('Stop')", NULL, NULL, &sErrMsg);
sqlite3_exec(db, "BEGIN TRANSACTION", NULL, NULL, &sErrMsg);
...

Importé 864913 enregistrements en 18.13 secondes

Insérer des données puis créer un index

...
sqlite3_exec(db, "END TRANSACTION", NULL, NULL, &sErrMsg);
sqlite3_exec(db, "CREATE  INDEX 'TTC_Stop_Index' ON 'TTC' ('Stop')", NULL, NULL, &sErrMsg);

Importé 864913 enregistrements en 13.66 secondes

Comme prévu, les insertions en bloc sont plus lentes si une colonne est indexée, mais cela change en revanche si l'index est créé après l'insertion des données. Notre ligne de base sans index est de 96 000 insertions par seconde. Créer d'abord l'index, puis insérer des données nous donne 47 700 insertions par seconde, alors que l'insertion des données puis créer un index nous donne 63 300 insertions par seconde.

Je serais heureux de recevoir des suggestions d'essais d'autres scénarios ... Et je compilerai bientôt des données similaires pour les requêtes SELECT.


Answers

Je ne peux tirer aucun profit des transactions tant que je n’ai pas élevé cache_size à une valeur plus élevée, par exemple PRAGMA cache_size=10000;


Sur les inserts en vrac

Inspiré par cet article et par la question du débordement de pile qui m'a amené ici - Est-il possible d'insérer plusieurs lignes à la fois dans une base de données SQLite? - J'ai posté mon premier référentiel Git :

https://github.com/rdpoor/CreateOrUpdate

qui charge en vrac un tableau d'ActiveRecords dans des MySQL , SQLite ou PostgreSQL . Il inclut une option permettant d'ignorer les enregistrements existants, de les écraser ou de générer une erreur. Mes repères rudimentaires montrent une amélioration de la vitesse 10 fois supérieure à celle des écritures séquentielles - YMMV.

Je l'utilise dans le code de production, où j'ai souvent besoin d'importer de grands ensembles de données, et j'en suis assez content.


Essayez d’utiliser SQLITE_STATIC au lieu de SQLITE_TRANSIENT pour ces insertions.

SQLITE_TRANSIENT SQLite à copier les données de chaîne avant le renvoi.

SQLITE_STATIC dit que l'adresse mémoire que vous lui avez donnée sera valide jusqu'à ce que la requête soit exécutée (ce qui est toujours le cas dans cette boucle). Vous éviterez ainsi plusieurs opérations d'allocation, de copie et de désallocation par boucle. Peut-être une grande amélioration.


Si vous ne vous souciez que de la lecture, une version un peu plus rapide (mais pouvant lire des données obsolètes) consiste à lire à partir de plusieurs connexions de plusieurs threads (connexion par thread).

Commencez par trouver les articles dans le tableau:

 SELECT COUNT(*) FROM table

puis lu en pages (LIMIT / OFFSET)

  SELECT * FROM table ORDER BY _ROWID_ LIMIT <limit> OFFSET <offset>

où et sont calculés par thread, comme ceci:

int limit = (count + n_threads - 1)/n_threads;

pour chaque fil:

int offset = thread_index * limit

Pour notre petite (200 Mo) db, cela représente une accélération de 50 à 75% (3.8.0.2 64 bits sur Windows 7). Nos tables sont fortement non normalisées (1000-1500 colonnes, environ 100 000 lignes ou plus).

Trop ou trop peu de threads ne suffiront pas, vous devez vous mesurer et vous profiler.

Aussi pour nous, SHAREDCACHE a ralenti la performance, alors je mets manuellement PRIVATECACHE (car il a été activé globalement pour nous)


Après avoir lu ce tutoriel, j'ai essayé de l'implémenter dans mon programme.

J'ai 4-5 fichiers qui contiennent des adresses. Chaque fichier contient environ 30 millions d’enregistrements. J'utilise la même configuration que vous suggérez, mais mon nombre d'insertions par seconde est très faible (~ 10.000 enregistrements par seconde).

Voici où votre suggestion échoue. Vous utilisez une seule transaction pour tous les enregistrements et une seule insertion sans erreur / échec. Supposons que vous divisez chaque enregistrement en plusieurs insertions sur des tables différentes. Que se passe-t-il si le record est cassé?

La commande ON CONFLICT ne s'applique pas, car si vous avez 10 éléments dans un enregistrement et que vous avez besoin d'insérer chaque élément dans une table différente, si l'élément 5 génère une erreur CONSTRAINT, toutes les 4 insertions précédentes doivent également être supprimées.

Donc, voici où le retour en arrière vient. Le seul problème avec la restauration est que vous perdez toutes vos insertions et commencez par le haut. Comment pouvez-vous résoudre ce problème?

Ma solution consistait à utiliser plusieurs transactions. Je commence et termine une transaction tous les 10.000 enregistrements (ne demandez pas pourquoi ce nombre, c’est le plus rapide que j’ai testé). J'ai créé un tableau de taille 10.000 et y inséré les enregistrements réussis. Lorsque l'erreur se produit, je fais une restauration, commence une transaction, insère les enregistrements de mon tableau, valide et commence une nouvelle transaction après l'enregistrement cassé.

Cette solution m'a permis d'éviter les problèmes que je rencontrais lorsque je traitais des fichiers contenant des enregistrements incorrects / en double (j'avais presque 4% d'enregistrements incorrects).

L'algorithme que j'ai créé m'a aidé à réduire mon processus de 2 heures. Processus de chargement final du fichier 1h30, ce qui est encore lent mais pas comparé aux 4 heures qu’il a initialement pris. J'ai réussi à accélérer les inserts de 10 000 / s à ~ 14 000 / s

Si quelqu'un a d'autres idées sur la façon d'accélérer les choses, je suis ouvert aux suggestions.

MISE À JOUR :

En plus de ma réponse ci-dessus, vous devez garder à l'esprit que les insertions par seconde dépendent du disque dur que vous utilisez également. Je l'ai testé sur 3 ordinateurs différents avec des disques durs différents et j'ai eu des différences énormes dans le temps. PC1 (1h 30m), PC2 (6h) PC3 (14h), alors j'ai commencé à me demander pourquoi cela serait.

Après deux semaines de recherche et de vérification de plusieurs ressources: disque dur, mémoire vive, cache, j'ai découvert que certains paramètres de votre disque dur peuvent affecter le taux d'E / S. En cliquant sur les propriétés du lecteur de sortie souhaité, vous pouvez voir deux options dans l'onglet Général. Opt1: Compressez ce lecteur, Opt2: Autorisez les fichiers de ce lecteur à être indexés.

En désactivant ces deux options, les trois ordinateurs mettent maintenant à peu près le même temps (1 heure et 20 à 40 minutes). Si vous rencontrez des insertions lentes, vérifiez si votre disque dur est configuré avec ces options. Cela vous fera gagner beaucoup de temps et de maux de tête en essayant de trouver la solution


Plusieurs astuces:

  1. Mettre des insertions / mises à jour dans une transaction.
  2. Pour les anciennes versions de SQLite - Envisagez un mode de journal moins paranoïaque ( pragma journal_mode ). Il existe NORMAL , puis OFF , ce qui peut considérablement augmenter la vitesse d’insertion si vous ne craignez pas trop que la base de données ne soit corrompue en cas de panne du système d’exploitation. Si votre application plante, les données devraient être correctes. Notez que dans les versions plus récentes, les paramètres OFF/MEMORY ne sont pas sécurisés en cas de blocage au niveau de l'application.
  3. Jouer avec les tailles de page fait aussi une différence ( PRAGMA page_size ). Avoir des tailles de page plus grandes peut rendre les lectures et les écritures un peu plus rapides car les pages plus grandes sont conservées en mémoire. Notez que plus de mémoire sera utilisée pour votre base de données.
  4. Si vous avez des index, appelez CREATE INDEX après avoir effectué toutes vos insertions. Cela est nettement plus rapide que la création de l'index, puis la création de vos insertions.
  5. Vous devez être très prudent si vous avez un accès simultané à SQLite, car toute la base de données est verrouillée lorsque des écritures sont effectuées et, bien que plusieurs lecteurs soient possibles, les écritures sont verrouillées. Cela a été quelque peu amélioré avec l’ajout d’un WAL dans les nouvelles versions de SQLite.
  6. Profitez d'économiser de l'espace ... les bases de données plus petites vont plus vite Par exemple, si vous avez des paires clé-valeur, essayez si possible de transformer la clé en INTEGER PRIMARY KEY , qui remplacera la colonne de numéro de ligne unique implicite de la table.
  7. Si vous utilisez plusieurs threads, vous pouvez essayer d'utiliser le cache de pages partagées , ce qui permettra aux pages chargées d'être partagées entre les threads, ce qui peut éviter des appels d'E / S coûteux.
  8. Ne pas utiliser !feof(file) !

J'ai également posé des questions similaires here et here .


Les importations en bloc semblent donner de meilleurs résultats si vous pouvez fractionner vos instructions INSERT / UPDATE . Une valeur de 10.000 ou plus a bien fonctionné pour moi sur une table avec seulement quelques lignes, YMMV ...



Culprit: False Data Dependency (et le compilateur n'en est même pas conscient)

Sur les processeurs Sandy / Ivy Bridge et Haswell, l'instruction:

popcnt  src, dest

semble avoir une fausse dépendance sur le registre de destination dest . Même si l'instruction n'écrit que, l'instruction attendra que dest soit prêt avant l'exécution.

Cette dépendance ne tient pas seulement les 4 popcnt partir d'une seule itération de boucle. Il peut effectuer des itérations de boucle, ce qui empêche le processeur de paralléliser différentes itérations de boucle.

Le unsigned vs uint64_t et d'autres tweaks n'affectent pas directement le problème. Mais ils influencent l'allocateur de registre qui affecte les registres aux variables.

Dans votre cas, les vitesses sont le résultat direct de ce qui est bloqué dans la chaîne de dépendance (fausse) en fonction de ce que l'allocateur de registre a décidé de faire.

  • 13 GB / s a ​​une chaîne: popcnt - add - popcnt - popcnt → itération suivante
  • 15 Go / s a ​​une chaîne: popcnt - add - popcnt - add → itération suivante
  • 20 Go / s a ​​une chaîne: popcnt - popcnt → itération suivante
  • 26 Go / s a ​​une chaîne: popcnt - popcnt → itération suivante

La différence entre 20 Go / s et 26 Go / s semble être un artefact mineur de l'adressage indirect. De toute façon, le processeur commence à frapper d'autres goulots d'étranglement une fois que vous atteignez cette vitesse.

Pour tester cela, j'ai utilisé l'assemblage en ligne pour contourner le compilateur et obtenir exactement l'assemblage que je veux. Je divise également la variable de count pour casser toutes les autres dépendances qui pourraient déranger les repères.

Voici les résultats:

Sandy Bridge Xeon @ 3.5 GHz: (code de test complet peut être trouvé en bas)

  • GCC 4.6.3: g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
  • Ubuntu 12

Différents registres: 18.6195 Go / s

.L4:
    movq    (%rbx,%rax,8), %r8
    movq    8(%rbx,%rax,8), %r9
    movq    16(%rbx,%rax,8), %r10
    movq    24(%rbx,%rax,8), %r11
    addq    $4, %rax

    popcnt %r8, %r8
    add    %r8, %rdx
    popcnt %r9, %r9
    add    %r9, %rcx
    popcnt %r10, %r10
    add    %r10, %rdi
    popcnt %r11, %r11
    add    %r11, %rsi

    cmpq    $131072, %rax
    jne .L4

Même registre: 8.49272 Go / s

.L9:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # This time reuse "rax" for all the popcnts.
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L9

Même registre avec chaîne brisée: 17.8869 Go / s

.L14:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # Reuse "rax" for all the popcnts.
    xor    %rax, %rax    # Break the cross-iteration dependency by zeroing "rax".
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L14

Alors qu'est-ce qui a mal tourné avec le compilateur?

Il semble que ni GCC ni Visual Studio ne sont conscients que popcnt a une fausse dépendance. Néanmoins, ces fausses dépendances ne sont pas rares. C'est juste une question de savoir si le compilateur est conscient de cela.

popcnt n'est pas exactement l'instruction la plus utilisée. Ce n'est donc pas vraiment une surprise qu'un grand compilateur puisse manquer quelque chose comme ça. Il semble également n'y avoir aucune documentation nulle part qui mentionne ce problème. Si Intel ne le divulgue pas, personne ne le saura à l'extérieur jusqu'à ce que quelqu'un le rencontre par hasard.

( Mise à jour: A partir de la version 4.9.2 , GCC est conscient de cette fausse dépendance et génère du code pour le compenser lorsque les optimisations sont activées.Les principaux compilateurs d'autres fournisseurs, y compris Clang, MSVC, et même ICC d'Intel ne sont pas encore au courant cet erratum microarchitectural et n'émettra pas de code qui compense pour cela.)

Pourquoi le CPU a-t-il une fausse dépendance?

Nous ne pouvons que spéculer, mais il est probable qu'Intel ait la même manipulation pour beaucoup d'instructions à deux opérandes. Les instructions communes comme add , sub prennent deux opérandes dont les deux sont des entrées. Intel a donc probablement popcnt dans la même catégorie pour simplifier la conception du processeur.

Les processeurs AMD ne semblent pas avoir cette fausse dépendance.

Le code de test complet est ci-dessous pour référence:

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

   using namespace std;
   uint64_t size=1<<20;

   uint64_t* buffer = new uint64_t[size/8];
   char* charbuffer=reinterpret_cast<char*>(buffer);
   for (unsigned i=0;i<size;++i) charbuffer[i]=rand()%256;

   uint64_t count,duration;
   chrono::time_point<chrono::system_clock> startP,endP;
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %4  \n\t"
                "add %4, %0     \n\t"
                "popcnt %5, %5  \n\t"
                "add %5, %1     \n\t"
                "popcnt %6, %6  \n\t"
                "add %6, %2     \n\t"
                "popcnt %7, %7  \n\t"
                "add %7, %3     \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "No Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Chain 4   \t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "xor %%rax, %%rax   \n\t"   // <--- Break the chain.
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Broken Chain\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }

   free(charbuffer);
}

Un benchmark tout aussi intéressant peut être trouvé ici: http://pastebin.com/kbzgL8si
Ce benchmark varie le nombre de popcnt qui sont dans la chaîne de dépendance (false).

False Chain 0:  41959360000 0.57748 sec     18.1578 GB/s
False Chain 1:  41959360000 0.585398 sec    17.9122 GB/s
False Chain 2:  41959360000 0.645483 sec    16.2448 GB/s
False Chain 3:  41959360000 0.929718 sec    11.2784 GB/s
False Chain 4:  41959360000 1.23572 sec     8.48557 GB/s




c performance sqlite optimization