Hashmaps

[benibela]

I have closely examined the hashmap code, since I need a hashmap and FLRE's hashmap is faster than most. It is very impressive.

But there is a lot of duplicate code and freeing of things that are already freed by reference counting. This pull request removes them.

There are two things not addressed here. EntityToCellIndex is only used to track deleted entities, so it probably could be removed, by changing the detection to empty keys or values. it would reduce the memory use of the maps by like 25%. Secondly, the same hashmap implementation occurs four times in FLRE. Surely that could be merged to a single generic hashmap?

[benibela]

Delete is not so good, not fully deleting the indices. If there was a list of deleted entities, they could be reused. It could put a pointer/index to the next deleted entity in the entity value. And if findCell would return deleted cells, it could reuse deleted cells (keep searching until an empty cell, but remember the first deleted cell, and return that deleted cell, if not matching key is found).

And resize does not need to add all entities to a new entity array, it could reuse the old entity array and just remove deleted entities.

Behold, a generic hashmap. And it is 10% faster despite using a worse hash function (edit: well, now I ran the test again and it is not faster anymore :/ edit2: need to break this down further. So insertions are 17 to 23% faster, but lookups are 30% slower. in the link, not in the PR)

[BeRo1985]

The hashmap of TFLRE is based on the semi-lockfree thread-safe POCAHash* stuff of https://raw.githubusercontent.com/BeRo1985/poca/master/src/POCA.pas where the POCAHash stuff of my POCA script engine works with parallel new shadow copies during resizing until the resizing is finished.

Just so you know from the backgrounds of the FLRE HashMap why they appear at first sight unoptimized regarding the delete and resize operations, because they originally came from POCA, where they had to work semi-lockfree with multithreaded POCA scripts using temporary shadow copies and interact with the POCA Garbage Collector.

See POCAHashResize POCAHashPut POCAHashPut POCAHashPutCache POCAHashPut POCAHashSymbolChainCache and so on.

A POCA Hash Type is like a LUA Table Type or like a JavaScript/ECMAScript object, see https://github.com/BeRo1985/poca/wiki/Syntax

[benibela]

Still it is not optimal for a single threaded map. I keep learning new things about hashmaps

If the map would store the hash of each entitiy, it could be resized faster. But then it needs more memory. So perhaps not storing the hash is better.

Python uses the same construction with an array of entities and one array mapping hashs to entity index, to minimize the memory usage. But they switch between 1-byte/2-byte/4-byte/8-byte indices to save memory on small arrays and still be able to store larger ones.

Add resizes it when the size reaches (1 shl LogSize), but then LogSize is increased and it is resized to (2 shl LogSize), so the load factor seems to be always between 25% and 50%. Probably the entities array could be half as large and still work exactly the same. The CellToEntityIndex array might need the empty fields to be faster?

Deletion becomes really difficult after removing the EntityToCell Array. I could not get it working in a generic case. If the key is a pointer, deleted entries could be marked with nil, but not when it stores string keys, because nil is the empty string. A special string could mark it, but fpc does not allow to inline functions doing pointer(str) = ..., which made it inefficient. And there would be no special marking key in an int->int hashmap. Although if it would store the hash in the entity array rather than recomputing it, it could mark deleted entries with a zero or -1 hash. On the other hand, actually deleting entities rather than marking them, in an O(n) deletion operation, works generically and well. I almost never use deletion.

And then one needs hashsets. Is a hashset a hashmap with a void value, or is a hashmap a hashset of pairs?

An enumerator for the for in loop could either return a pointer to an entitiy item, or a wrapper with map structure and an index in the entitiy array. Former is simpler, but latter is more stable, if the map is resized during enumeration.