Would not testing len(self.difference(other)) == 0 be more efficient? Making a copy of a set and removing elements one by one may be faster than add elements one by one, because we only need to allocate a single chunk of memory for a set.

It depends on relative values of len(self), len(other) and len(set(other)). For example, the following code may be optimal in some cases:

    tmp = set()
    it = iter(other)
    for item in it:
        # if item in self: ?
        tmp.add(item)
        if len(tmp) >= len(self):
            self = self.difference(tmp, it)
            if not self:
                return True
            self.difference_update(other)
            return not self
    else:
        return False  # len(self) > len(set(other))

The disadvantage of such optimizations is that they make the code much more bigger. The current code is small and simple, and good enough in most cases.