-
May 17th, 2019, 01:53 AM
#1
Thread Starter
Hyperactive Member
Which is faster RichClient cSortedDictionary or cCollection
-
May 17th, 2019, 01:58 AM
#2
Re: Which is faster RichClient cSortedDictionary or cCollection
I think you can insert items to cCollection significantly faster.
cheers,
</wqw>
-
May 17th, 2019, 06:38 AM
#3
Thread Starter
Hyperactive Member
Re: Which is faster RichClient cSortedDictionary or cCollection
-
May 17th, 2019, 01:24 PM
#4
Re: Which is faster RichClient cSortedDictionary or cCollection
What wqweto writes is true -
but only for the case where you add Items into a cCollection without specifying Keys.
In a cCollection we have .Add Item, Optional Key, ... (without Keys to allow plain, unsorted "List-mode with Index-access only")
And in a cSortedDictionary it's the other way around with .Add Key, Optional Item
(a cSortedDictionary without Items would allow scenarios, where one is only interested in an always sorted List of Keys).
So one can leave out one or the other in these Container-Classes.
When we talk about adding of true Key/Value-pairs though, the cSortedDictionary should be a bit faster,
because the cCollection (which is implemented nearly identical - using a sorted Key-List for fast Key-access - and not a Hash) -
will have to maintain an "index-table which represents the Add-Order of items" in addition.
So this double-indexing within the cCollection is the cause for a relatively small disadvantage...
(memory- and performance-wise, compared to a cSortedDictionary in case of added Key/Value-pairs).
Note, that a cSortedDictionary will enumerate always in SortKey-Order -
whereas from a cCollection you can enumerate in Add-Order but also in SortKey-Order.
Olaf
-
May 18th, 2019, 08:29 AM
#5
Thread Starter
Hyperactive Member
Re: Which is faster RichClient cSortedDictionary or cCollection
Thanks Olaf. I also read somewhere that you had written a hash class but i have not been able to find it. Basically I need to fastest key value pair lookup possible. I did test Tricks hash class and it was about a 3rd faster than cSorted however it fell over at scale. I started to debug it and ran out of time.
I did benchmarks myself on cSorted, cCollection , scripting duct (not even in the game) and trick hash class. If Olaf's hash class exists could someone point me at it and I will give it a go.
Thanks
-
May 18th, 2019, 09:13 AM
#6
Re: Which is faster RichClient cSortedDictionary or cCollection
For best performance you have to specialize your container (e.g. in .Net you have Dictionary<string, string> or Dictionary<string, int> that are fine-tuned instances of the generic clss).
You cannot expect general purpose container w/ Variant keys returning Variant values to perform best *and* has minimal impact on memory -- simply not possible and AFAIR trick's hash-map was Variant<->Variant container.
Just make up your mind that you need keys that are strings and search for a fast String<->Variant hash-map, or even better String<->String one.
Also hash-sets (that is a collection w/o values, only being able to check for key existence) are usually faster and need less memory, so container type is the starting point of your research.
cheers,
</wqw>
-
May 18th, 2019, 11:11 AM
#7
Thread Starter
Hyperactive Member
Re: Which is faster RichClient cSortedDictionary or cCollection
Thanks wqw.
You approach makes sense. Do you know of a specialized string to variant container. Do you have knowledge of either commerci
-
May 18th, 2019, 11:50 AM
#8
Re: Which is faster RichClient cSortedDictionary or cCollection
I'm sure Olaf has such one, will let him chime in.
FYI, built-in VBA.Collection is a String<->Variant container too
cheers,
</wqw>
-
May 18th, 2019, 01:01 PM
#9
Re: Which is faster RichClient cSortedDictionary or cCollection
Originally Posted by wqweto
I'm sure Olaf has such one, will let him chime in.
I've posted code for cHashD into the CodeBank some time ago:
http://www.vbforums.com/showthread.p...lass-(no-APIs)
@vbwins
Here is a variant of the original code, which was reduced to "String-Keys only mode":
Code:
Option Explicit 'Olaf Schmidt in August 2016
Private Type SAFEARRAY1D
cDims As Integer
fFeatures As Integer
cbElements As Long
cLocks As Long
pvData As Long
cElements1D As Long
lLbound1D As Long
End Type
Private Declare Sub BindArray Lib "kernel32" Alias "RtlMoveMemory" (PArr() As Any, pSrc&, Optional ByVal CB& = 4)
Private Declare Sub ReleaseArray Lib "kernel32" Alias "RtlMoveMemory" (PArr() As Any, Optional pSrc& = 0, Optional ByVal CB& = 4)
Private Declare Function VariantCopy Lib "oleaut32" (Dst As Any, Src As Any) As Long
Private Declare Function VariantCopyInd Lib "oleaut32" (Dst As Any, Src As Any) As Long
Private Type HashTableEntry
Count As Long
DataIndexes() As Long
End Type
Private W() As Integer, saW As SAFEARRAY1D
Private mCompareMode As VbCompareMethod, mUniqueKeys As Boolean
Private mCount As Long, mDTUB As Long, mHashTableSize As Long
Private mLastKey, mLastIdx As Long, mLastExpectedCount As Long
Private mKeys() As String, mValues() As Variant, HashTable() As HashTableEntry
Private Sub Class_Initialize()
saW.cDims = 1
saW.cbElements = 2
BindArray W, VarPtr(saW)
mUniqueKeys = False
mCompareMode = vbBinaryCompare
mLastExpectedCount = 32768 'set the expected default HashTable-Size
ReInit
End Sub
Private Sub Class_Terminate()
ReleaseArray W
End Sub
Public Sub ReInit(Optional ByVal ExpectedCount As Long)
If ExpectedCount <= 0 Then ExpectedCount = mLastExpectedCount
If ExpectedCount < 100 Then ExpectedCount = 100
mLastExpectedCount = ExpectedCount
mHashTableSize = 8
Do Until mHashTableSize * 4 > ExpectedCount: mHashTableSize = mHashTableSize * 2: Loop
ReDim HashTable(0 To mHashTableSize - 1)
Dim i As Long
For i = 0 To UBound(HashTable): ReDim HashTable(i).DataIndexes(0 To 4): Next
mDTUB = 16: Erase mKeys
ReDim mKeys(0 To mDTUB)
ReDim mValues(0 To mDTUB)
mCount = 0
mLastIdx = 0
End Sub
Public Sub RemoveAll()
ReInit
End Sub
Public Property Get Count() As Long
Count = mCount
End Property
Public Property Get UniqueKeys() As Boolean
UniqueKeys = mUniqueKeys
End Property
Public Property Let UniqueKeys(ByVal RHS As Boolean)
mUniqueKeys = RHS
End Property
Public Property Get CompareMode() As VbCompareMethod
CompareMode = mCompareMode
End Property
Public Property Let CompareMode(ByVal RHS As VbCompareMethod)
mCompareMode = RHS
End Property
Public Function Keys()
If mCount Then mDTUB = mCount - 1 Else Keys = Array(): Exit Function
ReDim Preserve mKeys(0 To mDTUB): Keys = mKeys
End Function
Public Function Items()
If mCount Then mDTUB = mCount - 1 Else Items = Array(): Exit Function
ReDim Preserve mValues(0 To mDTUB): Items = mValues
End Function
Public Function Exists(Key As String) As Boolean
mLastIdx = FindIndex(Key, HashTable(CalcHash(Key))) + 1
Exists = mLastIdx
If mLastIdx Then mLastKey = Key
End Function
Public Function IndexByKey(Key As String) As Long
IndexByKey = FindIndex(Key, HashTable(CalcHash(Key)))
End Function
Public Sub Add(Key As String, Item)
Dim HashValue As Long, UB As Long
HashValue = CalcHash(Key)
If mUniqueKeys Then If FindIndex(Key, HashTable(HashValue)) >= 0 Then Err.Raise 457
'add the new Pair, prolonging the Keys- and Values-arrays
If mDTUB < mCount Then
mDTUB = (mDTUB + 16) * 1.6
ReDim Preserve mValues(0 To mDTUB)
ReDim Preserve mKeys(0 To mDTUB)
End If
mKeys(mCount) = Key
VariantCopyInd ByVal VarPtr(mValues(mCount)), ByVal VarPtr(Item)
'add the new DataIndex to the proper Hash-Buckets .DataIndexes-Array
With HashTable(HashValue)
UB = UBound(.DataIndexes)
If UB < .Count Then UB = UB + UB: ReDim Preserve .DataIndexes(0 To UB)
.DataIndexes(.Count) = mCount
.Count = .Count + 1
End With
mCount = mCount + 1
End Sub
Public Property Get KeyByIndex(ByVal IndexZeroBased As Long) As String
If IndexZeroBased < 0 Or IndexZeroBased >= mCount Then Err.Raise 9
KeyByIndex = mKeys(IndexZeroBased)
End Property
Public Property Get ItemByIndex(ByVal IndexZeroBased As Long)
If IndexZeroBased < 0 Or IndexZeroBased >= mCount Then Err.Raise 9
VariantCopy ItemByIndex, ByVal VarPtr(mValues(IndexZeroBased))
End Property
Public Property Let ItemByIndex(ByVal IndexZeroBased As Long, RHS)
If IndexZeroBased < 0 Or IndexZeroBased >= mCount Then Err.Raise 9
VariantCopyInd ByVal VarPtr(mValues(IndexZeroBased)), ByVal VarPtr(RHS)
End Property
Public Property Set ItemByIndex(ByVal IndexZeroBased As Long, RHS)
ItemByIndex(IndexZeroBased) = RHS
End Property
Public Property Get Item(Key As String)
Dim Index As Long, VT As Long
If mLastIdx Then
Index = mLastIdx - 1: mLastIdx = 0
If mLastKey = Key Then VariantCopy Item, ByVal VarPtr(mValues(Index)): Exit Property
End If
Index = FindIndex(Key, HashTable(CalcHash(Key)))
If Index >= 0 Then VariantCopy Item, ByVal VarPtr(mValues(Index))
End Property
Public Property Let Item(Key As String, RHS)
Dim Index As Long
Index = FindIndex(Key, HashTable(CalcHash(Key)))
If Index = -1 Then Add Key, RHS Else VariantCopyInd ByVal VarPtr(mValues(Index)), ByVal VarPtr(RHS)
End Property
Public Property Set Item(Key As String, RHS)
Item(Key) = RHS
End Property
Private Function CalcHash(Key As String) As Long
Dim l As Long, i As Long, S As String
If mCompareMode Then
S = LCase$(Key)
saW.cElements1D = Len(S)
saW.pvData = StrPtr(S)
Else
saW.cElements1D = Len(Key)
saW.pvData = StrPtr(Key)
End If
l = 65233
For i = saW.cElements1D - 1 To 0 Step -1
l = (l + W(i) + i) * 3727 And &HFFFF& '
Next
CalcHash = (l + saW.cElements1D) And (mHashTableSize - 1)
End Function
Private Function FindIndex(Key As String, H As HashTableEntry) As Long 'return -1, when no Key can be found
Dim i As Long
If mCompareMode = 0 Then
For i = 0 To H.Count - 1
If Key = mKeys(H.DataIndexes(i)) Then FindIndex = H.DataIndexes(i): Exit Function
Next
Else
For i = 0 To H.Count - 1
If StrComp(Key, mKeys(H.DataIndexes(i)), mCompareMode) = 0 Then
FindIndex = H.DataIndexes(i): Exit Function
End If
Next
End If
FindIndex = -1
End Function
Friend Sub CheckHashDistribution() 'just for testing
Dim i As Long, Count As Long, cc As Long, Min As Long, Max As Long
Min = &H7FFFFFFF
For i = 0 To UBound(HashTable)
Count = HashTable(i).Count
If Count Then
If Min > Count Then Min = Count
If Max < Count Then Max = Count
cc = cc + 1
End If
Next
Debug.Print "Distribution over a HashTable with"; UBound(HashTable) + 1; "slots:"
Debug.Print "Used-HashSlots:"; cc
Debug.Print "Min-Entries:"; Min
Debug.Print "Max-Entries:"; Max
End Sub
Note, that in your own Performance-Tests, you will have to compile cHashD into native code
(ideally with all extended Compiler-Options checked, except the top-one for "Aliasing").
To really help with your scenario (to suggest other speed-increasing measures),
we would have to know what it is concretely, that you're trying to do...
From other code you've mailed per PM - I've seen that it tries for fast lookups on IP-connections
(storing a connection-info-entry under a Key of "IP4_1:Port1: IP4_2:Port2").
Not sure, whether we still talk about the same scenario...
Olaf
Last edited by Schmidt; May 18th, 2019 at 01:11 PM.
-
May 20th, 2019, 05:25 AM
#10
Re: Which is faster RichClient cSortedDictionary or cCollection
A few days ago, I posted a small test program in my thread:
http://www.vbforums.com/showthread.p...=1#post5387307
-
May 20th, 2019, 07:00 AM
#11
Thread Starter
Hyperactive Member
Re: Which is faster RichClient cSortedDictionary or cCollection
Thanks for the replies guys. My agent component uses raw sockets to various things about network traffic such as who is talking to who on what port, for what duration etc and summarize information by end point (an end point example would be a mysql server with hundreds of connections) into one set of metrics for that end point. It also tracks and times dns requests and interesting ICMP messages about reach-ability etc. It is critical for my component that it is as efficient as I can make it given what I am working with. So Olaf it is the same scenario. Thanks for the classes. I did look in the code bank but I must have missed it. I thank you all for your assistance.
EDIT.
The core requirement is to be able to add/update/check for existence/remove string keys where the value might be a string,number or object/class as quickly as possible.
I will do some more benchmarks. I see the Olaf's hash table class intentionally leaves out remove so I will need to add this.
thanks again.
Last edited by vbwins; May 20th, 2019 at 07:26 AM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|