Warum nicht?
Nun ja, bei einem 35 mp Bild kann ich mir zwar vorstellen, dass ich vielleicht 50% herausholen kann, aber das ist in dieser Zeit Region nicht so relevant. zumal 35 mp Bilder eher die Ausnahmen sind. Kleinere Bilder z.B. in HD Auflösung dauern ca. 150ms und da lohnt sich vermutlich kein MT.
Bei meiner Set-Variante ist die MT-Variante beilspielsweise bei 4 logischen Prozessoren bei mir um den Faktor 3,2 schneller.
Also deutlich schneller als nur die 50% die du erwartest.
Aber im Grunde stimmts schon - wenn's nicht notwendig warum dann noch einen zusätzlichen Aufwand betreiben und neue Unwägbarkeiten mit reinholen.
Also wie gesagt: Was willst du genau zählen bzw. wozu brauchst du es?
Ja, damit hast Du natürlich Recht!
Eigentlich will ich damit den Benutzern meines Programms nur eine Zusatzinformation bieten.
Insofern sollte die PARGB-Methode wohl ausreichend sein.
Anfangs dachte ich auch, dass ich dafür schnell mal eine Funktion schreibe und alles ist gut.
Dass sich das Problem quasi als Beispiel für die Schwäche einer Interpretersprache herausstellen sollte, habe ich nicht geahnt.
Auf jeden Fall hat es sich für mich zu einem sehr interessanten Thema entwickelt, bei dem ich eine Menge dazu gelernt habe. 
Und ich danke euch allen für die rege Teilnahme und die tollen Lösungen! 
Eigentlich will ich damit den Benutzern meines Programms nur eine Zusatzinformation bieten.
WAS?!? Wir schwitzen hier Blut und Tränen, rackern unermüdlich um noch das letzte bisschen Quäntchen rauszukitzeln.
Und für was?: Für ne popelige Zusatzinformation!
Wir dachten hier ginge es um Leben und Tod oder zumindest den Weltfrieden!
... 
Ich finde es immer super sich auf ein eigentlich nebensächliches Problem mit voller Kraft draufzustürzen 
WAS?!? Wir schwitzen hier Blut und Tränen, rackern unermüdlich um noch das letzte bisschen Quäntchen rauszukitzeln.
Separates the boys from the men
Wie viele Farben hat dieses 32-bit PNG Bild wirklich?
IrfanView: 18276
GIMP: 17894
XnView: 17894
Oscar's Variante: 18161
Meine FB Variante: 19520
GIMP und XnView scheint nur 24- bit zu zählen.
Lang lebe das Bitmap Dateiformat, dort ist es wenigstens eindeutig definiert welchen Wert welche Farbe hat...
Wie viele Farben hat dieses 32-bit PNG Bild wirklich?
Alle falsch.. hier ist die richtige Zahl! 
Pff... langweilier, wenn dann wird per Hand gezählt 
Also!
Das hier hat mir irgendwie keine Ruhe gelassen. Wir hatten jetzt Assembler, C, C++... Und C++ sogar multithreaded, allerdings durch die Sets relativ langsam. Ich hab also mal eine Implementation in purem Win32-C mit Threading geschrieben. So langsam muss ich aber auch kapitulieren. Hier mal die Statistiken, jeweils meine C-MT-Implementation gegen AspirinJunkies C++-Sets.
Folgende Bildmaße wurden verwendet: klein (1024x768), mittel (1920x1280), groß (5590x3731).
x | AJ Single | AJ Multi | CT Multi
klein | 120.36 | 51.87 | 25.46
mittel | 375.95 | 151.47 | 36.89
groß | 2340.58 | 350.63 | 202.09Ich weiß zwar nicht, warum meine Implementation bei dem mittleren Bild so extrem heraussticht... Aber prinzipiell kann man so auf jeden Fall noch was rausholen! Ich teile das Bild einfach in mehrere gleiche Abschnitte auf und gehe diese dann in verschiedenen Threads durch. Am Ende, wenn alle Threads fertig sind, zähle ich die einzelnen Farben.
typedef struct arrayinfo {
unsigned int* start;
unsigned int length;
} arrayinfo_t;
unsigned char* colors;
const int colorLen = 0xffffff + 1;
DWORD WINAPI colorThread(void* data) {
unsigned int i;
arrayinfo_t* part = (arrayinfo_t*) data;
for(i = 0; i < part->length; i++) {
colors[*(part->start + i) & 0xffffff] = 1;
}
return 0;
}
int DLL_EXPORT getColorCount(unsigned int* pixel, int len) {
int i, colorSum = 0;
colors = (unsigned char*) calloc(colorLen, sizeof(unsigned char));
HANDLE threads[THREADS];
arrayinfo_t* data[THREADS];
for(i = 0; i < THREADS; i++) {
data[i] = (arrayinfo_t*) malloc(sizeof(arrayinfo_t));
data[i]->start = pixel + i * (len / THREADS);
data[i]->length = len / THREADS;
threads[i] = CreateThread(NULL, 0, colorThread, data[i], 0, NULL);
}
WaitForMultipleObjects(THREADS, threads, TRUE, INFINITE);
for(i = 0; i < THREADS; i++) {
CloseHandle(threads[i]);
free(data[i]);
}
//calculate sum
for(i = 0; i < colorLen; i++) colorSum += colors[i];
free(colors);
return colorSum;
}DLL, vollständiger Source usw. alles im Anhang.
Hmm, kannst du bitte mal die FB Version checken? Die FB Version ist auf meiner Kiste ungefähr gleich schnell wie deine MT Version!
Download: https://www.mediafire.com/file/8qansw4x5…CountColors.zip
Ich habe auch das 36 MPixel Bild hinzugefügt!
Danke.
FB:
Loading image
Image dimension: 7360x4912
Counting all 24-bit colors
Unique color count: 402990
321.7085356591269 msChesstiger's MT:
Zeit: 318.318642564774 ms
Anzahl der Farben: 402990Klasse!
Prinzipiell machst du bei deinem Threading das was manuell OpenMP für mich macht.
Wirklich interessant finde ich aber die Tatsache dass die endgültige Zählung der Farben bei dir in einer Schleife über 16.777.216 Elemente läuft.
Und das am Ende als Single-Thread!
Das dies im Endeffekt dennoch meist schneller ist als die Variante per atomaren Inkrement erstaunt mich wirklich.
Ah, das hab ich ganz übersehen. Bei mir kommt da raus...
klein: 18.49 ms
mittel: 33.51 ms
groß: 195.28 ms
riesig: 285.78 ms
Ist also dennoch ein My schneller als der simple C-Code von oben!
Selbst, wenn ich noch die Summation der Werte parallelisiere, ist da nicht mehr so viel zu holen.
( AspirinJunkie Da war echt noch was zu machen. Atomare Inkrements scheinen nicht ganz so performant zu sein... Aber auch hier macht sich MT nochmal bezahlt.)
klein: 19.78 ms
mittel: 32.83 ms
groß: 182.60 ms
riesig: 254.05 ms
#define THREADS 4
typedef struct pixelainfo { /* pixel array info */
unsigned int* start;
unsigned int length;
} pixelainfo_t;
typedef struct countinfo {
unsigned int start;
unsigned int length;
unsigned int ret;
} countinfo_t;
unsigned char* colors;
const int colorLen = 0xffffff + 1;
DWORD WINAPI colorThread(void* data) {
unsigned int i;
pixelainfo_t* part = (pixelainfo_t*) data;
for(i = 0; i < part->length; i++) {
colors[*(part->start + i) & 0xffffff] = 1;
}
return 0;
}
DWORD WINAPI additionThread(void* data) {
int i;
countinfo_t* part = (countinfo_t*) data;
part->ret = 0;
for(i = 0; i < part->length; i++) {
part->ret += colors[part->start + i];
}
return 0;
}
int DLL_EXPORT getColorCount(unsigned int* pixel, int len) {
int i, colorSum = 0;
colors = (unsigned char*) calloc(colorLen, sizeof(unsigned char));
HANDLE threads[THREADS];
pixelainfo_t* pixelparts[THREADS];
countinfo_t* countparts[THREADS];
for(i = 0; i < THREADS; i++) {
/* partitioning pixel map and sum map, also start color count threads */
pixelparts[i] = (pixelainfo_t*) malloc(sizeof(pixelainfo_t));
pixelparts[i]->start = pixel + i * (len / THREADS);
pixelparts[i]->length = len / THREADS;
threads[i] = CreateThread(NULL, 0, colorThread, pixelparts[i], 0, NULL);
countparts[i] = (countinfo_t*) malloc(sizeof(countinfo_t));
countparts[i]->start = i * (colorLen / THREADS);
countparts[i]->length = colorLen / THREADS;
}
/* wait for color count threads (JOIN) */
WaitForMultipleObjects(THREADS, threads, TRUE, INFINITE);
for(i = 0; i < THREADS; i++) {
/* close color count threads, start addition threads */
CloseHandle(threads[i]);
free(pixelparts[i]);
threads[i] = CreateThread(NULL, 0, additionThread, countparts[i], 0, NULL);
}
/* wait for addition threads (JOIN) */
WaitForMultipleObjects(THREADS, threads, TRUE, INFINITE);
for(i = 0; i < THREADS; i++) {
/* close addition threads, calculate final sum from parts */
CloseHandle(threads[i]);
colorSum += countparts[i]->ret;
free(countparts[i]);
}
free(colors);
return colorSum;
}Das ist noch etwas, aber nicht so viel, wie ich erwartet hätte. Wobei man fairerweise auch sagen muss, dass jetzt die Grenze des Machbaren erreicht ist. Der eigentliche DllCall dauert bei meiner neuen Multithreaded-Variante selbst für dein Riesen-Löwenzahnbild nur noch knappe 28 ms, also Pi mal Daumen 10% der Zeit. Der Rest geht für LockBits drauf..... Jetzt wäre der Moment gekommen, dort was zu optimieren.
Edit:
Ich habe mich jetzt mal etwas informiert. LockBits erstellt eine komplette Kopie der Bitmap. Das muss natürlich Ar...langsam sein. Man könnte evtl. GDIPlus durch was anderes ersetzen.
Edit²:
So, ich habe jetzt eine Implementation mit FreeImage gebastelt. Das Bild wird per FreeImage in AutoIt geladen und an meine DLL weitergegeben. Allerdings zeigt sich hier, dass die Werte für JPEGs etwas abweichen. Das Verhalten wurde ja schon zuvor beobachtet. Allerdings ist so nochmal ein MASSIVER Geschwindigkeitsvorteil zu erreichen. Beispiel am Löwenzahn-Bild: GDIPlus + DLL => ~250 ms, FreeImage + DLL => ~191.93 ms.
chesstiger : Klasse Version und super schnell! Aber halt auch nicht mit voller Alphakanal-Unterstützung.
Ich denke, das Problem dabei dürfte klar sein. Für die Array-Varianten kann man nicht 4GB Speicher reservieren.
AspirinJunkie und UEZ haben zwar gezeigt, dass es möglich ist, auch den Alphakanal mit einzubeziehen und das klappt bei den bisherigen Bildern auch recht gut.
Ich dachte mir aber, dass die Schwachstelle dieser Umsetzungen bei der Anzahl der Farben liegt. Solange das "nur" eine Million Farben sind, ist noch alles gut, aber was passiert bei 7680 x 4320 Pixel (8k-Bildern)?
Und um das mal mit möglichst vielen (33.177.600) Farben zu testen, habe ich ein Testbild generiert:
#include <GDIPlus.au3>
_GDIPlus_Startup()
$iW = 7680
$iH = 4320
$hImage = _GDIPlus_BitmapCreateFromScan0($iW, $iH)
Global $iTimer = TimerInit(), $iColor = 0, $iTimerDiff = TimerDiff($iTimer), $iAlpha
For $iY = 0 To $iH - 1
For $iX = 0 To $iW - 1
_GDIPlus_BitmapSetPixel($hImage, $iX, $iY, BitShift(Mod($iAlpha, 256), -24) + $iColor)
$iColor += 1
$iAlpha += 1
If TimerDiff($iTimer) - $iTimerDiff > 250 Then
$iTimerDiff = TimerDiff($iTimer)
ToolTip($iColor)
EndIf
Next
Next
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : TimerDiff($iTimer) = ' & TimerDiff($iTimer) & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
_GDIPlus_ImageSaveToFile($hImage, @ScriptDir & '\Test.png')
_GDIPlus_BitmapDispose($hImage)
_GDIPlus_Shutdown()Das erstellen dauert aber mehrere Minuten. Wer nicht so lange warten will, kann sich das Bild von meiner Homepage herunterladen: http://www.technik-hobby.de/test/index.html
Die DLL von AspirinJunkie funktioniert auch mit diesem 8k-Bild. Wobei jetzt die Single-Thread-Version (ca. 14 s) schneller ist, als die Multi-Thread-Version (ca. 21 s). 
UEZ: Deine FB-Exe stürzt nach kurzer Laufzeit ab (nachdem das 8k-Testbild geladen wurde).
Für ein ARGB-Bild benötigt man aber nicht zwangsweise 4 GB Speicher! Man kann den Speicherbedarf erheblich reduzieren, man muss nur bisher ungenutzten Speicher effektiv nutzen.
Im Endeffekt haben wir für jede mögliche Farbe (das sind 2^32 + 1, von #00000000 bis #FFFFFFFF) nur die Information, ob sie auftritt oder nicht. Zwei mögliche Zustände... Das schreit doch nach der Kodierung in einem Bit!
Man kann zum Beispiel ein 2^28 + 1 Array of Short (2 Byte) verwenden. (2^28 + 1) * 2 Byte = 536.870.914 Byte = 512 MByte. Das ist zwar auch nicht wenig, aber annehmbarer als 4 GByte.
Praktisch habe ich das so gelöst, dass die vordersten 4 Bit der Farbe (also die vordere Hälfte des Alpha-Wertes) mit dem jeweiligen Array-Element (indexiert durch die restlichen 28 Bit) verodert werden. Am Ende beim Summieren zähle ich dann einfach die Bits jedes Elementes. Funktioniert prima, und dauert bei Oscars Testbild inklusive LockBits... Ziemlich genau eine Sekunde, wobei davon auch nur knapp 400 ms für den DllCall draufgehen. Alles im Anhang!
#include "main.h"
#include "32bit.h"
unsigned short* colors32;
unsigned int colorLen32 = 0x0fffffff + 1; //28 bit
__inline int numberOfSetBits(unsigned int i) {
/* here be dragons */
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
DWORD WINAPI colorThread32(void* data) {
unsigned int i;
pixelainfo_t* part = (pixelainfo_t*) data;
for(i = 0; i < part->length; i++) {
colors32[*(part->start + i) & 0x0fffffff] |= 1 << ((*(part->start + i) & 0xf0000000) >> 28);
}
return 0;
}
DWORD WINAPI additionThread32(void* data) {
unsigned int i;
countinfo_t* part = (countinfo_t*) data;
part->ret = 0;
for(i = 0; i < part->length; i++) {
part->ret += numberOfSetBits(colors32[part->start + i]);
}
return 0;
}
long DLL_EXPORT getColorCount32(unsigned int* pixel, int len) {
int i;
long colorSum = 0;
colors32 = (unsigned short*) calloc(colorLen32, sizeof(unsigned short));
HANDLE threads[THREADS];
pixelainfo_t* pixelparts[THREADS];
countinfo_t* countparts[THREADS];
for(i = 0; i < THREADS; i++) {
/* partitioning pixel map and sum map, also start color count threads */
pixelparts[i] = (pixelainfo_t*) malloc(sizeof(pixelainfo_t));
pixelparts[i]->start = pixel + i * (len / THREADS);
pixelparts[i]->length = len / THREADS;
threads[i] = CreateThread(NULL, 0, colorThread32, pixelparts[i], 0, NULL);
countparts[i] = (countinfo_t*) malloc(sizeof(countinfo_t));
countparts[i]->start = i * (colorLen32 / THREADS);
countparts[i]->length = colorLen32 / THREADS;
}
/* wait for color count threads (JOIN) */
WaitForMultipleObjects(THREADS, threads, TRUE, INFINITE);
for(i = 0; i < THREADS; i++) {
/* close color count threads, start addition threads */
CloseHandle(threads[i]);
free(pixelparts[i]);
threads[i] = CreateThread(NULL, 0, additionThread32, countparts[i], 0, NULL);
}
/* wait for addition threads (JOIN) */
WaitForMultipleObjects(THREADS, threads, TRUE, INFINITE);
for(i = 0; i < THREADS; i++) {
/* close addition threads, calculate final sum from parts */
CloseHandle(threads[i]);
colorSum += countparts[i]->ret;
free(countparts[i]);
}
free(colors32);
return colorSum;
}UEZ: Deine FB-Exe stürzt nach kurzer Laufzeit ab (nachdem das 8k-Testbild geladen wurde).
Also bei mir läuft die Exe:
Loading image
Image dimension: 7680x4320
Counting all 32-bit colors
Sorting color array
Counting unique colors
Unique color count: 33177599
Time: 8275.271474720455 msWenn ich nur die 24-Bit betrachte (Inline ASM):
Loading image
Image dimension: 7680x4320
Counting all 24-bit colors
Unique color count: 16777216
Time: 701.3580921111782 msProbiere bitte mal diese Exe.
Probiere bitte mal diese Exe.
Ja, mit der Version funktioniert es, ohne Absturz:
Loading image
Image dimension: 7680x4320
Counting all 32-bit colors
Sorting color array
Counting unique colors
Unique color count: 33177599
Time: 5697.371319770126 ms