Thinq - A Linq Experiment

Thinq - A Linq Experiment

   View/Download the source code from the project's GitHub



   So I wrote a program, just an experiment, where I was making a range class using IEnumerables (C#), and each element doesn't have to increment by one, but any amount. so I was creating ranges like 7 to 10 million, increment by 7, so upon enumeration it would yield multiples of 7. This is also called arithmetic progression.

   Then I started combining different multiples with query operators like Where operator or Intersect like IEnumerable result = multiples7.Intersect(multiples13.MoveNext()), essentially creating a function that keeps only those numbers that are multiples of both 7 and 13, starting with the least common multiple.

   So I began testing. After some playing, I decided to take the first 7 primes, and find any common multiples to them between 1 and 10 million. Much to my surprise, it found all the common multiples of the first 7 prime numbers under 10 million (there are only two of them, 4849845 & 9699690), and it did it in 500 milliseconds on some very modest hardware (1 core, 2.16GHz, 4GB ram).

   I bumped up the ceiling to 50 million and I got an OutOfMemoryException because the IEnumerable holds on to every value it gets from the function MoveNext(). I threw in some metrics and discovered that it took about 3 seconds and some 32-million, 64-bit integers for my computer to declare 'out of memory'.

   Well, at least it was fast, even if it did eat up all my ram in 3 seconds, it was still promising. 

   The solution was to create an IEnumerator that was aware of the arithmetic sequences that constrained the results set. When MoveNext() is called repeatedly during enumeration, I avoid the infinite memory requirement by restricting the result set returned from MoveNext(); it returns the next whole number that is divisible by every arithmetic sequence's 'common difference', or increment value. In this way, you have created a enumerable sequence that is the _intersection_ of all of the sequences.

   The enumerator is prevented from running to infinity by obeying two limits: A maximum numeric value (cardinal) that GetNext() will return to ("results less than 50 million") and a maximum quantity of results (ordinal) that GetNext() yields ("the one millionth result").    If either of these limits are exceeded, the while loop will fail to evaluate to true. It is very common for my processor-intensive, long running or 'mathy' applications to employ a temporal limit (maximum time-to-live) or support cancellation, but this little experiment has been so performant that I have been able to get by without one.

   So what kind of improvement did we get out of our custom enumerable? I can now find all the common factors for the first 8 prime numbers up to 1 billion in 25 seconds! I was impressed; the application used to max out around 50 million and run out of memory, and now it can investigate to one billion in a reasonable amount of time and the memory it uses is not much more than the 8 or so integers in the result set. 1 billion, however seems to be the sweet spot for my single 2.13 GHz laptop. I ran the same 8 primes to 2 billion and it took 1 minute, 12 seconds:

TIME ELAPSED: 01:12.38
LCM[3,5,7,11,13,17,19,23] (max 2,000,000,000)

17 FACTORS:

111546435 
223092870 
334639305 
446185740 
557732175 
669278610 
780825045 
892371480 
1003917915 
1115464350 
1227010785 
1338557220 
1450103655 
1561650090 
1673196525 
1784742960 
1896289395

Lazy IEnumerable file reader class: When to inherit from IDispose?

    Need to read just the few couple lines from a gigantic data file? Or maybe you need a forward-only, load-only-what-you-need file reader pattern? Here is a construct I have been toying with, its a class that treats a file stream like an IEnumerable.

    Note added 8/1/15: TODO: Add constructor overload that accepts the starting filepointer position, optional ending filepointer position.

    This has the benefit of not using any resources if you never use it, allows you to incrementally read gigantic files without loading it all into memory (you might need to call the StreamReader.DiscardBufferedData() method every once in a while), and because its IEnumerable, you can write queries against it that are lazy; they don't actually execute until the run-time actually NEEDS it, such as calling the IEnumerable.ToList() or 'Count()' extensions, for example. Be careful with ToList() if the file is a gigabyte or more, as calling ToList() will cause the whole thing to be read right then.

    If instead you just need to iterate through each line only until you find what you are looking for, or use Linq and a predicate to search for a particular line that satisfies a condition, then this pattern will save your application from having the load the whole thing in memory:

public class EnumerableFileReader
{
    public FileInfo File { get { return _file; } }
    public bool FileExists { get { return _file.Exists; } }

    private FileInfo _file;

    public EnumerableFileReader(string fileLocation)
        : this(new FileInfo(fileLocation))
    {
    }

    public EnumerableFileReader(FileInfo file)
    {
        if (!file.Exists)
        {
            throw new FileNotFoundException();
        }

        _file = file;
    }

    public IEnumerable FileLines()
    {
        if (!FileExists) yield break;

        string line;
        //long internalBufferSize = 0;

        using (StreamReader reader = _file.OpenText())
        {
            while ((line = reader.ReadLine()) != null)
            {
                //if (internalBufferSize++ > 90000) {   reader.DiscardBufferedData(); internalBufferSize = 0; }
                yield return line;
            }
        }

        yield break;
    }
}

    It struck me that it might be a good idea to make the class inherit from IDisposable, so the StreamReader doesn't get left around in memory, holding a file open. Indeed; all those yield keywords make it look like the stream object will just hang around there if FileLines is never called again to finish the enumeration. However, it turns out this is probably not necessary but the answer is, as you might expect: IT DEPENDS. It depends... on how you are going to use the class. Looking into the subject, I discovered that when you use the yield keyword, the compiler generates a nested class which implements the IEnumerable, IEnumerator and IDisposable interfaces and stores all context data for you under the hood. I'm not going to drop the IL (or CIL) here, but if you are curious, just open up your IEnumerable class in ILSpy. Just make sure you change the language in the drop-down box at the top from C# to IL, otherwise it will be hidden.

    So just when is our class disposed of? Well anytime you explicitly call Dispose on the Enumerator or the Stream, which one might expect. However, this will dispose of a lot more than just the stream or the enumerator alone, but all of the associated constructs that are generated around the enumerator/yield pattern. to be disposed of. Dispose will also be called at the end of enumeration. This includes when you run out of things to enumerate, any time you use the yield break or return keyword, or the program flow leaves the using statement surrounding the Stream. Here is something I didn't know: Dispose is also called when you call the IEnumerable.First() or FirstOrDefault() extension. Also, any time you use a foreach loop around the IEnumerator, the object will get disposed after you are done looping or after you break or leave the loop.

  

So, in short: As long as you're using LINQ extensions or foreach loops, the disposal is taken care of for you automatically. However, if you are manually calling the Enumerator().MoveNext() on the method, then you need to call dispose yourself, or rather, implement the IDisposable pattern.

    Being able to use EnumerableFileReader in a using statement/disposable pattern would likely be expected of a file reader class. You could have your dispose method set a boolean flag and then call FileLines(), and add an if statement in the while look of your FileLines() method that will yield break when the dispose flag is set to true, but cleaning up properly can be tricky if your IEnumerator has more than one or two return yield statements. I would instead suggest that that we use one of the tricks we just leaned above and just have our Dispose() function call .FirstOrDefault() on the FileLines() method:

public class EnumerableFileReader : IDisposable
{
[...]

    public void Dispose()
    {
        FileLines().FirstOrDefault();
    }

[...]
}