Jump to content
  • Advertisement
Sign in to follow this  
Thevenin

Growth of a C# List

This topic is 4292 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm adding message logging to my MMORPG server. However, having each message get added to the database separately may be a bottleneck (dispite the fact that the database is locally accessible). My idea right now is to store all the messages in a list (C# List), and then have the list unload into the database when the server goes down for its daily server-save. However, if the computation speed growth of a C# List is O(n), this is probably a terrible idea, so before I go and implement it, I'm wondering if someone could tell me if C# does its lists as arrays, linked-lists, BSTs, etc. Also, does it matter if I type safety it? Does it make a difference if it's value or reference typing?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Thevenin
However, if the computation speed growth of a C# List is O(n), this is probably a terrible idea, so before I go and implement it, I'm wondering if someone could tell me if C# does its lists as arrays, linked-lists, BSTs, etc.

A List<T> is implemented internally with an array. The array is created with some initial size (there's a constructor overload to specify it, IIRC), and when the list is filled to capacity, a new array is created that's twice as big as the old one, and the contents of the old copied to the new one.

In practice, this performs very well.

Quote:

Also, does it matter if I type safety it?

In general, a type safe generic list is always preferrable to a non-generic one.

Quote:
Does it make a difference if it's value or reference typing?


I can't parse this.

Share this post


Link to post
Share on other sites
What good is a log if logged messages may not be available? What does your log tell you when the server crashes? And when do you need your log, if not when the server crashes? In other words, if you want a useful log, make sure that messages are persisted immediately.

Share this post


Link to post
Share on other sites
Quote:
Original post by Thevenin
I'm adding message logging to my MMORPG server. However, having each message get added to the database separately may be a bottleneck (dispite the fact that the database is locally accessible).

My idea right now is to store all the messages in a list (C# List), and then have the list unload into the database when the server goes down for its daily server-save.

However, if the computation speed growth of a C# List is O(n), this is probably a terrible idea, so before I go and implement it, I'm wondering if someone could tell me if C# does its lists as arrays, linked-lists, BSTs, etc.

Also, does it matter if I type safety it? Does it make a difference if it's value or reference typing?


since C# has bounds checking on all arrays the worst case scenario is probably O(n) (with jagged arrays).
the real issue however is memory footprints, you really want the array to fit into the cache if you intend to traverse it often enough to bother about it being O(n).

a LinkedList generally allows for faster operations (add/delete etc) but suffer from a much larger memory footprint which could result in far worse performance.

modern cpu:s are extremely fast but can loose around 80% of their performance simply by constantly needing data that isn't in the cache.

in what way is the log going to be used ?
if its viewable by admins and GMs only i would suggest throwing it into the DB as soon as the list reaches a predetermined size (since old data won't get accessed extremely often). your server should be multithreaded anyway and the DB server most definitly is so the game shouldn't freeze while you store data. by doing the storing when the list reaches a certain size you're able to control your cache and the query complexity.

if its viewable by players aswell (as a personal messagelog) i suggest you simply store a local copy at their computers (managed by the client) and simply discard it when they sign off. they can load a new size limited log from the server when they sign on. (last 100 messages for example)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Don't bother saving log messages to a database. Use a text file instead.

I suggest saving messages in a List and then saving them to the text file every so often. You could try different frequencies and see which interval works best. But I really wouldn't worry too much about something like this. The overhead involved in writing to a file is minimal compared the overhead of the MMORPG itself.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Don't bother saving log messages to a database. Use a text file instead.

I suggest saving messages in a List and then saving them to the text file every so often. You could try different frequencies and see which interval works best. But I really wouldn't worry too much about something like this. The overhead involved in writing to a file is minimal compared the overhead of the MMORPG itself.


it depends a bit on the nature of the log.

a system log used to find the cause of an unexpected crash for example should probably be sent to stderr by default.

the OS can then easily pipe it into a file if you want that.

chat message logs used to detect abusive players etc are better stored in a DB for easy access.

Share this post


Link to post
Share on other sites
Quote:
Original post by Arild Fines
A List<T> is implemented internally with an array. The array is created with some initial size (there's a constructor overload to specify it, IIRC), and when the list is filled to capacity, a new array is created that's twice as big as the old one, and the contents of the old copied to the new one.

In practice, this performs very well.


Performs very well, relative to what, not performing? This sounds absolutely terrible.

Quote:
Original post by Arild Fines
I can't parse this.


<int>, <short>, <byte> VS <Int32> <Short> <Byte>

Share this post


Link to post
Share on other sites
Quote:
Original post by Thevenin
Quote:
Original post by Arild Fines
I can't parse this.


<int>, <short>, <byte> VS <Int32> <Short> <Byte>


C# isn't java. As far as I know, int and Int32 are synonyms, as are short and Short, byte and Byte, ...

Share this post


Link to post
Share on other sites
Quote:
Original post by SamLowry
As far as I know, int and Int32 are synonyms, as are short and Short, byte and Byte, ...


Interesting, I never knew that. Regardless though, the point I'm trying to make should be apparent -- does it make a difference to a C# List's performance if the template is a reference type, or a value type?

Share this post


Link to post
Share on other sites
Quote:
Original post by Thevenin
Quote:
Original post by SamLowry
As far as I know, int and Int32 are synonyms, as are short and Short, byte and Byte, ...


Interesting, I never knew that. Regardless though, the point I'm trying to make should be apparent -- does it make a difference to a C# List's performance if the template is a reference type, or a value type?


There should be no real difference. The .NET runtime machinery will instantiate separate class implementations for generics when used with value types, and will have reference types share one implementation, meaning you won't have to worry about boxing/unboxing (something which java suffers from).

Of course, the typical performance difference between value types and reference types still apply, but that has nothing to do with generics.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!