Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Inefficiency of Dictionary<long, T> compared with Dictionary<(int, int), T>

Discussion in 'Scripting' started by ngyJlP, Aug 16, 2022.

  1. ngyJlP

    ngyJlP

    Joined:
    Jul 4, 2018
    Posts:
    25
    Set and retrieve time of 1,000,000 values on my machine by key :

    0.066 (set) - 0.069 (retrieve) ----- key: (short, short)
    0.019 (set) - 0.020 (retrieve) ----- key: int <= (short << 16 | short)

    Yet:

    0.169 (set) - 0.180 (retrieve) ----- key: (int, int)
    5.182 (set) - 5.224 (retrieve) ----- key: long <= ((long) int << 32 | int)

    In each case the shift operations take a negligible time.

    Converting a (short, short) tuple into an int is 3x more efficient. Converting a (int, int) tuple into a long is x30 times less efficient. Yet there are as many (int, int) tuples as there are long, same way with (short, short) tuples and int.

    Someone cares to explain?
     
  2. Kurt-Dekker

    Kurt-Dekker

    Joined:
    Mar 16, 2013
    Posts:
    38,520
    Nope. Only one explanation and you can find it yourself: Window -> Analysis -> Profiler.
     
  3. ngyJlP

    ngyJlP

    Joined:
    Jul 4, 2018
    Posts:
    25
    It's called in Awake(). If I call it at runtime I don't think the profiler will help explain why in the general case Dictionary<(int, int), T> is far more efficient than Dictionary<long, T>.
     
  4. jvo3dc

    jvo3dc

    Joined:
    Oct 11, 2013
    Posts:
    1,520
    It is indeed not what you would expect. I mean, the first case I'd expect, one int as key being faster than two shorts in a Tuple. The second case does seem odd to me on 64 bit hardware. Maybe you can share the actual code?
     
  5. Lo-renzo

    Lo-renzo

    Joined:
    Apr 8, 2018
    Posts:
    1,503
    What happens if you supply a custom comparer to the dictionary for the long so you can implement your own GetHashCode()? That could explain why (int, int) does better because ValueTuples use different hashing than long which perhaps would be faster than the default or perhaps for your set of longs it'd reduce collisions.

    Here's the default long's implementation of GetHashCode() which also shifts bits, so depending what your ints are beforehand it could be a problem.
    Code (CSharp):
    1. // The value of the lower 32 bits XORed with the uppper 32 bits.
    2. public override int GetHashCode() {
    3.     return (unchecked((int)((long)m_value)) ^ (int)(m_value >> 32));
    4. }
     
    Last edited: Aug 16, 2022