[API Proposal]: Add readonly Capacity property to HashSet<T> and Dictionary<K,V> and TrimExcess to HashSet<T>

[theodorzoulias]

Background and motivation

The complexity of enumerating a HashSet<T> or a Dictionary<TKey, TValue> is determined not by its Count, but by its internal capacity. There are scenarios where both of these structures are enumerated frequently, and during their lifetime they might grow very large and then shrink to a small size. In these scenarios it makes sense to call TrimExcess at a point when the current Count has become too small compared to the current capacity, in order to speed up the enumeration of the collection.

If a Capacity property was exposed, it could be used for example like this:

dict.Remove(key);
if (dict.Count < dict.Capacity >> 2) dict.TrimExcess(dict.Count << 1);

In the above example the capacity of the dictionary is reduced to double its size, when its size becomes a quarter of its capacity. So a dictionary with capacity 1000 will have its capacity reduced to 500 when the Count drops below 250.

Currently it's not possible to know the internal capacity of these collections, without keeping track of their Count after every operation that affects their size. Which is quite cumbersome. Or by using reflection, which is not efficient and safe.

Also currently it's not possible to trim a HashSet<T> to a specific capacity, like it's possible with a Dictionary<TKey, TValue>. The HashSet<T>.TrimExcess method has no overload with a capacity parameter.

API Proposal

namespace System.Collections.Generic
{
    public class HashSet<T>
    {
        /// <summary>
        /// Gets the total number of elements the internal data structure can hold
        /// without resizing.
        /// </summary>
        public int Capacity { get; }

        /// <summary>
        /// Sets the capacity of this set to hold up a specified number of elements
        /// without any further expansion of its backing storage.
        /// </summary>
        public void TrimExcess(int capacity);
    }

    public class Dictionary<TKey, TValue>
    {
        /// <summary>
        /// Gets the total number of elements the internal data structure can hold
        /// without resizing.
        /// </summary>
        public int Capacity { get; }
    }
}

Alternative Designs

A TrimExcess overload with a loadFactor parameter would also do the job:

public void TrimExcess(double loadFactor);

...but its usage would not be completely obvious, and it could collide with the existing overload that has an int capacity parameter. Related issue: #23744

Risks

None that I am aware of.

[ghost]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and motivation

The complexity of enumerating a HashSet<T> or a Dictionary<TKey, TValue> is determined not by its Count, but by its internal capacity. There are scenarios where both of these structures are enumerated frequently, and during their lifetime they might grow very large and then shrink to a small size. In these scenarios it makes sense to call TrimExcess at a point when the current Count has become too small compared to the current capacity, in order to speed up the enumeration of the collection.

If a Capacity property was exposed, it could be used for example like this:

dict.Remove(key);
if (dict.Count < dict.Capacity >> 2) dict.TrimExcess();

Currently it's not possible to know the internal capacity of these collections, without keeping track of their Count after every operation that affects their size. Which is quite cumbersome. Or by using reflection, which is not efficient and safe.

API Proposal

public class HashSet<T>
{
    /// <summary>
    /// Gets the total number of elements the internal data structure can hold without resizing.
    /// </summary>
    public int Capacity { get; }
}

public class Dictionary<TKey, TValue>
{
    /// <summary>
    /// Gets the total number of elements the internal data structure can hold without resizing.
    /// </summary>
    public int Capacity { get; }
}

API Usage

As shown above.

Alternative Designs

A TrimExcess overload with a loadFactor parameter would also do the job:

public void TrimExcess(double loadFactor);

...but its usage would not be completely obvious, and it could collide with the existing overload that has an int capacity parameter. Related issue: #23744

Risks

None that I am aware of.

Author:	theodorzoulias
Assignees:	-
Labels:	api-suggestion, area-System.Collections, untriaged
Milestone:	-

[danmoseley]

The usual concern with these very commonly instantiated generic types is that making them larger grows the generated code many times over in a typical app. Clearly the added code here would be minimal but we would need some evidence that this is a common enough need.

[theodorzoulias]

@danmoseley my actual recent case of needing this API was with a HashSet<T>. I don't remember ever needing it with Dictionary<TKey, TValue>, so as far as I am concerned adding it only on the HashSet<T> would be OK.

[danmoseley]

@jkotas what would your concern level be about the bytes generated by a simple getter over a field? int Capacity { get { return _entries.Length; }}

[jkotas]

I am ok with it. It has to also check for _entries == null.

[theodorzoulias]

In retrospect adding the HashSet<T>.Capacity alone will not result in a totally satisfactory solution to my problem, without the HashSet<T>.TrimExcess overload that has an int capacity parameter. This overload currently exists only in the Dictionary<TKey, TValue>, and not in the HashSet<T>. The existing parameterless HashSet<T>.TrimExcess method leaves (almost) no space for future expansion in the collection, and as a result the next Add is likely to trigger an expensive doubling of the collection's capacity.

The scenario that I want to cover involves a HashSet<T> with a constantly changing Count, that never settles down to a final Count during its life time. The desirable shrinking behavior would be to half its capacity when the Count has become a quarter of its capacity. For example a collection with capacity 1000 should have its capacity reduced to 500 when the Count drops below 250.

set.Remove(entry);
if (set.Count < set.Capacity >> 2) set.TrimExcess(set.Count << 1);

An API that might be an even better solution to my problem, if it existed, could be a HashSet<T> with linked nodes, similar to the LinkedDictionary<TKey, TValue> proposed here. That API would offer an enumeration complexity determined by its Count, and not by its capacity. And in my case I care mainly about the performance of enumerating the collection, not about the memory it consumes.

[eiriktsarpalis]

I'm seeing a couple of options here:

1. Update the API proposal to include a HashSet<T>.TrimExcess(int capacity) overload (seems fairly straighforward to incorporate and there is precedent in Dictionary).
2. Close this issue in favor of other solutions?

[ghost]

This issue has been marked needs-author-action since it may be missing important information. Please refer to our contribution guidelines for tips on how to report issues effectively.

[theodorzoulias]

@eiriktsarpalis having the HashSet<T>.TrimExcess(int capacity) API would be really nice. It would open more options at managing the capacity of the collection. Should I include it in this proposal, or create a new API proposal?

[eiriktsarpalis]

Updating this one should suffice, thanks.

[theodorzoulias]

@eiriktsarpalis done!

[theodorzoulias]

I found the related issue #27618, where an additional usage scenario for this API was mentioned by @Grauenwolf in a comment: object pooling scenarios.

[bartonjs]

Video

We looked at some other types in the namespace that had the same pattern of EnsureCapacity(int)+TrimExcess(void) and squared it off to have both get_Capacity+TrimExcess(int).

namespace System.Collections.Generic
{
    public partial class HashSet<T>
    {
        /// <summary>
        /// Gets the total number of elements the internal data structure can hold
        /// without resizing.
        /// </summary>
        public int Capacity { get; }

        /// <summary>
        /// Sets the capacity of this set to hold up a specified number of elements
        /// without any further expansion of its backing storage.
        /// </summary>
        public void TrimExcess(int capacity);
    }

    public partial class Dictionary<TKey, TValue>
    {
        /// <summary>
        /// Gets the total number of elements the internal data structure can hold
        /// without resizing.
        /// </summary>
        public int Capacity { get; }
    }

    public partial class Queue<T>
    {
        public int Capacity { get; }
        public void TrimExcess(int capacity);
    }

    public partial class Stack<T>
    {
        public int Capacity { get; }
        public void TrimExcess(int capacity);
    }
}

[hrrrrustic]

What about PriorityQueue? It also has EnsureCapacity and TrimExsess(), does it make sense to include it to this API for consistency?