Merge: lib/code/standard: hash no more divides object_id by 8
authorJean Privat <jean@pryen.org>
Fri, 21 Aug 2015 19:22:36 +0000 (15:22 -0400)
committerJean Privat <jean@pryen.org>
Fri, 21 Aug 2015 19:22:36 +0000 (15:22 -0400)
Since objects are allocated on 64bit word boundaries, it made scene to remove the three 000 lower bits and increase the entropy of the hashcode.
Unfortunately, primitive objects like low Int values or Bool have a object_id lower than 8. shifting the 3 last bits was thus a bad idea.

Therefore, programs that used Int or Bool as keys (or part of keys) did have a lot of hash collisions.
For instance, before, for lib/ai/examples/puzzle.nit:

* number of collisions: 525428 (84.49%)
* average length of collisions: 12.44

After:

* number of collisions: 256223 (41.20%)
* average length of collisions: 3.16

The change have a limiting effect on programs that mainly use standard objects as keys.

Before, for nitc:

* number of collisions: 661715 (16.18%)
* average length of collisions: 2.24

After:

* number of collisions: 711614 (17.40%)
* average length of collisions: 2.25

Pull-Request: #1646
Reviewed-by: Lucas Bajolet <r4pass@hotmail.com>
Reviewed-by: Alexis Laferrière <alexis.laf@xymus.net>


Trivial merge