il est très efficace, dans le cas d'une réduction, je précise

je ne sias pas bien, l'algo que j'implementerai en premier serait un algorithme par "proportion" pour chaque pixel de l'image d'arrive, je calculerais quelle proportion de l'image de depart tu dois recevoir. Ensuite je ferrais le calcul en nombre flottant et j'arrondirais a l'entier le plus pres.

Mais tu as d'autre facon de faire ca j'imagine. Par exemple, tu peux faire le meme algo dans different espace de codage des couleurs. Je ne sais pas si ca donnerais d'autre resultats en UV, mais dans l'espace de fourrier, je suis sur que ca donenrais qqch de different.

Tu dois aussi pouvoir utiliser les "derives locales" pour extraire les contours et donne plus d'importance aux contours et ainsi conserver la nettete de l'image.

c'est bizarre, parce qu'on s'attendrait à un truc tout simple de la part de Paint, une pauvre interpolation linéaire, voire aucune interpolation du tout...

il semble entourer les contours de l'image par des pixels légèrement plus clairs... ce doit être un mode de réduction assez catastrophique, mais le fait est que visuellement, ça rend très bien

faire de l'interpolation dans l'espace YUV pourrait etre suffisant pour donner qqch de different. Je n'y connais pas grand chose personnellement.

http://elf.cs.pub.ro/so/wiki/laboratoare/resurse/injections

Article assez intéressant.

Effectivement, ça a l'air intéressant… et un peu inquiétant aussi.

Quelqu'un pour m'aider à écrire le code de la méthode de simplification de Mc Clusky en C ?

Hello,

C'est noël, je me cherche des bouquins, j'ai déjà plus ou moins flashé sur celui là :

http://www.amazon.com/Art-Readable-Code-Dustin-Boswell/dp/0596802293

Maintenant je cherche un autre bouquin qui serait une référence en architecture et en low level en général. Quelques lacunes, pas mal de choses oubliées, il est temps de repasser tout ça de fond en comble. (comportement processeur, mémoire, floating et fixed point, bitwise operations, branching, etc...)
Un livre (ou une suite de) à conseiller en particulier ?

http://elybob.wordpress.com/2010/07/20/sequential-structure-layout-for-speed/

Au passage, une idée de pourquoi le layout de droite est plus rapide que celui de gauche ?

Voir ce site pour voir comment il utilise la matrice :
http://www.codeproject.com/Tips/95443/Sequential-Structure-Layout-For-Speed

La seule chose que je vois c'est que ça réarrange les données en chunks de 16 bytes, mais le byte en plein milieu je ne comprend pas, pourquoi ne pas le mettre simplement à la fin ?

deja il passe de int a byte, mais ca n'explique probablement pas la difference.
Apres je doute assez de ce resultat. J'imagine qu'il essaye de montrer un probleme de prefetch de cache. mais n'importe quel compilateur avec execution profiling devrait arrive a emmetre des instructions de prefetch qui donneront le meme resultat.

Deplus, avoir un byte devrait provoquer des lectures pas aligne sur une ligne de cache et les performances devrait s'effondrer sur tous les processeurs x86 et aboutir a une segfault ou bus error sur tous les power pc et ARM.

je ne sais plus bien dans quel bouquin j'ai appris ces trucs la. Tanenbaum a ecrit un livre la dessus, mais il est souvent critique... Il y en a un autre qui est repute meilleur, mais je ne me rappelle plus du nom.

J'ai envie de dire, oublions son code, il est gorgé d'erreurs, je viens de voir qu'il passe de 8 a 16 dans son poor layout par exemple.

Et j'ai tourné son benchmark sur 2 millions au lieu de 200, si on enlève le premier passage, qui est forcément plus lent, tout est identique ensuite. Ce qui confirme ce que je pensais, c'est pas logique son code. Me voila soulagé.

cependant tu as raison en disant qu'avoir a la fin est probablement meilleur qu'au debut parceque ca fait des access "cache aligned" ce qui arrange certainement la vie pour la vectorisation

C'est pour ça qu'il me faut un livre et pas lire n'importe quoi sur le net

Je viens de voir le prix du Tanenbaum, outch, ça m'a rappelé le prix des 4 volumes de Knuth. ($200 sur amazon ^^)
Dommage que ça soit si cher parce que j'aurai bien prit les 4 volumes. Si ta mémoire te reviens sur celui réputé meilleur, je prend.

http://igoro.com/archive/gallery-of-processor-cache-effects/

Qqchose me turlupine à l'exemple 3. Il démontre qu'en voulant accéder (lecture écriture) au 16ème int de toutes les cache line, il remplit ses cache L1D et unifié à 32kB et 4MB.

Mais par exemple à partir d'un tableau de 32kB, le processeur ne récupère pas à nouveau un chunk de 32kB et donc les timings ne devraient-ils pas baisser au bout de quelques cycles ?

Pareil à 4MB, quand on ache L2 est débordé, s'il a un tableau de 8MB, le cache ne va-t-il pas se remplir deux fois, causant certes pas mal de cache miss au début mais finalement améliorer les perfs sur la longueur ?

Laisse moi reprendre les exemples 1 et 2 pour commencer.

Une ligne de cache fait 64 octets typiquement.
Donc si tu fais:
for (int i=0; i<length; i++) foo += array[i];
tu lis tous les element du tableau et donc tu rapatries length/(64/4) lignes de cache.

Si tu fais
for (int i=0; i<length; i += 16) foo += array[i];
tu accedes a des element avec un offset de 64. Donc tu accede a un element dans chaque ligne de cache que compose le tableau et tu rapatries length/(64/4) lignes de cache.

Si tu fais
for (int i=0; i<length; i += 32) foo += array[i];
tu accedes a des element avec un offset de 128. Donc tu accede a un element dans chaque ligne de cache que compose le tableau et tu rapatries length/(64/4)/2 lignes de cache.

Dans le dernier cas, tu accedes deux fois moins de ligne de cache que dans les deux premier cas. Donc la deuxieme boucle prendra deux fois moins de temps que la premiere.

Maintenant l'exemple 3.

Dans l'exemple 3, il cherche a voir experimentalement la taille des caches. Son experience alloue un tableau de taille N et il ecris dans toutes les cases du tableau d'indice multiple de 16. Il modifie exactement M valeur du tableau avec M constant mais bien plus grand que tous les N qui vont etre teste.

Quand N est inferieur a 32KB. Le tableau tient integralement en cache L1. Donc chaque access au tableau demande exactement une lecture et une ecriture au cache L1.

Quand N est entre 32KB et 4MB. Le tableau tient integralement en cache L2. Donc chaque access au tableau demande au plus une lecture ecrite en cache L2. Cependant, si la ligne de cache acceder est en cache L1, alors l'access sera plus rapide. Or, tous les access memoire sont fait lineairement, donc l'adresse memoire lue n'est pas dans le cache L1 car plus de 32KB de memoire ont ete deplace dans le cache L1 depuis le dernier access a cette addresse memoire. (Ceci est vrai parceque N est plus grand que 32KB.) En bref, quand N > 32KB, le cache L1 est parfaitement inutile parceque aucune des zone memoire place dans le cache L1 ne sera reutilise avant d'etre ejecter du cache (pour y mettre qqch d'autre)

Quand tu as un tableau de plus de 4MB, les caches L1 et L2 sont inutile parceque quand tu lis une addresse tu as lue au moins 4MB de donne depuis le dernier access a cette adresse.

Ce phenomene montre la politique d'eviction de cache. La politique la plus commune est LRU (Least Recently Used). Quand tu cherches a placer une donnee en cache et que ton cache est rempli, tu cherches la ligne de cache que tu n'as pas utilise depuis le plus longtemps et tu la met a la poubelle. LRU a de bonne propriete theorique parcequ'elle minimise optimalement le pire scenario (si tu veux des details, demandes moi. Mais en bref, si tu suppose qu'un adversaire malicieux essaye de te faire faire le plus de defaut de cache possible, LRU est la politique ou il arrive a te faire faire le moins de defaut de cache.)

Finalement, note que les caches materiels ne font pas exactement LRU sur tout le cache parceque le cache est la plupart tu temps associatif a X voies. Mais perso, je n'ai jamais rencontre dans la nature un code qui a de mauvaise perf a cause du fait que le cache n'est pas pleinement associatif.

Paulop: le moindre pavé d'informatique digne d'achat coûte 50€, oui.

Sinon, merci pour le lien sur les effets de cache. Je lirai ça en détail à l'occasion, ça a l'air très instructif vu mon niveau de connaissances sur le sujet.

Qu'elle méthode peut-on envisager pour éviter le débordement du cache ?
Si j'ai un tableau de 8MB et mon cache L2 fait 4MB, je veux éviter de déborder le L2 parce que au delà les performances sont trop mauvaises.

Là à froid j'imagine un compteur et quand on atteint 4MB on récupère localement la seconde partie du tableau ?

QQchose comme

char* p = array[0];
for( int i = 0 ; i < array.length-1 ; ++i )
{
if ( i == 4MB )
{
p = array[i];
}
}

Je doute que ça marche en fait
Doit bien y avoir un moyen de vider le cache pour y mettre la seconde partie du tableau ?