Missiles Hate My Hamsters

Hi there.  Thanks for taking a break from your Incursion-fighting to read this here devblog.  It's about missiles and CPUs and stuff.

I want to preface all of this by saying that the changes are not on TQ yet. We are going to turn on individual elements one-at-a-time, analyze the results, and once we have a good analysis, make changes and turn on the next one. For this reason, there is no set release schedule but you may begin feeling the effects in fleet battles starting on Thursday. Testing may show that the changes made are not safe and we won't be able to use them. I thought this would be interesting enough to share, but please do keep this disclaimer in mind as you read on.

Missiles

As we've mentioned before, missiles are expensive.  CCP Masterplan did some awesome work on Destiny to make them less impactful, but even after those we still weren't pleased with how expensive missiles were versus other weapons system, so we spent some time digging into exactly why and fixing the problems.

To understand why missiles are more expensive than, say, lasers, it's helpful to ask what missiles do that gun-style weapons don't.  Well, here's a list:

·         Put a physics ball into simulation

·         Put an item into the solar system's inventory

·         Introduce an item to Dogma - the attribute tracking system

·         Simulate a path through space detecting collision with their target

·         Explode

·         Removal from Dogma, inventory and physics

So...lots of things.  Some of them are cheap (pathing through space, unintuitively, fits that description), some are quite expensive (Masterplan's work significantly reduced the "Put a physics ball into simulation" portion, for instance).  All useful things too, necessary so you can outrun a missile, or smartbomb them to death, or use defender...well, the first two at least.

We spent some time digging into each of these specifically to see if there were any gains to be had.  We found quite a lot:

·         The query to check if the character has skills for a type of item did its job twice needlessly

·         Fetching the modifiers for an attribute would query the required skills for the item type twice needlessly

·         Removed some crusty features that haven't been used in years

·         Missiles had all of the entity setup data that NPC AIs had.  Nearly all unused, so they're not set up now.

·         Various different systems were treating missile explosion like ship explosion.  They don't do that now.

·         The missile damage calculation was reordered so data wasn't fetched until needed.

Two big changes came out of this investigation as well:

Fake Dogma for Missiles

Previously, when you launched a missile (or group of missiles, bless your heart), a new item was created for it in the Dogma system.  Being a new item, none of its attributes were known, so pretty much every time an attribute was queried the cache would miss and we'd end up doing a full calculation.  That takes about .08ms, which isn't very much time, but when you've got about 10 attributes per missile and a few hundred missiles, it becomes significant.

The key observation here is that a missile in space has the same modifiers on it as a missile sitting in the launcher.  With that knowledge, we can simply copy the full set of attributes from the in-launcher missile to our new in-space missile and don't even bother setting up anything else for it in Dogma.  Since in-launcher missiles don't really have an identity, it comes down to querying "those missiles in that launcher", which will remain the same between launches, so we'll only do the calculations once and use them until you switch ammo types.  This also significantly impacted the time to launch and explode a missile, since setup and teardown of these "fake" Dogma items is much faster than full items.

Inventory Setification

During the testing of the changes above, I noticed that as the day went on, performance degraded a bit.  Comparing a Telemetry trace from early in the day with late, I narrowed the difference down to the bit of code that removes an in-space missile from the system inventory.  This made some sense, but in a scary way...over the course of the day I had spawned and blown up many ships, leaving a lot of debris in the system.  If the cost of manipulating the system inventory is highly influenced by the amount of things in space, then that's a big problem.

Turns out it really is a big problem.  Technical mumbo-jumbo ahead!

Whenever we do a query to our database, we get the results back in a data structure derived from Python's "list" data structure, which implementation-side is an array of pointers to the elements' values.  This is ideal for nearly all cases, since we get back an ordered list of rows from the database that we don't mess with at all.

Inventories are a completely different use case however.  We get back that initial query from the database, but then we mess with it heavily and don't particularly care about order.  Adding to a list is cheap, you just tack onto the end (and grow if need be), but search and removal are horrendous.  Since list doesn't have indexing nor sorting, a search for inclusion is exhaustively linear.  Removing an item from a list involves doing a linear search of the list for the item in question followed by copying the remaining entries in the array one slot up.  O(n) is usually a sign you're done, but in this case it's a sign of a major problem.

The solution proved to be terribly simple - have the inventory system specifically ask for a Python "set" structure instead of the usual list-based.  There were only a couple places in the codebase that treated an inventory specifically as a list, which were quickly fixed up.  This showed a very significant improvement in the missile throughput of the server, and will likely have significant impact across the game since inventories are used a lot.

Enough words, I want a pretty graph!

Fine.

Methodology note:  For these numbers, I had 200 ships shooting on a devhaxed Drake.  Rate of fire was hacked to be high enough to saturate the server, then the number of repeats per second was recorded from the node and averaged over an about 60 second period of steady-state.

tl;dr:  We're looking at roughly a 5x load reduction for missiles since we started this work.  They remain considerably more expensive than guns, but reasonably so given what they do.  Hopefully this'll help once we get them all proven safe through QA and onto TQ.

Fly safe, my Drake-obsessed friends,

~CCP Veritas