2 Attachment(s)
[VB6] "HashTub" - a collection class
We have a very versatile Collection class built into VB6 and we also have Scripting.Dictionary. Most of the time one or the other of these is all we need. But sometimes we have a special need for larger scale collections.
Scripting.Dictionary works well (if used carefully) up to 100K items or so. But beyond that point performance begins to degrade exponentially.
HashTub
A simple hash table where Keys are String and Item values are Variants.
A memory hog meant for very large tables (approx. one million or more entries, max about 18 million but less for Variant String items, Variant array items, etc.). Long key strings can also limit the maximum count. Most programs will do better using a Collection or a Scripting.Dictionary unless they need a huge table.
If you don't need Variants you can adjust to specific types (Long, String, some Class, etc.) and save on memory.
Assigning to an existing Item updates the Item's value. Item access is by key or index, indexes are base-1 like a Collection. A new item must be added by key.
No "insert" or "remove" operations.
Assign the Chunk property first. This should be 1/20 to 1/2 of the expected population. Larger is more wasteful, smaller is slower.
A better String hash might improve performance. Keys are case-sensitive and Unicode-aware. The current hash can accept ANSI Strings as well as normal Unicode Strings as keys.
HashTub is a fairly small class, 100% VB6 aside from one API call used for hashing.
Sample Run
Requirements
Windows 2000, or earlier 32-bit Windows versions (including Win9x) with IE 5.0 or later installed. That is for the HashData() API call. If you substitute another hash it should work wherever VB6 runs.
Methods and Properties
Add NewItem, NewKey
Chunk [R/W]
Count [RO]
Exists(Key) [RO]
Key(Index) [RO]
Item(Index or Key) [R/W, write adds when Key is new]
Trim
Tweaks
Memory consumption can be reduced by changing the Item type from Variant to a specific type (String, Long, Currency, etc.).
You could also define a UDT in a static .BAS module and then you could use that as your Item type.
You can improve performance by dropping features. One is to drop access by Index. Then you will no longer need or have to update the NodeIndexes array. At that point the "Key" parameter can be passed ByRef and this speeds things up too.
You can also drop Object support even if you stay with Variant Items. That can simplify the code a little but gains little or nothing in performance. The capability isn't worth using though because creating a million or more Objects isn't a viable strategy.
Re: [VB6] "HashTub" - a collection class
The times are elapsed times. Your times will vary based on your hardware and how busy your system is.
Re: [VB6] "HashTub" - a collection class
It is pretty good.
The result for 1 million items adding is 2.94 sec on VBIDE, 1.69 sec for exe.
MakeKey takes time. I just use "k" & I as a key On my testing.
Please add delete and insert functions if possible.
Using C#'s Dictionary, the one million items adding takes 0.96 sec.
Quote:
/* Add one million items using Dictionary
Time Elapsed: 957ms
CPU Cycles: 2,127,340,168
Gen 0: 15
Gen 1: 8
Gen 2: 4
*/
/* Add one million items using SortedDictionary
Time Elapsed: 10,388ms
CPU Cycles: 23,924,587,466
Gen 0: 20
Gen 1: 10
Gen 2: 3
*/
Code:
Dictionary<string, int> dict = new Dictionary<string, int>();
CodeTimer.Time("Add one million items using Dictionary", 1, () =>
{
for (var repeat = 0; repeat < 1000000; repeat++)
{
dict.Add("k" + repeat, repeat);
}
});
2 Attachment(s)
Re: [VB6] "HashTub" - a collection class
While MakeKey() is slow, it was used for a good reason. The idea was to try to test a broad range of keys, in particular fairly widely varying length. The cost hardly matters since the same approach is used for both test cases.
It should be obvious that in a real program you wouldn't do that sort of thing. Your alternative fails to help test the quality or effectiveness of the hash function.
As for the straw man you propped up... well do you have any idea how .Net generics work? In particular the generics predefined in the massive .Net runtime?
Many commonly used .Net runtime Generics select among a large number of precompiled tightly written tailored C++ classes hacked for .Net compatibility. The numerous System.Collections.Generic.Dictionary classes are an example of this very thing.
So if you want to draw comparisons at least try to compare apples to apples. Here's a version more appropriate for comparing with your C# choice. It also uses your dumbed down keys. Why not just use a String made from the number though? That "k" prefix adds nothing of value here.
I think this tailored version compares pretty favorably, all things considered.
If you want additional functionality you can go ahead and add it. Getting what you are asking for and retaining good performance will probably require a less simplistic approach though. If you can do it then great, I'm sure others will be waiting to see the result of your efforts.
