1

I have array of nearly 1,000,000 records, each record has a field "filename".

There are many records with exactly the same filename.

My goal is to improve memory footprint by deduplicating string instances (filename instances, not records).

.NET Framework 2.0 is a constraint. no LINQ here.

I wrote a generic (and thread-safe) class for the deduplication:

public class Deduplication<T>
    where T : class
{
    private static Deduplication<T> _global = new Deduplication<T>();

    public static Deduplication<T> Global
    {
        get { return _global; }
    }

    private Dictionary<T, T> _dic;// = new Dictionary<T, T>();
    private object _dicLocker = new object();

    public T GetInstance(T instance)
    {
        lock (_dicLocker)
        {
            if (_dic == null)
            {
                _dic = new Dictionary<T, T>();
            }

            T savedInstance;
            if (_dic.TryGetValue(instance, out savedInstance))
            {
                return savedInstance;
            }
            else
            {
                _dic.Add(instance, instance);
                return instance;
            }
        }
    }

    public void Clear()
    {
        lock (_dicLocker)
        {
            _dic = null;
        }
    }
}

The problem with this class is that it adds a lot of more memory usage, and it stays there until the next GC.

I searching for a way to reduce the memory footprint without adding a lot of more memory usage and without waiting for the next GC. Also i do not want to use GC.Collect() because it freezes the GUI for a couple of seconds.

DxCK
  • 4,402
  • 7
  • 50
  • 89
  • No LINQ, no answer :-&( – evanmcdonnal Sep 12 '13 at 23:41
  • If I read you correctly, you have two problems to solve. One is that all the string objects still have to get created first and then garbage collected after they're "looked up". The second is that Dictionary may not be the most space efficient structure for your need. What is the average length of a filename, and what is the ratio of duplicates? – hatchet - done with SOverflow Sep 12 '13 at 23:57
  • I creating those strings in my code from UTF-16 encoded bytes. average length of a filename is 26.2 chars. 57.6% of filenames are duplicate of another filename in the other 42.4%. – DxCK Sep 13 '13 at 00:35
  • You could try running a CRC32 on each filename and store it in a hashset. However you might get collisions. – ChrisWue Sep 13 '13 at 03:33

3 Answers3

1

If you do not want to intern your strings. You could take a similar approach to Java 8's string deduplication (which is done by the GC on the heap).

  1. Get the hash values of the strings as they are added.
  2. If the hash does not exist, associate it with the string.
  3. If the hash does exist, compare the strings with the same hash character by character.
  4. If your comparison matches, store a reference to the original string instead of a new copy.

This would reduce your memory footprint assuming you have a lot of duplicates, but interning would probably perform a lot better as it is done at a lower level right on the heap.

Chris Shepley
  • 41
  • 3
0

You could stick all strings in a prefix tree. Depending on how different you path names are this should automatically deduplicate common substrings. A quick search on google yielded in this C# implementation.

ChrisWue
  • 18,612
  • 4
  • 58
  • 83
-1

I'd recommend you double-check that your memory footprint isn't already optimized. .NET automatically interns duplicate strings on the heap, which means you can have multiple identical String objects point to the same memory address. Just call String.Intern(targetString). That's why Strings are immutable, and StringBuilder exists.

More immediately, if you're having trouble with the leftover strings on the heap, you can kick off a garbage collection right after you finish (or even periodically during the run):

GC.Collect();

Eric Lloyd
  • 509
  • 8
  • 19