Sorting overhead vs dict implementation for tape.trainable_params

[dwierichs]

Feature details

#1836 introduces two sorted statements in the Tape methods get_parameters and set_parameters, applied to trainable_params.
In almost all known cases, the set tape.trainable_params already is sorted internally (in an unstable sense, as it is a set), which makes these sorted calls very fast (best case performance of Timsort is O(n)).
However, get_parameters and set_parameters are called quite often and the overhead might add up.

The "issue" would be to check whether implementing trainable_params as a dict instead of a set would be faster. It has the benefit of preserving insertion order (trainable_params is assumed to always be created from sorted integers) from Python3.7 onwards and one could simply set all values to None. Unfortunately, Python3.7 does not guarantee insertion order preservation for sets which made #1836 necessary in the first place.

Implementation

One would probably change qml.math.trainable_indices and some places in tape/tape.py to use a dict with dummy values None instead of a set.
The major work would be in the test suite, where there is a lot of explicit checks of the trainable_params that need to be adapted accordingly to check for such a dict with dummy values instead of the original set.

How important would you say this feature is?

1: Not important. Would be nice to have.

Additional information

No response

[CatalinaAlbornoz]

Hi @dwierichs, I think this is a great idea! I've created a ticket for the team to take a look at this.
Thank you for this suggestion!

[dwierichs]

This is taken care of in#1904 byimplementing trainable_params as a list.