|
Hello everyone,
I am migrating from C++ to C#. Two questions about memory footprint of Dictionary class object instance.
1.
If I call remove method to remove some elements from the Dictionary, will the memory footprint be reduced? (suppose there is no other reference to the removed item) I have some suspecision that Dictionary is not truly removing the element and just mark a flag or something, which still refer this removed item to block it from GCed.
2.
I have two ideas to reduce memory footprint of Dictionary, one is mentioned in (1), to remove some entries. The other is to create a new Dictionary instance, and insert only necessary items into the new Dictionary instance, and reference only the new Dictionary instance in the future.
Which way is better from memory footprint reduce perspective?
thanks in advance,
George
|
|
|
|
|
George_George wrote: If I call remove method to remove some elements from the Dictionary, will the memory footprint be reduced? (suppose there is no other reference to the removed item) I have some suspecision that Dictionary is not truly removing the element and just mark a flag or something, which still refer this removed item to block it from GCed.
When you remove an item from a dictionary, the key value pair is cleared, but kept. This means that if you store reference types in the dictionary, the reference will be removed. If you store value types in the dictionary, the value is cleared but kept, but that is rarely a problem as value types are small.
If you have made a large structure that you store in a dictionary, removing items would not reduce the memory footprint. But then your problem is that you have constructed a structure that breaks every recommendation, and that it works poorly is not because of a problem with the dictionary.
George_George wrote: The other is to create a new Dictionary instance, and insert only necessary items into the new Dictionary instance, and reference only the new Dictionary instance in the future.
That would only be beneficial if you have removed a huge number of items from the collection.
George_George wrote: Which way is better from memory footprint reduce perspective?
Do you think that you have an actual memory footprint problem?
Despite everything, the person most likely to be fooling you next is yourself.
|
|
|
|
|
Thanks Guffa,
1.
You always have comprehensive answers. I do not quite understand "the key value pair is cleared, but kept", kept for what? I think the word clear is conflicting to "kept".
2.
Could you provide more descriptions about why based on the above theory, reference types are cleared from memory, but value types are not?
3.
I think when insert value types into Dictionary, it will be value copied, right?
regards,
George
|
|
|
|
|
George_George wrote: I do not quite understand "the key value pair is cleared, but kept", kept for what? I think the word clear is conflicting to "kept".
The key value pairs are kept in an internal array. When you remove an item, the key value pair structure is kept in the array (i.e. the array is not replaced with a smaller array), but the key and value properties are assigned the default value of their respective type.
George_George wrote: Could you provide more descriptions about why based on the above theory, reference types are cleared from memory, but value types are not?
Because the reference types are stored outside the dictionary itself so that they can be garbage collected, while value types are stored in the key value pair structure in the internal array of the dictionary.
George_George wrote: I think when insert value types into Dictionary, it will be value copied, right?
Yes.
Despite everything, the person most likely to be fooling you next is yourself.
|
|
|
|
|
Thanks Guffa,
I like your description below,
1.
--------------------
The key value pairs are kept in an internal array. When you remove an item, the key value pair structure is kept in the array (i.e. the array is not replaced with a smaller array), but the key and value properties are assigned the default value of their respective type.
--------------------
My confusion is, if the item is removed, GCed, then its memory is reclaimed and saved. But a new instance of default value of the reference type is created? So, no space saved?
2.
Sounds like the way to reduce memory footprint to maximum is to create a new one and insert only necessary ones. Right?
regards,
George
|
|
|
|
|
George_George wrote: My confusion is, if the item is removed, GCed, then its memory is reclaimed and saved. But a new instance of default value of the reference type is created? So, no space saved?
The default value of a reference is null, so for reference types the reference to the instance is replaced with a null reference.
George_George wrote: Sounds like the way to reduce memory footprint to maximum is to create a new one and insert only necessary ones. Right?
Yes, but only if the dictionary actually has a memory footprint problem. The data that the dictionary needs to keep track of each item is typically 16 bytes. There has to be quite a lot of unused entries before there are so much memory to reclaim that it's worth it. If the dictionary doesn't have that many entries to get rid of, all you accomplish is more work for the garbage collector.
Despite everything, the person most likely to be fooling you next is yourself.
|
|
|
|
|
Thanks Guffa,
1.
Guffa wrote: The data that the dictionary needs to keep track of each item is typically 16 bytes.
4 bytes for key reference variable and 4 bytes for value reference variable on a 32-bit machine? And the total should be (8 + 8) 16 bytes for a 64-bit machine?
2.
Guffa wrote: There has to be quite a lot of unused entries before there are so much memory to reclaim that it's worth it.
Why "there are so much memory to reclaim that it's worth it"? Sorry my English is not very good. Could you say in some other words please?
3.
Guffa wrote: If the dictionary doesn't have that many entries to get rid of, all you accomplish is more work for the garbage collector.
Why "all you accomplish is more work for the garbage collector"? Could you say in some other words please?
regards,
George
|
|
|
|
|
George_George wrote: 4 bytes for key reference variable and 4 bytes for value reference variable on a 32-bit machine? And the total should be (8 + 8) 16 bytes for a 64-bit machine?
The structure that the dictionary uses internally to keep track of an item looks like this:
[StructLayout(LayoutKind.Sequential)]
private struct Entry {
public int hashCode;
public int next;
public TKey key;
public TValue value;
}
If the key and value are reference types, this adds up to 16 bytes on a 32-bit system.
George_George wrote: Why "there are so much memory to reclaim that it's worth it"?
The internal array of the dictionary doesn't grow every time you add an item, intead it's size is doubled every time it grows. This means that the dictionary would have to contain at least 50% unused items before you are sure to gain anything at all by moving the items to a new dictionary.
George_George wrote: Why "all you accomplish is more work for the garbage collector"?
Because you would just create a bunch of new objects and release a bunch of old objects, but the amount of memory used would still be the same.
Despite everything, the person most likely to be fooling you next is yourself.
|
|
|
|
|
Great Guffa!
1.
next field is used to keep a linked list for all the items which has the same hash code?
2.
So, each reference type variable will use 8 bytes on 32-bit machine, and 16 bytes on a 64-bit machine?
3.
"This means that the dictionary would have to contain at least 50% unused items" -- I am previously a C++ developer. Like vector, it only grows when its capability is the same as its size.
In C#, is it working the same way -- only grow when it is full? Or always keep at least 50% free? I am confused about why do you think a Dictionary is always keeping at least 50% unused items -- I do not agree, I think it should be Dictionary grows 50% each time when it is full? Any comments? Please feel free to correct me if I am wrong. 
4.
"but the amount of memory used would still be the same" -- I doubt it and I want to make some tests. For example, if in the old Dictionary, the capability is 10 but used item is only 3. If I create a new Dictionary, and insert the 3 elements into the new Dictionary, I am not sure whether the capability of the new Dictionary is still 10.
What APIs of Dictionary or scenario could be used to make a simple test? I want to make some tests under your ideas to learn more.
regards,
George
|
|
|
|
|
George_George wrote: next field is used to keep a linked list for all the items which has the same hash code?
I don't know, really. I haven't examined the internal code of the dictionary that closely.
George_George wrote: So, each reference type variable will use 8 bytes on 32-bit machine, and 16 bytes on a 64-bit machine?
No. On a 32-bit system a reference is 32 bits, which is 4 bytes.
George_George wrote: In C#, is it working the same way -- only grow when it is full?
Yes.
George_George wrote: I am confused about why do you think a Dictionary is always keeping at least 50% unused items
I never said that. Where did you get that from?
George_George wrote: For example, if in the old Dictionary, the capability is 10 but used item is only 3. If I create a new Dictionary, and insert the 3 elements into the new Dictionary, I am not sure whether the capability of the new Dictionary is still 10.
Then you have 70% unused entries, so the new dictionary is very likely to shrink. If you for example have 4 items in a dictionary with the capacity 7, and copy to a new dictionary, the capacity of the new dictionary would also be 7.
The capacity of a dictionary is always a prime number (for some not so obvious reason). When growing the internal array, it picks the closest higher prime number.
You can download Lutz Roeder's .NET Reflector to look at the code of the dictionary (you find it in the mscorlib dll).
If you want to check the capacity of a dictionary object, you have to use reflection to check the length of the private entries array.
Despite everything, the person most likely to be fooling you next is yourself.
|
|
|
|
|
Thanks Guffa,
1.
Guffa wrote: I never said that. Where did you get that from?
Sorry my English is not good. This is what you said before -- "This means that the dictionary would have to contain at least 50% unused items before you are sure to gain anything at all by moving the items to a new dictionary.".
Especially "contain at least 50% unused items", could you help to clarify please if I previously make a wrong understanding?
2.
--------------------
Then you have 70% unused entries, so the new dictionary is very likely to shrink. If you for example have 4 items in a dictionary with the capacity 7, and copy to a new dictionary, the capacity of the new dictionary would also be 7.
--------------------
I like your description above, clear.
What makes me confused is your below comments before. Especially why do you think "still be the same"? From your above sample, there is possibility that the new Dictionary could be smaller than the old one, right?
"Because you would just create a bunch of new objects and release a bunch of old objects, but the amount of memory used would still be the same"
regards,
George
|
|
|
|
|
George_George wrote: This is what you said before -- "This means that the dictionary would have to contain at least 50% unused items before you are sure to gain anything at all by moving the items to a new dictionary.".
If the dictionary have too few unused entries, you can not gain anything by moving the items to a new dictionary. It has to have something like 50% unused items, otherwise it's likely that the new dictionary will just get the same capacity as the current dictionary.
George_George wrote: From your above sample, there is possibility that the new Dictionary could be smaller than the old one, right?
Yes, there is a possibility. But you have to have removed a lot of items from the dictionary for it to be likely.
Despite everything, the person most likely to be fooling you next is yourself.
|
|
|
|
|
Thanks Guffa,
Guffa wrote: If the dictionary have too few unused entries, you can not gain anything by moving the items to a new dictionary. It has to have something like 50% unused items, otherwise it's likely that the new dictionary will just get the same capacity as the current dictionary.
How do you get the figure -- 50%? What is your calculation process? Or just a rough estimation based on your experiences?
regards,
George
|
|
|
|
|
The figure 50% might be bit conservative, it's based mostly on how other collections work. If you look at the relations between consecutive prime numbers, you will se that the figure may be a bit smaller, perhaps 10-20%. However, the relation between prime numbers varies quite a bit, the ones that I looked at varied between 2% and 66%.
Despite everything, the person most likely to be fooling you next is yourself.
|
|
|
|
|
Thanks Guffa,
I have got your idea.
When we remove an item from Dictionary, the slot is still there and referred to NULL.
My question is, whether the slot will be reused when we insert
1. any new key/value pair?
Or
2. only new key/value pair which has the same key value as the previously deleted item?
regards,
George
|
|
|
|
|
When you remove an item from a dictionary, the entry is placed in a bucket of unused entries. These entries are reused when adding any new items to the dictionary.
Despite everything, the person most likely to be fooling you next is yourself.
|
|
|
|
|
Thanks Guffa,
Good to learn it is always reusable for the deleted slots, no matter whether or not the original key value of the deleted item is the same as the key value of the new inserted item. 
regards,
George
|
|
|
|
|
1. I'm fairly sure that the capacity of the Dictionary will not be reduced when items are removed, but Dictionary doesn't have a Capacity property to check (unlike List).
Personally, I would not consider the memory used by items in the Dictionary as part of the Dictionary's footprint; after all, an instance of some class may be in several collections at once.
If the Dictionary holds the only reference to a particular instance and you remove that item, the instance will be garbage collected (at some point later).
2. With a List you can Remove entries and then set .Capacity to trim off the excess, not so with Dictionary. 
|
|
|
|
|
Great PIEBALDconsult!
For 1,
From your analysis, if I removed the item from Dictionary, the item will be GCed (if no other reference), right?
My confusion is why do you think the capacity of Dictionary will not be impacted after item removal?
For 2,
I am confused. How can you use .Capacity to restrict the size of the List? We can continue to insert and the List will continue to grow, right? Correct me if I do not understand your points correctly.
regards,
George
|
|
|
|
|
1) I think of Lists and Dictionaries as merely a dynamic bunch of slots, the number of slots is the capacity, more slots will be added as needed. Removing the contents of a slot doesn't remove the slot, something else may be put in that slot later.
Plus, each slot doesn't contain the actual contents, only a reference to the contents. (Even with value types.)
2) It doesn't restrict it, it can still grow afterward.
But if you use a List to collect a bunch of things, and then remove many of them from the List, trimming the excess may be a good idea if you aren't going to add a bunch more items.
|
|
|
|
|
Thanks PIEBALDconsult,
Great! You always have wonderful answers which brings me further insights.
1.
For Dictionay, when we call Remove, the slots will still be there. When we add elements later, will the slots be resued?
2.
For Dictionary, for the slots which is empty (pointing to NULL reference) because of removed elements, are they avaliable to be reused for any new inserted elements or the slots are binded to special key hash value (which special key element can reuse)?
3.
PIEBALDconsult wrote: trimming the excess may be a good idea
Do you mean trim the empty slots? Which API in List class perform slot trim function?
regards,
George
|
|
|
|
|
Hi all,
I'm new to the C# and .Net programming, but I've got experience in other programming languages such as C, C++ and Java.
I need access to webcam for capturing video and to process each frame in real time.
I've read several articles about it and seen how to access to the webcam with avicap32.dll but I'd like to know if there's a better way.
Thanks for your attention 
|
|
|
|
|
I would expect that DirectX is the way to go, only thing is, Managed DX is very lame. There are better wrappers for DX around on the web that expose more functionality. Ultimately, you're going to be p/invoking DX because C# itself isn't going to do this for you.
Christian Graus
Please read this if you don't understand the answer I've given you
"also I don't think "TranslateOneToTwoBillion OneHundredAndFortySevenMillion FourHundredAndEightyThreeThousand SixHundredAndFortySeven()" is a very good choice for a function name" - SpacixOne ( offering help to someone who really needed it ) ( spaces added for the benefit of people running at < 1280x1024 )
|
|
|
|
|
Hi Christian,
I've tried with directX already, in particular with namespaces Microsoft.DirectX and Microsoft.DirectX.DirectInput I've coded a simple method for enumerating the devices connected to the system but it doesn't show me the webcam.
On msdn I've seen that the directx are used for build games and managed devices are joystick, mouse and keyboard.
How can I do it ?
Thanks
|
|
|
|
|
DirectInput is used for things like keyboards, mice, joysticks, etc. You actually want DirectBlow DirectShow, and you have to build a filter, blah blah blah (you'll swear you're in hell when you start testing with other web cams). I hate DirectShow.
EDIT - a quick search on Google led me to this:
http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=1339&lngWId=10[^]
And there's even an article here on CP:
http://www.codeproject.com/KB/audio-video/cameraviewer.aspx[^]
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001
modified on Saturday, May 17, 2008 8:42 AM
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
