Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Task: Create lower-level implementation of LinkedHashSet<T> #95

Open
NightOwl888 opened this issue Aug 14, 2024 · 1 comment
Open

Task: Create lower-level implementation of LinkedHashSet<T> #95

NightOwl888 opened this issue Aug 14, 2024 · 1 comment
Labels
design is:enhancement New feature or request pri:normal up for grabs This issue is open to be worked on by anyone
Milestone

Comments

@NightOwl888
Copy link
Owner

Our current LinkedHashSet<T> implementation uses a quirk of the HashSet<T> design to produce the correct ordering, but it involves expensive allocations when an item is removed followed by an add or insert. While this is somewhat unlikely in production, these allocations can add up and result in additional undesired GC overhead.

.NET 9.0 now includes an OrderedDictionary<TKey, TValue> that should provide the correct ordering functionality. It is MIT licensed, so there is no issue with copying it.

I believe we can just bring over the implementation of the hash code calculation and change the entries array from a KeyValuePair<TKey, TValue> to type T. But we need to make sure that a null value for T is supported.

We should keep the same API members (in the same order in the source code) that we have currently, but replace the implementation to use the new arrays instead of cascading the call to HashSet<T>. See the J2N and Microsoft implementations of HashSet<T> to get an idea of how each member can be implemented. We should be keeping all of the same optimizations that Microsoft has for these methods (looking at the latest .NET 8.0 implementation).

We already have tests in J2N.Tests.xUnit to confirm it behaves as expected, we just need to create an implementation that passes the tests.

@NightOwl888 NightOwl888 added is:enhancement New feature or request design pri:normal up for grabs This issue is open to be worked on by anyone labels Aug 14, 2024
@NightOwl888 NightOwl888 added this to the 2.1 milestone Aug 14, 2024
@NightOwl888
Copy link
Owner Author

NightOwl888 commented Oct 12, 2024

The current thinking on this is to name the class derived from OrderedDictionary<TKey, TValue> as OrderedHashSet<T>. "Linked" refers to a specific implementation that uses linked lists (fragmented memory), and OrderedDictionary<TKey, TValue> instead uses blocks of adjacent memory elements. There are pros and cons to each approach, and both might be a reasonable replacement for LinkedHashSet<T> in different use cases. We could probably port the data structure of LinkedHashSet<T> from Apache Harmony later, but I think we should include the OrderedHashSet<T> based on OrderedDictionary<TKey, TValue> first since it is optimized for use in .NET.

@NightOwl888 NightOwl888 modified the milestones: 2.1, Future, 2.2 Oct 13, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
design is:enhancement New feature or request pri:normal up for grabs This issue is open to be worked on by anyone
Projects
None yet
Development

No branches or pull requests

1 participant