33 replies to this topic

[l0calh05t]

STL basically says: valid implementation may be stateful or stateless.

C++11 added stateful allocators as a requirement. Question is... how many years until it becomes widely available?

[hupsilardee]

I don't use STL because I never figured out how to delete from a list while iterating through, so I made my own classes for List<>, Array<>, and Map<>

My containers allow me to do this

List<Zombie> zombies;

uint zcount = zombies.Count();
for (uint i = 0; i < zcount; i++)
{
	 uint bcount = bullets.Count();
	 for (uint j = 0; j < bcount; j++)
	 {
	 	 if (collide(bullets[j], zombies[i]))
	 	 {
	 	 	 bullets.Remove(j);
	 	 	 zombies.Remove(i);
	 	 }
	 }
}

[Olof Hedman]

I don't use STL because I never figured out how to delete from a list while iterating through, so I made my own classes for List<>, Array<>, and Map<>

Update your iterator with the one that is returned by erase, and it should work fine.

it = collection.erase(it);

Just out of curiousity, how does your container handle it?
For example the fact that "bcount" and "zcount" no longer is valid after you "Remove".
Also, how does it handle that the index will "skip" one element when you erase?

Edited by Olof Hedman, 15 May 2012 - 03:55 AM.

[rip-off]

I don't use STL because I never figured out how to delete from a list while iterating through

Looking at your code, you still haven't. That loop is fundamentally wrong in a number of ways. In addition to the cases Olaf highlighted, what if multiple bullets collide with a given zombie in a single frame? You'll end up removing zombies who might be nowhere near the bullet.

Standard C++ containers approach this problem by design - if using iterations, there are established idioms for erasing while iterating:

bool handleBulletCollision(vector<Bullet> &bullets, const Zombie &zombie)
{
    for (auto i = bullets.begin() ; i != bullets.end() ; ++i)
    {
        if(collides(*i, zombie))
        {
            bullets.erase(i);
            return true;
        }
    }
    return false;
}

void handleZombieBulletCollisions(vector<Zombie> &zombies, vector<Bullet> &bullets)
{
    auto i = zombies.begin();
    while(i != zombies.end())
    {
        if(handleBulletCollision(bullets, *i))
        {
            i = zombies.erase(i);
        } 
        else
        {
            ++i;
        }
    }
}

We could re-write the latter function something like:

void handleZombieBulletCollisions(vector<Zombie> &zombies, vector<Bullet> &bullets)
{
    auto end = zombies.end();
    auto i = remove_if(zombies.begin(), end, [&bullets](const Zombie &zombie) {
        return handleBulletCollision(bullets, zombie);
    });
    zombies.erase(i, end);
}

That implementation involves less copies being made if multiple zombies are removed in a single pass.

[hupsilardee]

Sorry. That code was not strictly accurate, it's just that I got in the habit of storing the count like that before a loop, when using STL. Here is an actual example, from the code I used to actually test the Array<> class

	 for (uint i = 0; i < list.GetCount(); i++)
	 {
        printf("List[%i] = %i\n", i, list.Get(i));
    }
    for (uint i = 0; i < list.GetCount(); i++)
    {
        if (list.Get(i) % 2 == 0)
        {
            list.Remove(i);
            i--;
        }
    }
    for (uint i = 0; i < list.GetCount(); i++)
    {
        printf("List[%i] = %i\n", i, list.Get(i));
    }

[rip-off]

Direct, idiom free translation:

#include <vector>
#include <cstdio>
#include <cstdlib>

int main()
{
    std::vector<int> numbers;

    for(unsigned i = 0 ; i < 20 ; ++i)
    {
        numbers.push_back(std::rand() % 50);
    }

    for (unsigned i = 0; i < numbers.size(); i++)
    {
        std::printf("List[%i] = %i\n", i, numbers[i]);
    }

    for (unsigned i = 0; i < numbers.size(); i++)
    {
        if (numbers[i] % 2 == 0)
        {
            numbers.erase(numbers.begin() + i);
            i--;
        }
    }

    for (unsigned i = 0; i < numbers.size(); i++)
    {
        std::printf("List[%i] = %i\n", i, numbers[i]);
    }
}

[mdwh]

Your original posts said one should not use lists at all, not that vectors are usually better.

Please quote where I said that.

... your linked lists, trees, etc., rather than just using LinkedList<MyClass> (or whatever the STL syntax is).

If you're worried about performance, you should strongly consider not using linked lists at all.

(My apologies if I misinterpreted what that first quote meant.)

Edited by mdwh, 15 May 2012 - 09:52 AM.

[rip-off]

I fundamentally disagree with your characterisation of the words I said. I believe "strongly consider not using lists" more closely matches "vectors are usually better" than "not use lists at all". That is what I meant, and that is what the words actually mean, as I understand.

[freakchild]

Which is better...that part of Standard C++ formerly known as STL or your own?

This is a common query and I doubt anyone has the definitive answer because what was once known as STL covers quite a wide range of concepts. Likely any one individual has only a very limited use for and knowledge of a subset of it, even if that's a large subset. I don't think it's possible for anyone to really be an expert across the entire STL because I doubt any single person has used every single feature.

It's important to understand this...because people should expect quite a varying range of opinions and you need to consider the subset of functionality that is relevant to your own work. For game development, we’re really only talking about a few specific types of containers that are relevant to run time. Tools are fair game for a much wider range of needs.

Once upon a time, at least to settle this query for my own purposes I considered the subset that I would use normally, discarding concepts I would never use and features I would never really be interested in during my life as a game developer. I looked deeply into the implementations I was interested in and tried to see if I could improve on them performance wise.

What I found was that most implementations were quite well developed and were quite efficient - at least as much as they could be. There was very little room for direct optimization, which wasn’t even worth the effort. For the optimizations that were possible...typically they'd be related to the deployment/use and as such would also be necessary if you were to take the ‘rolling your own’ containers option anyway or the optimizations were possible only by removing features to allow corner cutting.

The latter were more interesting to me because clear performance (and memory) wins were easy and possible via this route. This should surprise no one though…because the outcome of removing features is a more specialized case and as we all know, specialized cases will generally be more performant than generic ones. I actually don’t find too much fault with STL for being generic and flexible either – that’s kind of the point of it. I should also add that programming IMHO is often about making trade off decisions and sometimes generic/flexible is just a better choice anyway.

Unfortunately, this result did give me the excuse I needed to continue using and maintaining my own containers because I don’t need to give clock cycles away anyway. However, before the haters applaud I will also add that while such exercises do provide measurable gains at the instruction level please bear in mind that the % of time your program counter is iterating over such instructions is very minimal. The gains you’ll see to your frame rate by such techniques are often not going to be as noticeable.

I should also add that while I do use my own containers, that wasn’t an excuse for me to throw STL containers away. I still use them actually, particularly in code that I share with others or in code that needs to be more flexible.

A TL/DR version, which is also roughly the takeaway from my own research

• In rolling your own it’s easy to make performance gains, but you’re not really optimizing STL – you’re removing features and making something else. Apples and oranges don’t really compare.
• I did make some memory gains too, as I briefly hint at above.
• The more features you add, the more the gap will close on any gains you made - the more pointless having your own will be.
• If you can live without those features the performance gains are worth it at the instruction level.
• The same performance gains have limited worth overall, largely due the time your program counter is in these so called problem areas. Or…there should be bigger fish to fry when you look at your performance profile.
• It is possibly worth using your own to gain maximum performance for your run time regardless (as I say above…why thrown cycles away).
• Rolling your own is an interesting exercise, particularly if you do look at the existing implementations. You’ll learn a lot about them and I think make wiser decisions for having that knowledge.
• Rolling your own with the intention of supporting all the same features is pointless. Things will exist in your version for the same reason they exist in vendor versions, which have already been optimized as they are. You really will be reinventing the wheel here and you’ll do that via creating a less optimal wheel at least in the first instance.
• Where you don’t need performance, the only possible need to use your own might be for reasons of consistency and not using two different types of containers.
• It’s my opinion that your tools/pipeline and generally your higher level code are better off using STL/standard C++ library containers though. Why?…
  
• They are more flexible and this sort of code generally needs to have that benefit
• The same code will be more maintainable due to using something more flexible
• Because they are standard and everyone should know them. Not everyone will be aware of the nuances of your own version, even if it’s a version shared amongst several people.
• The advantage of the alternative has no place here.

YMMV of course.

Edited by freakchild, 15 May 2012 - 05:57 PM.

[Zoner]

traits and algorithms only (in particular sort). The generic containers are more or less banned, though a bitset has managed to make its way into our codebase since its such a pain to write one that scales up into the hundreds of bits.

[Promit]

The biggest rule of thumb is this: If you have to ask, you should use STL. There are many legitimate reasons to avoid using the standard libraries, but it is almost guaranteed that if you are encountering those reasons, you already understand why and what the correct solution is. Instead, spend your time on understanding how the STL works and why it works the way it does.

One caveat that I do feel is worth mentioning: STL containers like std::vector are extremely efficient in optimized builds. The design of these classes relies heavily on several categories of C++ optimizations. There are good reasons for this, but at the end of the day it means that heavy container usage will show an unexpectedly high impact in "debug" builds. What's more, mixing debug and release compilations (selective optimization) of these containers can be extremely dangerous. So a lot of the home-rolled crowd like the fact that the jump in performance from debug to release is not so extreme.

That said, all halfway decent games become unplayable in debug mode about halfway through development anyway

[jbadams]

The biggest rule of thumb is this: If you have to ask, you should use STL.

Quoted for emphasis; that is an excellent guideline.

[Conoktra]

I don't ever use the STL, period. Not even when time is tight and I just "need to get it done". But then again I am a die-hard Lisper, so... take it for a grain of salt.

Edited by Conoktra, 14 June 2012 - 10:20 PM.

[jbadams]

@Conoktra: that's not really helpful in a discussion that specified C++ up-front. Obviously users of other languages won't be using the C++ Standard Library; if one is available they might however be well advised to use the standard library of their language of choice, for the same reasons given in favour of the C++SL in this topic.