In-Game Events and Gatherings

what is the O(n^2) nature of drones? why would a single drone have to iterate through all other objects do do something? I mean this should NEVER be the case. Even the simpelst form of spatial subdivision (like a basic quad tree) would bring this down to logarithmical complexity. Even n-body simulations use tricks to not have exponential complexity at runtime.

Uhm, multithreading the code? :)
Street rumour says you doing singlethreaded processing in the age of multicore architectures. Of course, this is easier said than done, i pretty much know, and this would require shittons of effort and would have the pitfall of even more "side effects". :)

In a world where latency matters, I don't see this being as big of a problem if everything is done on the tick. This would lead to some interesting cases such as a double-knockout but I think the EVE community would be happy with such a setup.

I would imagine this could very much become like a map-reduce problem, where on the tick, multiple threads work on the processing of a given number of ships / elements, and then they are all collated at the end and then the main process goes to work, tots up the amount of damage to each ship, and applies it in 1 chunk.

Nobody in their right mind goes and rewrites an entire platform at one time. One does this incrementally and all of these examples were entire rewrites of the systems in question. I forgot one of the rewrites in my list since we never talked about it publicly, when we removed the custom Python importer in the summer of 2013. It was needed in the early days of EVE but not anymore.

its not n^2 unless its very badly implemented. n^2 would be if each drone would have to communicate with each other drone/object. If they don't influence each other they don't have to do that. Regarding client-server communication a drone is like any other object on grid which has to be communicated to the client. Its not peer2peer after all - even in worst case scenario you should never have n^2 complexity in systems like that.


Regarding multithreading, even a essentially sequential system can be distributed via pipelining/layering - one of the oldest forms of parallelization for large monolithic systems. Solutions do exist, CCP just has to think out of the box.

The wiki page linked here has some stats, and several links at the bottom to past dev blogs.

https://wiki.eveonline.com/en/wiki/Tranquility

Maybe kit your 60 blades with some expensive GPU's and run the physics of each local node through a bunch of physics oriented shaders - should alleviate the syncing issues, and you'll have CPU left over to crunch the market 0.01 iskers.

I was told I should drop this in here... So here it is.


"Given the O(n^2) nature of drones"

Is there more information on this? Is this an algorithm where each each drone needs to be compared against every other drone?

I ask because one of my more recent projects at work was an O(nm) where I needed to full cross compare two sizable lists, pretty much like an O(n^2). I'm also generally interested in problems like this.

pseudocode:

Naive

foreach(n in List1)
foreach(m in List2)
compare(n,m)


Better cache reuse version

partitionList1 = BreakIntoSmallerCacheFriendlyGroups(List1)
partitionList2 = BreakIntoSmallerCacheFriendlyGroups(List2)

foreach(p1 in partitionList1)
foreach(p2 in partitionList2)
foreach(n in P1)
foreach(m in p2)
compare(n,m)

In my case, I was able to get a 30% speed up. Of course I used a "parrallel foreach" on the outer loop and did not actually use "foreach". IEnumberables are actually expensive compared to arrays. Nothing like watching a dual socket sexacore Xeon running at 100% trying to crunch a 80k x 100k comparison :-)

We're potentially eyeing up lists of sizes over 1mil each, looking into better ways to prune and categorizes into smaller groups. Anything to weed out knowing if two items should even be comapred with each other. We're now looking into something more like O(nm(1-r)^k), where we want to get r and k and large as possible.