Reprise du message précédent :

 
Custom allocateur ?

Gagné
 
Le GC de go n’est pas générationel, et il est tweaké principalement pour limiter les pauses
 
Leur théorie c’est que t’as jamais besoin d’une G0 parce que les objets qui vivent pas longtemps ne s’échappent pas, donc ils sont jamais alloués sur le tas.

je suis en train de soupçonner append(), je cherche son code source là.

Tu append plein de valeurs une à une sur une slice vide?

yep

Peut valoir le coup de préallouer avec make(T[], 0, <cap> ) alors.

Et si t'as une boucle autour du remplissage de ta slice, de réutiliser la slice avec un magnifique

pour la "vider" sans désallouer l'array qui est derrière (notes que si t'as des pointeurs dedans ça va pas les relâcher vu que l'array les retient, auquel cas tu peux vouloir tout mettre à nil d'abord).
(à la main naturellement parce que les abstractions c'est pour les niais)

 
genre le mari de ma belle soeur, ie la soeur de ma femme.
 

ahhhhh ton beau-beauf

dites, vous avez une idée pour une représentation très compacte d'histogrammes ?
l'image est en palette avec très peu de couleurs (une dizaine), il faut que je puisse ajouter et soustraire des histogrammes très vite aussi.
 
pour l'instant, j'en suis à ça:

type StoredHistogram struct {
    colors []byte
    values []uint64
}

mais cherche encore mieux. j'ai des tuiles entières d'histogrammes.

L'Europe régule, donc vous allez avoir un léger tassement de marge (faudra doubler le headcount de jubi pour servir de caution et dire que vous faites des efforts et limiter le montant des amendes) et des barrières à l'entrée insurmontable.
Heureusement il y a les taxis automatiques et le healthcare
 

Tu as quand même deux débats qui amènent des réponses différentes et contradictoires : tu as le problème de privacy, qui inquiète beaucoup l' "Opinion publique" avec déjà des actions en cours pour l'adresser, et tu as le problème de compétition, ou plutôt son absence, qui permet d'en faire le minimum et qui intéresse surtout les technocrates. Sur le second je suis assez sceptique sur les actions en cours aux USA, vu les préoccupations sur la Chine je pense que le théâtre actuel ne va pas donner grand chose et que ce qui est bon pour Google/Facebook est bon pour Washington. Cela va aussi beaucoup crier au protectionnisme quand l'Europe de l'ouest va se mettre à légiférer.
 
 

BEPS n'est pas passé donc vous (pouvez) continuez
 
 
Et pour faire plaisir à Jubi alors qu'il doit finir son rapport hebdomadaire sur ce qu'il a fait cette semaine pour détruire les démocraties :
 

(c'est du très très lourd une fois de plus par Marianne : Amazon rachète des sites industriels pour en faire des entrepôts et embaucher des chomeurs, et la BPI utilise AWS, on est sur des affaires d'Etat digne des écoutes de l'Elysée).

type StoredHistogram struct {
    colors []byte
    values []uint64
}

J'ai rien compris.

type StoredHistogram struct {
    colors []byte
    values []uint64
}

 
En général pour stocker les données je ne m'emmerde pas et j'ai des map<double, color> qui représente un intervalle normalisé (la clef va de 0 à 1)   (+ une méthode un peu complexe à côté pour étalonner cet intervalle en fonction d'un min/0/max arbitraire)
T'as un soucis de mémoire ici ?

ouais je crois que t'as raison, je vais séparer les couleurs, et considérer que chaque image est une image binaire pour chaque couleur de la palette.  
ça va être super creux et je vais pouvoir utiliser 3 représentations: la tuile est pleine, la tuile est creuse, ou la tuile a du mouvement (cas normal).

d'additionne et je soustrais des histogrammes l'image est suffisamment grosse pour pas renter en mémoire, oui. elle est tuilée sur disque par contre, donc j'ai des caches à différents niveaux de hiérarchie et si le dernier niveau est viré de la mémoire, je peux retourner la chercher sur le disque.
 
J'ai aussi tout un système compliqué pour essayer d'accéder les tuiles dans l'ordre, pour essayer d'éviter le churn

Par "tuilée" tu veux dire que ton histo est stocké sur disque et que tu charges qu'une sous-séquence des valeurs à chaque fois, genre t'as 50 miyards de (catégorie, valeur) mais tu vas prendre just entre 500 millions et 600 millions en mémoire? Ou bien aucun rapport? Et comment marchent tes additions et soustractions, tu combines les valeurs si elles sont de la même "couleur" ou ça change de "couleur"?

Monochrome ?

Monochrome c'est ambigu, tu peux avoir du monochrome avec des nuances (le niveau de gris est monochrome).

Binaire est un sous-ensemble de monochrome qui n'a que deux valeurs.

Alors sur le disque j'ai une image "normale" sauf qu'elle fait 70Go a des headers spéciaux, et est stockée en fragments de 256x256 pixels.
l'espace des couleurs est une petite palette (une dizaine de valeurs)
 
je sais pas trop ce que je peux révéler, mais en gros il existe un système de filtrage qui s'appelle "box filtering", qui a une implémentation très smart avec https://en.wikipedia.org/wiki/Summe [...] _algorithm quand t'es en RGB, tu fais l'algo 3 fois, une fois par bande de couleur.
 
Quand t'es en palette le mieux que tu puisses faire, c'est trouver la couleur majoritaire dans un rectangle (tu passes d'une moyenne à une majorité), donc l'unité de compte c'est l'histogramme, tu calcules l'histogramme d'un rectangle et tu va chercher la couleur majoritaire dessus. et des histogrammes ça s'additionne et ça se soustrait bien (par couleur). Et tu as l'équivalent d'un box filter sur une image palettisée. Mais tu as fait quelques millions d'opérations sur des histogrammes.
 

monochrome et où les valeurs sont 0 ou 255 et rien entre.

Oh ok cette histoire de couleur ça m'avait perturbé, je croyais que c'était des canaux de couleur. Du coup on a une image monochrome 4bits, et on fait des histogrammes pour chaque tuile ? Donc 10 entiers par tuile ?

on fait des intégrales d'histogrammes par tuile, sois à c'qu'on te dit !

ça fait 65536 histogramme par tuile, à multiplier par la taille de stockage d'un histogramme

Et ce serait pas mieux, plutôt que de calculer la valeur majoritaire, de repasser en rgb et de chercher la couleur de ta palette la plus proche de la moyenne de la zone d'intérêt ? La couleur majoritaire ça paraît un peu raide

C'est sur que du point de vue calcul c'est un peu plus gourmand mais bon...

niet, ça serait pas mieux.

Ouais j'avais pas encore compris. Maintenant c'est bon. De toutes façons, ce qui compte c'est les valeurs.

Mais bon voila, chaque histogramme c'est 10 entiers (16 bits si t'es vraiment radin), x65536 pixels. C'est quoi la question déjà ?

Si tu veux faire le malin, tu cases ça dans 5 images monochromes 32 bits et tu fais tes calculs en réutilisant des bibliothèques de traitement d'image.

y'en a 7 millions des paquets de 65536 pixels. mais ils sont eux-mêmes issus d'additions et soustractions, et ces opération mettent le GC en vrac.

Time for The Ballast!

Ça fait quoi... 10TB. C'est trop?

oui

type StoredHistogram struct {
    colors []byte
    values []uint64
}

Pour 10 couleurs, une technique peut être, au lieu de stocker les valeurs, de stocker l'écart à la valeur centrale ou moyenne. L'avantage, c'est que celui-ci ne tient que sur un octet au lieu de deux. Je pense que tu dois pouvoir faire toutes les opérations d'addition/soustraction dans cette représentation compacte et ne convertir qu'au tout dernier moment.

Sinon, j'imagine que les opérations doivent pouvoir être vectorisées pour tirer partie du SIMD, voire d'une carte graphique, mais ça nécessite un codage un peu sioux. C'est peut-être l'occasion de s'amuser avec CUDA.
En tout cas, même sans recourir à ces techniques, bien réfléchir à la représentation en mémoire (utiliser au maximum l'alignement) va avoir une influence majeure sur les performances de tes algorithmes. Ca va probablement  faire du code pédestre à base de boucles imbriquées mais pour ce qui est des perfs, c'est encore ce que le compilateur optimise le mieux.

Si je comprends bien, tu dois calculer des sum area tables sur les histogrammes eux-mêmes ?

disons que mon espace de travail c'est des histogrammes au lieu de RGB.

Mais du coup quand tu dis que 10 To ( je me suis gourré, c'est 3) c'est trop, comment tu comptes faire ? C'est la taille des histogrammes. Le seul moyen de descendre c'est d'en baisser la résolution, tu peux passer en 8 bits au lieu de 14 mais ça va pas changer l'ordre de grandeur.

je sais pas encore trop, je suis en train d'évaluer diverses techniques, j'espérais juste obtenir des idées que j'aurai pas vues ici, mais manifestement j'ai juste rendu tout encore plus compliqué, parce que maintenant je dois expliquer tout en détails sans que personne ne propose rien de nouveau, voire une subir une vague hostilité.

hum, en fait j'ai une 20aine de couleurs, ~800 000 tuiles et seulement 8 d'entre elles sont uniformes en couleur.

Y'a pas d'hostilité, il y a que si tu retiens des infos on ne peut pas forcément donner d'idées pertinentes. Après c'est toi qui vois ce que tu peux/veux dévoiler ou non, sachant que ça a l'air assez spécifique, mais avec des infos livrées au compte-goutte, on est obligé de combler les trous ou se limiter à des généralités, et à toi de prendre ce qui est pertinent ou pas.

ouais, c'est la merde les clients pas open-source à moitié paranos.

j'vais peut-être réponde à hepha, si ça m'aide pas ça peut aider les autres. Pour chaque tuile je calcule et garde en mémoire le bord droit et bas (et en particulier la coins bas droite) de son intégrale. Et ensuite je les propage à toutes les tuiles, comme ça je sais placer chaque tuile dans le reste de l'image intégrale. Ensuite si j'ai besoin d'une valeur dans une tuile, je sors la tuile du disque et je vais calculer la valeur dessus, je replace la valeur dans l'image globale grace à ces tokens dans les coins. Et j'ai essayé d'être malin avec une hiérarchie de cache et des accès consécutifs pour compenser le temps de calcul, mais j'ai pas trouvé la bonne formule encore.

edit: c'est pour ça que ma question initiale portait sur la représentation, cette technique suppose de pouvoir faire une tonne d'additions rapidement

Je prends le sujet en cours, donc je vais peut-être dire une bêtise. Mais est-ce que la représentation intervallaire qu'on utilise dans certains cas (quand on a plus de lecture que de modifications des infos) pour modéliser une arborescence/hiérarchie en BD pourrait pas t'aider pour les accès ?

j'essaye de réfléchir à un truc comme ça aussi, mais j'ai le cerveau poussif.

Désolé je vais pas apporter de réponse, mais le sujet m'intéresse pour la curiosité personnelle.
Juste pour savoir si j'ai bien compris.
On a une image qui fait 70go en tout, découpée en tuile de 256x256 pixels sur le disque.
Et la structure de données proposée au dessus correspond, pour un pixel de la tuile, à un histogramme intégral pour chacune des couleurs de la palette (une dizaine).
Et tu voudrais une représentation globale de l'image (j'imagine le premier niveau en mémoire?) avec les histogrammes intégral du "premier niveau" puis redescendre plus bas pour avoir la valeur qui va bien ?

disons que je vais faire une tonne d'accès random sur l'image intégrale globale.

Ok c'est plus clair pour moi.