YBoy360 a écrit 673 commentaires

Je me suis emballé, il faut 2 comparaisons et appliquer 2 masks. Par contre, autant on perd sur de l'AMD sur cette boucle par rapport à la version non long, mais on divise par 2 sur mon ARM (Mediatek je crois…).

Si après correction j'obtiens des gains, je te les communiquerai.

Pour info, la version utilisant des long est presque encore 2 fois plus rapide sur ARM que la version int …

Par contre ça impose des contraintes d'alignement.

size_t find_int_c4l(const int k, const int* v, const size_t n) {
    size_t i = 0;
    size_t n2 = n >> 1;
    const long* vl = (const long*)v;
    const long kl = (long)(((long)k>>32) + k);
    unsigned int index = 0;

    for (; i <= n2; i += 8, vl += 8) {
        index = 0;
        __builtin_prefetch(vl + 256, 0, 1);
        index = vl[0] != kl ? index : 1;
        index = vl[1] != kl ? index : 1;
        index = vl[2] != kl ? index : 1;
        index = vl[3] != kl ? index : 1;
        index = vl[4] != kl ? index : 1;
        index = vl[5] != kl ? index : 1;
        index = vl[6] != kl ? index : 1;
        index = vl[7] != kl ? index : 1;
        if (index == 1) {
            break;
        }
    }
    if (index == 0) return i;
    else
        for (int j = 0; i < 8; j++) {
            if (vl[j] == kl) return i + j; 
                        //Attention, il == 2 * i...
        }
}

Sur ARM (un chromebook avec Debian dessus), j'obtiens de meilleurs score pour la version "CMOV" sur le main que j'ai mis au-dessus, les valeurs sont loader bien avant le CMOV, donc pas besoin de prédiction de valeur, elles sont dispo lors du cmov (il faudrait faire du profiling, j'ai la flème).

$ ./test.x
C1 = 928197 (499999984), C2 = 605687 (499999984), C3 = 538721 (499999984), C4 = 539927 (499999984), C5 = 545717 (499999984)

C3 et C4 sont 2 versions CMOV, les autres utilisent les branchements. C5, c'est le code que tu as mis dans l'autre commentaire.

$ cat /proc/cpuinfo 
processor       : 0
BogoMIPS        : 26.00
Features        : fp asimd evtstrm aes pmull sha1 sha2 crc32 cpuid
CPU implementer : 0x41
CPU architecture: 8
CPU variant     : 0x0
CPU part        : 0xd03
CPU revision    : 4
[ . . . 8 cores qui semblent identiques ]

size_t find_int_c3(const int k, const int* v, const size_t n) {
    unsigned int mask = 0;
    size_t i = 0;
    for (; i < n - 8;) {
        mask = v[i] != k ? mask : 1;
        mask = v[i+1] != k ? mask : 2;
        mask = v[i+2] != k ? mask : 4;
        mask = v[i+3] != k ? mask : 8;
        mask = v[i+4] != k ? mask : 16;
        mask = v[i+5] != k ? mask : 32;
        mask = v[i+6] != k ? mask : 64;
        mask = v[i+7] != k ? mask : 128;
        i += 8;
        if (mask != 0) i += n;
        __builtin_prefetch(v + i + 512, 0, 1);
    }

    i -= n + 8;
    if (mask == 0) return n;
    if (mask == 1) return i;
    if (mask == 2) return i + 1;
    if (mask == 4) return i + 2;
    if (mask == 8) return i + 3;
    if (mask == 16) return i + 4;
    if (mask == 32) return i + 5;
    if (mask == 64) return i + 6;
    if (mask == 128) return i + 7;
}

size_t find_int_c4(const int k, const int* v, const size_t n) {
    size_t i = 0;
//  size_t n2 = n >> 1;
//  const long* vl = (const long*)v;
//  const long kl = (long)(((long)k>>32) + k);
    unsigned int index = 0;

    for (; i <= n; i += 8, v += 8) {
        index = 0;
        __builtin_prefetch(v + 256);
        index = v[0] != k ? index : 1;
        index = v[1] != k ? index : 1;
        index = v[2] != k ? index : 1;
        index = v[3] != k ? index : 1;
        index = v[4] != k ? index : 1;
        index = v[5] != k ? index : 1;
        index = v[6] != k ? index : 1;
        index = v[7] != k ? index : 1;
        if (index == 1) {
            break;
        }
    }
    if (index == 0) return i;
    else
        for (int j = 0; i < 8; j++) {
            if (v[j] == k) return i + j;
        }
}

size_t find_int_c5(const int k, const int* v, const size_t n) {
      size_t i = 0;
       for (; n - i >= 8; i += 8,v+=8)
         {
          __builtin_prefetch(v+256); //54/148
          if (v[0] == k) return i;
          if (v[1] == k) return i + 1;
          if (v[2] == k) return i + 2;
          if (v[3] == k) return i + 3;
          if (v[4] == k) return i + 4;
          if (v[5] == k) return i + 5;
          if (v[6] == k) return i + 6;
          if (v[7] == k) return i + 7;
        }

       for (; i != n; i++,v++)
        if (v[0] == k)
          return i;
       return n;
}

Le fait que C3 soit plus rapide que C4 est contre-intuitif, mais le prefetch n'est pas placé aux mêmes endroits. Je m'attendais à de plus de différences…

Perso j'adore ce Chromebook, pour 250 EUR t'as un Linux sur ARM (certes, ça ne vaut pas un RPi). Mais il y a un très bon écran.

C'est ce que j'ai constaté (l'efficacité de la prédiction de branchement, dans le cas ou k n'est présent qu'une fois en fin de tableau), ça doit être lié aux architectures cependant.

Mais, même dans ce cas très favorable à la prédiction, le temps mis est pratiquement égal à la version cmov. Donc prédiction OK == cmov en temps dans ce cas. La version cmov est constante en temps, alors que si pour un algo la prédiction n'est pas bonne 1 fois de temps en temps, tu es très pénalisé.

Il faudrait faire un autre journal ou on compte les occurrences de k…

Oui, il faut ajouter le code pour les n non multiple de 8, j'aurais dû le préciser. Dans le main, n >> 8, n % 8 == 0, et k est positionné en fin de tableau. Normalement, on regarde d'abord les données, ensuite on fait un profile sur des benchmarks typiques, puis on envisage quoi optimiser. L'avantage de ces hypothèses, c'est que l'on sait ce que l'on test.

Si k a de forte chance d'être présent dans le tableau (par exemple plus de 1/8 des valeurs sont k) ou que les tableaux sont très petits, il faut considérer d'autres méthodes, évidement.

J'essaierai de comparer les résultats de ce main sur un M1 ou un Raspberry PI. Sur Intel, le remplacement des jumps par les cmov (conditional mov) ne semble pas si interesante que cela, car dans l'hypothèse "k a peu de chance d'être rencontré" rend la prédiction de branchement efficace (par rapport au cmov), puisque c'est toujour le même chemin qui est emprunté par le code.

Je n'ai pas fait le cas n < 8, j'ai considéré que la recherche se faisait sur un grand tableau.

As-tu essayé avec le prefetch placé à la main ? même si ce n'est pas "conseillé", car lié au HW, pour les grands tableaux, même pour des accès contiguë, on y gagne.. Pour les accès aléatoire un peu complexe, calculer l'adresse à précharger peut être coûteux.

Le combo SSE + prefetch doit être intéressant dans ton cas, puisque plus on optimise, plus le prefetch devrait agir, car son effet est constant.

Je viens de corriger la boucle, il est difficile d'éviter les jumps (dans le code ci-dessus, il aurait fallu utiliser "|" au lieu de "&").

J'ai également ajouté les options de compilation suggérées au-dessus, et le prefetch sur le premier algo :

$ gcc -march=native -funroll-all-loops -O3 -g test.c -o test.x
$ ./test.x 
C1 = 138643 (499999984), C2 = 89029 (499999984)

size_t find_int_c(int k, const int* v, size_t n)
{
  for (size_t i = 0; i != n; ++i) {
    if (v[i] == k) {
      return i;
    }
    __builtin_prefetch(v + i + 512, 0, 1);
  }
  return n;
}

size_t find_int_c2(const int k, const int* v, const size_t n) {
      int index = 0;
      size_t i = 0;
      for (; i < n - 8;) {
        index = 0;
        if (v[i] == k) index = 1;
        else if (v[i + 1] == k) index = 2;
        else if (v[i + 2] == k) index = 3;
        else if (v[i + 3] == k) index = 4;
        else if (v[i + 4] == k) index = 5;
        else if (v[i + 5] == k) index = 6;
        else if (v[i + 6] == k) index = 7;
        else if (v[i + 7] == k) index = 8;
        if (index != 0) i += n;
        i += 8;
        __builtin_prefetch(v + i + 512, 0, 1);
    }

    i -= n + 8;
    if (index == 0) return n;
    if (index == 1) return i;
    if (index == 2) return i + 1;
    if (index == 4) return i + 2;
    if (index == 8) return i + 3;
    if (index == 16) return i + 4;
    if (index == 32) return i + 5;
    if (index == 64) return i + 6;
    if (index == 128) return i + 7;
}

Les gains sont bien moins importants dans ce cas. On peut cela dit avoir envie d'éviter de dérouler toutes les boucles.. Puisque cela fait grossir la section code. Bref. On gagne quand même 40 % avec le déroulage manuel.

Il faut utiliser objdump pour observer le code compilé, ensuite, il faut fournir la commande de compilation.

Sans forcer, je divise par 2.6 le temps de la boucle original (j'ai eu la flemme de calculer le résultat exacte).

size_t find_int_c2(const int k, const int* v, const size_t n)
{
      int index = 0;
      size_t i = 0;
      for (; i < n - 8;) {
        int r0 = v[i++] - k;
        index = r0 == 0 ? 1 : index;
        int r1 = v[i++] - k;
        index = r1 == 0 ? 2 & index : index;
        int r2 = v[i++] - k;
        index = r2 == 0 ? 4 & index : index;
        int r3 = v[i++] - k;
        index = r3 == 0 ? 8 & index : index;
        int r4 = v[i++] - k;
        index = r4 == 0 ? 16 & index : index;
        int r5 = v[i++] - k;
        index = r5 == 0 ? 32 & index : index;
        int r6 = v[i++] - k;
        index = r6 == 0 ? 64 & index : index;
        int r7 = v[i++] - k;
        index = r7 == 0 ? 128 & index : index;
        if (index != 0) i += n;
        __builtin_prefetch(v + i + 512, 0, 1);
    }

  return index != -1 ? i + index : n;
}

Voila l'idée, supprimer les Jumps. Je pense que ça peut s'améliorer d'un facteur 2 ou 3.

$ gcc -march=native -O3 -g test.c -o test.x
$ objdump -dS test.x
$ ./test.x 
C1 = 228117 (499999984), C2 = 85911 (999999993)

Le main:

int main() {
    int* tab = malloc(SIZE * 4);
    for (int i = 0; i < SIZE; i++) {
        tab[i] = i;
    }
    clock_t c1 = clock();
    size_t r1 = find_int_c(SIZE - 16, tab, SIZE);
    clock_t c1end = clock();

    clock_t c2 = clock();
    size_t r2 = find_int_c2(SIZE - 16, tab, SIZE);
    clock_t c2end = clock();

    printf("C1 = %ld (%ld), C2 = %ld (%ld)\n", c1end - c1, r1, c2end - c2, r2);
}

C'est Google Workspace plus ou moins ce que tu décris. Tu peux aussi développer des applications interagissant avec drive, avoir de la visio intégrée dans ton agenda, le tableau blanc, le tout fullweb, ou depuis le mobile.

Par exemple, l'intégration d'OnShape avec Drive : en 1 click (et pas mal de sous) tu as un SolidWorks, hébergé sur AWS. Tu as un workflow d'édition, l'historique des modifications directement accessible. L'intérêt est de ne pas héberger la solution sur GApps. Je ne pense pas que Sharepoint autorise l’interaction avec d'autres plateformes de la sorte (ou alors avec une intégration limité). Cela dit, je ne connais pas bien Sharepoint.

Pas tout à fait d'accord, si le mail a très mal évolué le responsable n'est autre qu'Outlook. La mise en forme des clients Outlook des mails est désastreuse. GMail et quelques autres sont plus respectueux des interlocuteurs. Il m'arrive même de ne pas répondre en format "text-only".

Je suis curieux de savoir ce que M365 propose de si intéressant par rapport à la concurrence (au hasard Drive). Rien ne me semble "plié". Au contraire. Peut-être que la solution n'est pas celle que l'on pense, mais un ensemble de solutions hétérogènes, à coup de R et Jupyter Lab pour remplacer Excel, reveal.js pour remplacer PP (ou arrêter ces bêtises de présentation inutile la plupart du temps). Pour Word, il y a des solutions basée sur Git qui permettent de générer du PDF… Je ne voyais pas le bout du tunnel avec les applications Access, en 2 ans, elles ont totalement disparu de mon entourage.

C'est sûr que de vouloir remplacer Exchange / Office par une solution identique sera un sacré challenge. De même, choisir OnlyOffice, dont 95 % du code vient de MS, c'est prendre un risque. En terme de pérennité, je suis pas sûr que le compte y soit.

Merci pour l'idée! Il est aussi possible de mettre des caméras thermiques avec reconnaissance faciale près de la fameuse machine à café et surveiller la consommation électrique pour la bouilloire.

Si on oublie son mot de passe.

Il y a un thread de discussion, pour ceux intéressés :

Call for Discussion : New Project to support the Wayland display server on Linux

Mince, c'est un oubli ou ce sera ajouter plus tard ?

On peut toujours utiliser swt, le toolkit graphique d'Eclipse, basé sur Gdk, donc supportant nativement Wayland. Malheureusement les applications Swing utilisent AWT ces applications doivent passer par XWayland.

C'est un problème lorsque l'on a besoin du "fractional scaling" pour avoir la même taille de police sur plusieurs écrans différents (ou qu'on aime bien les grosses polices).

Chez Alcatel en 2000, tous les postes aux US et en France que j'ai pu voir (non Solaris) étaient sous Mandrake… Cela-dit, JAMAIS Alcatel n'a donné un euro à Mandrake, car ils avaient un contrat cadre avec SuSE…

On voit à quel point le service des achats (et une certaine incompétence de la direction) entraînent certaines boites Françaises en très bonne santé vers le fond. Sans doute pas les seules responsables, il y a l'incohérence systématique des décisions de la direction aussi (du moins chez Alcatel).

Je teste la mga9, manque plus que la mise à jour de Plasma / Wayland :) .. J'ai quelques petit glitches graphiques avec les cartes Radeon (VII et m'en rappelle plus), sinon le tout est prometteur.

Merci pour ton travail!

Précossément.

À part vouloir tripler les autoroutes dans des zones submergées de béton, Je n'ai pas de souvenir positif envers cette personne. Même Frank Riester me paraît plus sympathique.

Kool! Très tentante cette petite machine … Bravo à AMD, et Valve pour le coup. Ce sont sans doute parmis les contributeurs les plus importants pour le desktop linux qui viendra un jour.

Outre le fait d'apprécier Arch pour la documentation qu'elle nous offre, l'essayer est encore plus instructif. C'est vraiment une distribution méritante : pas trop élitiste car très bien documentée (et en Français SVP), et utilisant les technos récentes.

Allez, un petit arch-chroot pour la route, et j'y suis.

Ton premier message parlait de mono-parentalité dans la littérature… Et du rapport entre son absence et la liberté d'expression (c'est le sujet du journal).

Enfin bon, écoute ça, ça te permettra de relativiser cette association.

C LA MORT

C'est quoi vouloir un enfant ? Un vieux truc réac. J'en ai 2, je sais de quoi je parle.

C'est aussi le mot important de ton commentaire.

T'as des émissions comme "Droit de réponse" aujourd'hui ?

La mono-parentalité n'était pas un sujet à l'époque (on en avait rien à foutre). Aujourd'hui, les droits de l'enfant n'en sont pas un. P-e que demain dans notre avenir radieux, les enfants auront le droit de connaître leur vrais origines (biologique), et qu'on interdira le don de sperme anonyme. Enfin ce serait le minimum pour eux.

Il faut éviter les généralités, mais par rapport à ce que nous subissons aujourd'hui, à l'époque (années 70-80) :

• pas de réseaux sociaux (qu'y a t-il de plus narcissique);
• une culture underground bien plus présente et secrète qu'aujourd'hui, en réel décalage avec la société.

La liberté d'expression semblait plus grande.

Quand tu vois aujourd'hui que le rayon Fnac sur la Franc-maçonnerie est environ 30 fois plus fourni que les rayons "Mathématiques, Physique, Histoire des sciences, Chimie …" réuni, tu prends pitié de cette France qui ne représente plus grand chose dans le monde, à l'image d'un journal de TF1, qui ne parle que de nos petites actualités à nous qui nous sont bien proche Le regard de la France sur le monde, c'est le néant, même si ce n'est pas nouveau.

Avant, il y avait cependant moins de bouquins qui se posent en reflets de la société. Bien avant l'age d'Internet, il y avait des bouquins sur les fusées, les mathématiques, les sciences… il y avait le défi d'expliquer que je ne retrouve plus aujourd'hui (maintenant il y a Wikipedia). Les médias et journalistes d'aujourd'hui n'ont plus que la forme pour s'exprimer, il n'y a plus de fond. La communication des grandes entreprises a pris le pas sur l'information.

Les stéréotypes me semblent également présents dans les oeuvres contemporaines. Il n'y a qu'a regarder la publicité pour du shampoing ou tu voies une personne chauve et toutes les combinaisons de couple (sauf enfants et couple standard), ou les Marvels où l'incarnation de la force est la femme. Avant il y avait les SAS et autres Frédéric Dard, peut-être que ça se prenait moins au sérieux, mais je comprends que le sentiment d'exclusion puisse gêner.

La pub Pétrole Hahn m'a toujours fait marrer, est-ce qu'il fallait la prendre au premier degré?

j'ai recompilé master avec ce pull request il y a 2 semaines (J'observe les pull-requests sur ce projet, il y a d'ailleurs pas mal d'activité). Malheureusement pas eu le temps de trop tester la fin du fameux Topological Naming Problem.

En plus d'être un savoureux numéro pour nous autre les Français, j'espère qu'ils parviendront à merger les patches de realthunder (ce gars est un tueur).

Merci pour l'information.

Merci pour tes journaux, il y a plus de 2 personnes qui apprécient ceux-ci, t'inquiètes !

Et j'approuve ta franchise, il y a une prise de risque appréciable (on est pas forcé d'être d'accord sur tout, désolé pour cette banalité.).