Guild Wars 2

I believe that I’ve witnessed a correlation between skill lag in a large-scale Keep / Stonemist battle and the event associated with the defensive tick.

I haven’t had the opportunity to repeat these observations due to play time issues, so I was hoping that I could get a few more eyes watching for a correlation. Basically, when you’re in a skill-laggy situation defending around Stonemist, watch the timer and observe whether or not, if only for 10-15 seconds afterward, if the lag is markedly lessened.

It could have been complete coincidence, but my spidey sense is tingling. Also, anet should check server load average 15 second interval graph for dips that correlate with defense events.

That seems like a feasible correlation.

The server must track all event participants to reward them. After the event, that should all clear out. If lag goes down noticeably right after a defensive event turnaround it could mean that there’s some problem with how they are doing this tracking.

(Imagine, for example, that the list of event participants was a flat array or linked list. Every time someone kills someone or does a repair, it searches through the list, top to bottom, to see if they are already in the list or not. As this list grows, this process takes more and more CPU time and with hundreds of people constantly getting kills it could be a huge drain. If this was the problem, a hash table in place of the flat list could fix it. [Bro do you even code?])

Slamz.5376:

(Imagine, for example, that the list of event participants was a flat array or linked list. Every time someone kills someone or does a repair, it searches through the list, top to bottom, to see if they are already in the list or not. As this list grows, this process takes more and more CPU time and with hundreds of people constantly getting kills it could be a huge drain. If this was the problem, a hash table in place of the flat list could fix it. [Bro do you even code?])

Seriously… Even linear search on the worst constructed in-memory list containing a few hundred items is lightning fast on today’s systems. Not that I recommend writing lazy code, or expect that they did, but… [This is not the performance issue you’re looking for.] [Bro do you even deliver production applications?]

It is not “lightning fast”. It’s the slowest possible algorithm you can use. If you write code that may use it hundreds of times per second on a server which is also busy doing a hundred other things, then I’m pretty sure I don’t want to see your production applications.

Slamz.5376:

It is not “lightning fast”. It’s the slowest possible algorithm you can use. If you write code that may use it hundreds of times per second on a server which is also busy doing a hundred other things, then I’m pretty sure I don’t want to see your production applications.

Still living in the land of theoretics, I see…. Of course it’s the slowest possible algorithm you can use. That’s why I chose it as an example. I also said it wasn’t something I would do in production. The point is that as bad as the practice as it is, for in memory data structures with small counts, this is just not going to have the performance impact you’re expecting. And in fact, at some point you count the cost in terms of code complexity, memory cost, etc, and some times you may well do things the dumb brute force way. Hooray for trade-offs. In any event, I urge you to try this on your own… For example on my system I was just able to run 1000 full length linear searches through an array of 1000 elements in about .06 seconds, without touching the CPU. So, even if ANet was this amazingly stupid to not have kept a scratch table or used a KvP structure, etc, it’s just not going to have the perf impact that you want to think it is.

Or, to put it back in theoretical terms…. Even an O(N) operation approaches the speed on of an O(Log(N)) operation for low values of N.

O(n) is fine when n is like 5.
There is a massive difference between O(log n) and O(n) when n is 100.

So for values under 5 or so, you might as well use O(n).
For much more than that you should use a binary search, at least, for O(log n).
At some point you should consider a hash table.

Not that there’s anything wrong with using a hash table for n=100, just that the gains over a binary search at n=100 aren’t that big. That’s the argument you might actually use and win.

But to argue that O(n) is fine in a WvW battleground that can have > 100 players going into a list that may need to be updated many times per second? That’s just lazy programming, not to mention bad practice and probably not a real keen thing to have in your sample code you show at your next interview.

O(n) into the 100s of items is an amazing waste of resources.

Sure, I agree with everything you just said. But here’s what I’m saying…. It’s an example terrible lazy programming without a doubt. But even at that, the operations that you are doing an excessive number of times (comparing values in an in-memory list) are so minimal that it has a negligible impact on CPU cycles in this case, and so will not cause any kind of performance hit that is noticeable to an end user.

Are you still a nerd if it’s something you do professionally? Yes…? Oh…

Slamz.5376:

O(n) is fine when n is like 5.
There is a massive difference between O(log n) and O(n) when n is 100.

So for values under 5 or so, you might as well use O(n).
For much more than that you should use a binary search, at least, for O(log n).
At some point you should consider a hash table.

Not that there’s anything wrong with using a hash table for n=100, just that the gains over a binary search at n=100 aren’t that big. That’s the argument you might actually use and win.

But to argue that O(n) is fine in a WvW battleground that can have > 100 players going into a list that may need to be updated many times per second? That’s just lazy programming, not to mention bad practice and probably not a real keen thing to have in your sample code you show at your next interview.

O(n) into the 100s of items is an amazing waste of resources.

Except it is very common for a lot of operations. Usually you dont get into trouble computationally until its at least O(n^2), but even then for a lot of computations O(n^2) isnt going to get you into trouble until you are well into the thousands. I dont think event computation is O(n) every time someone hits something. When the defense quest ends is where the costly computation is, but it should only be O(n) which isnt a big deal.

A zerg fight can be brought down to O(n^(n)) in computation. Which makes this defense quest problem so trivial in comparison.

I know it’s a long shot, but I’ve seen instances where you call a loop, not knowing that each iteration has a nested loop in and of itself, and somewhere deep in that was a read/write to a disk that really didn’t need to be there.

Anyway – semantics and logarithm theory aside, could a few people just check next time they are in that scenario?