Out of Memory - List with ten million items

Question

I am trying to perform some analysis on a text file with approximately ten million lines containing passwords. I was doing this by reading each line of the file, creating a class with the value as a parameter, and then adding that class to a list. After line 4,000,000 I get an out of memory exception. Short of storing everything in a SQL database, is there anything else that could be done?

Edit: What I am trying to do is take the password, add it to a Credential object, and then add that to a list.

public class Credential
    {
        public string Password { get; set; }

        public static readonly List<string> specialCharacters = new List<string> { "@", "!", "~", "*", "^", "&", "\\", "/", "#", "$", "%", "<", ">", ".", ",", "?", ")", "(", "'", "\"", "+", "=", "_", "-", ";", ":", "{", "}", "]", "[", };

        public Credential(string password)
        {
            this.Password = password;
            this.Mapping = new Dictionary<int, CredentialValueType>();
            for (var i = 0; i < this.Length; i++)
            {
                this.Mapping.Add(i, new CredentialValueType(this.Password[i]));
            }
        }


        public Dictionary<int, CredentialValueType> Mapping { get; private set; }

        public int Length
        {
            get
            {
                return this.Password.Length;
            }
        }
        public bool HasUppercase
        {
            get
            {
                return this.Password.Any(c => char.IsUpper(c));
            }
        }
        public bool HasLowercase
        {
            get
            {
                return this.Password.Any(c => char.IsLower(c));
            }
        }
        public bool HasNumber
        {
            get
            {
                return this.Password.Any(c => char.IsNumber(c));
            }
        }
        public bool HasSpecialCharacter
        {
            get //Verify that this works right...
            {
                return this.Password.Where(a => specialCharacters.Contains(a.ToString())).Count() > 0;
            }
        }
    }

public struct CredentialValueType
{
    public char Value { get; set; }
    public ValueType ValueType { get; set; }

    public CredentialValueType(char val)
    {
        this = new CredentialValueType();
        this.Value = val;
        if (char.IsUpper(val)) this.ValueType = ValueType.UpperCase;
        else if (char.IsLower(val)) this.ValueType = PasswordStats.ValueType.LowerCase;
        else if (char.IsNumber(val)) this.ValueType = PasswordStats.ValueType.Number;
        else this.ValueType = PasswordStats.ValueType.SpecialCharacter;
    }
}

My function is as follows:

public class PasswordAnalyzer
    {
        public IList<Credential> Credentials { get; private set; }

        public PasswordAnalyzer(string file, int passwordField = 0, Delimiter delim = Delimiter.Comma)
        {
            this.Credentials = new List<Credential>();
            using (var fileReader = File.OpenText(file)) //Verify UTF-8
            {
                using (var csvReader = new CsvHelper.CsvReader(fileReader))
                {
                    csvReader.Configuration.Delimiter = "\t";
                    while (csvReader.Read())
                    {
                        var record = csvReader.GetField<string>(passwordField);
                        this.Credentials.Add(new Credential(record));
                        System.Diagnostics.Debug.WriteLine(this.Credentials.Count);
                    }
                }
            }
        }
    }

Answer 1

Rather than creating 4 million dictionaries, you could store your Mapping in an array. I'm sure that'll save a lot of room, but without more information regarding how much memory is being consumed and so forth, it's hard to tell if this will resolve your problem.

I'm assuming your code shown is not your actual code, but if you're just needing to iterate through the lines, use an IEnumerable, and yield each result. You'll be much nicer on the memory requirements since you'll only have one "line" in memory at a time.

Answer 2

If you add the [Serializable] attribute to your Credential and CredentialValueType classes, you can store their state in a file stream rather than an in-memory list.

[Serializable]
public class Credential
{
    //code omitted
}

[Serializable]
public class CredentialValueType
{
    //code omitted
}

Store your credential objects.

var binFormatter = new Runtime.Serialization.Formatters.Binary.BinaryFormatter();

// Open a file stream to write the objects into
using (var fs = new FileStream(@"C:\temp.dat", FileMode.Create))
{

    // Begin looping through your file here.

    // Get a line from the file and convert it to an object
    var credential = new Credential(line);

    // Serialize your Credential object onto the stream.
    binFormatter.Serialize(fs, credential);

    // End looping through your file here

    // Ensure the buffer is flushed before closing the stream.
    fs.Flush();
}

Now your credential objects can be processed one at a time by reading them back and deserializing them.

var binFormatter = new Runtime.Serialization.Formatters.Binary.BinaryFormatter();

using (var fs = new FileStream(@"C:\temp.dat", FileMode.OpenOrCreate, FileAccess.Read))
{
    do
    {
        // Deserialize the credential from the file stream
        var credential = (Credential)binFormatter.Deserialize(fs);

        // Process the credential here

    // Loop until the end of the file
    } while (fs.Position < fs.Length - 1)

}

I have been using this to create feed files that are several GB in size on a machine that has less memory than the size of the file.

The downside is that you can't use LINQ on the list of Credential objects in conjunction with this technique. But if you know the types of things you are scanning for, you can optimize your process so you only need to loop through the CSV file once, and then you can loop through your Credential objects more than once to find the data you are looking for.