Replacing the vb collection object (Warning - this is a lot to read)
Like everyone else I think the VB Collection object is missing some features. I thought about using a Dictionary but I have read that deploying scrunn.dll can be problamatic. So, I set out on a quest to replace it with something else.
First I used an object called Hive (freevbcode.com):
Hive is a drop in replacement for the collection object. The source is in vb and is freelly available, but it wasn't very fast at all.
Next I found flexbag (http://www.spidereye.com/software/flexbag/) . The Flexbag object is pretty fast, and is a drop in replacement for the vb collection. It offers some nice extra feature, and is free to use. But inserting at the first item is incredibly slow and the source is not available because it's a compiled dll programmed in ATL and C++.
Then I found the HashTable and LinkedList classes(vb2themax.com):
There both pretty fast, free to use, the source is in VB6 and available. The linkedlist object is very fast but doen't use keys. The HashTable is fast but only allows inserting past the last item. There is another big problem with both of these classes, the Remove methods do not work correctlly at all. Fortunatley these things can be fixed.
Lastly I found the Indexed Object Collections (vbaccelerator.com):
Very fast but they use indexe number only, instead of keys. The code for this is in vb6, freelly available, and very advanced (it uses a typelib). Editing the source would not easy for noobie at all.
So, with these finding in hand I decided to make my own collection object that could replace the standard collection with as little fuss as possible and with as many features as possible. I took the linkedlist and hashtable concept and merged them. Now I have a double linked list with a hashtable of keys. I'm calling this object either KeyedLinkedList or HashList.
The HashList/KeyedLinkedList is:
Openly available with vb6 source and feature rich.
can handle DuplicateKeys
return a array of the keys in use
return an array of the values/objects stored in the list
can move to the first item, last item, next item, previous item, or foward/back by a given number.
Ignore case sensitive keys macthing.
determine wether or not it's at the BOL or EOL.
determine whether or not a key exists.
Allow you to set the size of the list. This speeds up the appending and insertion process.
Allow you to set the chunksize of the list. this determines how much the list grows by when it runs out of empty slot for appending/inserting.
automatically create 8, 10, 12, 32 character keys if none is supplied.
allows empty keys.
return an item by key or index.
return the next item to use the same key.
remove an item by key or index.
remove all items.
clear all items and set the list back to its default size. this helps reclaim memory... I think.
return a key by index number.
return a index number by key.
return its current position in the list.
insert items to the end of the list.
insert items before or after others item in the list
And my initial testing shows it to be faster than most of the collection objects mentioned above.
With all that said let me also state that it does not provide support for enumerating throught the list with the IUknown interface, beside that it's a drop in replacement for the vb collection object. It also has one dependency class called StringAppendar which is a very fast vb6 class object for concantanating strings. StringAppendar is only used to automatically create keys and can be replaced with a string varaible. I found string appendar on the web but can't remember where.
so try it out and tell me what you think. If there are no bugs in it than I'll post it in the codebank in a few days.
Microsoft
------------------------------------------------
622: VB Collection:Add
10212: VB Collection:Read (* this could be a lot faster if enumeration was used)
651: VB Collection:Remove
674: VB Collection:Insert
528: VB Collection:Clear
------------------------------------------------
272: Dictionary:Add
58: Dictionary:Read
9405: Dictionary:Remove
0: Dictionary:Insert N/A
0: Dictionary:Clear
VBAccelerator
------------------------------------------------
219: Standard Collection:Add
10229: Standard Collection:Read
10901: Standard Collection:Remove
223: Standard Collection:Insert
493: Standard Collection:Clear
------------------------------------------------
286: Optimised Index Collection:Add
26: Optimised Index Collection:Read
512: Optimised Index Collection:Remove
1679: Optimised Index Collection:Insert
499: Optimised Index Collection:Clear
CVMichael, Damn that's fast. Did you never finished implementing keys into your double linkedlist?
I think I'm going to fix the vb2themax linkedlist re-indexing issue next. Obviously a linkedlist performs much faster a hashtable, but I don't expect any speeds close to those c++ scores.
Here is the time taken to add 100,000 items to the KeyedLinkedList.
4286: KeyedLinkedList:Add
371: KeyedLinkedList:Read
51706: KeyedLinkedList:Remove
4293: KeyedLinkedList:Insert
49955: KeyedLinkedList:Clear
not very good is it. But I'm running this code on a Via C3 733 processor which is equivalent to a Intel PII 350.
Last edited by frigginjerk; Aug 12th, 2003 at 08:03 PM.
I've also made a class that uses Keys, but it's not very fast...
here are the results I got:
19448 Add...
120 Reding by Index...
7000 Reding by Key...
8172 Reding by Key (Random)...
170 Reding by Key Index...
1813 Reding by Key Index (Random)...
3745 Remove All...
I think the Random reading does the testing better, because when reading from 1 to 100,000, it basicly does a GoNext, witch is faster than actually looking for it not knowing where it is in the first try...
Do something like:
VB Code:
TM = GetTickCount
For I = 1 To Items
Col.GoToKey "Key " & Fix(100000 * Rnd)
O = Col.Item
Next I
Debug.Print GetTickCount - TM, " Reding by Key (Random)..."
I tried some more testing. I was able to improve the seek by index code (since it's a double linked list it can also seek in reverse now), which improves many functions. Here is a new comparison against the vb collection object.
10000 Items
------------------------------------------------
0: KeyedLinkedList:RemoveAll
347: KeyedLinkedList:Add
434: KeyedLinkedList:ReadByKey
156: KeyedLinkedList:ReadByRandomKey
4074: KeyedLinkedList:ReadByIndex
31: KeyedLinkedList:ReadByMoveNext
111: KeyedLinkedList:Remove First
305: KeyedLinkedList:Insert Before First
550: KeyedLinkedList:RemoveByKey
303: KeyedLinkedList:Insert After Last
504: KeyedLinkedList:RemoveByRandomKey
3017: KeyedLinkedList:Insert After Random
535: KeyedLinkedList:RemoveAll
Well this thread hasn't received any responses aside from CVMichael. So this will be my last addition to this thread unless somebody else show interest.
I've created a DLL project called vbHashListLib and have attached it to this reply. It contains both the HashList and LinkedList classes (I finished fixing the vb2themax linkedlist). I optimized the removal methods of both classes for faster results, and cleared up a couple of small bugs.
I've just stumbled across this thread whilest looking for something faster than a collection.
I've been looking into the dictionary object, however I'm interested the stuff you've been doing here.
What was the verdict on your original project - KeyedLinkedList?
From the look of things you've produced two further options
within vbHashListLib - HashList and LinkedList?
Which of these 2 / 3 would you say is the one to use?
Last edited by aconybeare; Nov 3rd, 2003 at 12:13 PM.
It really depends on what your trying to do. If you don't need keys a linked list is definately the way to go, because no key indexing has to be done.
I'm attaching another version of the vbHashlist library which has two more object types, an ObjectList (re-implementation of Steve McMahon's Object Collection found at vbaccelerator.com, this requires a tlb file also in the archive) and what I call an Advanced Linked List.
The Advanced Linked List is much faster at returning items but slower at adding and re-indexing items.
If you need a Keyed collection the vbHashList is faster when you get into thousands of items in your collection, especially at adding items and removing items. It also offers a lot of features not found in the Dictionary and intrinsic Collection objects. But it does not offer a fast was of enumerating through items like the IUknown or IEVariant COM interfaces, so it's slower when looping through objects.
Give some info on what your tring to do and Ill to try to answer as best as I can.
Re: Replacing the vb collection object (Warning - this is a lot to read)
Originally posted by frigginjerk I thought about using a Dictionary but I have read that deploying scrunn.dll can be problamatic.
In all the years I've been using the Dictionary object, I've never once deployed it - and I've written a lot of applications for download from websites like download.com
Just thought I'd mention that
Microsoft MVP : Visual Developer - Visual Basic [2004-2005]
I've been tasked with speeding up an application, which processes +/- 1.5 million records a day. Essentially this application manipulates and concatenates strings from text files, stores them in collections, before processing them. I've already looked into the string side of things, amongst other things I'm using a class similar to the one you use within the HashList and or KeyedLinkedList (I haven't worked out whether this is one and the same yet) called AppendString, which uses the CopyMemory API, found on - FreeVBCode.com http://www.freevbcode.com/ShowCode.Asp?ID=154 I've added two more options to this class PrefixString and ClearString.
With regards to the collections, some of the collections don't need keys so I'm going to convert them to use arrays, however others require keys, which are used to ensure duplicates aren't added, if a duplicate is found use the most recent one. The main collection stores upto 3000 records at any one time.
Will download your latest zip and give it a go
I see that you've not included the dictionary object in your test project, is there a reason for that?
Cheers Al
Last edited by aconybeare; Nov 4th, 2003 at 04:29 AM.
String concatenation is horrendously slow in VB.
What I would suggest is using a dynamic array, and instead of concatenating the text together, store the text in the next index of the array. Then do your processing at the end on the array...
Microsoft MVP : Visual Developer - Visual Basic [2004-2005]
Thanks, just had a look. I've made a note of them for future reference, I'm not looking to bundle the text files with my app. The AppendString class I mentioned above uses the CopyMemory API, so not sure whether I can get it to work any snappier than it already is.
Thanks, just had a look. I've made a note of them for future reference, I'm not looking to bundle the text files with my app. The AppendString class I mentioned above uses the CopyMemory API, so not sure whether I can get it to work any snappier than it already is.
Thanks Al
Well I mentioned them because of the string append function
VB Code:
Private Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (Destination As Any, Source As Any, ByVal Length As Long)
Private Function appendFromArray(ByRef strArray() As String) As String
Dim i As Long, lengthOfBuffer As Long, strBuff As String, currPos As Long
I didn't do much testing with the dictionary object because it is basically a hashtable. It doesn't allow duplicate keys, or retrieval by index, but it is a lot faster than a collection. If you need a simple object that retrieve items by key and never by index then the Dictionary will get the job done very quickly.
HashList / KeyedLinkedList are the same. I changed the name of the project to HashList (just a personal preference) soon I after I posted it here.
Instead of using an array you should test the LinkedListAdvanced class I posted, it's very fast in my opinion.
Last edited by frigginjerk; Nov 4th, 2003 at 05:30 AM.
Plender,
Oh right, sorry!! I didn't want to get bogged down in downloading another proj etc. at the moment. I'm a bit single minded okay maybe half minded, can't multi-thread but I see that this function can be used to concat. the dynamic array you mentioned earler.
Great, thanks for your advice. It sounds like the Dictionary obj is the one for me at the moment, however I do have all the other stuff, which I will keep for future ref. I'll test out the LinkedListAdvanced v's an Array.
Argh that's a major consideration I'm glad you brought that up. Currently as each Item is dealt with it's removed from the collection. How does your HashList compare on that score?
well here's the latest scores on the same machine.
10000 Items
------------------------------------------------
000000: clsHashList:RemoveAll
000364: clsHashList:Add
000168: clsHashList:ReadByKey
000162: clsHashList:RemoveByKey
000381: clsHashList:Insert First
000191: clsHashList:ReadByRandomKey
004883: clsHashList:ReadByIndex
000048: clsHashList:ReadByMoveNext
000143: clsHashList:Remove First
000373: clsHashList:Insert Last
000182: clsHashList:RemoveByRandomKey
003649: clsHashList:Insert After Random
000615: clsHashList:RemoveAll
------------------------------------------------
If testing method hold true then the HashList is very much faster. You should really do you own testin though, because I haven't toyed much with the dictionary for a long time.
I gotta go to bed now (it's 3 am here, and I have work in the morning), so if you have anymore questions I get to them in about 6 or 7 hours.
I've been doing some testing with the hashList and have found that is has a nasty habit of hanging. I guess I might be calling it incorrectly here is my function I've tried to strip it down. Plus it returns a msgbox "invalid key" which should probably be removed.
I've been timing the HashList V's the dictionary obj including removing items.
5 items in the list
1024 iterations
for each iteration do the following -
Populate the obj
Retrieve the last Item
Remove the first item
Remove all
dict - 13.82 milliseconds
HL - 246.49 milliseconds
Col - 184.17 milliseconds (obviously can't clear col on each loop so collection eventually holds 5 * 1024 - 1024 = 4096 items)
I know my testing method isn't pure (No doubt you'll shoot me down here).
VB Code:
Private Sub cmdHashList_Click()
Dim myHashList As clsHashList
Dim i As Long ' Iteration Counter
Dim x As Long ' Number of iterations
Dim y As Long ' used to create Key
' Used to split the string
Dim myParams As String
Dim TempParams As String
Dim intPostn As Integer
Dim strOut As String
Dim strReturn As String
Set myHashList = New clsHashList
x = 1024 ' CLng(txtIterations.Text) '1024 'this is changed per test
I've added the dictionary obj to your test project and these are the results. You are right that the removal is slow, else the dictionary seems to be ahead.
Looks like the way forward with the Dictionary is - Do not remove items if you can help it. Once the entire col has been processed call removeAll (Obviously this approach won't work for everyone, but in my case this should work)
aconybeare, excellent work. Aren't you glad you did that testing afterall?
Modifing items was the one thing I never tested with the HashList, so I'm really glad you brought that weakness to light. However I have no idea right now why the code, I not the best programmer around so I don't doubt that it would hang at all.
Looking at back at the features you do want to utilize it probably would have been best to test the clsHashTable instead of the clsHashList, but the dictionary would still have trounced it.
I don't see any fault in your code, and clearly the Dictionary object is performs best.
Thanks for all your help. The HashListLib is an excellent bundle, which has made a place for it'self in my toolbox. Please let me know if you make any changes or alterations, or at least post the changes here.
Re: Replacing the vb collection object (Warning - this is a lot to read)
I know this is a really old thread, but I just wanted anyone interested to know that I posted a final version of clsLinkedListAdvanced in the codebank. I fixed some bugs and made it faster.
Hope, I dont offend anybody by bringing this up so long after the thread started.
Reply With Quote
not very good is it. But I'm running this code on a Via C3 733 processor which is equivalent to a Intel PII 350.
I didn't want to get bogged down in downloading another proj etc. at the moment. I'm a bit single minded okay maybe half minded, can't multi-thread but I see that this function can be used to concat. the dynamic array you mentioned earler.
