Originally Posted By: Khaled
Originally Posted By: Protopia
1. To change how the linked_list is ordered will break backwards compatibility for any scripts which rely on order.

Which is why I have stated many times that you should not depend on the order of hash table items.

In the real world, people have relied on this order even if you stated that they should not rely on it in some places (though NOT in the help file). So in the real world this change will break scripts.

Originally Posted By: Khaled
Originally Posted By: Protopia
4. In real-world use of hash tables, is there any evidence that moving the most recently accessed item to the beginning of the linked list will improve performance?

It is an optimization that is generally recommended to speed up access for items that are retrieved more often than others.

I can see no reason why you shouldn't move it to the first position in the slot if slots > 1. The cost of doing this is very small, though I am unsure just how often it will produce noticeable benefits in the real world (i.e. how often a script will do an $hget(table,item) for the same item in quick succession).

Originally Posted By: Khaled
If I decide to make my hash table implementation return items in a specific order in particular contexts, this means that I will need to support this in all future hash table improvements, or if/when I change to a new/better hash table implementation. That simply is not practical. Especially since I have repeatedly said, many times, you should not depend on the hash table preserving order since that is not a normal feature of hash tables.

The only thing I am suggesting is that the existing functionality for ordered recall with slots=1 is retained. I am not proposing any changes which will require items to be delivered in any sequence if slots > 1 - and indeed in a previous post I pointed out that users like me and others should NOT try to box you in to e.g. specific hash routines which would then restrict your ability to improve code, so we are agreed on this.

However depending on implementation, alternative search mechanisms enabled by flags might in practice deliver items in a sequence which people then come to rely on (like slots = 1 did) - and if you ever decide to implement these, you should bear this in mind. That said, if such a sequence is intrinsic to how the items are stored, then it would be unlikely that any future changes would impact that, and perhaps you could accept those restrictions.

It is of course your choice as to what you decide to implement - but in my defence I would say that all of my suggestions have been designed to be simple to implement and to preserve backward compatibility whilst delivering significant performance improvements for large hash tables.

(I do not have any code which needs large hash tables, and therefore I am not seeing any performance issues even with non-hashed access, so I am personally not that worried whether you implement them or not. My suggestions are only for the benefit of anyone who does use large hash tables, and particular anyone who uses unhashed access to such tables.)

Last edited by Protopia; 28/10/18 11:01 AM.