Prime Layer Hashing

Members in Groups are represented through prime layer hashing tables. It works like a normal hash table, except it links layers together rather can copying values into a new table when expanding. It uses 30 - 40% more index memory on average than a sorted array, but it is over twice as fast. The structure stores pointers, which will be freed if overwriting them with a new value at the same property id.

Introduction

An object got usually few properties, for example in the range 4 to 20. Simple objects tend to be used for high performance tasks. In addition to this, for advanced algorithms it is common to "tag" objects with extra properties and remove them later. The issue here is about simple objects with frequently changing properties. Prime layer hashing technique is a way to link hash layers together in order to minimize collisions. All layers got size in the sequence of prime numbers.

Example: We have 3 layers with size 5, 7 and 11. When looking up a value, prime hash layer first checks the largest layer, then the second largest and so on. If you insert properties with a multiple of 5*7*11, then it takes 3 ids to fill up the 3 layers before you need a new one. The next layer will have size 13. The more layers we add, the slower will it be to get or set values.

Memory Usage

When testing prime layer hashing for memory usage, we can insert numbers randomly and see how many slots are free when it creates a new layer. For Groups, the closest test to real applications is to add a random X*million to an increasing numbers, because that is similar to how property ids are generated.

• A = layers
• B = average filled slots, using random X*1000000 added to an incrementing number
• C = number of total slots
• D = unused slots
• E = unused slots in percent

    A	B	C	D	E
    2	5	5	0	0%
    3	7.96	12	4.04	33.67%
    4	14.35	23	8.65	37.61%
    5	22.68	36	13.32	37%

B = changed to complete random numbers

    A	B	C	D	E  
    2	2.5	5	2.5	50%  
    3	6.9	12	5.1	42.5%  
    4	13.8	23	9.2	40%  
    5	22.86	36	13.14	36.5%  

B = changed to incrementing numbers from 0

    A	B	C	D	E
    2	5	5	0	0%
    3	12	12	0	0%
    4	23	23	0	0%
    5	36	36	0	0%

B = changed to incrementing numbers, but 1 000 000 added randomly.

    A	B	C	D	E
    2	5	5	0	0%
    3	7.87	12	4.13	34.42%
    4	15.55	23	7.45	32.39%
    5	24.33	36	11.67	32.42%