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.

Here are my intial tesing scores in milliseconds. The items inserted and iterated through are class a single class module with 4 basic properties.

Note that most of the collections iterate like this

VB Code:

for i = 1 to 10000
        set o = col.item(i)
next i

the keyedlinkedlist was iterated with this code:

VB Code:

col.movefirst
for i = 1 to 10000
       set o = col.itembyindex
       col.movenext
next i

10000 Items
------------------------------------------------
335: KeyedLinkedList:Add
30: KeyedLinkedList:Read
612: KeyedLinkedList:Remove
316: KeyedLinkedList:Insert
573: KeyedLinkedList:Clear

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

SpiderEye
------------------------------------------------
888: Flexbag:Add
27: Flexbag:Read
607: Flexbag:Remove
37918: Flexbag:Insert
532: Flexbag:Clear

Vb2theMax
------------------------------------------------
373: HashTable:Add
142: HashTable:Read
112: HashTable:Remove
0: HashTable:Insert N/A
521: HashTable:Clear
------------------------------------------------
223: LinkedList:Add
36: LinkedList:Read
499: LinkedList:Remove
216: LinkedList:Insert
499: LinkedList: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

Just wanna show off :)

I made a double linked list a while ago in ATL C++
this is the code I used to test:

VB Code:

Private Declare Function GetTickCount Lib "kernel32" () As Long
 
Private Sub Form_Load()
    Dim Col As New CLinkList, TM As Long, I As Long, O As String
    Const Items As Long = 100000
    
    TM = GetTickCount
    For I = 1 To Items
        Col.AppendItem "test " & I
    Next I
    Debug.Print GetTickCount - TM, " Add..."
    
    TM = GetTickCount
    Col.GoFirst
    For I = 1 To Items
        O = Col.ItemC(I)
    Next I
    Debug.Print GetTickCount - TM, " Reading by index..."
    
    TM = GetTickCount
    Col.GoFirst
    For I = 1 To Items
        O = Col.Item
        Col.GoNext
    Next I
    Debug.Print GetTickCount - TM, " Reading with GoNext..."
    
    TM = GetTickCount
    Col.GoFirst
    For I = 1 To Items
        Col.GoToIndex I
        Col.Remove
    Next I
    Debug.Print GetTickCount - TM, " Removing..."
    
    TM = GetTickCount
    For I = 1 To Items
        Col.InsertItem "test " & I
    Next I
    Debug.Print GetTickCount - TM, " Inserting..."
    
    TM = GetTickCount
    Col.RemoveAll
    Debug.Print GetTickCount - TM, " RemoveAll..."
End Sub

The result:

1332 Add...
100 Reading by index...
110 Reading with GoNext...
1963 Removing...
1312 Inserting...
1182 RemoveAll...

And... please notice the extra ZERO (ie: 100000 items) in the items added... so divide the results by 10...

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.

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)..."

PS: I got a P4, 1.4GHz

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

------------------------------------------------
0: VB Collection:Clear
599: VB Collection:Add
10626: VB Collection:ReadByKey
22587: VB Collection:ReadByRandomKey
658: VB Collection:RemoveByKey
612: VB Collection:Insert Before First
518: VB Collection:Clear

I tried the same comparison at 100,000 items but after 20 minutes of waiting for the vb collection to finish I just "end tasked" it.

Could somebody else please try the keyedlinkedlist, I really want some feedback on this

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.

Any reponses?

Friggin,

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?

aconybeare,

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.

Quote:

---

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 :)

Doh!, forgot to add the attachment.

Friggin,

Thanks for getting back to me. :thumb:

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

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...

Plender,

Many thanks for that I'll look into it, once I've sorted out my collections.

Cheers Al

In so far as working with strings is concerned, either of these might be of interest to you :

http://www.vbforums.com/showthread.p...hreadid=158543
http://www.vbforums.com/showthread.p...hreadid=195896

Plender,

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 :thumb:

Quote:

---

Originally posted by aconybeare
Plender,

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 :thumb:

---

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
    For i = 0 To UBound(strArray)
        lengthOfBuffer = lengthOfBuffer + Len(strArray(i))
    Next
    strBuff = Space$(lengthOfBuffer)
    For i = 0 To UBound(strArray)
        CopyMemory ByVal StrPtr(strBuff) + currPos, ByVal StrPtr(strArray(i)), LenB(strArray(i))
    currPos = currPos + LenB(strArray(i))
    Next
    appendFromArray = strBuff
End Function

aconybeare,

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.

Plender,
Oh right, sorry!! :o 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.

Result thanks! :bigyello:

Earlier I posted that you could not enumerate through the Hashlist quickly. This was somewhat inaccurate.

By using this code you will traverse the list as quickly as possible.

VB Code:

'obj is an instance of clsHashList
obj.MoveFirst
for I = 1 to obj.Count
     set obj2 = obj.ItemByIndex(0)
     obj.MoveNext
Next I

Friggin,

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.

Many many thanks

Al

aconybeare,

Glad to help. Just remeber that removing individual items from a dictionary is a very slow process, look at my second post in this thread.

Best of luck to you and remeber to let us know how this works out for ya.

Friggin,

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?

Al

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.

Friggin,

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
    myParams = "SYS_INSTC,JOB_NUM,CUST_AGRD_DATE,SYS_DATE,My_TIME"
    
    For i = 0 To x
        TempParams = myParams
        y = 0
        ' This loop is faster than using split()
        Do While LenB(TempParams) <> 0
           intPostn = InStr(TempParams, ",")
               If intPostn <> 0 Then
                  strOut = Left$(TempParams, intPostn - 1)
               Else
                  strOut = TempParams
                  TempParams = vbNullString
               End If
           ' Add to the HL Collection
           myHashList.Add Value:=strOut, sKey:="a" & CStr(y)
           TempParams = Right$(TempParams, Len(TempParams) - intPostn)
           strOut = vbNullString
           y = y + 1
         Loop
         
         ' Retrieve the last item
         strReturn = myHashList.Item("a" & CStr(y - 1))
         
         ' Remove the first item in the list
         myHashList.Remove "a" & CStr(0)
         
         ' Clear the HashList
         myHashList.RemoveAll
    Next
    
    MsgBox "All Ok"
End Sub

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)

Code:

---

1000 Items
------------------------------------------------
000000:  clsHashList:RemoveAll
000014:  clsHashList:Add
000004:  clsHashList:ReadByKey
000004:  clsHashList:RemoveByKey
000017:  clsHashList:Insert Before First
000004:  clsHashList:ReadByRandomKey
000004:  clsHashList:ReadByIndex
000001:  clsHashList:ReadByMoveNext
000003:  clsHashList:Remove First
000017:  clsHashList:Insert After Last
000005:  clsHashList:RemoveByRandomKey
000023:  clsHashList:Insert After Random
000004:  clsHashList:RemoveAll
------------------------------------------------
000000:  VB Collection:Clear
000016:  VB Collection:Add
000004:  VB Collection:ReadByKey
000007:  VB Collection:RemoveByKey
000018:  VB Collection:InsertBeforeFirst
000005:  VB Collection:ReadByRandomKey
000010:  VB Collection:RemoveByRandomKey
000000:  VB Collection:Clear
------------------------------------------------
000000:  Dictionary:RemoveAll
000009:  Dictionary:Add
000001:  Dictionary:ReadByKey
000011:  Dictionary:RemoveByKey
000002:  Dictionary:ReadByRandomKey
000011:  Dictionary:RemoveByRandomKey
000003:  Dictionary:RemoveAll
------------------------------------------------

---

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.

Friggin,

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.

Cheers Al

I dont know whats going on LOL!:lol: :confused:

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.

Thanks for the update.

If anyone else comes across this thread in a search, the Codebank article is:
http://www.vbforums.com/showthread.php?t=387848