Implementation: identical PC names?
Goto page Previous  1, 2, 3, 4  Next
 
Post new topic   Reply to topic    mudlab.org Forum Index -> Coding
View previous topic :: View next topic  
Author Message
Lindahl



Joined: 29 May 2005
Posts: 56

PostPosted: Fri Jun 03, 2005 4:51 pm    Post subject: Reply with quote

Quote:
I think it's obvious one ought to be optimizing for lookup failure, not success. Which optimizes for lookup failure better, an STL map or an LRU link list? Something else?


The obvious answer is keeping the nickname list as small as tolerable - which is really just making the list large enough for the player to name his friends and enemies (the social circle). Generally, humans really have a limited number of people in their social circle, so a small number (32 to 64) of nicknames is pretty reasonable.

Yes, generally, in busy scenarios, you want to optimize for failure. However, optimizing for success is a good thing too. A player will likely be interacting with things he knows by name.

You can actually optimize a lot more for failure by having boundaries, by having upper and lower bounds of the set of nicknames - this is independent of list structure, of course. Since nicknames AND IDs will typically have the same lifetime, the boundaries will generally be small if you don't have too large of a nickname list. If you provide more nickname slots than a player will generally use, your players will generally name almost everything, greatly increasing the chances that the IDs will be spread far apart (since obsolete nicknames will persist due to overabundance of space) - just some musings.
Back to top
View user's profile Send private message
Author Message
Traithe



Joined: 13 May 2005
Posts: 50

PostPosted: Fri Jun 03, 2005 11:10 pm    Post subject: Reply with quote

All right... I'm about to ask what probably amounts to a stupid question grounded in a lack of appreciation for the constraints of data access times, but - is storing all this information and retrieving it as needed in a database rather than in memory out of the question?
Back to top
View user's profile Send private message Visit poster's website
Author Message
Lindahl



Joined: 29 May 2005
Posts: 56

PostPosted: Fri Jun 03, 2005 11:53 pm    Post subject: Reply with quote

Traithe wrote:
All right... I'm about to ask what probably amounts to a stupid question grounded in a lack of appreciation for the constraints of data access times, but - is storing all this information and retrieving it as needed in a database rather than in memory out of the question?


It depends if you're caching it or not. If you just fetch the data from the database every time you need it then you're gonna run into problems. The entire nickname table should probably stay in memory as long as you don't allow too many nicknames. You'll also want to consider disk synchronization times if you start allowing large numbers of nicknames.
Back to top
View user's profile Send private message
Author Message
eiz



Joined: 11 May 2005
Posts: 152
Location: Florida

PostPosted: Fri Jun 03, 2005 11:58 pm    Post subject: Reply with quote

Traithe wrote:

All right... I'm about to ask what probably amounts to a stupid question grounded in a lack of appreciation for the constraints of data access times, but - is storing all this information and retrieving it as needed in a database rather than in memory out of the question?


Well... Brian's performance doomsaying can usually be ignored, but going all the way to PostgreSQL every time is going to hurt you very badly. So yes, I would avoid that. Although it would be pretty easy to add a row-level cache to the Aetas DB interface, this is not currently present and we typically load all of an object's data into memory at once.


Last edited by eiz on Sat Jun 04, 2005 12:00 am; edited 1 time in total
Back to top
View user's profile Send private message Visit poster's website
Author Message
Traithe



Joined: 13 May 2005
Posts: 50

PostPosted: Sat Jun 04, 2005 12:00 am    Post subject: Reply with quote

Hmm.

I still cringe a bit at the thought of an always-loaded in-memory table containing all this information, though - sort of like always-loaded helpfiles, pfiles (no joke - I've seen a major top 10 MU* using this model - holy crap), etc.

What about storing all the information in pgsql, and then loading/unloading the character's nametable as the player itself is loaded/unloaded?

Would also relieve any sync issues, since you'd just update the copy of the table that's currently in memory and then write the whole thing to the database when the player is unloaded.
Back to top
View user's profile Send private message Visit poster's website
Author Message
eiz



Joined: 11 May 2005
Posts: 152
Location: Florida

PostPosted: Sat Jun 04, 2005 12:01 am    Post subject: Reply with quote

Traithe wrote:
What about storing all the information in pgsql, and then loading/unloading the character's nametable as the player itself is loaded/unloaded?


Yes, this is how it would be done.

Traithe wrote:
Would also relieve any sync issues, since you'd just update the copy of the table that's currently in memory and then write the whole thing to the database when the player is unloaded.


That's not how Aetas works. It would be saved when the rest of the object is synced to the DB, whenever that happens.

BTW:

Traithe wrote:
pfiles (no joke - I've seen a major top 10 MU* using this model - holy crap), etc.


I'm the sort of person who would do this. RAM is (relatively) cheap, and MUD datasets are rarely all that large. Of course, it would have to be demand-loaded (unless you wanted minute-long startups), but still...
Back to top
View user's profile Send private message Visit poster's website
Author Message
Traithe



Joined: 13 May 2005
Posts: 50

PostPosted: Sat Jun 04, 2005 12:04 am    Post subject: Reply with quote

Right, okay. If we're talking about only temporary memory residence then why the big worry about the size of each individual nickname entry?

I'd imagine each would need two ints - one id for the nicknamed object, one id for the nickname-rememberer - probably a char[255] for the nickname, and possibly another char[255] in the case of nicknamed players for their original short desc - so even if the IDs match up, if the player's desc changes (temporarily or otherwise) from when they were originally remembered the nickname entry won't kick in to mask their desc.

Even including all that per table entry doesn't seem like it would create massive swaths of wasted memory, particularly since there'd only be a small percentage of them loaded into memory at one time - right?
Back to top
View user's profile Send private message Visit poster's website
Author Message
Traithe



Joined: 13 May 2005
Posts: 50

PostPosted: Sat Jun 04, 2005 12:05 am    Post subject: Reply with quote

eiz wrote:
I'm the sort of person who would do this. RAM is (relatively) cheap, and MUD datasets are rarely all that large. Of course, it would have to be demand-loaded (unless you wanted minute-long startups), but still...


Are you serious???

Even at a relatively small production MU* like SoI we've still probably got on the order of 8 to 10k pfiles after only a few years of being open.

This other particular MUD must have a database that's dozens of orders of magnitude larger than that.

That is a lot of memory.

Edit: After re-reading your post, I thought I should clarify: I'm talking load-all-pfiles-on-mud startup here, not load-on-demand. <g> That's why I was a little flabbergasted.
Back to top
View user's profile Send private message Visit poster's website
Author Message
eiz



Joined: 11 May 2005
Posts: 152
Location: Florida

PostPosted: Sat Jun 04, 2005 12:08 am    Post subject: Reply with quote

Traithe wrote:

Even at a relatively small production MU* like SoI we've still probably got on the order of 8 to 10k pfiles after only a few years of being open.


Yep. I'm serious. =) Okay, I wouldn't really do it, since it's so trivial to not do it. My definition of a lot of memory is 'too large to fit in a 32-bit address space'. As for load-on-startup, well, that's crazy talk.

Traithe wrote:

I'd imagine each would need two ints - one id for the nicknamed object, one id for the nickname-rememberer - probably a char[255] for the nickname, and possibly another char[255] in the case of nicknamed players for their original short desc - so even if the IDs match up, if the player's desc changes (temporarily or otherwise) from when they were originally remembered the nickname entry won't kick in to mask their desc.


Using fixed length strings like that would be silly. Honestly, this is such a total non-issue, I'm kind of annoyed that Brian had to go and bring it up and get you worried. Wink std::map<object_id, std::string> is all it takes. As for invalidating nicknames, probably yes.

Traithe wrote:

Even including all that per table entry doesn't seem like it would create massive swaths of wasted memory, particularly since there'd only be a small percentage of them loaded into memory at one time - right?


If you used your insanely large layout, it could be a problem if you had several hundred concurrent users each with hundred(s) of nicknames. Fortunately, I know you're not going to do such a silly, wasteful thing.
Back to top
View user's profile Send private message Visit poster's website
Author Message
Tyche



Joined: 13 May 2005
Posts: 176
Location: Ohio, USA

PostPosted: Sat Jun 04, 2005 1:43 am    Post subject: Reply with quote

Lindahl wrote:
Quote:
I think it's obvious one ought to be optimizing for lookup failure, not success. Which optimizes for lookup failure better, an STL map or an LRU link list? Something else?


The obvious answer is keeping the nickname list as small as tolerable - which is really just making the list large enough for the player to name his friends and enemies (the social circle). Generally, humans really have a limited number of people in their social circle, so a small number (32 to 64) of nicknames is pretty reasonable.


Answer: The STL map search miss performs at O(ln N) and the LRU linklist search miss performs at O(N). The ratio of search misses to hits will be overwhelmingly in favor of misses. Problem is you've just wasted your time (hypothetically of course) optimizing in the wrong direction.

BTW, just what are the requirements?


Last edited by Tyche on Sat Jun 04, 2005 1:49 am; edited 1 time in total
Back to top
View user's profile Send private message Visit poster's website
Author Message
Lindahl



Joined: 29 May 2005
Posts: 56

PostPosted: Sat Jun 04, 2005 1:47 am    Post subject: Reply with quote

Tyche wrote:
Lindahl wrote:
Quote:
I think it's obvious one ought to be optimizing for lookup failure, not success. Which optimizes for lookup failure better, an STL map or an LRU link list? Something else?


The obvious answer is keeping the nickname list as small as tolerable - which is really just making the list large enough for the player to name his friends and enemies (the social circle). Generally, humans really have a limited number of people in their social circle, so a small number (32 to 64) of nicknames is pretty reasonable.


Answer: The STL map search miss performs at O(ln N) and the LRU linklist search miss performs at O(N). The ratio of search misses to hits will be overwhelmingly in favor of misses. Problem is you've just wasted your time (hypothetically of course) optimizing in the wrong direction.


But now you need two data structures, bloating the size. You've now got 16 bytes of pointer data for 16 bytes of real data - assuming an average of 12-bytes for a nickname.

EDIT: I guess I let my ego get in the way of my brain.. lol. If you assume a maximum of 255 names, you really only need 4 bytes, assuming 1 byte for each pointer. But you still lose out on the ability to report to the player which name is most likely obsolete.
Back to top
View user's profile Send private message
Author Message
eiz



Joined: 11 May 2005
Posts: 152
Location: Florida

PostPosted: Sat Jun 04, 2005 1:57 am    Post subject: Reply with quote

Lindahl wrote:

But now you need two data structures, bloating the size.


Not really. Lookups from nickname -> ID are significantly more rare than the other direction - users only type so fast. A linear scan should work fine.

BTW, something kind of related that I saw on Lambda the Ultimate the other day is Judy. Now that is an obscenely complicated data structure.
Back to top
View user's profile Send private message Visit poster's website
Author Message
Lindahl



Joined: 29 May 2005
Posts: 56

PostPosted: Sat Jun 04, 2005 2:05 am    Post subject: Reply with quote

Quote:
BTW, something kind of related that I saw on Lambda the Ultimate the other day is Judy. Now that is an obscenely complicated data structure.


Reminds me of monolithic systems - the do-all data strcuture Rolling Eyes. You should see the globally shared multibuffer class I've written for out-buffers. I guess it isn't that bad, but it's pretty cool, I must say. But now we're getting way off topic, so I'm done here.

Thanks for the link by the way, provides some good reading.
Back to top
View user's profile Send private message
Author Message
Tyche



Joined: 13 May 2005
Posts: 176
Location: Ohio, USA

PostPosted: Sat Jun 04, 2005 6:23 pm    Post subject: Reply with quote

eiz wrote:

BTW, something kind of related that I saw on Lambda the Ultimate the other day is Judy. Now that is an obscenely complicated data structure.


Interesting. The evolution of that appears to start with the ternary search trie. I posted an implementation here. Muir mentioned Teelf has one as well. Later I noted that an R-way trie would probably perform better (per Sedgewick), though I couldn't bring myself to code it. The Judy document calls them digital tries. What Judy appears to do is break down the byte barrier into bits and control the actual layout of exactly where and how nodes and leaves are allocated. No wonder it's complicated. Velly interesting though.
Back to top
View user's profile Send private message Visit poster's website
Author Message
Gromble



Joined: 08 Oct 2005
Posts: 23

PostPosted: Wed Oct 19, 2005 1:16 pm    Post subject: Reply with quote

Traithe wrote:

I still cringe a bit at the thought of an always-loaded in-memory table containing all this information, though - sort of like always-loaded helpfiles, pfiles (no joke - I've seen a major top 10 MU* using this model - holy crap), etc.


Memory is cheap and certainly faster than going off to persistent store, so I don't see much of an issue with caching a lot of data in memory. In the embedded (real-time) world, in-memory databases are quite common.

With respect to caching player files, yes you'd probably want to control that a bit since the numbers can get huge over the lifetime of a server. You could simply age out inactive accounts and archive their associated files after 30/60/90 days of inactivity.

-Gromble
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    mudlab.org Forum Index -> Coding All times are GMT
Goto page Previous  1, 2, 3, 4  Next
Page 3 of 4

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Powered by phpBB © 2001, 2002 phpBB Group
BBTech Template by © 2003-04 MDesign