[SOLVED] Dictionaries, new dictionary typing, and their operating speeds

Dictionaries, new dictionary typing, and their operating speeds

I just discovered Godot introduced Dictionary type-casting in v4.4, and I decided to play around with it a bit. I was curious whether using type-cast dictionaries would be more or less efficient time-wise, but it led me to discover some results that are quite confusing to me.

First, processing speeds change based on what type of variable the key and value are?

For instance:

func _ready() -> void:
    var typedDict: Dictionary[String, int] = {}
    var regDict: Dictionary = {}
    var regVar = {}
    
    var startTimeTyped: float = Time.get_unix_time_from_system()
    for i in range(300000):
        typedDict[str(i)] = i
    print(Time.get_unix_time_from_system() - startTimeTyped)
    
    var startTimeReg: float = Time.get_unix_time_from_system()
    for i in range(300000):
        regDict[str(i)] = i
    print(Time.get_unix_time_from_system() - startTimeReg)
    
    var startTimeVar: float = Time.get_unix_time_from_system()
    for i in range(300000):
        regVar[str(i)] = i
    print(Time.get_unix_time_from_system() - startTimeVar)

Outputs the times

0.14694118499756

0.14383983612061

0.14430594444275

but if I switch which the key is and which the value is (as below)...

func _ready() -> void:
    var typedDict: Dictionary[int, String] = {}
    var regDict: Dictionary = {}
    var regVar = {}
    
    var startTimeTyped: float = Time.get_unix_time_from_system()
    for i in range(300000):
        typedDict[i] = str(i)
    print(Time.get_unix_time_from_system() - startTimeTyped)
    
    var startTimeReg: float = Time.get_unix_time_from_system()
    for i in range(300000):
        regDict[i] = str(i)
    print(Time.get_unix_time_from_system() - startTimeReg)
    
    var startTimeVar: float = Time.get_unix_time_from_system()
    for i in range(300000):
        regVar[i] = str(i)
    print(Time.get_unix_time_from_system() - startTimeVar)

Is much faster, for some reason, even though the data the dictionaries are handling is exactly the same?

0.09886193275452

0.0967800617218

0.09556293487549

Keep in mind these numbers are different on each run, but they tend to be consistent within ~0.002-0.003 seconds.

This is just assignment, of course. Since nothing is actually done with these dictionaries, I have no idea what kinds of simplifications are going on in the background of Godot's compiler to make it more efficient based on the knowledge the operations listed never have an impact outside the for-loop. So, let's add some.

Updated [String, int] code:

func _ready() -> void:
    var typedDict: Dictionary[String, int] = {}
    var regDict: Dictionary = {}
    var regVar = {}
    
    var startTimeTyped: float = Time.get_unix_time_from_system()
    for i in range(300000):
        typedDict[str(i)] = i
    for i in range(299999, -1, -1):
        var intValue: int = typedDict[str(i)]
        intValue += 1
        typedDict[str(i)] = intValue
    print(Time.get_unix_time_from_system() - startTimeTyped)
    
    var startTimeReg: float = Time.get_unix_time_from_system()
    for i in range(300000):
        regDict[str(i)] = i
    for i in range(299999, -1, -1):
        var intValue: int = regDict[str(i)]
        intValue += 1
        regDict[str(i)] = intValue
    print(Time.get_unix_time_from_system() - startTimeReg)
    
    var startTimeVar: float = Time.get_unix_time_from_system()
    for i in range(300000):
        regVar[str(i)] = i
    for i in range(299999, -1, -1):
        var intValue: int = regVar[str(i)]
        intValue += 1
        regVar[str(i)] = intValue
    print(Time.get_unix_time_from_system() - startTimeVar)

These times were usually quite close, but the typed Dictionary still performed worse on average:

0.25205421447754

0.25151801109314

0.25120687484741

This is obviously no longer in the realm of comparable to [int, String] dictionaries, since there's so many other operations going on here that would be drastically different in the code adopted for the other example, but what is going on with these times?

Why is assigning String keys to int values so much slower than assigning int keys to String values? Why is the typed Dictionary not any more efficient than an untyped Dictionary (or even a regular Variant variable)? I would have assumed that type-casting made processes involving the variables run faster, because the compiler knows more about what kinds of contents the variable can hold, but that doesn't seem to be the case here. Is it just because the program is so small the compiler can surmise all the information the type-casting gives it anyway? If that is the case, however, then why is the type-cast Dictionary consistently slower than regDict?

Solution

Why is assigning String keys to int values so much slower than assigning int keys to String values?

Dictionaries must convert the key into something they can use to index into their internal data. This is a process called hashing. Hashing a string is slower than hashing an integer, so using an integer as the key is a bit faster.

Why is the typed Dictionary not any more efficient than an untyped Dictionary (or even a regular Variant variable)?

Actually making use of type information during interpretation is a fairly recent development of GDScript (introduced with 4.0), and still has a lot of potential for further improvements. The tiny differences you're seeing indicate that typing simply doesn't affect the performance here. If the ranking of the performance is consistent, it probably has more to do with some other factor, such as the order in which you run the tests.