|
Hello everyone,
I have a very simple data structure representing a book, including ID/title/author/price, no more big field, all are strings. My application provides simple interface to query book information by book ID.
1.
And I want to store book information into Dictionary, book ID as key and other data as value. My question is are there any best practices about the size of a Dictionary should be? The total data is very big (a couple of G bytes monitored from physical serialized file), and I am not sure whether I should divide the data into several Dictionary or just use one?
2.
Does Dictionary use page file to swap storage (e.g. Dictionary could be able to store more information than physical memory limitation of current computer if it could use swap page file) or just use pure memory?
thanks in advance,
George
|
|
|
|
|
Hi George,
I haven't used any memory-based data structure larger than my system's physical
memory, and I don't plan to do so any time soon: the data structure would be
loaded into (virtual) memory and immediately swapped out to the page file on
disk again, yielding bad system performance.
Whenever you need large amounts of data, and certainly if you are using
only small parts of it at a time, use a database. SQLServer Express is freely
available, and SQL queries can be organized in all popular .NET languages.
BTW: A dictionary is no different from any other data structure as far as memory
behavior goes; data structures don't decide themselves on whether they get
swapped out. It is the memory manager that decides on these mathers,
irrespective of the structures or classes involved.
|
|
|
|
|
Hi Luc,
To tell the truth, my SQL is very bad and I just want to skip to learn it.
So, your point is Dictionary could use page swap file and could contain more data than physical memory?
regards,
George
|
|
|
|
|
Hi George,
George_George wrote: Dictionary could use page swap file and could contain more data than physical memory?
technically yes (and so could a byte array, or anything else).
and practically no, you will probably not be satisfied by the performance
of your app.
|
|
|
|
|
Thanks Luc,
You mean even if page file enables us to use larger memory than physical memory limitation, the access is slow?
regards,
George
|
|
|
|
|
Hi George,
I assume your data is on disk somehow. So populating a data structure
(Dictionary or anything else) first will read the data from disk; since
this overflows the physical memory, it will spill over to the page file(s),
so performance will resemble a huge file copy before anything useful will
be possible.
If you could skip the "load all data first" step, you would not incur
this penalty. The easiest way to do this, is by using a database.
The database code is smart enough to cache data, and uses available
memory in an optimal way.
Also, when the application is very simple (so you could do without
a database), then the required SQL will also be very simple. Maybe
you just need a single table, and a single SELECT line, as in
SELECT * FROM books where books.ISBN = '1234-5678-1234'
|
|
|
|
|
Keep in mind that a database will use SEVERAL TIMES as much memory as your raw data, due to overhead (indexing etc...). A hash table will give faster retrievals and allow you to store more data in memory.
|
|
|
|
|
Thanks Alan!
Any ideas to my question below?
--------------------
And I want to store book information into Dictionary, book ID as key and other data as value. My question is are there any best practices about the size of a Dictionary should be? The total data is very big (a couple of G bytes monitored from physical serialized file), and I am not sure whether I should divide the data into several Dictionary or just use one?
--------------------
regards,
George
|
|
|
|
|
Thanks Luc,
I am considering using SQL solution seriously. And I am also interested to do benchmark.
One more question, in my scenario is it better store all data inside one Dictionary instance or split into a couple Dictionary instances (e.g. Dictionary instance to store book name starts with letter A, instance with letter B, etc.)? Any best practices about the size of Dictionary which should not exceeds?
regards,
George
|
|
|
|
|
Hi George,
splitting a homogeneous set of data items over multiple collections
(as in 26 collections, one for each initial letter value)
will typically not help you at all:
- it will require more code,
- it will not result in more compact data,
- the only thing it would achieve is a better "locality of data" which at
best is a second-order effect, and as far as I can see is irrelevant here.
So I suggest you go for a database with one huge table, or if you don't
want a DB, a single huge Dictionary. I personnally would go with SQLServer
Express as I said before. As others have said, a DB is performance-optimized;
furthermore the application seems very simple, so any DB could do, hence
pick a popular and cheap one: SQLServer Express, unless your needs exceeds
one of its limitations: 8GB of data (not sure), and maybe a limited number
of concurrent users (not sure at all).
|
|
|
|
|
George_George wrote: To tell the truth, my SQL is very bad and I just want to skip to learn it.
Use db4o[^]
|
|
|
|
|
Hi Giorgi,
I read the introcution for db4o and it is just a database, I think SQL Server should be more superior than it. Why do you think db4o is more suitable for my solution?
regards,
George
|
|
|
|
|
|
Thanks Giorgi,
I understand basic ADO.Net, Store Procedure and T-SQL. I just do not know advanced SQL materials.
My question is, for just query in my scenario, for using object database compared with using relational database like SQL Server, which one is better? Why?
regards,
George
|
|
|
|
|
Well, I am not 100% sure. As I said when using object databases you don't need to map rows to classes but I am not sure about performance. Perhaps it depends on implementation of the object database. On the other hand, if you need to build system with many users accessing the same data I believe Sql server will handle it better though I haven't tested it myself.
Here is some comparison: http://en.wikipedia.org/wiki/ODBMS#Advantages_and_disadvantages[^]
|
|
|
|
|
Thanks Giorgi,
I will read it carefully. How do you think of using Dictionary v.s. using database in my scenario?
regards,
George
|
|
|
|
|
If the data is small you can use dictionary. In case of large amount of data I would use database. If you don't want each user to install sql server you can use 'portable databases' such as sql compact edition or sqlite.
|
|
|
|
|
George_George wrote: So, your point is Dictionary could use page swap file and could contain more data than physical memory?
Yes. Kind of like you can ask more questions than you are mentally capable of understanding.
If you have so much data that you are worried about performance, better leave performance up to the experts. You should use a database and let the Database, OS and Hardware developers expertise handle the performance issues. There is absolutely no way in the universe that you are going to out perform them.
led mike
|
|
|
|
|
I am totally confused, what is your proposed technical solution?
regards,
George
|
|
|
|
|
George_George wrote: I am totally confused,
Yeah, there's a shocker.
George_George wrote: what is your proposed technical solution?
Still having trouble with the Reading thing eh? 
led mike wrote: You should use a database
led mike
|
|
|
|
|
A Dictionary in C# is implemented as a hash table. There's a tradeoff between time and space here. If you use a bigger hash table, your lookups will run faster (until you exceed physical memory).
Anything you can do to reduce the amount of memory used will improve performance. For example:
1. Store all prices in a table. In your book data structure represent the price as an index into that table. (If there are no more than 65K prices, this can be a short int.) Since many different books have the same price, this will save space.
2. For the author and title, you can use Huffman coding, which will save over 50% of the space used. Huffman coding can be used to compress ASCII text so that the most common letters are represented with one or two bits, giving an average of less than one byte per letter. Since strings in .NET are Unicode, this will save you more than 50%.
3. As a simpler alternative to Huffman coding, you can use Unicode but with the UTF-8 encoding, which will be a single byte for ASCII letters, saving you 50% over UTF-16 and other encodings.
As your hash-table size gets smaller, you get more collisions (multiple keys mapped to the same slot), which slow down retrieval. The Poisson Distribution allows you to calculate the expected number of collisions, given your hash-table size and number of records. (Assuming a random hashing function.)
|
|
|
|
|
Thanks Alan,
I feel confused when reading your reply.
1.
Seems you mean we should make hash table large enough with more keys and with less collisions in order to improve performance? But why you say "In your book data structure represent the price as an index into that table. (If there are no more than 65K prices, this can be a short int.) Since many different books have the same price, this will save space." -- my confusion is using price as key will cause books have the same price using the same key, which will cause more collisions which will degrade performance, your suggestion of using price as key conflicting with your point of reduce collision. Any comments?
2.
In my scenario, how could I control the size of the Dictionary (Hashtable), size do you mean the memory foorprint of the whole Dictionary instance or the # of keys of the Dictionary instance?
regards,
George
|
|
|
|
|
1. I suggested using an integer index as the key; not the price. If there are less than 65K prices (a virtual certainty), the integer index will be only two bytes, which is shorter than a typical price.
2. The integer indexes a table of prices (which could be a simple array of strings). This is not a hash table, so collisions are irrelevant here. You just look up the price string from the index.
3. The Dictionary size is set by the constructor (http://msdn.microsoft.com/en-us/library/tk84bxf4.aspx[^]), which will determine the memory footprint of the whole Dictionary. If you make it too small, .NET will attempt to reallocate a larger storage block and copy all your data when you exceed its storage capacity.
|
|
|
|
|
Thanks Alan,
1.
Could I simply understand your optimization rule to be,
- keep less confliction;
- while at the same time try to reduce memory footprint?
Does it correct understanding?
2.
In my scenario, I should set the capacity parameter of constructor of Dictionary as much as possible?
regards,
George
|
|
|
|
|
Yes. Since everything is in memory, some collisions are ok. You should probably experiment with different capacities to see which gives the best performance.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
