Hash function for Vector3 does not perform well

[ghost]

Operating system or device - Godot version:

Windows 10 / Godot 2.0.3

Issue description (what happened, and what was expected):

I have some performance issues with Vector3 used as a key in a dictionary (approx. 9k items & 50k tests). The execution gets 3 times faster if str(vec3) is used instead.

I was able to track the issue down to three calls of hash_djb2_one_float() function in hashfuncs.h but I cannot see any problem there. Maybe this particular hash function results in many collisions for my data (uniform non-cubic 3D grid).

[Zylann]

Does it performs the same with an integer-based Vector3i? (which doesn't exists in Godot).

[ghost]

I don't have a C++ version of my routines yet. Everything is in GDScript for now.

[neikeq]

ping @reduz

[reduz]

Can you make a small benchmark comparing different key types so I can work on that?

[akien-mga]

Sounds like an issue for @hpvb :)

[akien-mga]

(and yes a small benchmark would still be appreciated to work on this efficiently)

[hpvb]

Will look at it, I'll see if a more appropriate hash function for vector3 can be used here.

[hpvb]

I've tested this on master and I can't reproduce this performance discrepancy. Using the following code:

func _ready():
    var array = []
    for i in range(1, 1000000):
        array.append(Vector3(i, i, i))

    var dict = {}   

    var start = OS.get_ticks_usec()
    for i in range(1, array.size()):
        dict[array[i]] = 1
    var end = OS.get_ticks_usec()
    print("Elapsed time: " + str(end - start))

    array = []
    for i in range(1, 1000000):
        array.append(str(Vector3(i, i, i)))
    dict = {}

    start = OS.get_ticks_usec()
    for i in range(1, array.size()):
        dict[array[i]] = 1
    end = OS.get_ticks_usec()

    print("Elapsed time: " + str(end - start))

    get_tree().quit()

It appears there is not a big performance delta between using Vectors vs using Strings as keys. For example:

Elapsed time: 1326005
Elapsed time: 1135212

Perhaps this is Godot 2.x specific though, it is missing a lot of optimizations done in the 3.x series.