c++ benchmark: list or vector?

In games programming, it's likely to have a collection of objects you want to draw to the screen. In some cases, the number of items in such a collection can be quite high.

I wondered if there's an efficient option between using std::list or std::vector, and I did a benchmark to see it myself.

Scenario 1: Insert n items, traverse n times.

when n=100, there isn't a huge difference but list is better. For vector it's between 15ms and 78ms, and for list it's between 15ms and 62ms.
When I calculate the average of rates, I can see that list is ~%11 faster.

when n=300, I can't see a clear winner. For vector it's between 200ms and 310ms, and for list it's between 203ms and 343ms.
According to the average of rates, vector is ~%3 faster.

Here's the source for this benchmark:http://pastebin.com/f41f684cb

Scenario 2: Insert n items, traverse n times and replace %20 of items on every iteration whilst traversing.

when n=100, mostly list wins. For vector it's between 170msms and 250ms, and for list it's between 172ms and 190ms.
List is ~%5 faster on average.

when n=200, list is always the winner. For vector it's between 1360ms and 1531ms, and for list it's between 1297ms and 1422ms.
List is ~%7 faster.

Here's the source for this benchmark:http://pastebin.com/f522f7e6b

Conclusion

If the number of items in your world are around 300 or more, and you don't perform so many insert&remove operations, pick vector. Otherwise, pick list.

I think the reason behind the truth that vector can't deal with continuous insert&remove operations is that it has to relocate remaining elements in the array when you delete one of them. For list, it's far more easy because it's implemented as a linked-list which means it's just about modifying two pointers to remove an element.

On the other hand, I think the reason why the list beats vector for 100 items is about the allocation strategy that vector uses. I don't know exactly how MS implemented this in standard library, but it's generally something like doubling the allocated memory everytime it's completely consumed. If it starts with a number like 5, to reach 100 it must be doubled 5 times, and everytime it looks for a bigger chunk of memory. The memory management has to find a continuous part in the memory for it. And after 100, to reach 300 it hast to be doubled just twice.

Visual studio 2005 culture problem

Ok, I admit that it isn't a "problem". While working on our project "geekers", every time we update our project folder from subversion, we get this change to visual studio project file of the visual studio:


Ok, it's a desirable feature to have culture-specific data types in the xml streams. But do we really deserve this situation in this screenshot? I think we don't. :)
It remembers me a great article of Joel Spolsky, on "leaky abstractions."

Microsoft's another investment

As you can see on this page, microsoft is giving some of its products (visual studio, xna, windows server) to the students in UK for free. I've learned from Euan from our games project. I've already got those products thanks to MSDN membership of my university in Izmir, and many universities do.

An article I've read on 'Joel on software' claims that microsoft indeed would love to give its development products for free. Because the value of an operating system is dependent on the various software it has on it, and windows (with office) is the flagship product of microsoft. -- not visual studio --

I've never thought about it this way, and it really sounds smart.

Visual Studio SP1: Installation source for this product is not available

While trying to install Visual Studio 2005 SP1, I've encountered this error message: "Installation source for this product is not available".

After spending my whole day on this problem, I've found this blog entry:
http://dotnetslackers.com/...is_not_available.aspx

And this MSDN knowledge base entry & patch:
http://support.microsoft.com/default.aspx/kb/925336

And it managed to solve my problem. What a sunday!

Sun buys MySQL

It is not unreasonable, but it was unexpected; just like Serkan agreed. And in the digg post, the submitter's comment is: "Didn't see that one coming" :)

I can understand it, because the current commercial-opensource hybrid status of java is just like how MySQL is running for years. Probably, sun has foreseen more profit in this kind of work model.

Through a software guy's eye, I can tell that MySQL will strenghten its connections with Java, and it will implement/stabilize features which java used to supply from Oracle. Because of their strong relationship in the industry, this is something important for Oracle, as well.

DirectX Demo Project

Here is my DirectX demo project for Games Programming course at Abertay.

It makes use of:
- A point light and a directional light
- Shadows (planar)
- Animated meshes



And it's the url:
http://www.youtube.com/watch?v=xI8r653mX4U

Now I'm going to start to study for my Maths exam :)

How to print text in directx

First, you need to create a RECT object to set the area on screen, ID3DXFont object, and a D3DCOLOR object:

RECT lineRect;
ID3DXFont * pDefaultFont;
D3DCOLOR defaultFontColor;

This is how to initialise them:

A rectangle which has a height of 50px, on top of screen:
lineRect.left = 0;
lineRect.top = 0;
lineRect.right = 1024;
lineRect.bottom = 50;

How to create a font
D3DXCreateFont(Device, 30/*fontHeight*/,
0, FW_BOLD, 0, FALSE,
DEFAULT_CHARSET, OUT_DEFAULT_PRECIS,
DEFAULT_QUALITY, DEFAULT_PITCH | FF_DONTCARE,
TEXT("Calibri"), &pDefaultFont );

I'm not going to deal with the details of D3DXCreateFont method, but you can find the reference here:
http://msdn2.microsoft.com/en-us/library/bb172773.aspx

How to set the color:
defaultFontColor = D3DCOLOR_ARGB(255, 255, 255, 255);

Now you can write your text:
pDefaultFont->DrawTextA(NULL, "My Text Here", -1, &lineRect, DT_RIGHT, defaultFontColor);

Sometimes I strongly miss the VB6 times:
Print "my text here"
But of course, they're "incomparable" in terms of speed :)