Possible solution: add an ordered subtype of frozenset which would keep an array of items in the original order. The compiler only creates frozenset when optimizes "x in {1, 2}" or "for x in {1, 2}". It should now create an ordered frozenset from a list of constants (removing possible duplicates). The marshal module should save items in that order and restore ordered frozensets when load data. It should not increase memory consumption too much, because frozenset constants in code are rare and small.