Friday, September 26, 2008

Tail call optimization

wall

I had posted about tail call and how .NET handles it before. However there was some email exchanges and confusion on internal DLs around it and so I thought I'd try to elaborate more on how .NET goes about handling tail calls

Let’s try to break this down a bit.

a) A piece of C# code contains tail recursion .

static void CountDown(int num)
{
Console.WriteLine("{0} ", num);
if (num > 0)
CountDown(--num);
}

-


b) The C# compiler does not optimize this and generates a normal recursive call in IL

 IL_000c:  ...
IL_000d:  ...
IL_000e:  sub
IL_000f:  dup
IL_0010:  starg.s num
IL_0012:  call void TailRecursion.Program::CountDown(int32)

-


c) The Jitter on seeing this call doesn’t optimize it in any way and just inserts a normal call instruction for the platform it targets (call for x86)


However, if any compiler is smart enough to add the tail. recursive IL statement then things change.


a) Scheme code

(define (CountDown n)
(if (= n 0)
n
(CountDown (- n 1))))

-


b) Hypothetical IronScheme compiler will generate (note for scheme it has to do the optimization)

 IL_000c:  ...
IL_000d:  ...
IL_000e:  sub
  tail.
IL_0023:  call void TailRecursion.Program::CountDown(int32)
IL_0029:  ret

-


c) Based on which JIT you are using and various other scenarios the JIT now may honour the tail. IL instruction and optimize this with a jmp when generating machine instruction


Please note the may in the very last point and refer to here for some instances where the optimization still might not take place…

Wednesday, September 17, 2008

A* Pathfinding algorithm animation screen saver

I'm trying to learn WPF and IMO it is not a simple task. Previously whenever I upgraded my UI technology knowledge it had been easy as it build on a lot of pre-existing concepts. However, WPF is more of a disruptive change.

I decided to write some simple fun application in the effort to learn WPF. Since I cannot write a BabySmash application as Scott Hanselman has already done a awesome job out of it, I decided to code up a simulation of A* path finding algorithm and push it out as a screen saver. The final product looks as follows.

AStar

What it does is that it shows a source, a destination with blockages (wall, mountain?) in between and then uses A* algorithm to find a path in between them. This is the same kind of algorithm that is used in say games like Age of the Empires as workers move around collecting wood and other resources. The algorithm is documented here.

Features

  1. It supports plugging in your own scenes with help of the awesome screen/board designer I blogged about
  2. Comes with a WPF and a console client to show the animation
  3. Algorithm can be played with easily to change or tweak it.
  4. Shows full animation including start, end, obstacle, closed cells, current path being probed and the final path
  5. Multi-screen support. Each screen shows a different board being solved.

Limitations:

Obviously this was more of a quick dirty hobby project and there remains a ton to work on. E.g.

  1. Screen saver preview doesn't work.
  2. Setting dialog is a sham.
  3. The boards do not flip for vertically aligned screens
  4. The XAML data binding is primitive and needs some work
  5. The path can choose diagonally across cell even if it seems to cross over diagonal wall of obstacle.
  6. Mouse move alone doesn't shut down the screen saver. You need to hit a
  7. Many more :)

Download:

Download the final binaries from here. Unzip to a folder, right click on the *.scr and choose Install

Download sources (including VS 2008 sln) from here.

Enjoy.

Monday, September 15, 2008

How Many Types are loaded for Hello World

Fairy princess

Consider the following super simple C# code

namespace SmartDeviceProject1
{
class Program
{
static void Main(string[] args)
{
System.Console.WriteLine("Hello");
}
}
}

Can you guess how many managed Type gets loaded to run this? I was doing some profiling the .NET Compact Framework loader (for entirely unrelated reason) and was surprised by the list that got dumped. 87 types**, never could've guessed that...



  1. System.Object
  2. System.ValueType
  3. System.Type
  4. System.Reflection.MemberInfo
  5. System.Delegate
  6. System.MarshalByRefObject
  7. System.SystemException
  8. System.Exception
  9. System.Attribute
  10. System.Collections.Hashtable
  11. System.Enum
  12. System.Reflection.BindingFlags
  13. System.MulticastDelegate
  14. System.Reflection.MemberFilter
  15. System.Reflection.Binder
  16. System.Reflection.TypeAttributes
  17. System.DateTime
  18. System.Collections.IDictionary
  19. System.UnhandledExceptionEventHandler
  20. System.AppDomainManager
  21. System.Version
  22. System.Decimal
  23. System.Runtime.InteropServices.ComInterfaceType
  24. System.Collections.ICollection
  25. System.Collections.IEqualityComparer
  26. System.AppDomainManagerInitializationOptions
  27. System.ArithmeticException
  28. System.ArgumentException
  29. System.MissingMemberException
  30. System.MemberAccessException
  31. System.AppDomainSetup
  32. System.Reflection.AssemblyName
  33. System.Globalization.CultureInfo
  34. System.Reflection.Assembly
  35. System.Configuration.Assemblies.AssemblyHashAlgorithm
  36. System.Configuration.Assemblies.AssemblyVersionCompatibility
  37. System.Reflection.AssemblyNameFlags
  38. System.Globalization.CultureTableRecord
  39. System.Globalization.CompareInfo
  40. System.Globalization.TextInfo
  41. System.Globalization.NumberFormatInfo
  42. System.Globalization.DateTimeFormatInfo
  43. System.Globalization.Calendar
  44. System.Globalization.BaseInfoTable
  45. System.Globalization.CultureTable
  46. System.Globalization.CultureTableData
  47. System.Globalization.NumberStyles
  48. System.Globalization.DateTimeStyles
  49. System.Globalization.DateTimeFormatFlags
  50. System.Globalization.TokenHashValue
  51. System.Globalization.CultureTableHeader
  52. System.Globalization.CultureNameOffsetItem
  53. System.Globalization.RegionNameOffsetItem
  54. System.Globalization.IDOffsetItem
  55. System.TokenType
  56. System.Char
  57. System.IO.TextReader
  58. System.IO.TextWriter
  59. System.IFormatProvider
  60. System.Console
  61. System.RuntimeTypeHandle
  62. System.NotSupportedException
  63. System.Globalization.EndianessHeader
  64. System.Reflection.Missing
  65. System.RuntimeType
  66. System.Threading.StackCrawlMark
  67. System.Globalization.CultureTableItem
  68. System.Int32
  69. System.Security.CodeAccessSecurityEngine
  70. System.AppDomain
  71. System.LocalDataStoreMgr
  72. System.Threading.ExecutionContext
  73. System.LocalDataStore
  74. System.Collections.ArrayList
  75. System.Threading.SynchronizationContext
  76. System.Runtime.Remoting.Messaging.LogicalCallContext
  77. System.Runtime.Remoting.Messaging.IllogicalCallContext
  78. System.Threading.Thread
  79. System.Collections.Generic.Dictionary`2
  80. System.Runtime.Remoting.Messaging.CallContextRemotingData
  81. System.RuApplication starting
  82. System.Collections.Generic.IEqualityComparer`1
  83. Runtime.Remoting.Messaging.CallContextSecurityData
  84. System.Array
  85. System.RuntimeFieldHandle
  86. System.Globalization.CultureTableRecord[]
  87. System.Text.StringBuilder

**This is for the compact framework CLR. Your mileage will vary if you run the same on the desktop CLR.

Thursday, September 11, 2008

Designer for my path finding boards

I'm writing a small application (or rather a screen saver) that animates and demonstrates A* search algorithm. The idea is simple. On screen you see a start and end point and some random obstacles in between them. Then you see animation on how A* algorithm is used to navigate around the board to find a path (close to the shortest possible) between the two.

All of this is fairly standard. However, I got hit by a simple issue. I wanted to have the ability to design this board visually and also let my potential million users do the same. Obviously I don't have time to code up a designer and hence choose the all time manager's favorite technique. Re-use :)

So the final solution I took was to use Microsoft Office Excel as the WYSIWYG editor. I created a xlsx file with the following conditional formatting which colors cells based on the value of the cells.

Excel Conditional Formatting screen shot for blog

So in this case

  1. w = Wall marking the end of the table
  2. b = blocks/bricks/obstacle
  3. s = start
  4. e = end

Using this I can easily design the board. The designer in action looks as follows

Excel Designer For A* blog screenshot

Since the excel sheet has conditional formatting the user just types in s, e, b, w in the cells and they all light up visually. At the end he/she just saves the file using File => Save As and uses CSV format. This saves the file shown above as

w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,b,,,,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,s,,,,,,,,b,b,b,b,b,b,,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,,b,b,b,b,,b,b,b,b,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,b,b,b,,,,,,b,b,b,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,b,b,,,,,,,,b,b,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,b,b,,,,,,,,b,b,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,b,b,,,,,,,b,b,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,b,b,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,b,b,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,b,b,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,b,,,,,,,,,,,e,,,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,w
w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w

As you see the format is simply a row per line and every column separated by a comma. My simulator reads this file and renders using whatever renderer is configured (console or WPF).

More about the A* simulator to come soon...

Wednesday, September 10, 2008

It's is easy to claim that the world won't get destroyed today

Taken inside the Microsoft Campus Hyderabad

The clock is ticking and the Large Hadron Collider in Cern is going to get switched on today (9/10/2008). Even though there are speculations, CERN is claiming it's perfectly safe and the world won't end. But it's easy to claim that, who'll be around to prove them wrong in case they are :)

It's one of the coolest device at an operating temperature of < -270°C. But I'd get really angry if there's any disturbance to my Birthday celebrations!!