ReuvenLax

• Last Post

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
• Divergent Series

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...
• Another Math Puzzler

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...
• Finding Global Expressions: 2

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...
• Finding Expressions Globally

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...
• Extending Value Numbering 2

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...
• Extending Value Numbering

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...
• Some Nifty Compiler Tricks

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...
• Tricks of The Trade: How to use old tricks in new ways

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...
• Checking the status of a COM server

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...
• Volume Shadow Copy Service and the Microsoft Backup Infrastructure

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...
• Back to Math

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...
• Weird Math Stuff II

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...
• Math Puzzler Solution

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...
• Code Puzzler

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...
• Math Puzzler

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...
• Weird Math Stuff

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...
• Handling Errors

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...
• Some words on performance

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...