11
\$\begingroup\$

I am working on an application that reads lots of data from the network and puts it in a grid. I noticed that I could save some memory by reusing existing strings instead of always using the new strings that came off the wire. So here is the class that I wrote to accomplish that. It is simple and it works. But I was wondering if this had a name and, of course, if the code could be improved. One thing that I don't like is that I'm storing two references to each string.

public class StringCollection
{
  private Dictionary<string, string> lookup_ = new Dictionary<string, string>();

  public string Reuse(string s)
  {
    if (s == null)
    {
      return null;
    }
    string existing;
    if (lookup_.TryGetValue(s, out existing))
    {
      return existing;
    }
    else
    {
      lookup_.Add(s, s);
      return s;
    }
  }

  public void Clear()
  {
    lookup_.Clear();
  }

  public int Count { get { return lookup_.Count; } }

}
\$\endgroup\$
  • \$\begingroup\$ Making it generic would only make sense if it's use could be limited to immutable reference types. Plus, I only have a use for it with strings. \$\endgroup\$ – Chris Oct 19 '11 at 2:46
  • 4
    \$\begingroup\$ I question the usefulness of this. You're going to have to create an instance of the string anyway to get the key. What's the point of throwing it in a dictionary as key and value? I think you'll need to come up with a different way to tag the strings to make it more useful. \$\endgroup\$ – Jeff Mercado Oct 19 '11 at 2:57
  • \$\begingroup\$ The point is, you can let the input string go out of scope and be collected if it is already found in the Dictionary. As I said, it works. \$\endgroup\$ – Chris Oct 19 '11 at 3:07
  • 1
    \$\begingroup\$ DOH! I get it now... @JeffMercado, what he means is that he reads the string, and has it on a local scope. Then he checks in the dictionary, and re-uses the old copy. The new copy is discarded when local scope "closes". Otherwise the new string would be used, and not discarded. So, if he does a million cycles reading equal strings, with his method he will create a million strings but discard them and thus only have max two at a time in memory (the one in the dictionary, and new copy that will be checked and discarded); while otherwise he would have a million copies of similar strings. \$\endgroup\$ – ANeves Oct 19 '11 at 6:53
  • 1
    \$\begingroup\$ Sorry, I should have shown the usage of the class as well. ANeves figured it out. And yes, a HashSet would not work and neither would using the hash of a string as the key. \$\endgroup\$ – Chris Oct 19 '11 at 11:47
10
\$\begingroup\$

You might want to look into string interning:

The common language runtime conserves string storage by maintaining a table, called the intern pool, that contains a single reference to each unique literal string declared or created programmatically in your program. Consequently, an instance of a literal string with a particular value only exists once in the system.

While it has some memory-related side-effects, you could avoid having to build up a dictionary like this and throw away allocated strings to keep it updated.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ +1, perfect! But your remark on side-effects is very important: as we can read in the link you provide, the memory allocated for interned String objects is not likely 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. \$\endgroup\$ – ANeves Oct 19 '11 at 7:05
  • \$\begingroup\$ Thanks at least I have a name for the technique now. Yeah, I don't like that side effect. With my implementation, I can control when the strings are eligible for garbage collection. \$\endgroup\$ – Chris Oct 19 '11 at 11:49
1
\$\begingroup\$

You can use a HashSet<string> instead of a dictionary to half the number of references that you keep, but getting the reference out of the hash set is a bit more difficult.

I used this method to solve it:

public class LocalIntern {

  private HashSet<string> _lookup = new HashSet<string>();

  public string Reuse(string s) {
    if (s != null) {
      if (_lookup.Contains(s)) {
        s = _lookup.Where(i => i == s).First();
      } else {
        _lookup.Add(s);
      }
    }
    return s;
  }

  public void Clear() {
    _lookup.Clear();
  }

  public int Count { get { return _lookup.Count; } }

}

Basic function verification:

LocalIntern intern = new LocalIntern();

// store a string    
string data = "asdf";
intern.Reuse(data);

// create another string instance with the same value    
string data2 = String.Concat("as", "df");
// verify that they are in fact separate instances
Debug.Assert(!Object.ReferenceEquals(data, data2));

// look for the string
string d = intern.Reuse(data2);
// verify that the string was replaced
Debug.Assert(Object.ReferenceEquals(data, d));
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hmm, I thought it would have been a simple index into the set to grab the value. I never realized that we couldn't do that. On second thought, using the dictionary might have been the best thing to do to keep it O(1). \$\endgroup\$ – Jeff Mercado Oct 19 '11 at 8:03
  • 1
    \$\begingroup\$ @ANeves: Well, not perfect as you get a nasty O(n) lookup when you get the reference from the hash set, so that's a trade-off for the reduced memory use. That could be solved by implementing the hashing yourself instead of using HashSet, but that's a lot more code... \$\endgroup\$ – Guffa Oct 19 '11 at 9:40
  • \$\begingroup\$ This trade-off was not acceptable for me, which is why I went with the Dictionary. It seems like there should be a way to only store one reference and also keep the speed of the Dictionary. \$\endgroup\$ – Chris Oct 19 '11 at 23:14
  • \$\begingroup\$ In most cases, the memory used by the duplicate references will only be a small fraction of the memory used by the strings themselves. \$\endgroup\$ – Chris Oct 19 '11 at 23:18
0
\$\begingroup\$

The ideal thing here would be a WeakDictionary<string,string> (or better yet, a variation of a WeakHashSet<T> which allowed one to retrieve a reference to the stored item which matched a supplied key). Such a data structure would ensure that strings were shared whenever possible (a behavior which would not only reduce memory requirements, but also expedite comparisons among them, since comparing two distinct million-character strings that happen to be equal will take much longer than comparing two references to the same string). If one uses a Dictionary<string,string>, which is the best of the pre-existing classes for the purpose, it may be tricky to ensure that strings get kept as long as they may be useful, without having the dictionary keep them around even after they've become useless (if a string value has been used once before but all references outside the dictionary have been abandoned, having the string remain in the dictionary past the next GC cycle will generally serve no purpose; even if the same sequence of characters gets read again, it would generally be faster to have the old string evaporate and store a new string in the dictionary, than to have to compare all the characters in the new string against the ones in the old string and abandon the new one).

| improve this answer | |
\$\endgroup\$

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.