Mon premier blog

Aujourd'hui, j'ai essayé de mettre fin à mes jours: j'ai mangé d'une traite un tas de cachous lajaunie, provenant d'une boite qu'on a retrouvé lors d'une recherche archéologique entre nos bureaux au boulot.....

Bah comme dit le proverbe: "ce qui ne te tue pas te rend plus fort"...... me sens vachement plus fort..... et ... euh.... j'ai tellement d'inspirations qui se battent dans ma tete a propos de mon billet du mois que j'ai du mal a faire le tri......

Voila voila......

Alors du coup, j'ai décidé de vous faire plancher vous aussi sur un petit exercice qui m'a été proposé lors d'un "entretien" (j'aime pas le mot, disons que je discute avec des gens d'opportunités possibles :-) ) avec "un moteur de recherche super connu qui recrute a mort, y compris en europe, mais que je vous donne pas le nom pour que vous cherchiez un peu quand meme").

La question de base est simple (je vous la fait en francais, rien que pour vous): soit un tableau d'entiers qu'il est vachement grand, le tableau (vraiment grand, comme dans "ah la vache, quand meme !", voire "ca fait combien de chiffres, un nombre comme ca ???", ou carrément "mais meme mon disque dur stocke pas autant !!!"). On veut pouvoir compter le nombre de bits de ce tableau a 1 (ou a zéro, commencez pas à chipoter, c'est la meme méthode) rapidement. Pour ca, comme on est pas des raclures quand meme, et qu'on se doute un peu que le comptage des bits un a un dans le tableau va prendre un poil de temps, on vous file autant de mémoire vive que vous voulez (et vu les gens qui disent ca, j'ai tendance à y croire !!!).

On ramasse les copies dans 5 minutes......

Bien sur, il y a un indice: "vous avez plein de RAM"..... on se dit donc tout de suite qu'il va bien falloir utiliser un cache de quelquechose dans l'histoire, tant qu'a faire, ca serait bete de gacher tant de mémoire, de toutes facons, c'est la tournée du patron.

Il ne reste donc plus qu'a trouver que cacher:

- les restes de la blanquette de veau à l'ancienne d'hier soir, déjà. Bonne initiative pour etre sur de pouvoir les finir ce soir, mais soyons lucides, il vaut mieux les cacher au fond du frigo, derrière les trucs infames et repoussants (légumes, salade, yaourts 0%, etc....) que dans de la RAM (surtout qu'il faudrait la retrouver, après, la blanquette, dans autant de mémoire !!!).

- Les clés de bagnole, on oublie tout de suite, ca a fait un bide au ciné, déjà.

- le stock de saucissons. Laissez tomber, je suis un radar ambulant pour trouver toute trace de cochonnaille qui traine a moins de 500 metres, votre sauciflar n'a aucune chance de survie avec moi.....

- Une liste de sites webs intéressants autant qu'originaux, expliquant l'utilité de chaussures à semelles compensées pour la pèche aux crustacés..... mouais, on aura aussi vite fait d'utiliser un moteur de recherche pour ca, hein....

- Des trucs qu'on risque de calculer souvent. Ca, ca parait bien, comme base, pour des trucs à mettre dans un cache lors de gros calculs, ca doit etre ca.....

Et qu'est-ce qu'on va calculer souvent ? Bah le nombre de bits "d'une zone".

Forcément, générer un cache de l'ensemble des résultats possible de toutes les combinaisons du tableau gigantesque n'est pas crédible: ok, on nous a promis toute la mémoire qu'on veut, mais faudrait tant qu'à faire qu'on ne soit pas obligé de demander à nos arrière - arrière - arrière - arrière petits enfants de regarder le résultat (qui sera vraisemblablement 42), tellement ca serait long à remplir.

Non, on va travailler par blocs. Reflexe de base chez tout informaticien normalement (?) constitué (c'est à dire équipé de doigts assez souples pour faire CTRL-Space META-w CTRL-y CTRL-x CTRL-s), travailler par blocs de 32 bits.

On va donc faire une table de 2^32 valeurs, chaque valeur représentant le nombre de bits à un de sa position. Soit, en pratique: cache[i]=nbbits(i)

Sauf que 2^32 valeurs, ca fait quand meme déjà pas mal. Aucun problème pour ce qui est de la quantité de mémoire, c'est toujours la tournée du patron (rappel: ne FAITES PAS CA CHEZ VOUS !), c'est plutot pour le temps de remplissage que ca pourrait etre assez long.

Du coup, on peut se dire "bah pas grave, on va travailler avec un cache sur 8 bits, au lieu d'un cache sur 32 bits". Bah oui, un cache comme ca sur 8 bits, ca se remplit en meme pas 1 seconde sur une machine moderne.

Et si on pousse un peu plus loin, on peut meme se rendre compte que, une fois qu'on a le cache 8 bits, on peut s'en servir pour très rapidement générer le cache sur 32 bits (ou n'importe quel autre multiple de 8):

cache32[i] = cache8 [ (i&0xFF000000)>>24] + cache8 [ (i&0x00FF0000)>>16] cache8 [ (i&0x0000FF00)>>8] cache8 [ (i&0xFF)]

Et hop, le tour est joué.....

Sauf qu'en en rediscutant et en y réfléchissant, y'a un truc pas aussi simple que ca.....

Les machines actuelles sont tout, sauf un truc simple avec "un processeur" et "une mémoire".

Et entre autres choses, il y a des mémoires cache, qui sont nettement plus rapides que la mémoire principale, mais aussi nettement plus petits.

Et si on sait qu'un tableau de 256 entrées (notre cache de calcul sur 8 bits) tiendra meme sur dans la mémoire cache du 68000 de mon Amiga 500, je dois me rabbatre sur un PC récent pour qu'une table de 65536 entrées (un cache de 16 bits) aie de bonne chances de rester complètement dans la mémoire cache du CPU pendant toute l'exécution du programme, et ma table de 2^32 entrées, ca sent le sapin (pour ceux qui, au début de l'article, étaient déjà en train de préparer un commentaire genre "ah le noob, maintenant on a des machines sur 64 bits", votre table de 2^64 entrées dans un cache CPU, vous pouvez vous la mettre au fond a droite..... s'il y a assez de place, bien sur....).

On se trouve donc confronté à un épineux dilemne:

Soit on traite beaucoup de bits d'un coup (non, ceci n'est pas une insulte ou une phrase déplacée, c'est juste une discussion d'informaticiens), mais on est surs de faire une quantité massive de cache miss (je parle bien du cache mémoire du CPU), donc on va lire très souvent notre cache de calcul en mémoire principale (qui est plus lente).

Soit on s'assure que notre cache de calcul restera dans le cache du CPU, mais on travaille par plus petites quantités de données.

Et la, vous vous dites "ouhlala, heureusement qu'une équipe de professionel va faire ce test à ma place, dans un environnement stérile, avec des charlottes qui donnent l'air con sur la tete, un gros bouton rouge pour tout arréter en cas de problèmes, une équipe de secours sur place prète à intervenir et tout et tout !!".....

Et bien sur, en finaud (terme officialisé par l'académie francais pour traduire "hacker", qui, je vous le rappelle, n'a au départ aucune connotation négative et signale juste une curiosité technique) que je suis, j'ai sorti mon éditeur préféré, et j'ai commencé à coder le "proof of concept !".

Le quoi ?

Le "proof of concept !"

Le quoi ?

Le .... le "proufe aufe concepte", la preuve qui prouve que le concept marche, quoi.....

Aaaahhhh !!!! le "proof of concept !".....

Ouais, voila, j'aurais du commencer par dire ca..... je peux continuer, maintenant, c'est bon ?

Donc, disais-je, avant d'avoir été innoportunément interrompu (m'en fous, j'ai les traces des gens qui viennent lire le blog, je pourrai retrouver le coupable !), j'ai commencé à coder vite fait une preuve de concept ("une proof of concept", quoi).

Avant de me rendre compte d'un léger tout petit détail: je n'ai PAS toute la mémoire que je veux sur ma machine, et quand je déclare un tableau de 0xFFFFFFFF entrées (ouais, si je fais 1<<32 ou 0xFFFFFFFF+1, ca fait un tour de compteur, ca vaut zero....), mon compilateur m'envoie bouler, poliment, certes, mais fermement.....

Et meme si j'essaie subtilement un

unsigned char bits_32[1<<16][1<<16];

meme résultat, on m'explique que je suis bien gentil, mais qu'il faudrait pas non plus que je rève eveillé, ca existe pas des tabeaux comme ca, dans la vraie vie....

Du coup, je me retrouve dans un cas "a la con": un tableau de 2^16 octets, il va tenir dans mon cache, et un tableau de 2^24 octets, c'est une valeur "a la con" (en pratique, on n'aura pas la meme accélaration qu'en manipulant des mots machine, soit des blocs de 32 bits).....

Du coup, me reste 2 solutions:

- Ressortir mon Amiga.... tiens, si j'ai un peu le temps ce WE, je vais essayer.

- Finir mon process de recrutement chez "un moteur de recherche super connu qui embauche un max en ce moment", quoique ca m'arrangerait carrément qu'ils ouvrent un campus pas trop loin de Lille, plutot que de me proposer de bosser en Suisse, au Royaume Uni ou dans les pays scandinaves.....

Au moins, la bonne nouvelle, c'est que j'aurai pas eu a mettre une charlotte blanche qui donne l'air con sur la tete aujourd'hui.........