From: Jean Privat Date: Fri, 21 Aug 2015 19:22:36 +0000 (-0400) Subject: Merge: lib/code/standard: hash no more divides object_id by 8 X-Git-Tag: v0.7.8~77 X-Git-Url: http://nitlanguage.org Merge: lib/code/standard: hash no more divides object_id by 8 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 Reviewed-by: Alexis Laferrière --- a7621d37c40123612b0a70e2042fa6a54892727e