Do I understand correctly that the only way to add items to frozen set is to create new instance?

[voroninp]

Yes, the question contains the answer. =D
But my service keeps a huge set of items in memory, and this set should be extended once a day.

If I do it this way:

FrozenSet<Foo> foos =  ...;
IEnumerable<Foo> newFoos = ...;
foos = foos.Concat(newFoos).ToFrozenSet();

I am going to have O(2B+S) requirement of memory size, if I am not mistaken.
Yet I'd like to stay with O(B+S) memory by paying more with CPU cycles.

Are performance gains of using frozen set decrease with the size of the set?

[huoyaoyuan]

Yes, frozen collections are designed for maximum read performance. It's data structure is heavily specialized based on its content.

Yet I'd like to stay with O(B+S) memory by paying more with CPU cycles.

You can try ImmutableHashSet. The immutable collections share data structures between mutations while keeping both versions accessible.

[voroninp]

But ImmutableHashSet is not more performant than regular HashSet.

[Clockwork-Muse]

The use of extra memory (O(2B+S)) should be temporary, though - the older set should be GC'd once the new set is created (and it goes out of scope, etc). Are you sufficiently constrained that that's an issue?

Outside of that, you likely shouldn't be passing around a reference to FrozenSet<T> directly, but rather IReadOnlySet<T>. Which means you could use one of the other "friendlier" types here, if required. Or substitute some in-memory database or something with an equivalent readonly interface....