25 Feb, 2012, Satharien wrote in the 1st comment:
Votes: 0
I'm using lists to store pretty much everything non-variable(rooms, areas, etc), and it works flawlessly except for one thing. If the size gets too large for any individual list, it starts to slow down when adding elements to the list. It starts at around 200 with slight noticable lag(0.2-0.3sec), but when you get up to around 1000 and you try adding to the list it becomes … quite bad. (Note: I am talking about adding a single element to the list after x point, not loading all elements of the list up to x amount. For example: Loading element 201 into a 200 list, not loading 201 elements into the list)

I've tried both push_front and push_back, both seem to be the same amount of lag. (I would have assumed push_back would be virtually no lag since I 'think' it doesn't have to cycle through all the others and 'adjust' them, since you're just tacking something onto the end of it so you'd only have to modify the last element and the element being added)

What helps, but doesn't make it better is when mass loading: use 2 lists, the real one and a fake one that you dispose of when done. You load everything into the fake one first, and when it reaches a magic number(I settled on 60), it merges it into the real table and starts over. This sped it up certainly, but it felt sloppy. And it doesn't help when adding just one element, that lag is still there.

So I was just wondering if anyone else even uses lists, and if you do how do you solve this issue? atm i'm having to split world maps up into smaller world maps that link to each other, and it works… but I would have preferred a world map be a single world map area and not several world map areas strung together.

Thanks for your time and any advice/etc.
25 Feb, 2012, Kaz wrote in the 2nd comment:
Votes: 0
std::list<> has constant-time insertion to any point. That's not your problem.
25 Feb, 2012, Lyanic wrote in the 3rd comment:
Votes: 0
As Kaz said, the std::list isn't your problem. I use std:: lists, maps, vectors, etc all the time, inserting and removing thousands of elements with no latency issues. I'd wager you've either got some sort of programming inefficiency at work or a really obscure server/compiler/library problem. If you post the code, someone might be able to offer more assistance.
26 Feb, 2012, Kline wrote in the 4th comment:
Votes: 0
Just chiming in a third vote that "std::list" is not your problem. I use many lists in my game also and have never experienced a delay in pushing data into any of them.
26 Feb, 2012, Runter wrote in the 5th comment:
Votes: 0
How many resources do you have on the machine for this software? What's the hardware configuration? You need to eliminate incidental factors before you can conclude there's a problem with something in the standard template library. (read: it's not the STL and it's probably an incidental factor you aren't considering) Either way, as others have said, you shouldn't be having a problem like this. 200-300 ms for that is terrible.
26 Feb, 2012, Satharien wrote in the 6th comment:
Votes: 0
Lyanic said:
I'd wager you've either got some sort of programming inefficiency at work or a really obscure server/compiler/library problem. If you post the code, someone might be able to offer more assistance.


Basically:
void testRoomLimit(Area *a, int count)
{
for(int i = 0; i < count; i++)
{
Room *nR = new Room;
a->_rooms.push_back(nR);
}
}


..That is the code i'm testing. It's not identical, as I don't have it open atm. But it is essentially create the new room and push it onto the list. The constructor for room assigns some default values such as room name(Default room name) and desc(Default room desc). But other than that, nothing else is going on. Also, the _rooms is "std::list<Room *> _rooms;"

As for Runter, i'm not much of a server admin so i'm not 100% sure what you mean by resources and hardware config. I just have an old windows computer(Windows XP) that I stripped down and run the game on. I use Dev-CPP V4.9.9.2 to compile my code. (Edit for more info: Windows XP service pack 2. Pentium 4 CPU 3.20GHz and 2GB of ram)

Maybe i'm doing something wrong, I don't know. Maybe that code will scream 'omg that idiot is doing it all wrong' to someone, and if it does please enlighten me on how to properly use lists. They work fine, flawlessly, zero lag, when they're relatively small(100-200). But it lags when you start adding rooms when the list is over 500. Especially nearing 1000. Adding a single room is done the exact same way, minus the loop, and it still lags.
26 Feb, 2012, Runter wrote in the 7th comment:
Votes: 0
That hardware should be more than sufficient.

It may be just the process of creating a new room that's causing the problem. You should look into profiling your code so you know exactly where the lag is originating from. The code you posted isn't enough to determine it's actually the push_back call doing it. It may be initializing the room, or memory from creating new rooms after a certain point. Dunno.
29 Feb, 2012, David Haley wrote in the 8th comment:
Votes: 0
And you're sure that it's actually a list and not a vector, right? Vectors don't grow the same way as lists do.

In any case, I agree with Runter… the room allocation is far more likely to be your problem than the container.

Try doing just this:

a->_rooms.push_back(NULL)

that will isolate the actual insertion and let you know quickly where you need to focus your efforts (profiling can be kind of a PITA and I prefer to avoid it when I can get my answer with other methods).
01 Mar, 2012, drifton wrote in the 9th comment:
Votes: 0
i've never had an issue like that with std::list and we all would of heard something about that by now the how often its used. i've stored several thousand rooms in a list before just for a random map i generated as a test just to see how long it would take to pass event messages to each room, the only time i've had anything like what you are describing happen to me was when i wasn't handling my memory correctly and my computer started caching to disk what all are you running on your computer? 2gb of ram isn't all that much anymore?
01 Mar, 2012, David Haley wrote in the 10th comment:
Votes: 0
I think it's pretty clear that the list is not the culprit here and something else is happening. I'm pretty sure that 2gb of RAM is more than enough to handle this, unless something very strange is happening. :wink:
02 Mar, 2012, Runter wrote in the 11th comment:
Votes: 0
Yeah, 2 GB of ram still is a lot for a mud. Even muds using technology like ruby and python need a multitude less ram than that.
03 Mar, 2012, David Haley wrote in the 12th comment:
Votes: 0
Satharien, did you look into the things that were suggested? It would be nice to have a resolution posted to the thread.
03 Mar, 2012, Satharien wrote in the 13th comment:
Votes: 0
Here's what i've found after doing some testing:

Room *nR = new Room

-The above takes 0.000135 seconds to execute.

a->_rooms.push_back(nR)

-The above takes 0.000001 seconds to execute.

While cycling through lists of rooms(such as to find the next room ID when creating a new room) is where the slow down occurs. And it only seems to be if I put an if statement in the loop. The loop itself if I don't do anything in the loop executes in the 0.0000xx range, but soon as I add an if statement it jumps up quite high in execution time. I'll link the syntax i'm using below, maybe i'm doing something wrong I dunno. If you see something that's obviously slower or wrong, please let me know. I'm still fiddling around with it to figure out exactly what's causing the issue.

list<Room *>::iterator r;

for(r = (*a)->_rooms.begin(); r != (*a)->_rooms.end(); r++)
{
if(whatever)
//Random code
}
04 Mar, 2012, Kline wrote in the 14th comment:
Votes: 0
Can't say a see any problems there myself; looks like something I'd write actually. What are you trying to do within the if statements? Is the slowdown the same/as bad for a simple one-liner, like a log echo?
04 Mar, 2012, Tyche wrote in the 15th comment:
Votes: 0
Satharien said:
list<Room *>::iterator r;

for(r = (*a)->_rooms.begin(); r != (*a)->_rooms.end(); r++)
{
if(whatever)
//Random code
}


"whatever" or, more likely, "Random code" is definitely the problem, rather than anything you shared.

OTOH this looks suspicious.
Satharien said:
While cycling through lists of rooms(such as to find the next room ID when creating a new room) is where the slow down occurs.


If one were to search the "room list" for the next room ID when constructing a new Room, you'd reduce your performance to O(N) rather than O(1).

Consider storing the last room id as a class variable in Room, and simply update when you create a room.

class Room {
private:
static int top_room_id;
int room_id;
public:
static void get_a_room_id() {
return ++top_room_id;
}
Room() {
room_id = get_a_room_id();
}
};

int Room::top_room_id = 0;
0.0/15