Skip to main content
gamedev.net
🔒 Locked

Optimize count algoritm

Started by Mizipzor 49 replies 6.7k views
Original Post
Mizipzor
Mizipzor
Im doing an algoritm that counts the number of unique colors in a bmp picture. It works well when there are very few colors, but as soon as the unique colors are a few thousands it gets paaainfully slow. I use a std::map. Ive looked into std::vector and std::list to, but this one seemed to be the fastest. Heres the code for the algoritm itself: 

void colorCount()
{
        SDL_Surface* source = SDL_LoadBMP("a.bmp");
        Slock(source);	// lock surface

	rgb col;	// the current color we are working with
	pair< map<int, rgb>::iterator, bool > pr;
	map<int, rgb>::size_type size;

	// COUNT THE COLORS ----------------------------------------------------------------------------
	for(int y = 0; y < source->h; y++)
	{
		for(int x = 0; x < source->w; x++)
		{
			// get the color in Uint32
			SDL_GetRGB(getPixel(source, x, y), source->format, &(col.r), &(col.g), &(col.b));

			map<int, rgb>::iterator i;
			for(i = colors.begin(); i != colors.end(); i++)
			{
				if(i->second == col)
				{
					i->second.count++;	// we have seen it before, increase the count
					break;
				}
			}
			if(i == colors.end())	// we havent seen this color before, store it in the map
			{
				size = colors.size();
				pr = colors.insert(col_pair(size, col));
			}
		}

		cout << y << " lines of " << source->h << " done, found " << colors.size() << " unique colors so far." << endl;
	}
	cout << "Color counting DONE.\n----------------------------------------------------------------\n\n";

	Sulock(source);	// unlock surface
}
Heres the rgb color class I made along with the actual color map and a typedef: 

class rgb
{
public:
	Uint8 r;
	Uint8 g;
	Uint8 b;
	int	count;	// how many times have we seen this exact color?

	rgb()
	{
		r = g = b = 0;
		count = 1;
	}
	
	bool operator==(const rgb& a)
	{
		if(r == a.r && g == a.g && b == a.b)
			return true;
		else
			return false;
	}
};

map<int, rgb> colors;
typedef pair <int, rgb> col_pair;
Any tips for speeding this up are most welcome! :)
Palidine
Palidine
you should probably just use a std::set<rgb>

it only allows one entry of each hash. then just loop the bitmap and insert every pixel into the set. at the end, your color count is just mySet.size()

std::set<rgb> colors;rgb col;	// the current color we are working with// COUNT THE COLORS ----------------------------------------------------------------------------for(int y = 0; y < source->h; y++){	for(int x = 0; x < source->w; x++)	{		// get the color in Uint32		SDL_GetRGB(getPixel(source, x, y), source->format, &(col.r), &(col.g), &(col.b));		colors.insert(col);	}}//this is your countcolors.size();


You could have done this with your map if you made rgb the key, but set is the appropriate container for this task.

Pretty sure this rounds to O(n^2) no matter how you slice it, so it's always going to be relatively slow with bigger bitmaps.

-me
Mizipzor
Mizipzor
I changed the storage to a std::set but I got a bunch of errors. I thought that maybe std::set sorted on its own and added a operator to my rgb class:

class rgb{public:	Uint8 r;	Uint8 g;	Uint8 b;	int	count;	// how many times have we seen this exact color?	rgb()	{		r = g = b = 0;		count = 1;	}		bool operator==(const rgb& a)	{		if(r == a.r && g == a.g && b == a.b)			return true;		else			return false;	}	bool operator<(const rgb a)	{		if(r < a.r)			return true;		else			return false;	}};


But still, I get the following error from within the std::set code:

Error	1	error C2678: binary '<' : no operator found which takes a left-hand operand of type 'const rgb' (or there is no acceptable conversion)	h:\microsoft visual studio 8\vc\include\functional	143Error is here (-->):		// TEMPLATE STRUCT lesstemplate<class _Ty>	struct less		: public binary_function<_Ty, _Ty, bool>	{	// functor for operator<	bool operator()(const _Ty& _Left, const _Ty& _Right) const		{	// apply operator< to operands-->		return (_Left < _Right);		}	};
Palidine
Palidine
bool operator<(const rgb a)

should be:

bool operator<(const rgb a) const

and you should be passing by reference:

bool operator<(const rgb &a) const

-me
Excors
Excors
I think the problem is that you're using an iterator loop to find a value in the map, which means it has to examine every value until it finds the right one, instead of using the tree properties of the map to find it much faster. Use a std::map<rgb, int/*count*/> and i=colors.find(col) instead, and it should work better.
CTar
CTar
EDIT: Too late

The reason your operator< doesn't work is that it your code isn't const-correct, it should be:
bool operator<(const rgb a) const{	if(r < a.r)		return true;	else		return false;}


Do you know how to use map? It is an associative container, you have a key and a value. In this case you probably want to use a color (rgb) is the key and the count as the value. Simplified version of your original code, still using std::map would be (just so you can see how std::map is supposed to be used):
class rgb{public:	Uint8 r;	Uint8 g;	Uint8 b;	rgb()		:		r(0), g(0), b(0)	{	}	rgb(const rgb& copy)		:		r(copy.r), g(copy.g), b(copy.b)	{	}	rgb& operator=(const rgb& rhs)	{		r = rhs.r;		g = rhs.g;		b = rhs.b;		return *this;	}	bool operator==(const rgb& a)const	{		if(r == a.r && g == a.g && b == a.b)			return true;		else			return false;	}	bool operator<(const rgb& rhs)const	{		return (r < rhs.r);			}};void colorCount(){        	Slock(source);	// lock surface	std::map<rgb, int> colors; // Maps from a color to the associated count.	rgb col;	// the current color we are working with	// COUNT THE COLORS ----------------------------------------------------------------------------	for(int y = 0; y < source->h; y++)	{		for(int x = 0; x < source->w; x++)		{			// Increase the count of the color retrieved.			// Note that the first time a color is encountered its associated			// count is initialized to 0 and then increased, thus giving the correct			// result.			SDL_GetRGB(getPixel(source, x, y), source->format, &(col.r), &(col.g), &(col.b));			++colors[ col ];		}				cout << y << " lines of " << source->h << " done, found " << colors.size() << " unique colors so far." << endl;	}			cout << "Color counting DONE.\n----------------------------------------------------------------\n\n";	Sulock(source);	// unlock surface}
Fred304
Fred304
You could use an int array of size 2^24 which takes up 64 MiB of memory and use the rgb-color as an index into that array.

int[] count = new int[2^24];fill count with zeros;foreach color in picture  ++count[color];int unique = 0;foreach c in count  if (c > 0) ++unique;delete[] count;


BTW you don't need the if in the operator<, just return the expression immediately:
bool operator<(const rgb a) const{    return (r < a.r);}

nmi
nmi
You can view the image as a 1D-array of integers. Then you can sort those integers in n*log(n) time. Afterwards iterate through the array once to count the colors used.

int image[N]; // image data, N is number of pixels, e.g. N=320*200std::sort(image, image + N);int colors = 1; // #unique colorsfor (int i = 1; i < N; i++){  if (image[i-1] != image)    colors++;}
iMalc
iMalc
It will not work as desired with the supplied definition of operator less-than.

The reason is that any two colours with equal red components, yet different green or blue components will compare as equal. Well according to operator less-than colour a is not less than colour b, and colour b is not less than colour a. Therefore they are equal and it will thus only let you add one colour of distinct red value to the set.

Here is a usable definition of operator less-than for what you are doing:
bool operator<(const rgb &a) const{    return r < a.r || (a == a.r && (g < a.g || (g == a.g && b < a.b)));}


However another way would be to combine the r,g,b into a 32-bit int using something like ((((r<<8)|g)<<8)|b) and then just use a set of ints. Then you don't even have to write a comparison operator. It just compares ints directly which sould be faster.
Christer Ericson
Christer Ericson
Quote:
Original post by Mizipzor
Im doing an algoritm that counts the number of unique colors in a bmp picture. It works well when there are very few colors, but as soon as the unique colors are a few thousands it gets paaainfully slow.
Not to be blunt, but there are several problems with your code causing it to run slow.

Quote:
I use a std::map. Ive looked into std::vector and std::list to, but this one seemed to be the fastest.
This is your biggest problem. Before doing anything else, you may want to better familiarize yourself with std::map and its (proper) usage. What is killing you for sure is the innermost loop you have that iterates over the entries in the map. Don't do that. That said, this problem is a prime example of where using STL is just bad and you shouldn't use STL at all (more below).

Quote:
Any tips for speeding this up are most welcome!
The things that are problems with your code are (in order of seriousness):

1. Your usage of std::map, causing a needless third for-loop inside the two to iterate over the image. You need to fix your usage of std::map, or better, switch to a better algorithm that doesn't use STL (see below).
2. Your calls to API functions inside the loop. E.g. the SDL getPixel() function is not cheap, as it is a generic function that deals with surfaces of different bitdepths through a switch-statement (follow the link to see how much code is there).
3. You should never have compound expressions in the test of a for-loop, because these will, generally, be evaluated each time through the loop. That is:

// Don't EVER write this:for(int y = 0; y < source->h; y++)// Instead write it like so:for(int y = 0, ymax = source->h; y < ymax; y++)


As for a better algorithm, well, there are several possible approaches. Because you only need a count of the number of colors (and not a count of how many of each color) a very straightforward approach is to allocate a bitmap of 2^24 bits (that's 2^21 bytes or 2MB). Initially you clear all bytes to zero, then you just set bits in the bitmap corresponding to the color, counting the first time the bit is set. In (untested) code, it would look something like:

int bits[2*1024*1024];memset(bits, 0, 2*1024*1024);...int count = 0;for(int y = 0, ymax = source->h; y < ymax; y++) {    for(int x = 0, xmax = source->w; x < xmax; x++) {        int rgb = ...some fast getpixel function here, NOT using SDL_GetRGB() and getPixel()...        int offset = rgb >> 3;        int bitmask = 1 << (rgb & 7);        count += ((bits[offset] & bitmask) == 0);        bits[offset] |= bitmask;    }}

This code will be memory bound, meaning it will be waiting for memory fetches most/all of the time. If there's a need to make things even faster, that can be addressed too in various ways, but for starters, this should help a lot.
Vorpy
Vorpy
Would there be anything wrong with using a std::bitset instead of doing the bit manipulation by hand?
Christer Ericson
Christer Ericson
Quote:
Original post by Vorpy
Would there be anything wrong with using a std::bitset instead of doing the bit manipulation by hand?
In principle, yes, if you care about speed. As I'm home sick and bored I ran the test and my code, as given above, results in 27 instructions, 18 in the inner loop. Using std::bitset results in 42 instructions, 33 in the inner loop. Furthermore, the std::bitset version retains two calls to the lengthy _Xran() routine. While it's probably never called, you also have two additional branches in the std::bitset code (to branch around the calls) that can slow you down. (This test was on a PC, using VC++ 6.) So, yeah, if you actually bother to look, STL still is crap when it comes to speed.

Granted, as I said earlier, this routine is destined to be memory bound so the fact that the STL version is roughly twice as slow in the inner loop isn't likely to matter (as much) in this particular situation. (I couldn't be bothered to time it to get actual values; I'm not that bored!)
iMalc
iMalc
Quote:
Original post by Christer Ericson
(This test was on a PC, using VC++ 6.) So, yeah, if you actually bother to look, STL still is crap when it comes to speed.
If you use a decent compiler you might find things are a bit different.

One also needs to consider what his system constraints and typical inputs are. The fastest algorithm is probably one that chooses between various methods depending on the image size, and other information in the bitmap header.
silvermace
silvermace
Is there any way in SDL to get the entire image as an array instead of just a single pixel at a time? doing this may involve 2 loops, (the loop inside the SDL code to populate the array and your loop) but this will almost certainly begin to exploit the data prefetch logic on your CPU.

Additional to this, once you have the data in an array, you can operate on smaller blocks of the array (Intel optimization manual says 50% of the CPU cache, eg NW P4 has 512KB L2, so I would operate on 256KB blocks) this will exploit spatial locality.

lastly, (for release builds) if you are using VC++ 2003 or newer, supply the /arch:sse2 flag to the compiler to tell the compiler to make the minimum CPU spec an SSE2 capable architecture. (you can get the VC++ 2005 compiler for free if you download the VC++ Express Edition with the Platform SDK a total of 1.2GBs but it might be worth it. Also, the VC++ 2003 toolkit is still free and thats only 35MB...)
Excors
Excors
Quote:
int bits[2*1024*1024];

I assume that should be 'char' rather than 'int'.

Quote:
If you use a decent compiler you might find things are a bit different.

It seems to depend on luck more than on the compiler version. Using Christer's code (modified to use a char array, plus 'static' so it doesn't run out of stack space), compared to a version with bitset ("count += (bits[rgb] == 0); bits[rgb] = 1;"), reading pixels from a 256x256 int* with about 60K distinct random values between 0 and FFFFFF, repeated 512 times and timed in seconds with a rough error of around +/- 0.1s, on a P4 3.0GHz, with whatever compilers I have lying around, I get: 
            char[] vs bitsetMSVC6 /O2   : 3.50 vs 3.65 ("Version 12.00.8804")MSVC2003 /O2: 3.60 vs 3.65 ("Version 13.10.3077")MSVC2005 /O2: 3.65 vs 3.60 ("Version 14.00.50727.42")ICC /O3     : 2.65 vs 3.50 ("Version 9.0  Build 20050430Z")ICC /O3 /QxN: 3.05 vs 2.65GCC -O3     : 3.40 vs 3.40 ("gcc version 3.4.4 (cygming special)")

(/arch:SSE2 seems to have no effect on the times in MSVC2003/2005.)

The difference in all versions of MSVC and in GCC is mostly lost in the noise (though you could do much more precise profiling if you cared). The difference in ICC is significant, but you can choose which one's faster by changing the optimisation flags.

So neither version of the code is simply faster - they're just different, and compilers are no good at consistently generating optimal code. I suppose the char[] version gives you more opportunities to tweak the code and hope you push the compiler's optimiser far enough to generate different code, but the bitset version is easier to read and has fewer opportunities for bugs.

Quote:
other information in the bitmap header.

That sounds like the best way - if you have 256-colour indexed bitmaps, the problem can be solved much faster [smile]
Excors
Excors
Quote:
Original post by silvermace
Additional to this, once you have the data in an array, you can operate on smaller blocks of the array (Intel optimization manual says 50% of the CPU cache, eg NW P4 has 512KB L2, so I would operate on 256KB blocks) this will exploit spatial locality.


It actually is very helpful to make the 'bits' array smaller so it fits in the cache. If you process 1/8 of the color space at once (so 'bits' is 256KB, and source->data in this case is 256KB too), like:
static std::bitset<256*256*256/8> bits;int count = 0;for (int segment = 0; segment < 8; ++segment) {    bits.reset();    for (int y = 0, ymax = source->h; y < ymax; y++) {        for (int x = 0, xmax = source->w; x < xmax; x++) {            int rgb = source->data[y*xmax + x];            if (rgb >> 21 == segment) {                int idx = rgb & 0x1fffff;                count += (bits[idx] == 0);                bits[idx] = 1;            }        }    }}return count;

then it runs in 1.5 seconds in MSVC (vs 3.6 for the non-segmented version) and 1.4s in ICC+QxN. (It still works with the same improvement if source->data is much bigger than the cache - I guess that's because it's accessed linearly and doesn't stay in the cache for long, while 'bits' is accessed randomly all the time and so it does stay in.)

About using "ymax = source->h" instead of using source->h in the conditional: unfortunately it looks like that's an "it depends" optimisation too. In the above code, it has a significant benefit (saving about 0.5 seconds in MSVC2005). But I have the code in a "int func(Source* source)" function, and if I change that to "int func(Source* __restrict source)" (so the compiler knows there's no aliasing going on - maybe it thinks source->data could be pointing at part of 'bits', or something?), then the with-ymax version takes 1.4 seconds while the without-ymax is actually faster at 1.3 seconds. It's still a useful trick, but it seems it needs to be applied carefully and with measurement because compilers are just too unpredictable.

(And yes, I am that bored ;-) )

Still, this might be solving the wrong problem since the original poster was counting how many times each colour occurred, rather than simply the number of unique colours.
iMalc
iMalc
Quote:
Original post by Excors
Quote:
other information in the bitmap header.

That sounds like the best way - if you have 256-colour indexed bitmaps, the problem can be solved much faster [smile]
Yes, actually that was what I was hinting at. Also, if it is a 15/16 bit image then you can reduce the memory required if the bit-array techinque is used.

However, as we have just been reminded, the OP may still wish to know how many times each colour occurs.
Vorpy
Vorpy
Excors, if you're still bored, here's something else I'm wondering about. Based on what Christer Ericson said, I've realized that bitset apparently requires range checking while vector doesn't. Now I can't help but wonder if using a vector<bool> would do even better (assuming the implementation is specialized for one bit per value).

If the goal is to count how many times each color occurs, I like CTar's solution (except I wouldn't bother defining a copy constructor and an assignment operator that just do the same as the default would, but that's nitpicking).

[Edited by - Vorpy on January 4, 2007 9:49:59 PM]
Christer Ericson
Christer Ericson
Quote:
Original post by Excors
assume that should be 'char' rather than 'int'.
Yes. Or left as is, and changing the 3 and 7 to 5 and 31, respectively. As always, you get what you pay for!

Quote:
It actually is very helpful to make the 'bits' array smaller so it fits in the cache. If you process 1/8 of the color space at once (so 'bits' is 256KB, and source->data in this case is 256KB too)
Right, this is indeed exactly what I had in mind when I wrote my comment about addressing being memory bound. Your timing of this modification nicely shows how badly memory bound this routine is, and why the 3-something second timings you did are mostly irrelevant (i.e. not really saying anything about the quality of the code under ideal memory conditions).

Quote:
About using "ymax = source->h" instead of using source->h in the conditional: unfortunately it looks like that's an "it depends" optimisation too. In the above code, it has a significant benefit (saving about 0.5 seconds in MSVC2005). But I have the code in a "int func(Source* source)" function, and if I change that to "int func(Source* __restrict source)" (so the compiler knows there's no aliasing going on - maybe it thinks source->data could be pointing at part of 'bits', or something?), then the with-ymax version takes 1.4 seconds while the without-ymax is actually faster at 1.3 seconds. It's still a useful trick, but it seems it needs to be applied carefully and with measurement because compilers are just too unpredictable.
The aliasing is exactly what's happening (and it happens pretty much always, unless you explicitly use restrict, which people typically do not do, thus my recommendation to write for-loops the way I said). The difference between 1.3 and 1.4 seconds is again down to noise I reckon.

BTW, considering how bored I was and how bored you therefore must have been, shouldn't you be looking into Prozac or something? ;)
Excors
Excors
Quote:
can't help but wonder if using a vector<bool> would do even better

It seems to be about twenty times slower (at least for 256x256 images where there aren't many pixels to count), seemingly because it's resetting the vector with zeroes one bit at a time (!). That's certainly a case where generic STL algorithms don't work (since the optimiser isn't clever enough to remove the overhead) - the specialised bitset seems to work rather better.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.