Andrew

October 7, 2009

High Performance C++ Profiling

Filed under: Uncategorized — floodyberry @ 10:40 am

[This is about my C++ Profiler which may be found on Google Code under High Performance C++ Profiler]

My interest in code profiling started when I was making hudbot. What with code injection and patching, function hooking, data hijacking, and OpenGL, I knew I had relatively no experience in what I was attempting and that I could easily be producing some amazing slowdowns if I wasn’t careful.

Unfortunately, C++ profilers seem to come in three varieties, all of which have a fatal downside:

  1. Sampling Profilers which are fast, multi-threaded, but inaccurate and have decent output (sometimes too detailed). Some examples are VTune, CodeAnalyst, google-perftools and Sleepy.
  2. Instrumenting Profilers which are accurate, multi-threaded, but slow, and have decent output. Some examples are GlowCode and the now defunct DevPartner Profiler Community Edition.
  3. Instrumenting Profilers which are fast, accurate, but single threaded and have limited output. These range from extremely simple profilers like Peter Kankowski’s Poor Man’s Profiler to the more complicated and full-featured Shiny C++ Profiler.

The obvious outcome is that if you want fast and accurate, like I did, you’ll have to use an existing profiler or write it yourself and instrument your code manually. With a little work, fancy stuff like call trees can be added. Once you get it tested and working, you can start going crazy profiSegmentation fault.

Oh yeah, about that. There are no multi-threaded instrumented profilers that are open source, and depending on how your single threaded profiler works, the results when trying to use it in a multi-threaded environment can range from bad data to outright crashing. It’s possible to patch the profiler to only allow the main thread in, but this adds unnecessary slowdowns and doesn’t address how to profile other threads. This is where my profiler comes in!
(more…)

September 8, 2008

Generating .DLL Wrappers

Filed under: cplusplus,Programming,Win32 — floodyberry @ 5:25 am
Tags: , ,

A while ago I came across Create your Proxy DLLs automatically by Michael Chourdakis. I thought it was a good idea, but had some room for improvement:

  • Having to use an external .exe (dumpbin/tdump) was an unnecessary step, all the information you need is in the PE header!
  • He did not handle wrapping mangled names or forwarding forwards.
  • Generating an actual project instead of a command line compile call would be a lot more useful considering you will want to do some actual coding instead of generating an empty wrapper.
  • His coding style was somewhat awkward and not easy to modify.

With this in mind, I set about writing my own version. (more…)

July 9, 2008

The id Tech 4 Script Compiler Sucks Hard!

Filed under: Games,Optimization,Programming — floodyberry @ 3:23 pm
Tags: , ,

Whoever did most of the work on the id Tech 4 Script Compiler, I’m calling you out! I’ll grant that you managed to write a major component of a successful commercial engine, but… it’s just so bad. What confounds me even more is that all of the engines after DooM III did almost nothing (effective) to try and fix it: If you check out the Quake IV, Prey, and ET:QW SDKs, they all have the same basic compiler with a couple things bolted on. The ET:QW guys did do a bit of work on it and tried to speed it up a bit, but “glacially slow” doesn’t seem like much of an improvement on “geologically slow”.

I first noticed how bad it was when I was doing the ET:QW -> Tribes stuff and started playing around with the scripts. Being so use to Tribes style scripting, two things hit me right off:

  1. You have to exit the mission and recompile every script if you want to update a script you just edited. Ok, pretty annoying, but I’m just playing around so it should get easier.
  2. On my AMD64 3200+, recompiling was “damn slow” (~20 seconds) in Release mode and “I’m going to read a book” (~60 seconds) in Debug. Issue #1 just got a lot more annoying.

How did they manage to develop on this for longer than 10 minutes before going crazy, let alone create an entire game? Apparently I was the first to get fed up enough about it, so I went to check out the compiler and see if I could find any hot spots.

(more…)

April 29, 2008

Tribes 1 Physics, Part Four: Explosions

Filed under: Games,Tribes — floodyberry @ 12:30 pm
Tags:

Explosions (or more accurately, knockback), the final piece to the physics puzzle! If you implement all of the previous articles, make a disc launcher, plug in the apparently simple knockback force and radius from baseProjData.cs, and finally attempt to disc jump, you will be greeted with… a nice and wimpy boost. Playing around with the knockback force will only break explosions in new ways. Argh, you were so close! How could Tribes possibly screw this one up? (more…)

April 11, 2008

Tribes 1 Physics, Part Three: Collision

Filed under: Games,Tribes — floodyberry @ 7:47 pm
Tags:

This article covers the collision physics of Tribes 1, i.e. attempting to actually move the player and what to do when the player runs in to something. This is the most convoluted part of the physics and requires a lot of little touches to get right. Tribes movement and collision handling actually gets a little too low level, so I won’t be able to show exactly how it works (it gets down to dealing with the raw triangle lists which I don’t think all collision detection systems will let you get at), but it will be detailed enough so that there will be no major differences. (more…)

February 24, 2008

Tribes 1 Physics, Part Two: Movement

Filed under: Games,Tribes — floodyberry @ 11:48 am
Tags:

This article covers the movement physics of Tribes 1, i.e. jumping, jetting, and ground movement/friction. These account for ~90% of the “Tribes” feeling, although even 90% will still feel wrong to anyone who knows the authentic feel well. There will be some variables which are only set in the Collision code, but there shouldn’t be any confusion as to what they do. (more…)

February 20, 2008

Tribes 1 Physics, Part One: Overview

Filed under: Games,Tribes — floodyberry @ 11:04 pm
Tags:

Games have been trying replicate the feel of Tribes 1 for almost as long as it’s been out (Tribes 2 started development in mid-1999) and every single one of them has failed, usually miserably.

  • Tribes 2 physics are an abomination, although in hindsight it should have come as no surprise after the Base+ mod Dynamix play-tested in Tribes 1 to massive disdain. It’s as if they were trying to build on the success of Tribes 1 when it was 2 weeks old, not 2 years. Unfortunately for the majority of the community not in the beta, we didn’t find this out until after the game was paid for. Further mods such as Base++, Team Rabbit 2, and Classic attempted to rectify the situation yet were still only a pale ghost of Tribes 1.
  • Legends has always felt wrong despite how often they tweaked and twiddled the physics and boasted of having the original physics source code. If they did have the source, they either didn’t know how to implement it or didn’t have enough of the source to properly replicate all of the required physics.
  • Tribes Vengeance is so far removed from the feel of Tribes that it shouldn’t even enter the discussion. Jetting is wrong, air movement shouldn’t even exist, collisions are wrong, and skiing is a sick joke. I can only hope KineticPoet remembered what used to be and silently winced every time he sat down to work on the game.
  • The yet-to-be-released Fallen Empire: Legions appears to be following the “We’re not a Tribes 1 clone, so let’s make wacky changes to ram that home” mantra. Ideas like 6 way jetting (jetting down while in the air and laterally while on the ground), non-friction sliding a-la T:V, jetpack overdrive, a charge up sniper rifle, etc., sound like they could easily alter the game beyond good taste.

What all of these games ostensibly want is to appeal to Tribes 1 players, yet they attempt to accomplish this by using a different and/or completely arbitrary physics system, adding something that resembles a jetpack and skiing and hoping everyone likes it. While I don’t know if a carbon copy of Tribes 1 on a modern engine would be a success, I do know that almost any Tribes 1 veteran will be unsatisfied with any Tribes style game that does not replicate the feel of Tribes 1 regardless of how often the developers hide behind the claim of “not Tribes 1”.

These articles will solve that problem. I will provide everything needed for a 99% re-creation of the Tribes 1 physics on any 3d engine. There are a few pieces to the puzzle so I’ll be breaking the topics in to separate articles for movement, collision, and explosions. This article will go over the basics of the engine and document the structures and constants I’ll be using. (more…)

February 15, 2008

Writing a (Tribes 1) Master Server

Filed under: Games,Programming,Tribes — floodyberry @ 10:59 am
Tags: , ,

While I wrote this in September 2007, for various reasons I did not get around to putting the finishing touches on it. Please pretend you’re reading it then and not now!

After the hubbub over Sierra’s announcement that they were ceasing multiplayer support for Tribes 1 and the resulting scramble to locate a replacement master server, I decided to give a shot at writing one. The required feature set appeared simple enough to only take a week or so to implement but with enough gotchas to keep it suitably interesting. While I only had a vague idea of what was required, I got a jump start on proper design by finding Half-Life and Team Fortress Networking: Closing the Loop on Scalable Network Gaming Backend Services by Yahn W. Bernier, an article detailing the design, implementation, and potential problems of the Half Life master server. Even though some of the topics did not apply to the Tribes 1 requirements, e.g. I can’t alter the client’s behavior to auto rate-limit the server list transmission, the article was still quite valuable and an interesting read even if you aren’t implementing a master server. (more…)

May 17, 2007

C++ Templates and Class Inheritance

Filed under: cplusplus,Programming — floodyberry @ 1:03 am
Tags: ,

The following code is not legal C++:

template < class type >
struct A {
	void f() {}
	type mX;
};

template < class type >
struct B : public A<type> {
	void g() { mY = ( mX ); f(); }
	type mY;
};

The best part is that unless you know the obscure reason why it is not legal, it appears legal and might even compile and run perfectly depending on which compiler you’re using. Not surprisingly, that is exactly how I ran in to it. I was doing templated class inheritance and thought I was in the clear because everything ran fine with MSVC7.1 and ICC 9, but when I belatedly tried to compile with g++ 3.4.4, I ran in to the following errors: (more…)

April 14, 2007

UTF-8 Conversion Tricks

Filed under: cplusplus,Optimization,Programming — floodyberry @ 3:04 am
Tags: , , ,

UTF-8 is a wonderfully simple encoding format with some very nice properties, but the juggling required to convert to UTF-16, and UTF-32 can be a little tricky and fairly easy to do poorly. This is further compounded by the various error conditions you must keep an eye out for, such as overlong encodings, reserved ranges, surrogate markers, incomplete sequences, and so on.

These are a couple tricks you can employ to hopefully keep the conversion fast and robust.

(more…)

March 29, 2007

Breaking SuperFastHash

Filed under: Hashing,Programming,Security — floodyberry @ 3:31 am
Tags: ,

After the problems SuperFastHash had in Hash Algorithm Attacks, I decided to try and break it completely, i.e. generate collisions algorithmically instead of brute forcing them. The attempt was more successful than I had anticipated, although Paul is obviously aware of the weak mixing in the final bits as evidenced by his comment in the source code, “Force ‘avalanching’ of final 127 bits”. My favorite collisions encountered would have to be “10/4 < 3”, “10/5 = 2”, and “10/6 > 1”, which have the property of hashing to the same value while being mathematically correct!

As I was writing this, I came up with a way to attack Bob Jenkins’ lookup3 as well. Unlike SuperFastHash, the lookup3 attack is due to the way the input bytes are being read in and does not indicate a deficiency in the mixing itself. If you are using lookup3 with hash tables, the core function will still be quite safe; it will only need to be modified if you are using it to generate unique 64bit identifiers and the input data could be altered for a malicious purpose.

With that said, let’s look at the attacks:

(more…)

March 7, 2007

When Bad Hashing Means Good Caching

Filed under: Hashing,Programming — floodyberry @ 1:54 pm
Tags:

I was testing various string hashing algorithms on chained hash tables, primarily to look at the bucket distribution and number of key comparisons with both prime and power of 2 sized tables. Each table node was set up to remember it’s full hash value so bucket collisions would only drop to a key comparison on a true key collision. I initially wasn’t concerned with run times, but I tacked on a timer anyway so I could get a quick metric on how collisions and distribution were affecting performance and wound up running in to a rather odd situation. (more…)

October 6, 2006

Why Blizzard Loves Diablo II Cheats

Filed under: Diablo,Games — floodyberry @ 4:25 am
Tags: , ,

Blizzard loves cheats? Are you sure? What about all their anti-cheat measures, like Rust Storm, Warden, and the mass bans we always hear about? Surely they wouldn’t fight something they are in favor of. Or would they? Let’s take a deeper look in to Diablo II and see just who is profiting from the use and abuse of cheating.

(more…)

Blog at WordPress.com.