This blog has moved to Medium

Subscribe via email


Posts tagged ‘C#’

« Previous Entries

Playing around with PLINQ and IO-bound tasks

30/11/09, 1:04


I recently downloaded Visual Studio 2010 beta, and took the chance to play with PLINQ. PLINQ, for those of you in the dark ages of .Net Framework 2.0, is parallel LINQ – an extension to the famous query language that makes it easy to write parallel code (essential to programming in the 21th century, in the age of the many-core).

A code sample, as usual, is the best demonstration:

public static int CountPrimes(IEnumerable<int> input)
{
    return input.AsParallel().Where(IsPrime).Count();
}
 
private static bool IsPrime(int n)
{
    for (int i = 2; i*i < n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

This code sample, regardless of using an inefficient primality test, is fully parallel. PLINQ will utilize all your cores when running the above code, and I didn’t have to use any locks, queues, threadpools or any of the more complex tools of the trade. Just tell PLINQ “AsParallel()”, and it works.

I hit some gotcha when I tried to compare the parallel performance with the sequential one. Do you spot the problem in the following code?

public static void CountPrimesTest(IEnumerable<int> input)
{
    // parallel benchmark 
    var timer = new Stopwatch();
    timer.Start();
    CountPrimes(input.AsParallel());
    timer.Stop();
    Console.WriteLine("Counted primes in parallel took " + timer.Elapsed);
 
    // sequential benchmark
    timer = new Stopwatch();
    timer.Start();
    CountPrimes(input);
    timer.Stop();
    Console.WriteLine("Counted primes sequentially took " + timer.Elapsed);
}

This is all fine and dandy when the task at hand is CPU bound, but works pretty miserabbly when your task is IO bound, like downloading a bunch of web pages. Next, I simulated some IO-bound tasks (I used Sleep() to emulate IO – basically not using a lot of CPU for every task):

[ThreadStatic]
private static Random _random;
 
public static List<string> FindInterestingDomains(IEnumerable<string> urls)
{
    // select all the domains of the interesting URLs
    return urls.AsParallel().Where(SexFilter).
                Select(url => new Uri(url).Host).ToList();
}
 
public static bool SexFilter(string url)
{
    if (_random == null)
        _random = new Random();
 
    // simulate a download
    Thread.Sleep(1000);
    var html = "<html>" + _random.Next() + "</html>";
    return html.Contains("69");
}

Testing this with a list of 10 URLs took 5 seconds, meaning LINQ again spun only two cores, which is the number of cores on my machine. This really sucks for IO bound tasks, because most of the time the threads are idle, waiting on IO. Let’s see if we can speed this up:

// Use WithDegreeOfParallelism to specify the number of threads to run
return urls.AsParallel().WithDegreeOfParallelism(10).Where(SexFilter).
              Select(url => new Uri(url).Host).ToList();

This appeared not to work at first, because WithDegreeOfParallelism is just a recommendation or upper bound. You can ask PLINQ nicely to run with ten threads, but it will only allocate two if it so chooses. This is yet another example of C# being more magical than Java – compared to Java’s rich ExecutorService, PLINQ offers less fine grained control.

However, further testing revealed the damage is not so horrible. This is what happened when I put the above code in a while(true):

Tested 10 URLs in 00:00:05.0576333
Tested 10 URLs in 00:00:03.0018617
Tested 10 URLs in 00:00:03.0013939
Tested 10 URLs in 00:00:03.0013175
Tested 10 URLs in 00:00:04.0018983
Tested 10 URLs in 00:00:03.0024044
Tested 10 URLs in 00:00:01.0004407
Tested 10 URLs in 00:00:01.0007645
Tested 10 URLs in 00:00:01.0007280
Tested 10 URLs in 00:00:01.0003358
Tested 10 URLs in 00:00:01.0003347
Tested 10 URLs in 00:00:01.0002470

After some trial and error, PLINQ found that the optimal number of threads needed to run this task under its concurrency guidelines is ten. I imagine that if at some point in the future the optimal number of threads change, it will adapt.

P.S.
If you found this interesting, wait till you read about DryadLINQ – it’s LINQ taken to the extreme, run over a cluster of computers.

Tags: , , , , , ,
Comments Off on Playing around with PLINQ and IO-bound tasks

Java is less magical than C#

20/8/09, 21:42

I have been programming in C# for several years now, and recently made the switch to Java (at least for now). I noticed that Java, as a language, is “less magical” than C#.

What do I mean by that is that in C# things are usually done for you, behind the scenes, magically, while Java is much more explicit in the toolset it provides. For example, take thread-local storage. The concept is identical in both langauges – there is often a need for a copy of a member variable that’s unique to the current thread, so it can be used without any locks or fear of concurrency problems.

The implementation in C# is based on attributes. You basically take a static field, annotate it with [ThreadStatic], and that’s it:

[ThreadStatic]
private static ThreadUnsafeClass foo = null;
 
private ThreadUnsafeClass Foo
{
  get
  {
    if (foo != null)
      foo = new ThreadUnsafeClass(...);
 
    // no other thread will have access to this copy of foo
    // note - foo is still static, so it will be shared between instances of this class.
    return foo;
  }
}

How does it work? Magic. Sure, one can find the implementation if he digs deep enough, but the first time I encountered it I just had to try it to make sure it actually works, because it seemed too mysterious.

Let’s take a look at Java’s equivalent, ThreadLocal. This is how it works (amusingly enough, from a documentation bug report):

public class SerialNum {
     // The next serial number to be assigned
     private static int nextSerialNum = 0;
 
     private static ThreadLocal<Integer> serialNum = new ThreadLocal<Integer>() {
         protected synchronized Integer initialValue() {
             return new Integer(nextSerialNum++);
         }
     };
 
     public static int get() {
         return serialNum.get();
     }
 }

No magic is involved here – get() gets the value from a map, stored on the calling Thread object (source code here, but the real beauty is that’s it’s available from inside your IDE without any special effort to install it).

Let’s look at another example – closures.

In C#, you can write this useful piece of code:

var list = new List<int>();
...
// find an element larger than 10
list.Find(x => x > 10);

You can also make this mistake:

var printers = new List<Action>();
...
foreach (var item in list)
{
  printers.Add(() => Console.WriteLine(item));
}
Parallel.Foreach(printers, p => p())

An innocent reader might think this prints all the items in list, but actually this only prints the last items list.Count times. This is how closures work. This happens because the item referred to in the closure is not a new copy of item, it’s actually the same item that’s being modified by the loop. A workaround is to add a new temporary variable like this:

foreach (var item in list)
{
  int tempItem = item;
  printers.add(() => Console.WriteLine(tempItem));
}

And in Java? Instead of closures, one uses anonymous classes. In fact, this is how they are implemented under the hood in C#. Here the same example, in Java:

for (Integer item : list)
{
  final int tempItem = item;
  printers.add(new Action(){
    public void doAction()
    {
      // can't reference item here because it's not final.
      // this would have been a compilation error
      // system.out.println(item);
      System.out.println(tempItem);
    });
}
...

Notice it’s impossible to make the mistake and capture the loop variable instead of a copy of it, because Java requires it to be final. So … less powerful perhaps than C#, but more predictable. As a side note, Resharper catches the ill-advised capturing of local variables and warns about it.

I myself rather prefer the magic of C#, because it does save a lot of the trouble. Lambdas, properties, auto-typing variables… all these are so convenient it’s addictive. But I have to give Java a bit of credit, as the explicit way of doing stuff sometimes teaches you things that you just wouldn’t have learn cruising away in C# land.

Tags: , , , , ,
3 Comments

On the evils of yield

9/3/09, 23:14

I absolutely love yield. Don’t we all? It simplifies writing enumerations to the point of absurdity. Simplicity, however, is a double-edged sword – I spent the better part of this day debugging a most evil bug, that resulted from over-yielding.

At Delver (now Sears) we have a file-based repository containing millions of items. We try to make things as efficient as possible, and sometime we overdo it. Our sin for today is using IEnumerable a bit too much. This repository was designed to be:

  1. Scalable (within our constraints) – should able to hold several million tasks
  2. Fast
  3. Relatively convenient to use – the user should be able to iterate on it using foreach, for one.

To accomplish 1 and 2, we avoided allocating large in-memory structures because they wouldn’t be able to hold the amount of items we’re talking about. To provide a convenient interface, we used IEnumerable.

Here is a mock-up of the code (for simplicity, it doesn’t use the disk but an in-memory serialized dictionary):

public class PeopleRepository
{
    private readonly Dictionary _serializedPeople = new Dictionary();
 
    public void Save(Person person)
    {
        // this method, as innocent as it looks, make it more difficult to discover the bug. See ahead.
        Save(new[]{person});
    }
 
    public void Save(IEnumerable<Person> people)
    {
        var serializedPeople = from p in people select new {p.ID, p.Serialized};
        foreach (var p in serializedPeople)
            _serializedPeople[p.ID] = p.Serialized;
    }
 
    public IEnumerable<Person> Read(Predicate<Person> predicate)
    {
        foreach (int id in _serializedPeople.Keys)
        {
            var person = new Person(_serializedPeople[id]);
            if (predicate(person))
                yield return person;
        }
    }
}

The bug I tracked was that updates to the repository were not taking place, but instead were simply ignored. The first thing I tried, was writing a simple test:

// Setup
var repository = new PeopleRepository();
repository.Save(new Person(1, " John")); // oops, I put an extra space here
 
// Find &amp; Fix John
var john = repository.Read(p => p.ID == 1).First();
john.Name = john.Name.Trim();
 
// Fix poor John back to the repository
repository.Save(john);
 
// Make sure john is saved properly
john = repository.Read(p => p.ID == 1).First();
if (john.Name != "John")
    throw new Exception();

Sadly, this test passed with flying colors. More debugging revealed the problem happened because both our Read and Save methods returned IEnumerables. It appears that Read() read the items and made the required updates … but … when writing the items back to the repository, it iterated on them.

Let me repeat – we read some items, iterated on them and modified some, saved and thus reiterated. Bam!

Bam

The second iteration didn’t iterate on the modified items – because the internal implementation of Read used a yield statement, there was no actual collection returned. So the second iteration just caused the repository to re-read all the items from disk, and ignore the modified items.

Conclusion: whenever you see methods that return IEnumerables, be suspicious. Odds are it should return a List or Collection. And whatever you do, watch out from feeding that IEnumerable back to the same repository.

Here is a final test that almost reproduces the problem. It crashes with a CollectionWasModified exception, while my actual test & code just silently failed (because the repository I mocked up here doesn’t save to the disk, but rather keep everything in-memory).

// Setup
var repository = new PeopleRepository();
repository.Save(new Person(1, " John")); // oops, I saved a space in front of John
 
// Let's read and fix all people starting with a space
var people = repository.Read(p => p.Name.StartsWith(" "));
foreach (var person in people)
    person.Name = person.Name.Trim();
 
// store the modified points back
repository.Save(people);
Tags: , , , , ,
2 Comments

Efficient multiple totient calculation in C#

7/3/09, 20:30

For a certain problem in Project Euler, I needed a function to calculate the Totient of all numbers in [2..10^7]. Going over them one at a time and factorizing them would take too long, so I used a variant of the prime sieve to speed up the calculation. The code is not overly documented, but it should be relatively easy to grok once you understand how to calculate the Totient of a single number.

The time complexity is O(n log n).

/// <summary>
/// Return an array of all totients in [0..n-1]
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static long[] CalcTotients(long n)
{
    long[] divisors = GetDivisors(n);
    long i;
    var phi = new long[n];
    phi[1] = 1;
    for (i = 1; i < n; ++i)
        CalcTotient(i, phi, divisors);
 
    return phi;
}
 
/// <summary>
/// For every integer, the result will contain its lowest divisor.
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
private static long[] GetDivisors(long n)
{
    var divisors = new long[n];
    divisors[1] = 1;
    long i;
    for (i = 2; i < n; ++i)
    {
        if (divisors[i] != 0)
            continue;
 
        for (long j = i; j < n; j += i)
            divisors[j] = i;
    }
    return divisors;
}
 
private static long CalcTotient(long i, long[] phi, long[] divisors)
{
    if (phi[i] != 0)
        return phi[i];
 
    long div = divisors[i];
    if (div == i)
    {
        phi[i] = i - 1;
        return phi[i];
    }
 
    long lower = 1;
    int exp = 0;
    while ((i > 1) && (i % div == 0))
    {
        i /= div;
        lower *= div;
        exp++;
    }
    if (i == 1)
    {
        phi[lower] = ((long)Math.Pow(div, exp - 1)) * (div-1);
        return phi[lower];
    }
    phi[i*lower] = CalcTotient(i, phi, divisors) *
                         CalcTotient(lower, phi, divisors);
    return phi[i*lower];
}
Tags: , , , , , ,
Comments Off on Efficient multiple totient calculation in C#

Most annoying Euler problem yet

4/3/09, 1:39

In Problem 54, you receive a set of poker hands, and are asked to count the number of times Player 1 won. No algorithmic or mathematical intelligence here, just coding. I advise skipping it in favor of more interesting problems.

Some say the Chinese word for “crisis” is composed of “danger” and opportunity (others do not). I took the time to play with LINQ and lambdas for the first time (in C# at least), and it was a great deal of fun – even at my home computer which is currently suffering from lack of Resharper.

SPOILER SPOILER SPOILER

Here’s a bit of LINQ goodness. The method I used (SPOILER SPOILER) to calculate the winner of two similar hands is a weighted sum. I summed all the best cards with a high weight, then added less important cards with lower weight (for example, 3 twos get more weight each than 2 kings in the same hand).

Once I found which value is the best in a given hand (2 in the above hand), I used this little one liner to count the number of cards equal to the maximal value.

_cards.Where(c => c.Value == bestValue).Count();

Terse is the new black.

Tags: , , , , , ,
Comments Off on Most annoying Euler problem yet

Don’t switch your lock object mid-lock

18/2/09, 16:09

Today I encountered a weird exception from List.AddRange()

[Exception(System.ArgumentException)]:
Destination array was not long enough. Check destIndex and length, and the array's lower bounds.

Looking at the code, I saw it multithreaded like this:

List<int> tmp;
lock (_list)
{
    tmp = _list;
    _list = new List<int>(1);
}
 
// use tmp object like it's owned exclusively by this thread

The thinking here was to avoid “expensive” operations inside the lock, so we locked _list only for enough time to replace it with a new list, and then do the heavy lifting on the tmp variable (assuming no other threads can interfere). Most locks are used immutably – the lock object itself rarely changes identity.

Well, it appears the above code is indeed not thread safe. Here what I recon happened:

  1. Thread 1 acquired a lock on _list
  2. Thread 2 tried acquiring the lock, but blocked.
  3. Thread 1 changed _list to a new instance and released the lock on the old value of _list
  4. Thread 3 came and acquired the lock on the new value of _list
  5. Thread 2 was now released and acquired the lock on the old value of _list

At this point, both thread 2 & 3 got inside the critical section and grabbed the same value of _list (the new one) as their “exclusive” tmp, and then worked on it concurrently outside the lock. The easy solution is not to lock on an object whose identity (not state) changes. In this case, a lock either on the containing object or on a new custom object (object _lock = new object()) should do the trick.

This program reproduces the problem:

using System;
using System.Collections.Generic;
using System.Threading;
 
namespace tstlock
{
    public class LockTester
    {
        private List<int> _list = new List<int>(1);
 
        public void Run()
        {
            var threads = new Thread[40];
            for (int i = 0; i < threads.Length; ++i)
            {
                threads[i] = new Thread(ThreadFunc);
                threads[i].Start();
            }
            foreach (var thread in threads)
                thread.Join();
        }
 
        private void ThreadFunc()
        {
            for (int i = 0; i < 1000000; ++i)
            {
                List<int> tmp;
                lock (_list)
                {
                    tmp = _list;
 
                    // at this point _list is always supposed to be an empty list
                    // because all the additions to it are after the new list is allocated
                    _list = new List<int>(1);
                }
 
                var array = new []{1,2,3,54,5,6};
                tmp.AddRange(array);
                if (tmp.Count != array.Length)
                {
                    throw new Exception("Bug - tmp is not local as we thought");
                }
            }
        }
    }
}
Tags: , ,
3 Comments

C# Alternative to Directory.GetFiles()

16/2/09, 17:42

A while ago I was working with directories with thousands of files, and wanted to get only the first few files in the directory.
Directory.GetFiles() always returns the entire directory, and so is rather slow on huge directories.

I found and used this excellent post with a managed C++ class that does exactly what I wanted. A caveat I had with the code is that it didn’t work on 64bit machines when run in 64bit mode (instead of in WOW64 compatibility mode). Today I finally got the time to translate it to C#, so we can compile it as part of our solution instead of referencing a pre-built C++ dll. I’m also included a small wrapper DirectoryUtils, that provides an easier way to get a list of N files in a dir (simple API wrapper), plus an additional method to get a random selection of N files from that directory.

using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.IO;
using System.Runtime.InteropServices;
using Microsoft.Win32.SafeHandles;
using NUnit.Framework;
using FILETIME=System.Runtime.InteropServices.ComTypes.FILETIME;
using IEnumerator=System.Collections.IEnumerator;
 
namespace Semingo.IntegrationTests.DirectoryUtils
{
    public static class DirectoryUtils
    {
        /// <summary>
        /// Efficiently get only some files from a dir
        /// </summary>
        /// <param name="directory"></param>
        /// <param name="limit"></param>
        /// <returns></returns>
        public static List<string> GetFiles(string directory, int limit)
        {
            Assert.IsTrue(limit > 0, "Limit should be positive");
            List<string> result = new List<string>(limit);
            FilesFinder filesFinder = new FilesFinder(directory + "\\*.*");
            foreach (FoundFileData foundFile in filesFinder)
            {
                string fullFilename = directory + "\\" + foundFile.FileName;
                if (!IsFile(fullFilename))
                    continue;
 
                limit--;
 
                result.Add(fullFilename);
 
                if (limit == 0)
                    return result;
            }
 
            return result;
        }
 
        /// <summary>
        /// Return a random set of count files from a directory. (note, this can be slow on huge directories!)
        /// </summary>
        /// <remarks>
        /// If the directory has less files, all of it is returned
        /// </remarks>
        /// <param name="directory"></param>
        /// <param name="limit"></param>
        /// <returns></returns>
        public static List<string> GetRandomizedFiles(string directory, int limit
        {
            string[] files = Directory.GetFiles(directory);
            if (files.Length <= limit)
                return new List<string>(files);
 
            // we don't have enough, so we have to randomize
            int[] permutation = GenerateRandomPermutation(files.Length);
 
            // take first count files
            List<string> result = new List<string>(count);
            for (int i = 0; i < count; ++i)
            {
                result.Add(files[permutation[i]]);
            }
            return result;
        }
 
        private static bool IsFile(string name)
        {
            return File.Exists(name);
        }
 
        private static int[] GenerateRandomPermutation(int count)
        {
            int[] array = new int[count];
            for (int i = 0; i < count; ++i)
                array[i] = i;
 
            // http://forums.msdn.microsoft.com/en-US/csharpgeneral/thread/8b489948-f1b5-46d0-8bc5-bd94c418e41d/
            Random random = new Random();  // i.e., Random Class.  
            int n = array.Length;       // The number of items left to shuffle (loop invariant).  
            while (n > 1)
            {
                int k = random.Next(n);  // 0 <= k < n.  
                n--;                     // n is now the last pertinent index;  
                int temp = array[n];     // swap array[n] with array[k] (does nothing if k == n).  
                array[n] = array[k];
                array[k] = temp;
            }
            return array;
        }
    }
 
    /// <summary>
    /// Taken from http://blogs.msdn.com/yvesdolc/archive/2005/08/06/448673.aspx and translated to C#
    /// </summary>
    public class FilesEnumerator : IEnumerator<FoundFileData>
    {
        #region Interop imports
 
        private const int ERROR_FILE_NOT_FOUND = 2;
        private const int ERROR_NO_MORE_FILES = 18;
 
        [DllImport("kernel32.dll", SetLastError = true, CharSet = CharSet.Auto)]
        private static extern IntPtr FindFirstFile(string lpFileName, out WIN32_FIND_DATA lpFindFileData);
 
        [DllImport("kernel32.dll", SetLastError = true, CharSet = CharSet.Auto)]
        private static extern bool FindNextFile(SafeHandle hFindFile, out WIN32_FIND_DATA lpFindFileData);
 
        #endregion
 
        #region Data Members
 
        private readonly string _fileName;
        private SafeHandle _findHandle;
        private WIN32_FIND_DATA _win32FindData;
 
        #endregion
 
        public FilesEnumerator(string fileName)
        {
            _fileName = fileName;
            _findHandle = null;
            _win32FindData = new WIN32_FIND_DATA();
        }
 
        #region IEnumerator<FoundFileData> Members
 
        public FoundFileData Current
        {
            get
            {
                if (_findHandle == null)
                    throw new InvalidOperationException("MoveNext() must be called first");
 
                return new FoundFileData(ref _win32FindData);
            }
        }
 
        object IEnumerator.Current
        {
            get { return Current; }
        }
 
        public bool MoveNext()
        {
            if (_findHandle == null)
            {
                _findHandle = new SafeFileHandle(FindFirstFile(_fileName, out _win32FindData), true);
                if (_findHandle.IsInvalid)
                {
                    int lastError = Marshal.GetLastWin32Error();
                    if (lastError == ERROR_FILE_NOT_FOUND)
                        return false;
 
                    throw new Win32Exception(lastError);
                }
            }
            else
            {
                if (!FindNextFile(_findHandle, out _win32FindData))
                {
                    int lastError = Marshal.GetLastWin32Error();
                    if (lastError == ERROR_NO_MORE_FILES)
                        return false;
 
                    throw new Win32Exception(lastError);
                }
            }
 
            return true;
        }
 
        public void Reset()
        {
            if (_findHandle.IsInvalid)
                return;
 
            _findHandle.Close();
            _findHandle.SetHandleAsInvalid();
        }
 
        public void Dispose()
        {
            _findHandle.Dispose();
        }
 
        #endregion
    }
 
    public class FilesFinder : IEnumerable<FoundFileData>
    {
        readonly string _fileName;
        public FilesFinder(string fileName)
        {
            _fileName = fileName;
        }
 
        public IEnumerator<FoundFileData> GetEnumerator()
        {
            return new FilesEnumerator(_fileName);
        }
 
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
 
    public class FoundFileData
    {
        public string AlternateFileName;
        public FileAttributes Attributes;
        public DateTime CreationTime;
        public string FileName;
        public DateTime LastAccessTime;
        public DateTime LastWriteTime;
        public UInt64 Size;
 
        internal FoundFileData(ref WIN32_FIND_DATA win32FindData)
        {
            Attributes = (FileAttributes)win32FindData.dwFileAttributes;
            CreationTime = DateTime.FromFileTime((long)
                    (((UInt64)win32FindData.ftCreationTime.dwHighDateTime << 32) +
                     (UInt64)win32FindData.ftCreationTime.dwLowDateTime));
 
            LastAccessTime = DateTime.FromFileTime((long)
                    (((UInt64)win32FindData.ftLastAccessTime.dwHighDateTime << 32) +
                     (UInt64)win32FindData.ftLastAccessTime.dwLowDateTime));
 
            LastWriteTime = DateTime.FromFileTime((long)
                    (((UInt64)win32FindData.ftLastWriteTime.dwHighDateTime << 32) +
                     (UInt64)win32FindData.ftLastWriteTime.dwLowDateTime));
 
            Size = ((UInt64)win32FindData.nFileSizeHigh << 32) + win32FindData.nFileSizeLow;
            FileName = win32FindData.cFileName;
            AlternateFileName = win32FindData.cAlternateFileName;
        }
    }
 
    /// <summary>
    /// Safely wraps handles that need to be closed via FindClose() WIN32 method (obtained by FindFirstFile())
    /// </summary>
    public class SafeFindFileHandle : SafeHandleZeroOrMinusOneIsInvalid
    {
        [DllImport("kernel32.dll", SetLastError = true)]
        private static extern bool FindClose(SafeHandle hFindFile);
 
        public SafeFindFileHandle(bool ownsHandle)
            : base(ownsHandle)
        {
        }
 
        protected override bool ReleaseHandle()
        {
            return FindClose(this);
        }
    }
 
    // The CharSet must match the CharSet of the corresponding PInvoke signature
    [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Auto)]
    public struct WIN32_FIND_DATA
    {
        public uint dwFileAttributes;
        public FILETIME ftCreationTime;
        public FILETIME ftLastAccessTime;
        public FILETIME ftLastWriteTime;
        public uint nFileSizeHigh;
        public uint nFileSizeLow;
        public uint dwReserved0;
        public uint dwReserved1;
        [MarshalAs(UnmanagedType.ByValTStr, SizeConst = 260)]
        public string cFileName;
        [MarshalAs(UnmanagedType.ByValTStr, SizeConst = 14)]
        public string cAlternateFileName;
    }
}
Tags: , , ,
9 Comments

Never rely on tail recursion elimination

29/1/09, 15:30

Corollary: Never write a recursively method with an unbounded stack depth.

I previously posted a recursive implementation of Factorial, and asked the readers “not to bother saying it’s inefficient because of recursion, since it will probably be optimized away anyway”. Not true.

I don’t really understand why (just posted a question to StackOverflow), but C# does not generally perform tail recursion elimination (at least as my measly test show).

The following method can be easily optimized, both to work faster, consume less space and not to cause a StackOverflowException … but it is not optimized by the compiler (verified by Reflector and the fact a StackOverflowException was indeed thrown).

private static void Foo(int i)
{
    if (i == 1000000)
        return;
 
    if (i % 100 == 0)
        Console.WriteLine(i);
 
    Foo(i+1);
}

So … if for some reason you prefer writing recursive methods over using loops, do it only where performance is not a consideration and you have a good understanding of the maximal stack depth.

Tags: , , , , ,
8 Comments
« Previous Entries