1
\$\begingroup\$

I need to use large strings as a dictionary keys, and I want to optimize the repetitive GetHashCode() and Equals() calls in it.

The number of keys will be quite small (<1000), but each string length will be very big (it's generated SQL queries cache), and I expect a lot of hot lookups.

My idea is to make sure that each wrapped string is interned, so that we can rely on the string references of the same strings to be always the same:

public sealed class InternedString : IEquatable<InternedString>
{
    public InternedString(string s) => String = string.Intern(s);

    public string String { get; }

    public override bool Equals(object obj) => String.Equals(obj);

    public bool Equals(InternedString other) => String.Equals(other?.String);

    public override int GetHashCode() => RuntimeHelpers.GetHashCode(String);

    public static bool operator ==(InternedString l, InternedString r) =>
        l?.String == r?.String;

    public static bool operator !=(InternedString l, InternedString r) => !(l == r);
}

Can you review this class, with special attention to safety?

UPDATE

You can check the final code and benchmarks here: https://github.com/astef/InternedString

Usage:

// O(n) operation happens only here, so we want to re-use this object
var iString = new InternedString("typically_a_very_long_string_key");

// now any call to `GetHashCode()` and `Equals(...)` will run in a constant time
mySet.Add(iString);
\$\endgroup\$
  • \$\begingroup\$ It sounded like you were only asking for an opinion, I edited your question so that it fits more our format. \$\endgroup\$ – konijn Oct 25 '19 at 17:45
  • \$\begingroup\$ Safety against what? \$\endgroup\$ – Mast Oct 25 '19 at 18:51
  • \$\begingroup\$ I mean safety in general. Against bugs, against unexpected behavior. In particular, I was not sure if RuntimeHelper.GetHashCode is doing what I need, and if interning is reliable technique for this purposes, and if I'm not missing any corner-cases. It's just a few lines, but very low-level for me, and very critical for a program. \$\endgroup\$ – astef Oct 25 '19 at 21:48
  • \$\begingroup\$ Could you please show the code using InternedString? \$\endgroup\$ – Kiryl Z Nov 14 '19 at 11:08
  • \$\begingroup\$ @KirylZ Check the Usage section here github.com/astef/InternedString. For a more real-world example, imagine a sql insert query which is need to be generated at some point, then executed once with saving results to dictionary, and then the results must be queried by a sql command. \$\endgroup\$ – astef Nov 14 '19 at 12:37
3
\$\begingroup\$

Assuming each time you receive a new query you create an instance of InternedString to get/add another item from/into the dictionary, the performance benefit seems questionable:

  1. Impact of string.Intern

a) It needs to calculate a hash of the original string to make a lookup in the pool of strings

b) From official documentation -

The memory allocated for interned String objects is not likely to be released until the common language runtime (CLR) terminates. The reason is that the CLR's reference to the interned String object can persist after your application, or even your application domain, terminates.

  1. High rate of collisions seems to be the only beneficial scenario

The equality comparison that Dictionary does for items in the bucket is the case when you implementation might win when the bucket grows huge.

But do you really have that many collisions?

P.S.

Comparing strings you're not using String.ReferenceEquals to compare references of the interned strings, but rather == operator which for (sting vs string) leads to values comparison.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 2 - No, Dictionary and other hash-based collections call both GetHashCode and Equals on each lookup, not only for comparing items in a bucket. \$\endgroup\$ – astef Nov 14 '19 at 12:06
  • \$\begingroup\$ PS - good point. Even while in a "true" comparison case it will lead to a reference comparison, in a "false" scenario O(n) comparison will be performed. It can be optimized \$\endgroup\$ – astef Nov 14 '19 at 12:17
  • \$\begingroup\$ PS- I think that overloading == is a bad idea at all. And Equals is definitely need to do a reference comparison \$\endgroup\$ – astef Nov 14 '19 at 12:26
  • \$\begingroup\$ Agreed on the second one. Will remove it. Good catch! As for ==, the general recommendation is to avoid using the == and != operators when you test for equality \$\endgroup\$ – Kiryl Z Nov 14 '19 at 13:10
  • \$\begingroup\$ Although given it more thought, the second point is still valid if remove the part "more than one items". As the more items it the bucket, the more gain you get comparing by references \$\endgroup\$ – Kiryl Z Nov 14 '19 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.