Oh god... where has the lag gone? :|

[ph3n1x]

cannot log in right now

could not connect to server

[Slizyboy]

It was just a data structure that I had left as a sorted linked list, ....

<cries and dies a little inside> I'm sure you had a good reason for it at the time

I thought linked lists had cheap insertion but expensive random access?

Cheap insert *at head* - loftar was keeping a sorted linked list, which means each insert is O(n), since you have to traverse the list in linear time to find where to do your O(1) insert.

[loftar]

I thought linked lists had cheap insertion

Well, yes; but keeping it sorted is a different matter, since you have to look up the right element to insert at.

but expensive random access?

Only if you want to access them by index, which is quite rare in my experience. This list, however, I only use for finding the first element, and for cheap deletion. I should implement some heap structure instead (probably a Fibonacci heap). (The cheap workaround I wrote was to keep new elements in a separate list temporarily and then merge them together. That way, if n is the number of elements currently in the list, and m is the number of elements I want to insert, I'm reducing the complexity from O(nm) to O(m² + n), which is obviously much better when m << n, which is the case.)

<cries and dies a little inside> I'm sure you had a good reason for it at the time :P

Of course. It was simple and quick to implement. :) As I mentioned, I knew it would cause problems and that I'd have to reimplement it, but I wasn't interested at the moment, and then I forgot about it. :)

Fuck, I new it was somewhat temporary. What's worse is the game lags even more than before even though my internet connection isn't broken. Restarted it but it still lagged.

Well, the lag due to lack of bandwidth is, of course, unsolved. This fix should just have removed the huge lag spikes that happened about once a minute.

That said, I did recently find a (completely unrelated) possible way to improve network performance as well. It turns out the client is pretty bad, sometimes, at keeping objdelta ACKs to as few packets as possible. Sometimes, it divides them to one ACK per package, leading to high loss, the server never receiving them, and thus having to resend object data, which actually does seem to be quite a huge drain on bandwidth. I would imagine it causes, at least, temporary bouts of lag. I'll look into it sooner or later, but seeing as the client is open source and everything, someone else could do it for me if you want it done sooner. ;) (Mind you, looking back at the code for sending objdelta ACKs, it is very weird and I don't know what I was doing. I must have written it in separate sessions without thinking of what was there previously or something. Just don't be deluded there's some real thought behind the weirdness.)

[Wolfang]

all sounds very...fixable....

[RPGenie]

I have to say after a few hours of playing, that the lack of lag spikes makes this game infinitely more enjoyable and has me playing this game again. Looking forward to a very fun weekend of neeting this game up.

Top shelf and thanks to you devs for your continued effort on this game.

[Slizyboy]

...(probably a Fibonacci heap)...

Unless you're really looking to eke every last ounce of constant factors from your algorithm, a run-of-the-mill min-heap would probably be just fine, and a heck of a lot easier to implement in C. Friend of mine tried implementing a Fib heap a while back, gave up a week in.

It turns out the client is pretty bad, sometimes, at keeping objdelta ACKs to as few packets as possible...

Which files would this be in? My eyes gloss over at the sight of all of these file names and I can't pick out which one to look into for this.

[kaka]

Which files would this be in? My eyes gloss over at the sight of all of these file names and I can't pick out which one to look into for this.

haven.Session would be the starting point, I guess, but if there are more files involved than that, Loftar's gonna have to point them out.

[loftar]

Oh, right. :)

Kaka is right; the objdelta protocol is implemented entirely in the haven.Session class.