A gratuitously cute name.

I'm reading Effective C++ 3e and in the OO section Mr. Meyers has one point he wasnt people to remember: The battle of Hastings was in 1066... OK, the real bullet point is that public inheritance models "is-a". To illustrate his point he uses the example that a Penguin is-a bird, but then goes on to point out that this can get you in trouble if you assume that all birds can fly. Well, not all can and several ways to deal with this are brought up including one that brings me to my point:

class Penguin: public Bird {

public:

virtual void fly() { error("Attempt to make a penguin fly!"); }

};

This struck me a remarkably funny, particularly if you include exception handling:

virtual void fly() { throw new PenguinError("Attempt to make a penguin fly!"); }

Q: How do you attempt to make a penguin fly?

A: You throw it.

Q: Well how does that work out for ya?

A: The penguin seems to be 'in flight' for a bit and then crashes.

Right now I'm really regretting that I can't use exceptions at work because I can't wait to derive a Penguin class from Exception just for that case!

Static Initialization Check Feature

While thinking about how to do 3^rd party types for my sterilization library, I ran into an interesting problem; how to verify that boot time initialization is done correctly.

Some cases are easy, for instance, where the initialization is done by the same code author that defines the validity check. In that case the checks can just be appended to the initialization code.

The problem cases is where the two bits are separated. This is a sort of punting model where the first author "punts" by throwing out some state variable and expecting someone (a second author) to set them up correctly. In this case you have the problem of where to put the checks. If you put it in a static constructor in the module with the state variables, then it ends up running before any static constructors in the modules that could have set the values. Another option is having a test function that the second author needs to call, but they could forget. A third option would be to have a function that gets called at the top of main, err, yuck. The option I think I'll go with is to check that things are correct on the tare down and then force an immediate teardown at some point as part of the test rig.

What I'd really like is some sort of delayed assert that runs after all the static thiss but before main. Of course then I'll want something between that and main... (Yet another example of why to never have more than two levels of operation if you can avoid it) To avoid that issue it could be restricted to provably side effect free expressions. Given that in my case all I want to do is check that a global is non null this would be just fine for.

Of course, in my case what I'd really like is static whole program optimization and analysis to, where possible, rip out static constructors in favor of literal data segments and replace the checks I'm taking about with compile time checks. But now I'm just dreaming.

"Unit in the last place" floating point test

For about the third time, I have needed to look up how to code the Unit in the last place floating point test so I'm going to post this link so I can find it.

And to protect from that going dead the final code:

// Usable AlmostEqual function
bool AlmostEqual2sComplement(float A, float B, int maxUlps)
{
    // Make sure maxUlps is non-negative and small enough that the
    // default NAN won't compare as equal to anything.
    assert(maxUlps > 0 && maxUlps < 4 * 1024 * 1024);
    int aInt = *(int*)&A;
    // Make aInt lexicographically ordered as a twos-complement int
    if (aInt < 0)
        aInt = 0x80000000 - aInt;
    // Make bInt lexicographically ordered as a twos-complement int
    int bInt = *(int*)&B;
    if (bInt < 0)
        bInt = 0x80000000 - bInt;
    int intDiff = abs(aInt - bInt);
    if (intDiff <= maxUlps)
        return true;
    return false;
}

Lock free concurrency is neat.

This topic comes by way of a few interest of mine.

The first is non-locking concurrent solutions, or more actually some of the ways they are modeled and dealt with. A while ago I came across a description of a lock free hash table using a CAS instruction. I fond this to be really cool because it managed to proof correctness of a solution by using only a single concurrent primitive and a state transition diagram. That was my first introduction into lock free solutions and I have been somewhat interested in them from then on.

Another interest stems from my work. At one of the steps of our R&D we had a system that worked by doing computation purely as a pattern-match-and-extend operation. While I was working with this I was also taking a algorithms class so naturally, I tried to combine the two. The most interesting thing to come out of that was from attacking the minimum spanning tree problem. Given that the system in question is only additive, things tend to be cast in terms of classification. For this problem I chose to cast it in terms of edges to be removed so the question becomes how to identify edges in a graph that are not part of the minimum spanning tree? I have never managed to prove that this is correct, but what I can up with was to mark any edge that was the heaviest edge in any simple cycle. As it happens this is easy to define but insanely expensive to compute. I never did implement it but I keep kicking it around.

While that solution is intractable in real hard ware, it's interesting to note that it would work just fine on a system with unlimited concurrency.

1. Start a thread on every node
   
2. Every thread spawns a new thread for every edge from the current node.
   
3. each thread now checks to see if the current node is in it's ancestry. If it is, then the heaviest edge between that occurrence and the end is marked and the thread quits.
   
4. otherwise continue at step 2.
   

The next step is to notice that even under limited concurrency, this is a valid (but still impractical) transformation on a graph. Running something like Kruskal's Algorithm on the graph at any point will result in the same result as running it on the original graph. With a little hand waving, I can convince my self that you can even run them at the same time. Even more interestingly, you only need to make very few assumption (I'll get back to that) to show that you don't even need to use locks. Not even hardware locking like you would need for a CAS based algorithm.

This no-locking aspect is a result of the only state that is modified, only ever going in one direction (from "might be in the tree" to "not in the tree") and because Kruskal's algorithm won't care if it gets stale data, it will just take longer to reject it.

The solution is still impractical as finding cycles is not efficient. However, if half of Kruskal's algorithm is stolen and the extra threads just run around and test random edges to see if their endpoint share a sub-tree, I expect that this could be made very practical

Now back to the assumptions: The only assumption I can see that has to be maid to avoids even hardware locking is that writing to that status flag of one edge must not interact with any other status flags. This precludes using a bit array or anything else that places the flags closer than the granularity of the CPU's cache. On the other hand. Even if this can't be met, CPU's need some way to effectively solve this problem so I would expect that it isn't that much of an issue.

I just got a 25% speedup in my code!

I am working on a Connect-4 AI for an AI class. Being me I decided to go all out on the bit twiddling and whatnot to make the thing as compact and as fast as I could make it (there is a 30 seconds per move limit).

The big part turns out being how to test for a win/loss and how to score the leaves of the tree. I chose to go with bits masks for the board as it lets me do both of these with ANDs, shifts and XORs. I shift the bits so that each sequence of 4 spaces stack and then build a set of adders from ANDs and XORs. Checking the 4s bits finds wins and looses and masking with the inverse of the opponents and counting the 3s, 2s and 1s gives a heuristic for the state. The problem with this is that the direct way would end up with about 100 lines of bit ops and piles of goo for variables names. I actually started in on that tack but decided it wasn't a good idea.

What I settled on was a templated struct that handles the shift and adds and another struct to handle the next higher level of the mucking around. The main problem with that is that I end up with about 160 variables (most of which are not needed at the same time) that are locked into struct so I don't expect that the compiler will do a good job of reusing them (I also suspect that many of the methods won't get inlined as aggressively)

I was tossing around the idea of getting the code working and then editing the structs back into the main loop (inlining by hand) to address these issue and it occurred to me that if I turned the struct into templates I can do a named mixin and I don't need to alter the usage code one bit.

As an example, this code:

struct S
{
   int i;
   int I()
   {
      return i++;
   }
}

void main()
{
   S s1, s2;
   s1.i = 0;
   s2.i = 0;
   assert(s1.I == 0);
   assert(s2.I == 0);
   assert(s1.I == 1);
   assert(s2.I == 1);
}

becomes this code:

template S()
{
   int i;
   int I()
   {
      return i++;
   }
}

void main()
{
   mixin S!() s1;
   mixin S!() s2;
   s1.i = 0;
   s2.i = 0;
   assert(s1.I == 0);
   assert(s2.I == 0);
   assert(s1.I == 1);
   assert(s2.I == 1);
}

In my actual case this resulted in about a 25% speed boost.

of course this does have a few down side like I can no longer use this or any of it's aliases. I can't use the data as a struct and I can't copy it.

But all in all a 25% speedup for almost no coding is just cool!