As of this week, I no longer work at Microsoft. As such, this is my last post. My blog will continue at http://techravings.blogspot.com/ Reuven

Anyone who's taken a beginning calculus course spent some time studying (and maybe dreading) infinite series. A convergence definition was probably given as the convergence of the sequence of partial sums of the series. Next the course probably talked...

I'll pose an easy one this time. Everyone should be familiar with the Fibonacci sequence defined recursively as F(n) = F(n-1) + F(n-2). Fibonacci is often one of the first examples of recursion one learns, and also one of the first examples of how recursion...

In the last post, we discussed a method to find common subexpression on the entire control-flow graph using partitioning. Today, we're going to talk about another classic way of accomplishing this goal using data-flow analysis. Then I think I'm going...

In the last few posts, we examined ways of eliminating redundant expressions in basic blocks and in tree-structures of basic blocks. We examined the tree of extended basic blocks and then enhanced this algorithm to run over the immediate-dominator tree...

In the last post we extended the value-numbering algorithm to extended basic blocks. This is generally a win, but still leaves us wanting a bit more. Consider the following contrived program: x = y + z B1 if x == 0 a = y + z B2 else b = y + z...

Yesterday's post dealt with optimizing a single basic block. Most useful progams contain some control flow however, so in the next few posts we'll explore extending the algorithm to larger regions. The set of all basic block in a procedure form a graph...

Despite my having worked on Windows Storage for the past four years, one of my main interests has always been compilers. I had the good fortune to go to school at Rice University, a school that had one of the strongest compiler programs in the country...

At some point in your programming career, you've probably written a growable list. It might've been to implement a dynamic array or it might've been for a hash table, but I bet you've written one. After all, while you can usually find a library that has...

Every so often, your application makes a call on a COM interface pointer, and this call fails with RPC_E_DISCONNECTED. Or it fails with RPC_E_SERVER_DIED, or with RPC_E_SERVER_DIED_DNE, or any number of RPC errors. In most cases what this means is that...

Now that I've gotten some of my math fetish out of my system, I plan on blogging for a while on VSS and how to backup a Windows system. Starting with Windows XP, Microsoft has changed the way backup and restore of Windows system are done. We provided...

I haven't been blogging in a little while, and I want to start blogging about VSS related topics soon. However, for now I'll throw out another math puzzle, though this one is much easier. Remember that given a set U of real numbers, a real number x...

I left off last time explaining how invertible function spaces naturally form a group and how that leads to the concept of a group action. This concept turns out to be useful in examining any group, not just explicit function spaces. Any group G can be...

There are many solutions to this problem. Here's an easy one that everybody can understand. Let's construct a bipartite graph representing this problem. On the left side, we have a vertex for every integer lattice point (i.e. (0,0) (0,1) (1,1) etc...

What does the following code snippet do? bool test(const wstring& first, const wstring& second) { if (first.empty() && second.empty()) return true; if (first.empty()) return (second[0] == L'*') && test(first, second.substr...

Another quick problem before I head to sleep. Let T be a rectangle in the plane, and let the rectangle T1, T2, ..., Tn tile T. By this I mean that each of the tiling rectangles is contained in T, the union of all the rectangles equals T, and the intersection...

I'm going to diverge a bit from software topics today and talk about some wild and wonderful math topics. I haven't seriously thought about advanced math since I graduated, but recently some topics have started coming to mind. One of the strangest...

Proper handling of errors is one of the bugbears of software development. In Win32 most function can return an error code of some sort, and a good programmer will always check these errors or risk undefined behavior. Various attempts have been made to...

In my list of afterthoughts, the third item is performance. Why don't developers like thinking about performance from the start? It's clearly not for the same reasons as backup and security, since performance is about a product working well. Nobody will...

When people develop software, there are three things that aren't thought about until the final stages of development. Security Backup Performance As a corollary, some might add Manageability. Now all of these topics will probably have...

While discussing the weaknesses of splay trees, I realized that they have lots of problems in muli-threaded environments. Maintaining large trees in multi-threaded environments is always a challenge due to lock contention. The naive way of implementing...

A couple of weeks ago I started a personal blog on livejournal, http:\\www.livejournal.com\users\groovinsax, to chronical a trip to Argentina. That blog will remain my personal blog, while this blog will focus on my technical interests and my job at Microsoft...