Not sure if this is indicative of a bug, but I noticed that a frozenset created from a set seems to occupy a different amount of memory than a frozenset created from some other iterable. I observed this behavior with Python 2.7.5 and with Python 3.4.0 on Ubuntu 14.04 x86_64:

>>> from sys import getsizeof
>>> x = range(100)
>>> s = set(x)
>>> f0 = frozenset(x)
>>> f1 = frozenset(s)
>>> getsizeof(s)
8424
>>> getsizeof(f0)
8424
>>> getsizeof(f1)
4328
>>> f0==f1
True

Original question on StackOverflow available at https://stackoverflow.com/questions/23618259/memory-occupied-by-set-vs-frozenset-in-python-2-7