Results 1 to 11 of 11

Thread: Which is faster RichClient cSortedDictionary or cCollection

  1. #1

    Thread Starter
    Hyperactive Member
    Join Date
    Mar 2019
    Posts
    416

    Which is faster RichClient cSortedDictionary or cCollection

    thanks

  2. #2

  3. #3

    Thread Starter
    Hyperactive Member
    Join Date
    Mar 2019
    Posts
    416

    Re: Which is faster RichClient cSortedDictionary or cCollection

    Thank you.

  4. #4
    PowerPoster
    Join Date
    Jun 2013
    Posts
    7,219

    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

  5. #5

    Thread Starter
    Hyperactive Member
    Join Date
    Mar 2019
    Posts
    416

    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

  6. #6
    PowerPoster wqweto's Avatar
    Join Date
    May 2011
    Location
    Sofia, Bulgaria
    Posts
    5,120

    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>

  7. #7

    Thread Starter
    Hyperactive Member
    Join Date
    Mar 2019
    Posts
    416

    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

  8. #8
    PowerPoster wqweto's Avatar
    Join Date
    May 2011
    Location
    Sofia, Bulgaria
    Posts
    5,120

    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>

  9. #9
    PowerPoster
    Join Date
    Jun 2013
    Posts
    7,219

    Re: Which is faster RichClient cSortedDictionary or cCollection

    Quote Originally Posted by wqweto View Post
    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.

  10. #10
    PowerPoster
    Join Date
    Sep 2012
    Posts
    2,083

    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

  11. #11

    Thread Starter
    Hyperactive Member
    Join Date
    Mar 2019
    Posts
    416

    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
  •  



Click Here to Expand Forum to Full Width