frozenset constructor has different implementations depending on the input type: set (or frozenset), dict or iterator. The constructor preallocates the frozenset for set and dict, but not for generic iterator and so the set may have a suboptimal size.

Attached patch set_length_hint.patch optimizes also the 3rd case using operator.length_hint (PyObject_LengthHint in C).

Since it is an optimization, I prefer to only apply it to Python 3.5 to limit the risk of regression.