Messages

1

SFML wiki / [Sources] Thread-safe Resource Manager

« on: September 16, 2009, 01:15:59 pm »

I disagree. Most of the time, a resource that failed to load is not a catastrophic failure. A texture did not load? Ok, just use a default texture (maybe a nice hot pink :-P ). A font didn't load? Use the default font.

I think you must have a very different use case in mind than me.  If I'm writing a game and a texture fails to load, it means that my game data is corrupted somehow.  Even it I want to proceed with fallback data, I'm already at the stuff-is-screwed-up-who-cares-how-fast-it-is point.

I can't think of any example in the STL that this would apply to.

It really depends a lot on what you're doing in the loop.  For instance, in a loop that iterates over a vector and sums the elements, the call to end() will dwarf the actual body of the loop.

As a more realistic example of something (not in the STL) where this comes up is when people write depth-first tree iterators.  The "end" state for such an iteration is something like "all nodes are in the (implicit) visited set," so calling end() involves instantiating a set and adding all the nodes to it.

The other place I see things like this is when the exit comparison is more complicated, like "I == MyMap[Foo].end()".  Even that's not so bad, but it builds up as you add more indirections.

Plus, if you cache end() by default, your code becomes more self-documenting in that cases where you don't cache it must be because you're doing invalidating mutation, though having comments to that effect is still a good idea.

Besides, I'm deleting elements in this loop, so in the case where nontrivial work is done for end, it is likely that the cached iterator would become invalidated, so it poses an extra risk of undefined behavior.

Yup.  And I put a giant comment to that effect. ;-)

If you don't mind the extra entries (which especially for games that stream large amounts of resources might be a lot), you could just as well use weak pointers so that the deletion is taken care of automatically (and spread over multiple frames).

True, though boost::weak_ptr doesn't play nice with my other suggestion to avoid double-lookups. ;-)

2

SFML wiki / [Sources] Thread-safe Resource Manager

« on: September 16, 2009, 12:34:37 pm »

As an aside, I'm not trying to deride your code.  It's perfectly fine as it is and, to be honest, you'd probably need to beat on it pretty hard to bring out the issues I'm raising.

The reason I commented at all is that, while they're not critical in this case, from experience, some of those issues can and do cause performance problems in the real world.  While we can all agree that premature optimization is generally a bad thing, I think there's also a point where, if you can write the same code in an more or equally clean way and avoid potential pitfalls at the same time, it's worth it.  Think of it as a "defensive optimizing" technique: if the code is just as clean (or cleaner) and it removes the possibility of an issue, why not go for it?

EDIT: Also, std::map's of std::string's are just a hard-wired cringe response for me. One can imagine how a compiler, doing a lot of text processing, might beat on those.... ;-)

3

SFML wiki / [Sources] Thread-safe Resource Manager

« on: September 16, 2009, 12:23:51 pm »

A small question up front: Did you profile this (not in a synthetic benchmark) and notice any problem?

This particular case, no.  However, all of these are idioms picked up from working professionally on improving the compile-time performance of LLVM, where (mis-)use of the STL turned out to be a huge time sink.  The STL is nice and clean and better than most people's naive implementations, but it's not perfect, and using it poorly can result in performance surprises.

The intent was that the first two, at least, are simple enough that one can just adopt them as idioms without making your code awful

1. There is a good reason I did it this way: Your version adds an (empty) entry even when the resource could not be loaded (the exceptional case). Furthermore there is an error in your code: loaded must be a Resource, and not a Resource&.

You're right on the typo, but wrong about the failure case being a good reason.  If loading a resource fails, there's a high probability it was a catastrophic failure, and we're going to bail anyways, so nobody cares if we made an extra entry in the map.

2. Calling end() is slow?!? Sorry, but that is utter BS. Besides, the only loop that uses this frees resources (slow) and is meant to be called between levels (or whenever else there is a lot of time), so it isn't performance relevant.

I did mention that it's not (particularly) slow for std::map, but it can be for iterators in general.  Consider that the STL contains things like iterators for generating permutations, etc., which do non-trivial amounts of work to decide what end() means.  Again, while it's not a huge issue in this case, I think it's a worthwhile idiom to develop so that you're not surprised at some point later on.

3. A hash map might be better. You can try the tr1::unordered_map, to see if it is better, should there be performance problems (unlikely). Although I am not 100% sure if ReleaseUnusedResources can remain unchanged (different iterator semantics and all that).

Yes, ReleaseUnusedResources would have to change, since erasure from a hash_map invalidates all iterators.  The simple fix would be to iterate over the map calling reset() on the pointers, rather than actually removing them.  If you're really concerned about the size of the map itself, you could collect them in a vector and erase them afterwards.

BTW, string hashes are usually also linear in time ;-)

Yes, but they only need to be computed once per lookup.  An insertion into an std::map will perform a logarithmic number of comparisons, each linear in the length of the string.  A hash_map specialized for string comparisons would do a single linear hash at the beginning, and one for each hash collision, including the real hit.  Unless you have a god-awful hash function, that's a distinct improvement.

4

General discussions / Vec3, Vec2 Speed Test

« on: September 16, 2009, 11:28:19 am »

That's exactly what I meant with my suggestion. You were complaining about the compiler optimizing your code so that you aren't able to test well enough. -O0 disables optimizations and lets you profile your code.

Profiling unoptimized code isn't always very useful, since the things that take a long time in unoptimized code can be totally different than the things that take a long time in optimized code.

5

SFML wiki / [Sources] Thread-safe Resource Manager

« on: September 16, 2009, 11:01:55 am »

Some feedback:

1) You're doing two lookups into the map every time something is loaded.  You can avoid this by using references to update in place.  It also shortens the code.  In this particular situation it doesn't matter too much since it's on the uncommon path, but it's a good technique in general.

Code: [Select]


// P is either the pre-existing entry, or a default constructed (i.e. NULL)
// Resource if it wasn't already in the map.  Since P is a reference,
// we can update it in place.
Resource& P = resources[locator];
if (!P) {
  Resource& loaded = LoadResource(locator);
  if (loaded)
    P = loaded
  else
    throw std::runtime_error("BORK!");
}


2)  When iterating a container, it's generally best to cache the end iterator, as long as you're sure you won't be invalidating it.  std::map isn't particularly bad, but in general it's hard to know how much work is involved in calling end(), and I've seen simple loops that ended up being ridiculously slow entirely because they called end() on every iteration.  The idiom I typically use is below.  It's a bit more complicated, but I've found it a good habit to get into to avoid surprises down the road.

Code: [Select]


// This assumes we're using a map where (...) doesn't invalidate
// arbitrary iterators.  This is almost always the case with std::map
// (unless you do something really braindead), but most hash_maps
// offer weaker iterator guarantees, so be careful!
for (ResourceMap::iterator I = resources.begin(), E = resources.end(); I != E; ++I) {
  ...
}


3)  This is a meta-comment, but std::map isn't really what you want in this situation, for several reasons.

First, because it's a tree-based structure, lookup time is logarithmic.  So you're doing a logarithmic time operation each time you access a resource, even on the hot path.  You really want to be using a hash map structure, which can take longer in the uncommon case when a resource is actually loaded, but is constant time for the common case.  I think boost has hash maps, and it's not that hard to write your own.

Secondly, using the default comparison operators for maps of strings is generally a really bad idea, since comparing strings is linear in the length of the string.  You really want to be using a hash map with a hash function specialized for strings so that you're not doing several linear-time string comparisons on each insertion.

Third, std::map is very copy-heavy.  That is to say that any key or value used in the map will be duplicated many times.  Thus, for something with comparatively expensive copy semantics like std::string, you'll be paying a non-trivial amount of time making needless copies of the string.  You either want to use some sort of rope class that reduces the copy cost, or use a non-copying hash map.

The LLVM source base has a very good StringMap class that provides a very efficient string-to-T map that I usually pull in to projects where I need to do a significant amount of string mapping..

6

Feature requests / Speex (or other voice-oriented codec) support

« on: September 15, 2009, 02:51:06 pm »

In theory at least, the Ogg file-parsing code should be shareable with the Vorbis playback stuff, but I don't think the STB codec exposes it at that level.

You could conceivably use liboggz + libfishsound (both from Xiph) to make a generic anything-in-an-ogg-container decoder that would support Vorbis, Speex, and FLAC all in one.  See here for an example.

7

Feature requests / Speex (or other voice-oriented codec) support

« on: September 15, 2009, 10:38:18 am »

Just saying, it would be nice to have support for a voice-oriented codec.  You can pack voice audio into a much smaller data file using voice-specific encoding as opposed to something more general like Vorbis.