WOW! Err.. Software Rendering Engine Debug vs Release

LOL I did not call your entire pixel plot function an abomination... Just a little part of it... *cough* *cough*

No offense intended, btw

None taken, made me laugh.

Next note on optimizing my engine: I did an extremely silly thing. For the sake of convienance, yet again, I wrote my matrices classes using STL vectors. I thought nothing of it until I took a look at a profiler. Most of my entire loop was spent in vector operator[]. I didn''t even bother to think that matrix[1][2] wasn''t actually referencing the memory at matrix[1][2] but simply calling the STL implementation of the operator[], which in turn was making another call to the STL implementation of the operator [] for the other vector, since it was declared as vector< vector< double > > matrix.

Anyhow, to the point. STL operators were taking up a huge amount of time. After I cut out the STL and recoded everything using standard C arrays, I got another near order of magnitude speed increase. Cheers for profilers, I would have remained obvlivious to this indefinitely without GlowCode ( my profiler ).

Hmm...vector::operator[] should have been inlined. One problem I''ve had with that is that a debug build is much slower than the release build, though, since the debug has all these function calls on top of my vector ops.

Out of curiosity, what compiler, settings, and profiler are you using?

I didn''t bother checking out the exact implementation of []. However, when I removed the STL code, my code sped up, as mentioned, in the field of an entire magnitude.

Compiler is visual studio.net. The application settings are the default debug/release settings for an empty console application ( the window is created by the console application. I used this general methodology in case I decide to port it to another OS sometime, which would be somewhat more annoying if it had been built as a windows application ).

The profiler is GlowCode. My absolutely favorite light weight profiler. The speed increase was huge in both debug and release builds.

If you're curious, here is a profiling dump. The fields are mutilated, but its fairly obvious to see that the first number is the total time spent in the function, in decreasing order and listed in milliseconds. Its from a 72 second run.

12/19 of the top processor hogs from the profile are from the STL. I'm going to do away with the STL in my project all together. Its just too slow to have in a software renderer.

EDIT: Not to say the STL is inheritly slow but the overhead of relying on STL operat(ors/ions) thousands/millions of times per frame is.


[edited by - haro on July 16, 2003 1:01:31 AM]

Ok, AP clarified it for me, I forgot that you pay for the double dereference. For some reason I was thinking of a vector of size 16. Also interesting - if the vector was allocated in place, you don''t double dereference. Which is a good sanity check for me - since I write my Matrix44 as Vector4[4]!

Haro, stl shouldn''t impose an overhead unless you use it innappropriately. You should definitely have your own Vector3,4 and Matrix33,34,44 classes that allocate memory inline, rather than dynamically(as std::vector does).

But, should you need a linked list, or a dynamically resizeable vector, you should use stl, rather than writing your own. The reason why your matrix composed of vectors was slow was the double dereference - any vector class is going to have to pay for a dereference, and if it''s dynamically allocated, it can''t optimize it down to one dereference.

I assume by .net you mean 2002. I''ll have to check out GlowCode, never heard of it before.

quote:

---

But, should you need a linked list, or a dynamically resizeable vector, you should use stl

---

I''ve actually always found it significantly easier to write my own linked lists rather than using STL. For example, in my rendering pipeline my render list objects are connected to each other by a simple Object* next which the graphics engine sets which a new object is added to the pipeline. It creates a simple and efficient linked list.

After a few optimizations my framerate is up to over 300 FPS average, which has me feeling quite well off. Since I am still using my pixel plot function I decided to change it up a bit to be more efficient for the mean time. Here is the new one:

void GraphicsEngine::PixelPlot32Bit( int x, int y, float red, float green, float blue, GraphicsEngine *ge )
{
	static float redCopy = -1;
	static float greenCopy = -1;
	static float blueCopy = -1;
	
	static unsigned int r;
	static unsigned int g;
	static unsigned int b;
	
	static unsigned long final = 0;
	
	if( ( redCopy != red ) || ( greenCopy != green ) || ( blueCopy != blue ) )
	{
		redCopy = red;
		greenCopy = green;
		blueCopy = blue;
	
		r = (unsigned int)(0xff*red);
		g = (unsigned int)(0xff*green);
		b = (unsigned int)(0xff*blue);
		
		final = b + (g << ge->blueBits) + (r << (ge->blueBits + ge->greenBits));
	}

	if( !ge->bufferOpen )
		ge->GetAndLockBackBuffer();

	ge->backBufferData[ y * (ge->pitch+ge->width) + x  ] = final;
}

I added the function pointer stuff, hence the need to pass a pointer to a graphics engine (this), due to restrictions on creating function pointers to class members, in that they have to be static. So my static member function DrawPixel() just wraps the PlotPixel32Bit, PlotPixel16bit, etc functions. I''m pretty happy with the new function. Its running rather well.

I realize that STL is useful, but you can''t really use it in relevant loops. The [] operator for STL containers apparently has a tremendous overhead. So far its been the bottle neck of no less than 5 different functions. In fact removing the STL containers and using C containers has been the decidedly largest perfomance improver. In one loop, a matrix transform loop I used [] 8 times. In spite of all of the other work going on in that loop, the [] of a 1d vector was taking up 45% of the function''s time. I cut out the STL container and I picked up another 10-20 FPS. Its just rediculous.

yeah why use a vector for something completely static like a matrix?

I have to agree that STL seems to slow things down - to see it incurs *no* overhead is not true in my experience. I am developing software that deals with vectors with 000''s of entries and I replaced the vector with my own linked list and it''s much faster.

quote:

---

replaced the vector with my own linked list

---

err...

did you try std::list?

I have to agree with those who avoid the STL in time critical applications. The more I used the STL, the more I realized that it was full of serious design flaws, that could badly affect performance under a lot of different circumstances. I actually ended up writing my own striped-down version of an STL. It offers the same interfaces and basic functionality, but with different (and much simpler) internal organization. For example a linked list: I recreated list<> (double linked list), and an slist<> container (single linked list, takes less memory). Compared to STLPort, those very basic versions are approx. 3 times faster. Similar with the string class, which is particularily inefficient in STLPort. I also renamed std::vector<> to array<>, which is much more appropriate, IMO. A vector is something different.

Bottom line: in time critical code, you should definitely think about implementing your own set of standard classes. An optimized matrix and vector class is a must, but optimized container classes can also be beneficial for realtime applications.

My €0.02

quote:

---

Original post by JuNC

quote:

---

replaced the vector with my own linked list

---

err...

did you try std::list?

---

- nope

course I did - but it''s the usual trade-off of speed over simplicity. STL is a good general library buy can''t cater for every specific circumstance.

I agree totally, was just pointing out the oddness of that statement considering the totally different implementations of the two structures.

I am always suspicious of any sweeping generalization saying that "STL containers are slow".

* One major reason for slowness is improper usage -- for example, using a list instead of a vector and vice versa.
* Another major reason for slowness is inefficient usage -- usually unintended constructor and copy constructor calls.
* Another reason is that while STL containers are fast in general, they are not necessarily optimized for your particular situation.
* Lastly, unrealistic expectations -- iterating a thousand times through a list of a thousand elements will take a very long time no matter whose implementation you use.

Here is a not-so-sweeping generalization that is a good rule of thumb (but not completely true):

You can''t write a container library that is faster than STL with the same features, flexibility and convenience. If you need something faster, you will have to give up features, flexibility and/or convenience.

quote:

---

Original post by Yann L
I have to agree with those who avoid the STL in time critical applications. The more I used the STL, the more I realized that it was full of serious design flaws, that could badly affect performance under a lot of different circumstances. I actually ended up writing my own striped-down version of an STL.

---

Yann, do you think you could explain what you thought were the major design flaws? And what did you change in your container class library?

quote:

---

Original post by JohnBolton
I am always suspicious of any sweeping generalization saying that "STL containers are slow".

* One major reason for slowness is improper usage -- for example, using a list instead of a vector and vice versa.
* Another major reason for slowness is inefficient usage -- usually unintended constructor and copy constructor calls.
* Another reason is that while STL containers are fast in general, they are not necessarily optimized for your particular situation.

Here is a not-so-sweeping generalization that is a good rule of thumb (but not completely true):

You can''t write a container library that is faster than STL with the same features, flexibility and convenience. If you need something faster, you will have to give up features, flexibility and/or convenience.

---

Actually, as mentioned, I was using a container meant for random access ( a vector ) and performing 8 accesses per loop using the [] operator. The only problem was there is significant overhead using these operators since it is essentially a function call.

I believe a much less safe but much more efficient container would have the data openly accessible ie, I could reference it via container.data[12]. There would also be a container.size and a container.maxSize variable. This gets rid of any possible inefficiencies from access. The container would have just a couple of extremely simple functions, SetMinimumMaxSize(), Clear(), Remove( int loc ) and PushBack( class T o ) for example. Of course this puts a responsibility on the programmer not do silly things like changing the state variables inside the container, but also gives the exact same features, flexibility and convienance I''ve found with the STL.

Look at the profiler log I listed earlier. Most of the bottle necks were operator []. And this was all random access vectors, where the [] should not only be constant, but a constant of virtually zero.

I also have some fairly radical ideas though in opposition to OO. I really like OO, but people have gone overboard. They want their programs to be OO purely for the sake of OOness. Again, I really wish C++ had a "readonly" keyword. This way I could make the size of the container a "readonly int size" which means that it could be read from any class, but only modified from within the container class, or friend classes of container. This would allow me to insure the stability of the container without having to deal with the currently somewhat broken state of encapsulation which results in significant overhead. Fortunately a respectable number of proposals with the same basic idea have already been sent to the C++ commitee''s meetings, and its only a matter of time before something similiar to readonly/writeonly are implemented. ( All discussed in another thread - General Programming - Why aren''t readonly/writeonly C++ keywords?).

Your bottlenecks with [] were because either i) you were using a debug build, or ii) you weren't using any optimizations.

Either is perfectly valid, but if you want good performance, you'd expect to be using optimizations.

To show your argument about [] fails miserably, I compiled the following code:

std::vector<int> v1;
int* v2;

void f()
{
  int i1 = v1[30];
  int i2 = v2[30];

  printf("%i\n%i\n",i1,i2);

}

Note that they essentially do the same thing, both are very unsafe but equivalent (minus all the bookkeeping std::vector can do).

With no optimizations (MSVC++):

   
_i1$ = -4
_i2$ = -8
?f@@YAXXZ PROC NEAR					; f
; Line 7
	push	ebp
	mov	ebp, esp
	sub	esp, 8
; Line 8
	push	30					; 0000001eH
	mov	ecx, OFFSET FLAT:?v1@@3V?$vector@HV?$allocator@H@std@@@std@@A
	call	??A?$vector@HV?$allocator@H@std@@@std@@QAEAAHI@Z ; std::vector<int,std::allocator<int> >::operator[]
	mov	eax, DWORD PTR [eax]
	mov	DWORD PTR _i1$[ebp], eax
; Line 9
	mov	ecx, DWORD PTR ?v2@@3PAHA		; v2
	mov	edx, DWORD PTR [ecx+120]
	mov	DWORD PTR _i2$[ebp], edx
; Line 11
	mov	eax, DWORD PTR _i2$[ebp]
	push	eax
	mov	ecx, DWORD PTR _i1$[ebp]
	push	ecx
	push	OFFSET FLAT:$SG5321
	call	_printf
	add	esp, 12					; 0000000cH
; Line 13
	mov	esp, ebp
	pop	ebp
	ret	0

With -O2

   
?f@@YAXXZ PROC NEAR					; f, COMDAT
; File test.cpp
; Line 11
	mov	eax, DWORD PTR ?v2@@3PAHA		; v2
	mov	edx, DWORD PTR ?v1@@3V?$vector@HV?$allocator@H@std@@@std@@A+4
	mov	ecx, DWORD PTR [eax+120]
	mov	eax, DWORD PTR [edx+120]
	push	ecx
	push	eax
	push	OFFSET FLAT:??_C@_06DOOH@?$CFi?6?$CFi?6?$AA@ ; `string'
	call	_printf
	add	esp, 12					; 0000000cH
; Line 13
	ret	0

Note with -O2 the generated code is identical!

STL certainly isn't the choice in all situations but that particular bash just doesn't hold any water.

[edited by - JuNC on July 16, 2003 5:52:56 PM]

Showing me code that would cause crashes in multiple ways and doesn't even have a main body isn't exactly proving my point has no merit, as you claim. I decided to write a more in depth testing program. Here it is:

#include "timer.h"
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

#define SIZE 10000000

int main()
{

	vector< int > vi;
	vi.reserve( SIZE );
	int* ip;
	ip = new int[ SIZE ];

	
	Clock t;
	
	cout << "Starting." << endl;
	
	t.restartTimer();
	srand(123456);
	for(unsigned long i = 0; i < SIZE; i++)
	{
		ip[i] = rand();
		if( ip[i] == 71 )
		{
			srand( 666666 );
		}
	}

	cout << t.queryTimer() << " milliseconds passed for C container method." << endl;

	t.restartTimer();
	srand(123456);
	for(unsigned long i = 0; i < SIZE; i++)
	{
		vi.push_back( rand() );
		if( vi[i] == 71 )
		{
			srand( 666666 );
		}
	}
	cout << t.queryTimer() << " milliseconds passed for STL method." << endl;

	delete ip;
}

A very simple program. It just creates 10,000,000 integers stores them in the list, and then redundantly accesses the list at that point to determine if its equal to a random value, and if it does it performs an operation with side effects ( to prevent the compiler from optimizing out the test result.

Results:

Debug Build:

C array code : 160ms average
STL container code: 7300ms average

Release Build with /Od:

C array code : 170ms average
STL container code: 890ms average

Release Build With /O2

C array code : 180ms average
STL container code: 300ms average

STL code is getting somewhat close to C code in a completely speed optimized release build, but still very significantly slower. However, in typical work environment builds where you will be debugging and profiling, STL code is simply not acceptable.

STL and C code that do the identical things do not compile to the same code. They have completely different ways of doing so. I have no clue what you were trying to show with your program, and I'm actually somewhat suprised it even compiled depending on what you had in your entry point.

Conclusion: STL is simply not sufficiently fast for developing a software renderer.

[edited by - haro on July 16, 2003 7:20:32 PM]