Overview
Examples
Screenshots
Comparisons
Applications
Download
Documentation
Tutorials
Bazaar
Status & Roadmap
FAQ
Authors & License
Forums
Funding Ultimate++
Search on this site
Search in forums












SourceForge.net Logo
Home » Extra libraries, Code snippets, applications etc. » C++ language problems and code snippets » Time for little quiz!
Time for little quiz! [message #2219] Tue, 04 April 2006 14:02 Go to next message
mirek is currently online  mirek
Messages: 13050
Registered: November 2005
Ultimate Member
What is this construct supposed to do (and why):


void CreatePalette(const RGBA *s, int count, RGBA *palette, int ncolors)
{
	delete new sPalMaker(s, count, palette, ncolors);
}



Wink

Mirek
Re: Time for little quiz! [message #2229 is a reply to message #2219] Tue, 04 April 2006 19:12 Go to previous messageGo to next message
unodgs is currently offline  unodgs
Messages: 1361
Registered: November 2005
Location: Poland
Ultimate Contributor

luzr wrote on Tue, 04 April 2006 08:02

What is this construct supposed to do (and why):


void CreatePalette(const RGBA *s, int count, RGBA *palette, int ncolors)
{
	delete new sPalMaker(s, count, palette, ncolors);
}



Wink

Mirek


It look very interesting.. but I have no idea what this construction is supposed to do..

I would use delete new if I'd like to create object on heap (but what for?) and to end object live as soon as possible.

The next reason that came to my mind is you don't have to name the object..

But why delete new sPalMaker.. is better than simply
{
sPalMaker pm(s, count, palette, ncolors);
} ?

PS: Maybe this is stupid, but will compiler ignore creating the object if it is not created on heap because the pm isn't used further?

[Updated on: Tue, 04 April 2006 19:16]

Report message to a moderator

Re: Time for little quiz! [message #2232 is a reply to message #2219] Tue, 04 April 2006 20:04 Go to previous messageGo to next message
fudadmin is currently offline  fudadmin
Messages: 1298
Registered: November 2005
Location: London, UK
Senior Contributor
Administrator
luzr wrote on Tue, 04 April 2006 13:02

What is this construct supposed to do (and why):


void CreatePalette(const RGBA *s, int count, RGBA *palette, int ncolors)
{
	delete new sPalMaker(s, count, palette, ncolors);
}



Wink

Mirek


I'm lazy to think and test but my guess are some keywords:
some kind of clever pointers and/or references, auto counting ... memory management, deletion on creation when something related is not deleted but made free for shared use...
Re: Time for little quiz! [message #2233 is a reply to message #2232] Tue, 04 April 2006 20:36 Go to previous messageGo to next message
mirek is currently online  mirek
Messages: 13050
Registered: November 2005
Ultimate Member
Well, sorry for teasing, it is just an interesting solution for simple problem:

sPalMaker is "procedural object", in fact, it is routine wrapped in the class instance. All relevant work is done in constructor.

Now the trouble is that sizeof(sPalMaker) > 65KB, something I do not like to put to the stack (otherwise solution you propose would be OK as well). So "delete new" does exactly what I want - offloads memory requirements to the heap.

Mirek

[Updated on: Wed, 05 April 2006 10:46]

Report message to a moderator

Re: Time for little quiz! [message #2245 is a reply to message #2233] Wed, 05 April 2006 10:21 Go to previous messageGo to next message
victorb is currently offline  victorb
Messages: 78
Registered: December 2005
Location: Nice, France
Member
Mirek,

Could'nt you change this for a static function and allocate on the heap inside the static function? That might be easier to understand?

Victor
Re: Time for little quiz! [message #2248 is a reply to message #2245] Wed, 05 April 2006 10:53 Go to previous messageGo to next message
mirek is currently online  mirek
Messages: 13050
Registered: November 2005
Ultimate Member
That would be much more code to write. In fact, there is a couple of methods in class, and class intance here is a sort of replacement of Pascal's embedded function/procedures.

BTW, as this is quite nice implementation of median cut palette algorithm, and I was trying quite hard to google some code for this, maybe placing it here will make further implementors search easier:

Median cut palette algorithm in C++:

struct sPalMaker {
	int        histogram[RASTER_MAP_R][RASTER_MAP_G][RASTER_MAP_B];
	int        colorcount;
	struct Dim {
		int l, h;

		operator int() { return h - l; }
	};
	enum { G = 0, R = 1, B = 2 };
	void Copy(Dim *d, Dim *s)   { d[R] = s[R]; d[G] = s[G]; d[B] = s[B]; }
	struct Box {
		int     volume;
		int     colorcount;
		int     population;
		Dim     dim[3];
		int     avg_r, avg_g, avg_b;

		Dim&    operator[](int i)    { return dim[i]; }
	};

	void Update(Box& box, int ii);

	sPalMaker(const RGBA *s, int count, RGBA *palette, int ncolors);
};

void sPalMaker::Update(Box& x, int ii)
{
	x.colorcount = 0;
	x.population = 0;
	int a[3][RASTER_MAP_MAX];
	ZeroArray(a[R]);
	ZeroArray(a[G]);
	ZeroArray(a[B]);
	x.avg_r = x.avg_g = x.avg_b = 0;
	for(int r = x[R].l; r < x[R].h; r++)
		for(int g = x[G].l; g < x[G].h; g++)
			for(int b = x[B].l; b < x[B].h; b++) {
				int q = histogram[r][g][b];
				a[R][r] += q;
				a[G][g] += q;
				a[B][b] += q;
				x.avg_r += q * r;
				x.avg_g += q * g;
				x.avg_b += q * b;
				x.colorcount += (-q >> 31) & 1;
				x.population += q;
			}
	for(int i = 0; i < 3; i++) {
		Dim& d = x[i];
		while(d.l < d.h && a[i][d.l] == 0)
			d.l++;
		while(d.h > d.l && a[i][d.h - 1] == 0)
			d.h--;
	}
	x.volume = x[R] * x[G] * x[B];
}

static byte sRc(int avg, int pop, int div)
{
	return Saturate255(255 * (avg + (pop >> 1)) / pop / (div - 1));
}

sPalMaker::sPalMaker(const RGBA *s, int count, RGBA *palette, int ncolors)
{
	ASSERT(ncolors <= 256);
	ZeroArray(histogram);
	for(const RGBA *e = s + count; s < e; s++)
		histogram[s->r >> RASTER_SHIFT_R][s->g >> RASTER_SHIFT_G][s->b >> RASTER_SHIFT_B]++;
	Buffer<Box> box(256);
	box[0][R].l = 0;
	box[0][R].h = RASTER_MAP_R;
	box[0][G].l = 0;
	box[0][G].h = RASTER_MAP_G;
	box[0][B].l = 0;
	box[0][B].h = RASTER_MAP_B;
	Update(box[0], 0);
	if(box[0].population == 0)
		return;
	colorcount = box[0].colorcount;
	count = 1;
	int method = 1;
	while(count < ncolors) {
		int ii = -1;
		int maxv = 0;
		if(2 * count > ncolors)
			method = 1;
		for(int i = 0; i < count; i++) {
			int v = method ? box[i].volume : box[i].colorcount;
			if(box[i].colorcount > 1 && v > maxv) {
				ii = i;
				maxv = v;
			}
		}
		if(ii < 0)
			break;
		Box& b = box[ii];
		int ci = b[R] > b[G] ? b[B] > b[R] ? B : R : b[B] > b[G] ? B : G;
		if(b[ci] == 1) {
			if(method == 1)
				break;
			method = 1;
		}
		else {
			int m = (b[ci].l + b[ci].h) >> 1;
			Box& b1 = box[count];
			b1 = b;
			b[ci].h = m;
			b1[ci].l = m;
			Update(b, ii);
			Update(b1, count++);
		}
	}
	for(int i = 0; i < count; i++) {
		RGBA& c = palette[i];
		Box& x = box[i];
		c.r = sRc(x.avg_r, x.population, RASTER_MAP_R);
		c.g = sRc(x.avg_g, x.population, RASTER_MAP_G);
		c.b = sRc(x.avg_b, x.population, RASTER_MAP_B);
		c.a = 255;
	}
}

void CreatePalette(const RGBA *s, int count, RGBA *palette, int ncolors)
{
	ASSERT(ncolors <= 256);
	delete new sPalMaker(s, count, palette, ncolors);
}
Re: Time for little quiz! [message #2249 is a reply to message #2248] Wed, 05 April 2006 10:54 Go to previous messageGo to next message
mirek is currently online  mirek
Messages: 13050
Registered: November 2005
Ultimate Member
PS, note this nice gem as well:

x.colorcount += (-q >> 31) & 1;

Smile

Mirek
Re: Time for little quiz! [message #2251 is a reply to message #2249] Wed, 05 April 2006 11:20 Go to previous messageGo to next message
gprentice is currently offline  gprentice
Messages: 260
Registered: November 2005
Location: New Zealand
Experienced Member
luzr wrote on Wed, 05 April 2006 20:54

PS, note this nice gem as well:

x.colorcount += (-q >> 31) & 1;

Smile

Mirek




Do you feel like explaining?

I'm sure you know that right shift of a signed negative value has an implementation defined result and that int isn't always 32 bits and ... why would you write obscure code like this ???

Graeme
Re: Time for little quiz! [message #2252 is a reply to message #2251] Wed, 05 April 2006 12:04 Go to previous messageGo to next message
mirek is currently online  mirek
Messages: 13050
Registered: November 2005
Ultimate Member
gprentice wrote on Wed, 05 April 2006 05:20

luzr wrote on Wed, 05 April 2006 20:54

PS, note this nice gem as well:

x.colorcount += (-q >> 31) & 1;

Smile

Mirek




Do you feel like explaining?

I'm sure you know that right shift of a signed negative value has an implementation defined result and that int isn't always 32 bits and ... why would you write obscure code like this ???

Graeme



To avoid conditional jump in inner loop:

I need

if(q) colorcount++;

Now I know that q is positive number or zero. By negating positive number, you obviously get 1 in the highest bit. By negating zero, you get zero...

BTW, U++ guarantees int to be at least 32 bits (in other words, it requires it as well Wink Also, right shift is implementation defined, however it guarantees that it is a shift... (I mean, what is implementation defined is content of high bits, but obviously, existing bits have to be shifted...)

On the similar theme:

inline byte Saturate255(int x)             { return byte(~(x >> 24) & (x | (-(x >> 8) >> 24)) & 0xff); }


jump-less equivalent of min(max(x, 0), 255) (important in image processing).

Mirek

[Updated on: Wed, 05 April 2006 12:05]

Report message to a moderator

Re: Time for little quiz! [message #2253 is a reply to message #2219] Wed, 05 April 2006 12:23 Go to previous messageGo to next message
gprentice is currently offline  gprentice
Messages: 260
Registered: November 2005
Location: New Zealand
Experienced Member
ok, well sorry to be dumb but ... why do you want to avoid the conditional jump. Why do you think x.colorcount += (-q >> 31) & 1; is going to be more efficient than if(q) colorcount++; (or x.colorcount += bool(q); )

The compiler could be smart enough to generate a test and jump instead of shifting 31 times anyway or doing something else ??

BTW - I was thinking of 64 bit machines (regarding 32 bit ints) - but compilers for 64 bit seem to have standardized on 32 bits for int still?

Graeme

[Updated on: Wed, 05 April 2006 12:24]

Report message to a moderator

Re: Time for little quiz! [message #2254 is a reply to message #2229] Wed, 05 April 2006 12:31 Go to previous messageGo to next message
gprentice is currently offline  gprentice
Messages: 260
Registered: November 2005
Location: New Zealand
Experienced Member
unodgs wrote on Wed, 05 April 2006 05:12

luzr wrote on Tue, 04 April 2006 08:02

What is this construct supposed to do (and why):


void CreatePalette(const RGBA *s, int count, RGBA *palette, int ncolors)
{
	delete new sPalMaker(s, count, palette, ncolors);
}



Wink

Mirek


It look very interesting.. but I have no idea what this construction is supposed to do..

I would use delete new if I'd like to create object on heap (but what for?) and to end object live as soon as possible.

The next reason that came to my mind is you don't have to name the object..

But why delete new sPalMaker.. is better than simply
{
sPalMaker pm(s, count, palette, ncolors);
} ?

PS: Maybe this is stupid, but will compiler ignore creating the object if it is not created on heap because the pm isn't used further?





The compiler can ignore creating the pm object if it can determine that doing so makes no difference to the output (observable behaviour) of the program. There are situations where the compiler can elide (means ignore/not do) a call to a copy constructor even if the copy constructor has side effects (modifies a global variable or something) - the famous return value optimisation (RVO) being one - but apart from these, the compiler has to do what you tell it if it makes a difference to the output of the program.

Graeme
Re: Time for little quiz! [message #2255 is a reply to message #2253] Wed, 05 April 2006 13:14 Go to previous messageGo to next message
mirek is currently online  mirek
Messages: 13050
Registered: November 2005
Ultimate Member
gprentice wrote on Wed, 05 April 2006 06:23

ok, well sorry to be dumb but ... why do you want to avoid the conditional jump. Why do you think x.colorcount += (-q >> 31) & 1; is going to be more efficient than if(q) colorcount++; (or x.colorcount += bool(q); )



Most likely on any CPU since Pentium I: Failed branch prediction causes pipline stall - that is at least 12 CPU cycles wasted (31 on Prescott). Also, jumps cannot be fed to more executional units - while arithmetic ops can be. It is very likely that modern CPU will be doing those colorcount ops in the same time as operations around.

BTW, shifting 31 times is 1 cycle on AMD and PIII/Core/Conroe CPUs (unfortunately, it is more pricey for Netburst, however failed branch prediction is still even more pricey there).

Quote:


BTW - I was thinking of 64 bit machines (regarding 32 bit ints) - but compilers for 64 bit seem to have standardized on 32 bits for int still?



Yes, all major 64 bit CPUs today have 32bit ints. Well, to put it more straight, standard for all C compilers is to use 32 bit ints, other than that they support 8/16/32/64 integer quantities.

The reason is obvious - 32 bits is enough in most cases where integer quantity is to be used and 64 bit ints would eat much more space in data cache. BTW, AMD64 opcodes for 64 bit int operarations are 1 byte longer (they have "use 64 bits" prefix).

All that said, above jump-less technique would work with 64bit int as well.

Mirek

[Updated on: Wed, 05 April 2006 13:14]

Report message to a moderator

Re: Time for little quiz! [message #2263 is a reply to message #2252] Wed, 05 April 2006 14:26 Go to previous messageGo to next message
hojtsy is currently offline  hojtsy
Messages: 241
Registered: January 2006
Location: Budapest, Hungary
Experienced Member
luzr wrote on Wed, 05 April 2006 06:04


Now I know that q is positive number or zero. By negating positive number, you obviously get 1 in the highest bit.
I am afraid there is no guarantee provided by the C++ standard for the bit encoding of negative numbers. Depending on any specific encoding could be either implementation-defined or undefined behaviour. I suggest some other variants which have standard-defined behaviour.
if(q) colorcount++;            // supposed to be slow(?)
colorcount += (-q >> 31) & 1;  // luzr's solution
coloccount += bool(q);         // suggested solution 1
coloccount += (q != 0);        // suggested solution 2
coloccount += !!q;             // suggested solution 3

Re: Time for little quiz! [message #2265 is a reply to message #2263] Wed, 05 April 2006 14:52 Go to previous messageGo to next message
victorb is currently offline  victorb
Messages: 78
Registered: December 2005
Location: Nice, France
Member
Interesting to see that none of the 3 suggested solution generate a conditional jump... they make use of the "setne" opcode...
I don't have the cycle count for each instruction but it might be as optimal as "(-q >> 31) & 1" with the benefit of being understandable.

-> I vote for coloccount += (q != 0);

Victor
Re: Time for little quiz! [message #2266 is a reply to message #2263] Wed, 05 April 2006 14:53 Go to previous messageGo to next message
mirek is currently online  mirek
Messages: 13050
Registered: November 2005
Ultimate Member
In theory, you are right, Howver, it depends on what you praise more: Speed or possible protability to non-existent platform?

There are more cases like this when you have to narrow your focus.

Should we support machines with int less than 32 bits?

Should we support machines that follow neither big-endian nor little-endian mode?

Personally, it is OK with me if there is nothing in U++ that would limit it running on x86, PowerPC, ARM and Sparc. If there are implementation defined issues that differ in above architectures, we should handle them. If there is something that does not differ (like binary representation of integers), I simply do not care!

Mirek
Re: Time for little quiz! [message #2267 is a reply to message #2265] Wed, 05 April 2006 14:56 Go to previous messageGo to next message
mirek is currently online  mirek
Messages: 13050
Registered: November 2005
Ultimate Member
victorb wrote on Wed, 05 April 2006 08:52

Interesting to see that none of the 3 suggested solution generate a conditional jump... they make use of the "setne" opcode...
I don't have the cycle count for each instruction but it might be as optimal as "(-q >> 31) & 1" with the benefit of being understandable.

-> I vote for coloccount += (q != 0);

Victor


"setne" is a good point. However, it does not seem to be used with all compilers on all CPUs.... (but I guess it would deserve the conditional compilation at least).

Mirek
Re: Time for little quiz! [message #2269 is a reply to message #2267] Wed, 05 April 2006 15:04 Go to previous messageGo to next message
victorb is currently offline  victorb
Messages: 78
Registered: December 2005
Location: Nice, France
Member
"Setne" gets generated with GCC on a pentium M.

BTW,
I remove my vote for "colorcount += (q != 0)" adding an int with a boolean is not so nice...

And I propose suggested #4: "colorcount += (q)?1:0;" (this will generate the same code as #3 with GCC).

Funny to see how many post such a small statement "(-q >> 31) & 1" could generate Razz
Re: Time for little quiz! [message #2271 is a reply to message #2269] Wed, 05 April 2006 15:50 Go to previous messageGo to next message
hojtsy is currently offline  hojtsy
Messages: 241
Registered: January 2006
Location: Budapest, Hungary
Experienced Member
victorb wrote on Wed, 05 April 2006 09:04

I remove my vote for "colorcount += (q != 0)" adding an int with a boolean is not so nice...
At least it has standard-defined behaviour, which is an improvement over shifting negative numbers.

victorb wrote on Wed, 05 April 2006 09:04


And I propose suggested #4: "colorcount += (q)?1:0;" (this will generate the same code as #3 with GCC).
You don't really need parenthesis there: "colorcount += q ? 1 : 0;" First I thought that this variant may generate a branch.

victorb wrote on Wed, 05 April 2006 09:04

Funny to see how many post such a small statement "(-q >> 31) & 1" could generate Razz
I think that the big challenge is not to write fast & obfuscated code, but rather write fast and clean code. This example is small enough to test whether this is possible in C if you take the "fast" aspect to the extreme. I see the obfuscated version as practically assembly magic, even if it is written with C statements: the question is whether there is a C++ standard-conformant solution with the same or better runtime performance.
Re: Time for little quiz! [message #2273 is a reply to message #2271] Wed, 05 April 2006 17:42 Go to previous messageGo to next message
mirek is currently online  mirek
Messages: 13050
Registered: November 2005
Ultimate Member
victorb wrote on Wed, 05 April 2006 09:04


I think that the big challenge is not to write fast & obfuscated code, but rather write fast and clean code. This example is small enough to test whether this is possible in C if you take the "fast" aspect to the extreme. I see the obfuscated version as practically assembly magic, even if it is written with C statements: the question is whether there is a C++ standard-conformant solution with the same or better runtime performance.



Just my stance: While "setne" solution is even better and it is my fault that I missed that possibility, I believe that for time critical routine _implementation_ it is OK to be fast at the cost of being obfuscated. And this routine can be quite limiting in tasks like webservers that generate gifs...

When optimizing, assembler magic is what you often have to use... (actually, I even plan to write some nImage routines in assembler Wink

Mirek
Re: Time for little quiz! [message #2292 is a reply to message #2251] Thu, 06 April 2006 14:29 Go to previous messageGo to previous message
gprentice is currently offline  gprentice
Messages: 260
Registered: November 2005
Location: New Zealand
Experienced Member
gprentice wrote on Wed, 05 April 2006 21:20

luzr wrote on Wed, 05 April 2006 20:54

PS, note this nice gem as well:

x.colorcount += (-q >> 31) & 1;

Smile

Mirek




Do you feel like explaining?

I'm sure you know that right shift of a signed negative value has an implementation defined result and that int isn't always 32 bits and ... why would you write obscure code like this ???

Graeme



FWIW - Visual C++ and GCC describe their implementation defined behavior for integer bit operations - most likely all GCC versions do the sign extension mentioned and all VC versions treat signed as unsigned.

http://msdn2.microsoft.com/en-US/library/dxda59dh(VS.80).asp x

http://gcc.activeventure.org/Integers-implementation.html#In tegers-implementation

Graeme
Previous Topic: STL multimap
Next Topic: explanation of c++ typedef line
Goto Forum:
  


Current Time: Sat Jan 23 09:39:02 CET 2021

Total time taken to generate the page: 0.01171 seconds