How is Tie :: IxHash implemented in Perl?

Question

I recently came across a situation in Perl where using a hash that preserves order will make my code more readable and easier to use. After a short search, I found out about the Tie :: IxHash CPAN module, which does exactly what I want. Before I be careful about the wind and just start using it, I would like to get a better idea of ​​how it works and what kind of performance I can expect from it.

From what I know, ordered associative arrays are usually implemented as attempts that I have never used before, but I know that their performance meets my expectations (I expect that I will do a lot of reading and writing, and it will always be necessary to remember that the keys orders were originally inserted). My problem is that I cannot figure out if it was like this: Tie :: IxHash, or what kind of performance I should expect from it, or if there is some better / cleaner option for me (I really would not want to separate array and hash to accomplish what I need, as this leads to ugly code and space inefficiencies). I'm also curious for the sake of curiosity. If it was not implemented as a trie, how was it implemented? I know that I can get through the source code, but I hope someone else has done this, and I assume that I am not the only person who will be interested in the answer.

So ... Ideas? Suggestions? Advice?

Answer 1

A Tie :: IxHash object is implemented directly using the usual Perl building blocks that you would expect. In particular, such an object is a blissful array containing 4 elements.

• [0] hash link for storing user hash keys. This is used every time the module must check for a key.

• [1] A reference to an array for storing user hash keys in order.

• [2] A reference to a parallel array for storing values ​​is also in order.

• [3] An integer to track the current position in two parallel arrays. This is necessary for iteration.

In terms of performance, a good benchmark usually costs more than speculation. I assume that the biggest hit in performance will come with deletion, because arrays containing ordered keys and values ​​will require tuning.

Answer 2

The source will tell you how this feature is implemented and measures its performance.