Use Python `dict` instead of hasbrown - Version 6.0.0

[awolverp]

Using Python's dictionary in Rust (instead of hashbrown) can bring algorithm speeds close to Python's own dictionary performance. Since Python's dictionary follows a FIFO algorithm, we can use the dictionary directly and just add features like memory management and maxsize.

This way, most algorithms gain significant speed improvements, and a lot of overhead is eliminated.

Of course, with this change, features like capacity control and shrink_to_fit are lost.

Also in this way library can give you more control and access to everything.

[stalkerg]

Since Python's dictionary follows a FIFO algorithm, we can use the dictionary directly and add features like memory management and maxsize.

But it's still not FIFO.

This way, most algorithms gain significant speed improvements, and a lot of overhead is eliminated.

Can you provide examples? I just worry about GIL and how it can affect us, also, we will have more FFI calls.

[awolverp]

But it's still not FIFO.

Anyway, Python dictionaries are ordered, and this can be very helpful.

Can you provide examples?

For example, hasbrown only accepts usize as a hash, while Python’s hash is isize. If a dict is used, these conversions are unneeded.
Of course, these are just theoretical, before refactoring, I’ll definitely test it to make sure.

lrudict library is using dict inside, and now it is faster than cachebox's LRUCache

[stalkerg]

Anyway, Python dictionaries are ordered, and this can be very helpful.

Seems like during FIFO and limit on item numbers, we should do next(iter(d)) + del (push new upfront and delete oldest item), and it's relatively expensive for PyDict.

https://docs.python.org/3/library/stdtypes.html#dict.popitem -- popitem can remove only the first element.

[awolverp]

You were right. Using dict does not make sense in some algorithms. In other hand, hashbrown removed the raw API. I should find an alternative to hashbrown that give raw access, or we should stick with old version of hashbrown.