std::tr1::unordered_map vs __gnu_cxx::/stdext::hash_map

[MaikBeckmann]

Hello,

I know this game since yesterday and as a former elite frontier gamer (in the good old Amiga days) I'm very pleased.

I checked out your code and GCC said you're using

Code: Select all

hash_map<..>

which isn't part of the stl.

However, tr1 introduces

Code: Select all

unordered_map<..>

which is just another name for the same thing, AFAIK.

I did some coding and so far I can switch between the tr1::unorderd_map and hash_map. To make this happen I had to alter a statement like this

Code: Select all

  stdext::hash_map<foo, bar>

to

Code: Select all

  detail::unordered_map<foo, bar>::type

The ::type evaluates to either hash_map or tr1::unordered_map, depending on weather HAVE_STD_TR1 is defined or not.

This worked for the hole codebase -- vegastrike is up and running.

Are you interested in using the tr1::unordered_map as an alternative to hash_map?

Best,
-- Maik

[safemode]

is it faster? seriously, hash_map is a huge % of cpu use per frame

in reality, if hash map isn't standard, and unordered_map is, and it's basically a drop in replacement, then it'll probably get in.

[MaikBeckmann]

is it faster? seriously, hash_map is a huge % of cpu use per frame

I'll expect it to the the same peace of code.

in reality, if hash map isn't standard, and unordered_map is, and it's basically a drop in replacement, then it'll probably get in.

That's the point, it's standard. Every compiler which brings the tr1 extensions will have unordered_map, where hash_map will be dropped even by those supporting it right now.

For pre-tr1 versions of gcc and msvc hash_map will do the job. Thus there is no risk.

Fore you it's an investment into the future of your codebase, for me it's one more reason for digging through the codebase.

I'll prepare a patch anyway. It would be nice if you test it.

It will take some time, since I have to hack it again without the code-reformatings I've done to get the code right.

Additionally I have to figure out how to let autoconf check for tr1. I preferred to invest an hour into a cmake script, just because I know it better and I can use it for linux(at home) and windows(at work).

Regards,
-- Maik

[safemode]

as for code reformatting, I've been playing with bcpp to get the code formalized and pretty, but it still ends up requiring a little hand editing after a run through (macro's get indented and I hate that). It's not so important right now though, as no amount of beutifying the code is going to make it easier to follow when there's so much going on with the headers.

Doing the autoconf check should be nothing more complicated than checking for the ability to compile a program using the object.

If it compiles, yay, otherwise, use fallback.

Though, I suspect we could just use boost's objects for which TR1's objects are mostly derived. Since we use boost anyway, we should be able to use either "std"'s unordered_map if available or Boost's unordered_map,.

I suggest that fallback option and get rid of hash_map altogether. That way we merely change the "using namespace" line in code and include a different header in affected files. I think the function calls and objects are otherwise the same

[MaikBeckmann]

as for code reformatting, I've been playing with bcpp to get the code fomralized and pretty, but it still ends up requiring a little hand editing after a run through (macro's get indented and I hate that). It's not so important right now though, as no amount of beutifying the code is going to make it easier to follow when there's so much going on with the headers.

I used astyle for some time, but I turned away from this kind of tools. When I'm doing my code reviews I'll send cosmetic patches.

Though, I suspect we could just use boost's objects for which TR1's objects are mostly derived. Since we use boost anyway, we should be able to use either "std"'s unordered_map if available or Boost's unordered_map,.

I suggest that fallback option and get rid of hash_map altogether. That way we merely change the "using namespace" line in code and include a different header in affected files. I think the function calls and objects are otherwise the same

Tricky. unordered_map is in trunk, but isn't in 1.35. AFAIK it will be part of 1.36. The tr1 part of boost isn't adopted to use it yet, but I guess it will be for 1.36.

-- Maik

[safemode]

cosmetic patching probably wont be considered until closer to 0.6. In the meantime, the code base is gonna get shaken up pretty good from various fronts.

Weird about unordered_map not being in boost already, usually those types of primitives happen in boost first, then get considered for C++ stl.

Perhaps it's best to just switch to using boost's hash code, rather than tr1 or current stl hash type functions.

We ship a version of boost or 3 so we can guarantee thier state. Plus for some reason, boost 1.34 (debian unstable's) causes some major slowdowns. 1.33 in-tree seems to yield the fastest executable.

So if our 1.33 tree has hash functions. maybe we should patch to use them. That should simplify things until the far future.

[MaikBeckmann]

We ship a version of boost or 3 so we can guarantee thier state. Plus for some reason, boost 1.34 (debian unstable's) causes some major slowdowns. 1.33 in-tree seems to yield the fastest executable.

I compile against boost-trunk. Is there a wiki-page towards benchmarking of vegastrike?

-- Maik

[safemode]

just profiling. --enable-profile

compare the profile output between in-tree 1.33 and external trees.

Basically turning around after first launching and viewing Atlantis should be sufficient to show the difference i saw against debian's pkged boost.


We do need some better mission files setup to enable reproducable benchmarking using real in-game situations... but mostly it's just find something that slows down gameplay the most, and do it over and over again while profiling. Then track down the function responsible and see if it's slow, or if we just happen to call it a ton of times.

not much else work has been done to profile and measure latency in the codebase

[MaikBeckmann]

I did it this way:

stdext::hash_map was replaced by std::tr1::unordered_map. All header files use this syntax

Code: Select all

 std::tr1::unorderd_map<..>

while in source files this one is prefered

Code: Select all

  using std::tr1::unordered_map
  ..
  unordered_map<..>
  

in case it's occurs more than once.

For compilers which don't provide a tr1 implementation yet boost's unordered stuff has been added to boost/1_33 and is forwarded like this

Code: Select all

#include "boost/unordered_map.hpp"

namespace std { namespace tr1 {

  using boost::unordered_map;
  using boost::hash;

}} // namespace std::tr1
  

I'll provide a patch ASAP.

Best,
-- Maik

[klauss]

What are you trying to accomplish with that?

[MaikBeckmann]

What are you trying to accomplish with that?

std::tr1::unordered_map is standard, stdext::hash_map and __gnu_cxx::hash_map are not.

[klauss]

Anything under tr1 is whatever you want except standard.
It may be on its way to standardization... but compilers usually fall way behind the standards. One major compiler targeted by VS does not support it: MSVC. Heck, MSVC doesn't support truly standard stuff!

Besides... I read somewhere that they don't behave exactly alike. It may bring more trouble than it's worth for a patch that fixes something that already works... or did hash_map bring you some trouble?

[MaikBeckmann]

Anything under tr1 is whatever you want except standard.
It may be on its way to standardization... but compilers usually fall way behind the standards. One major compiler targeted by VS does not support it: MSVC. Heck, MSVC doesn't support truly standard stuff!

I expect MSVC to work with boost's unordered_map

Besides... I read somewhere that they don't behave exactly alike. It may bring more trouble than it's worth for a patch that fixes something that already works... or did hash_map bring you some trouble?

No trouble. I just saw the hacks you do to get gcc and msvc hash_map to work. This complexity is gone when boost/tr1 unordered_map is used.

However, it's just a patch. Grap it, try it and I don't mind if you drop it

The work is done and git dumped a patch to my disk, but I will review my changes tomorrow before I upload it.

Best Regards,
-- Maik

PS: Please see the bugtracker for a tiny patch which fixes the build for GCC-4.3 .

[safemode]

i think the boost version would be best rather than using compiler specific functions.


That said, if we want to look at something for performance consideration, linear_interpolate_uncapped is a good start.

[MaikBeckmann]

This patch is created against rev: 12136

Tested with
GCC-3.3.6
GCC-3.4.6
GCC-4.3.0


Have fun,
-- Maik