Where In The World Is Poland?

Did you ever take a closer look at the timezone tab on the Windows date and time panel? Depending on your Windows version, it is quite likely that Poland seems to be flooded on the timezone world map. Raymond Chen knows why.

Just Another Sudoku Solver (C++)

Closing this topic, here is the sourcecode of the C++ Sudoku Solver (originally in Java). Remember that this a template class, so all this code has to go to a header file. All allocation actions should be the same as under Java - which is important for runtime behavior comparison.

I coded this last night between 1am and 2am in the morning, so please don't shoot me in case of any mistakes ;-).

#pragma once
#include <vector>
#include <math.h>

template<int D> class Sudoku
{

public:

    Sudoku(int _startGrid[D][D])
    {
        solutions = new std::vector<int(*)[D]>();
        dimSqrt = (int)sqrt((double)D);
        for (int x = 0; x < D; x++) {
            for (int y = 0; y < D; y++) {
                squareIdx[x][y] = 
                (x / dimSqrt) * dimSqrt + (y / dimSqrt);
            }
        }

        copyGrid(_startGrid, startGrid);
    }

    virtual ~Sudoku() {
        for (std::vector<int(*)[D]>::iterator it = 
            solutions->begin(); it != solutions->end(); it++) {
            delete[] *it;
        }
        delete solutions;
    }

    std::vector<int(*)[D]>* solve() {
        for (std::vector<int(*)[D]>::iterator it = 
            solutions->begin(); it != solutions->end(); it++) {
            delete[] *it;
        }
        solutions->clear();
        copyGrid(startGrid, grid);
        for (int i = 0; i < D; i++) {
            for (int j = 0; j < D; j++) {
                usedInRow[i][j] = false;
                usedInColumn[i][j] = false;
                usedInSquare[i][j] = false;
            }
        }
        for (int x = 0; x < D; x++) {
            for (int y = 0; y < D; y++) {
                int val = grid[x][y];
                if (val != 0) {
                    usedInRow[x][val - 1] = true;
                    usedInColumn[y][val - 1] = true;
                    usedInSquare[squareIdx[x][y]][val - 1] = true;
                }
            }
        }

        digInto(0, 0);
        return solutions;
    }

private:

    void copyGrid(int src[D][D], int tgt[D][D]) {
        for (int x = 0; x < D; x++) {
            // for compatibility reasons with java we 
            // copy one-dimensional arrays only
            memcpy(tgt[x], src[x], D * sizeof(int));
        }
    };

    void digInto(int x, int y) {
        if (startGrid[x][y] == 0) {
            int square = squareIdx[x][y];

            for (int val = 1; val <= D; val++) {
                int valIdx = val - 1;
                if (usedInRow[x][valIdx] || usedInColumn[y][valIdx] || 
                usedInSquare[square][valIdx]) {
                    continue;
                }
                grid[x][y] = val;
                usedInRow[x][valIdx] = true;
                usedInColumn[y][valIdx] = true;
                usedInSquare[square][valIdx] = true;
                if (x < D - 1) {
                    digInto(x + 1, y);
                }
                else if (y < D - 1) {
                    digInto(0, y + 1);
                }
                else {
                    addSolution();
                }
                grid[x][y] = 0;
                usedInRow[x][valIdx] = false;
                usedInColumn[y][valIdx] = false;
                usedInSquare[square][valIdx] = false;
            }

        }
        else {
            if (x < D - 1) {
                digInto(x + 1, y);
            }
            else if (y < D - 1) {
                digInto(0, y + 1);
            }
            else {
                addSolution();
            }
        }
    };

    void addSolution() {
        int (*solution)[D] = new int[D][D];
        copyGrid(grid, solution);
        solutions->push_back(solution);
    };

    int startGrid[D][D];
    int grid[D][D];
    int dimSqrt;
    std::vector<int(*)[D]>* solutions;
    bool usedInColumn[D][D];
    bool usedInRow[D][D];
    bool usedInSquare[D][D];
    int squareIdx[D][D];

};

Previos Posts:

• Just Another Sudoku Solver
• Java Vs. .NET Vs. C++ Performance

Follow-Ups:

• Sudoku Benchmarking / .NET 2.0, Java 5 and Java 6 Results
• Hosting .NET Winforms Applications In MSIE

Computers In Old Movies

A colleague of mine - knowing about my interest for ancient computers - recently asked me whether I knew which system they were using in the 1968 movie "Hot Millions" with Peter Ustinov. I remember having seen this picture once, and I also remember they had a mainframe in the scenery. But the only image I could look up in internet is this one with Ustinov sitting in front of a terminal. I guess I will have to watch "Hot Millions" again in order to find out.

Anyway, this question caught my attention, so I did some more research and discovered that the first appearance of a computer in a cinema movie was probably a mockup named "EMERAC" (reminiscenting about ENIAC or UNIVAC?) in "Desk Set" with Katherine Hepburn from 1957. It even consisted of real computer parts, namely IBM 704 magnetic tapes and some panels from the famous SAGE military computer (based on vacuum tubes and ferrite core memory).



No list of computers in old movies would not be complete without HAL9000 from "A Space Odyssey". Timeless.

Java Vs. .NET Vs. C++ Performance

Well I am done with porting my little Sudoku Solver to C++. I took care to keep the algorithm equivalent, esp. on memory allocation (actually the only memory that is dynamically allocated is for storing away puzzle solutions). Not really surprisingly, C++ beats both C# and Java:

Platform	Execution Time (for several thousand valid solutions)
C++	250ms
C# (.NET 1.1) after NGEN	390ms
Java (JDK 1.4.2)	680ms
C# (.NET 1.1)	790ms

I calculated the execution time by feeding the solver with a sparsely populated puzzle that has thousands of valid solutions (Sudoku purists will point out that this is a non-well-formed puzzle). The algorithm uses a slightly optimized brute force approach (my intention was runtime comparison, not building a hyperfast solver algorithm) - so it finds all the solutions.

The algorithm, when implemented in C++, delivers around 60.000 valid solutions per second on my 2.4GHz Athlon for average one-solution 9x9 Sudoku puzzles. The time it takes to solve one of those can hardly be measured, and I didn't want to inject the same puzzle a thousand times for the benchmark.

It depends heavily on the intial puzzle values, though. I digged out a puzzle - one that is considered more or less unbreakable for humans - that took the C++ implementation 15ms to solve. 15ms for one solution, mind you.

I doubt that there is a lot of optimzing potential for Java Hotspot other but compiling the algorithm's main method (which only consists of a few lines of code anyway) to native code as soon as possible. Dynamic memory allocation only happens for storing away solution arrays, and those are not going to be garbage collected until the end, so there is not a lot of optimizing potential on the memory management side. The .NET CLR should JIT all of the code at startup anyway. I did some tests to go sure, and the numbers did not change neither under Java and nor under .NET even after running the same stack of puzzles many times in a row.

Previos Posts:

• Just Another Sudoku Solver

Follow-Ups:

• Just Another Sudoku Solver (C++)
• Sudoku Benchmarking / .NET 2.0, Java 5 and Java 6 Results
• Hosting .NET Winforms Applications In MSIE

Java Vs. .NET Performance

As a sidenote, I just ported yesterday's Sudoku Solver to C#, ran the same stack of puzzles, and compared execution times. Here is the result:

Platform	Execution Time (for several thousand valid solutions)
Java (JDK 1.4.2)	680ms
C# (.NET 1.1)	790ms
C# (.NET 1.1) after NGEN	390ms

What I did here was to feed the solver with a sparsely populated puzzle that has thousands of valid solutions, and measure the time of execution to find all the solutions in a brute-force manner. Just finding one solution would be beyond the scale of time measurement.

Right now I am working on a C++ port, so this will be another interesting comparison (my C++ coding is slower than it used to be, since I have not written a single line of C++ over the last two years).

Vanilla DAL 0.2.2 Released

I received some valuable feedback from some projects employing the Vanilla .NET Data Access Framework, so the following changes have been incorporated in release 0.2.2:

• SqlServer: quoted identifiers for table names and column names (square brackets).


• New Property FillParameter.SchemaHandling for defining whether DataSet schema should be preserved or updated by DB schema.


• SQL code may now be passed in directly, as well as pre-processed before execution. The sample application provides more details.


• Class "StatementID" has been renamed to "Statement".

Just Another Sudoku Solver

Yes, it's only brute force (just avoiding digging deeper into the search tree when it's proven wrong already), and yes, it's Java which implies array bounds checking, but it still delivers around 30.000 valid solutions per second for average 9x9 Sudokus on my 2.4GHz Athlon. Faster than my father-in-law who has been messing around with a single puzzle all night long. I couldn't watch it any longer [;-)], so I hacked in the following code.

package com.arnosoftwaredev.sudoku;

import java.util.ArrayList;
import java.util.Collection;

public class Sudoku {

 private int[][] startGrid;
 private int dim;
 private int dimSqrt;
 private ArrayList solutions;
 private boolean usedInColumn[][];
 private boolean usedInRow[][];
 private boolean usedInSquare[][];
 private int squareIdx[][];
 private int grid[][];

 public Sudoku(int[][] startGridParam) {
     if (startGridParam == null) {
         throw new IllegalArgumentException("Grid is invalid");
     }
     if (startGridParam.length == 0) {
         throw new IllegalArgumentException("Grid is invalid");
     }
     if (startGridParam.length != startGridParam[0].length) {
         throw new IllegalArgumentException("Grid is invalid");
     }
     dim = startGridParam.length;
     if (dim != 4 && dim != 9 && dim != 16 && dim != 25) {
         throw new IllegalArgumentException("Grid is invalid");
     }

     solutions = new ArrayList();

     dimSqrt = (int) Math.round(Math.sqrt(dim));

     usedInColumn = new boolean[dim][dim];
     usedInRow = new boolean[dim][dim];
     usedInSquare = new boolean[dim][dim];
     squareIdx = new int[dim][dim];
     startGrid = new int[dim][dim];
     grid = new int[dim][dim];
     for (int x = 0; x < dim; x++) {
         for (int y = 0; y < dim; y++) {
             squareIdx[x][y] =
             (x / dimSqrt) * dimSqrt + (y / dimSqrt);
         }
     }
     copyGrid(startGridParam, startGrid);
 }



 private void copyGrid(int[][] src, int[][] tgt) {
     for (int x = 0; x < src.length; x++) {
         System.arraycopy(src[x], 0, tgt[x], 0, src[x].length);
     }
 }

 private void digInto(int x, int y) {
     if (startGrid[x][y] == 0) {
         int square = squareIdx[x][y];

         for (int val = 1; val <= dim; val++) {
             int valIdx = val - 1;
             if (usedInRow[x][valIdx] || usedInColumn[y][valIdx] ||
             usedInSquare[square][valIdx]) {
                 continue;
             }
             grid[x][y] = val;
             usedInRow[x][valIdx] = true;
             usedInColumn[y][valIdx] = true;
             usedInSquare[square][valIdx] = true;
             if (x < dim - 1) {
                 digInto(x + 1, y);
             }
             else if (y < dim - 1) {
                 digInto(0, y + 1);
             }
             else {
                 addSolution();
             }
             grid[x][y] = 0;
             usedInRow[x][valIdx] = false;
             usedInColumn[y][valIdx] = false;
             usedInSquare[square][valIdx] = false;
         }

     }
     else {
         if (x < dim - 1) {
             digInto(x + 1, y);
         }
         else if (y < dim - 1) {
             digInto(0, y + 1);
         }
         else {
             addSolution();
         }
     }
 }

 private void addSolution() {
     int[][] solution = new int[dim][dim];
     copyGrid(grid, solution);
     solutions.add(solution);
 }

 public Collection solve() {
     solutions.clear();
     copyGrid(startGrid, grid);
     for (int i = 0; i < dim; i++) {
         for (int j = 0; j < dim; j++) {
             usedInRow[i][j] = false;
             usedInColumn[i][j] = false;
             usedInSquare[i][j] = false;
         }
     }
     for (int x = 0; x < dim; x++) {
         for (int y = 0; y < dim; y++) {
             int val = grid[x][y];
             if (val != 0) {
                 usedInRow[x][val - 1] = true;
                 usedInColumn[y][val - 1] = true;
                 usedInSquare[squareIdx[x][y]][val - 1] = true;
             }
         }
     }
     digInto(0, 0);
     return solutions;
 }

}

Follow-Ups:

• Java Vs. .NET Vs. C++ Performance
• Just Another Sudoku Solver (C++)
• Sudoku Benchmarking / .NET 2.0, Java 5 and Java 6 Results
• Hosting .NET Winforms Applications In MSIE

The Software Projekt Triangle

From Microsoft Project Online:

If time, money, or what your project accomplished were unlimited, you wouldn't need to do project management. Unfortunately, most projects have a specific time limit, budget and scope.

It is this combination of elements (schedule, money and scope) that we refer to as the project triangle. Understanding the project triangle will allow you to make better choices when you need to make tradeoffs. If you adjust any one side of the triangle, the other two sides are affected.

For example, if you decide to adjust the project plan to

• Bring in the scheduled finish date, you might end up with increased costs and a decreased scope.


• Meet the project budget, the result might be a longer schedule and a decreased scope.


• Increase scope, your project might take more time and cost more money in the form of resources

Quality is at the center of the project triangle. Quality affects every side of the triangle, and any changes you make to any side of the triangle are likely to affect quality. Quality is not a factor of the triangle; it is a result of what you do with time, money, and scope.

For example, if you find you have additional time in your schedule, you might be able to increase scope by adding tasks and duration. With this extra time and scope, you can build a higher level of quality into the project and its deliverables.

Or if you need to cut costs to meet your budget, you might have to decrease scope by cutting tasks or reducing task durations. With decreased scope, there might be fewer opportunities to achieve a certain level of quality, so a lower quality results from the need to cut costs.

Jeff Atwood even carpented "the iron stool of software project management" out of this.

Macs Do Windows Too

Harsh words on the Apple Boot Camp site (Boot Camp lets you install Windows XP on Intel-based Macs), e.g.:

Macs use an ultra-modern industry standard technology called EFI to handle booting. Sadly, Windows XP, and even the upcoming Vista, are stuck in the 1980s with old-fashioned BIOS. But with Boot Camp, the Mac can operate smoothly in both centuries.

Good for Apple that they don't have to worry about backward compatibility on old hardware. I also remember the pre-2002 era, when Mac OS still lacked memory protection and preemptive multitasking. How "1980s" does that sound?

Guy Kawasaki: The Art Of The Start

.NET 2.0, HttpWebRequest.KeepAlive And ServicePoint.ConnectionLimit

Since switching over to .NET 2.0, one of our applications occasionally threw "The request was aborted: The request was canceled." resp. "The underlying connection was closed: The request was canceled." errors. This happened maybe 1 out of 25 times when connecting to another server using HTTP, either directly via HttpWebRequest or on webservice calls, which also apply HttpWebRequest internally.

Digging further into the issue, it turned out that several people suggested to set HttpWebRequest.KeepAlive to false. And as matter of fact this worked. But KeepAlive=false will most likely imply a performance penalty as there won't be any re-use (also known as HTTP pipelining) of TCP-connections. TCP-connections are now closed immediately and reopened on each HTTP-request. To make things worse, we have SSL turned on, with both server and client certificates, so KeepAlive=false will then cause a complete SSL-Handshake now for each and every HTTP request to the same server. As a sidenote, KeepAlive=true with client authentication requires the initial authentication to be shared between all following requests, hence it is necessary to set HttpWebRequest.UnsafeAuthenticatedConnectionSharing=true. Please consult the MSDN documentation for more information about what that implies.

Back to the original topic, our application used to work fine under .NET 1.1, only .NET 2.0 seems to have this problem. And despite the fact that people have posted this issue over and over again, there is no Microsoft hotfix up to this day. KeepAlive=false is the only remedy.

By the way, another property that is essential for network throughput under .NET is HttpWebRequest.ServicePoint.ConnectionLimit. Microsoft started limiting the maximum number of parallel network connections some time ago (I once read in order to prevent malware from flooding the network - which sounds unlikely given that one can simply raise this limit programmatically, at least with admin credentials), and while this might not harm the single user when surfing the web, it surely is not suited for other kinds of applications. After the limit is reached, further request will be queued and have to wait for a running request to terminate. I am sure there are quite some applications out there which run into performance problems because of this.

The preset connection limit might vary depending on the underlying operating system and hosting environment. It can be changed programmatically by setting HttpWebRequest.ServicePoint.ConnectionLimit to a higher value, or in one of .NET's .config files (machine.config, app.config resp. web.config):

<system.net>
    <connectionManagement>
        <add address="yourtargetdomain.com" maxconnection="32">
        </add>
    </connectionManagement>
</system.net>

This is just one of many possible explanations, but that unfortunate limitation might boil down to a particular interpretation of RFC 2616 (HTTP1.1), which states:

Clients that use persistent connections SHOULD limit the number of simultaneous connections that they maintain to a given server. A single-user client SHOULD NOT maintain more than 2 connections with any server or proxy. A proxy SHOULD use up to 2*N connections to another server or proxy, where N is the number of simultaneously active users. These guidelines are intended to improve HTTP response times and avoid congestion.

So is any .NET application considered "single-user client" by default? Our system surely isn't a single-user client, it's more like a kind of proxy, with plenty of concurrent users and HTTP connections. And how many developers might now even have heard about this setting, and will find out once their application went into production?

Also note that phrase of "persistent connections". Of course it is a bad idea for the client to hold hundreds of connections captive and thus bringing the server to its knee. But as I have mentioned, we cannot pool any connections anyway, not even a few of them, thank's to .NET 2.0's "The request was aborted: The request was canceled."-bug.

Anyway, it's the server's responsiblitlity to determine when too many connections are kept alive. After all, HTTP-KeepAlive is something that the client might ask for, but that the server may always decline.

Jeff Atwood Takes On Joel Spolsky

Jeff Atwood openly asks if Joel Spolsky "jumped the shark" because of implementing their his company's flagship product FogBugz in an in-house Basic-dialect called "Wasabi". Wasabi can then be compiled to VBScript or PHP, depending on customers' requirements.

Back when I read about this approach, it made me raise an eyebrow as well. I remember thinking, "boy I thought I'd like to work at Fog Creek, but having to code in such a proprietary language would be no-go". And I was wondering if that wouldn't contradict their frequently mentioned efforts of trying to attract great programmers. Actually, of the best programmers I know, nobody would ever voluntarily program in something like VB or VBScript, let go Wasabi.

But he then went on describing how this decision made sense from a business point (platform independence at a minimum of effort, no complete rewrite necessary), so I said OK, I might not like it from a developer's perspective, but from a business perspective it could make sense.

Now Jeff Atwood probably is a more censorious person than me. He decided to rip apart Joel's argumentation and connect the Wasabi-story with Joel's criticism of Ruby. He continued to make some pretty hefty statements like "fifty thousand programmers' heads simultaneously exploding", "absolutely beyond the pale" or "amplifies the insanity". I usually like Jeff's artwork, but attaching a big red WTF label on Joel's forehead is not really subtle either. And the flaming continued in the comment sections of both blogs.

My recommendation: Please settle down! From reading one or two paragraphs in some Joel on Software article, nobody possesses the same amount of information that Joel Spolsky was basing his decision on. Also, recognizing that what seems right from a developer's view must not always be right from a business standpoint is something that many programmers still have to get into their minds.

But hey, let's not hang on each of Joel Spolsky's words either. He certainly is an extraordinary programmer and writer, but he might be mistaken as well at times (a possibility he openly admits).

Vanilla DAL Data Access Framework For SqlServer, Oracle and OleDB

Version 0.2.0 of the Vanilla DAL Data Access Framework adds support for OleDB and Oracle databases.

Vanilla DAL: Added Support For OleDB And Oracle

3:00am in the morning, I finally managed to add support for Oracle and for the generic OleDb ADO.NET provider (using MS Access, as this was all I had available) to Vanilla DAL. Client code stays free of database specifics, but I am still wondering what to do with SQL statements. Vanilla DAL enforces SQL statement externalization in XML resp. generates SQL on-the-fly, but I can't (and won't) prevent the developer from applying vendor-dependent SQL syntax. The format of parameter placeholders is vendor-specific as well... I am probably going to set up one global standard, and wrap away vendor details for SQL parameters.

I am planning to publish Vanilla DAL 0.2.0 within the coming week. Next task will be to provide documentation and more samples. After that is done, it might have reached a state which allows me to start promoting this framework (it's more of a skunkworks project right now).

Vanilla DAL 0.1.2 Released

I just released version 0.1.2 of my .NET data access framework "Vanilla DAL". Currently I am working on support for Oracle and OleDB providers, and this release lays the groundwork for the oncoming changes on an API level. When this is done, Vanilla DAL will move from pre-alpha to alpha status.

Installing Oracle 10g express edition was a time-consuming task, as always with Oracle. Being a small footprint edition, it seems to be consuming too many system resources for my taste. On the other hand, the administration tools have improved tremendously (remember those Java rich clients on Oracle 8?). Anyway, my best Oracle days are long gone (Oracle 5 in 1992 on DOS, Oracle 7.3 and Oracle 8 between 1997 and 2001 on DEC VAX, Sun Solaris and finally Windows). This time I only plan to migrate my test database over there, get the Oracle-specific implementation done and that will be it.

I am not quite sure if I will manage to keep the complete API backward compatible to the previous releases, this mainly has to do with the fact that ADO.NET data providers enforce different SQL parameter naming conventions (e.g. @name under SqlServer, ? under OleDB, :name under Oracle). The most important issue is to prevent any DB-specific code in application modules. As there is no parameter name but only a parameter position under OleDB, I am still looking for the optimal mechanism to hide this detail from application code.