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

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.

I think the argument against using PyObject_LengthHint for the general iterable case is that for inputs other than sets or dicts, the assumption is that significant deduplication will occur. With your patch, if I run:

myset = frozenset([0] * 1000000)

it will allocate space for, if I'm reading it correctly, two million entries, and use exactly one of them. Obviously not the common case, but preallocating when you have no idea how much duplication will occur seems like a bad idea.

With a set or dict, you know it's already deduplicated, so preallocation is always a good thing, but for the general case, you'll be using more memory than necessary much of the time.

I agree with Josh's arguments. Similar idea was already proposed and rejected (issue17338).

"I think the argument against using PyObject_LengthHint for the general iterable case is that for inputs other than sets or dicts, the assumption is that significant deduplication will occur."

Oh... I'm dumb :) Sorry.

Another option for frozenset only: we may adjust the internal size when the frozenset is created from an iterator.

Not sure how much that really helps. If I understand you correctly, it would be a memory optimization that would require a round of rehashing to use?

If you wanted to make a change that got "guaranteed" better performance, you might add support for dict's dict_keys and dict_items objects (since those have the same uniqueness guarantees as a set or dict, and I could easily see someone creating sets from them to remove the link to the original dict).

If you wanted to get crazy, you might add preallocation support for collections.abc abstract classes equivalent to the built-ins, specifically, Set, Mapping, KeysView and ItemsView. That's probably not a good idea though, since it ends up calling out to Python code more (slowing you down for the general case) and it's probably not as safe, since a user-defined implementation of those abstract classes might not strictly adhere to the same uniqueness or hashability contracts the built-ins provide.

AFAIU, Lev merely posted this because he feared it might be indicative of a bug. Since it isn't a bug but the by-product of a feature, I propose to close this issue as "not a bug".

Regardless, thank you for posting this report! We appreciate the concern.

I restore the original title, my title was a mistake.

title: memory used by frozenset created from set differs from that of frozenset created from other iterable -> set and frozenset constructor should use operator.length_hint to guess the size of the iterator
keywords: + patch
nosy: + vstinner
versions: + Python 3.5, - Python 3.1, Python 2.7, Python 3.2, Python 3.3, Python 3.4
messages: + msg218582