Formal proof of correctness for a full kernel

• The front page for the project


• The write up


• a write up of the write up

MPG for an electric car?

It looks like the EPA, GM and a few others are trying to figure out how to compare gas burning apples to plug in the wall oranges. Everyone knows what you are talking about when you quote MPG numbers but what about for a car that has gas tank or one that can be charged off the power grid?

It seems that the EPA is trying to come up with a standard for how to equate the two. Well just to throw my two cents in: equate them based on what really matters. No one really cares how much gas a car burns (except for concerns of range) what people really care about is either how much money it takes to go some distance or how much CO₂ you dump out doing it. The first number would be a bit tricky as both fuel and electric prices very a bit by region so some kind of national average would need to be used. The second one is no better because CO₂/kWh is a function of what is generating the reserve power on your grid? I happen to know that most hydro-power plants are run at either full power (or as close to it as something else lets them). The same almost surly goes for most of the renewable power sources as they tend to be use it or loose it systems. From that, all or most of the power production, will be from the dirtiest source around so it ends up being not at all trivial to compute.

---

Just out of curiosity, if a large chunk of the US fleet goes to plug in cars, how much power are we talking about? According to the linked article, 80% of cars go less than 40 mi/day and the only number cited for power consumption is 0.25 kWh/mi so if you assume the long tail puts the average at THE 80% mark, that gives you 10 kWh/day/car. If there is one electric car per 6 people in the US, that gives 50 GWhr/day or 1.5 TWhr/month of extra demand. For comparisons that is (based on mt reading of this report) about 0.1% of the total US electricity demand.

The best kind of vigilante justice

Every once in a while a story pops up about someone who takes the law into there own hands, almost always indicating a failing on some level: like the story of the town thug who got shot dead in the middle of a crowd of several hundred people and not one person saw the shooter.

Well here is a story that is just about the best possible case of vigilante justice I can think of: thief robs man, man tackles thief, man cuffs thief with wire ties, thief left for police in middle of main street. Now aside from the going after someone wielding a knife, and (maybe) the public humiliation factor, I can't see anything anyone can object to.

Google is funny.

I A few hours ago, Claimed a site in google's web masters tools. One of the ways to do this is to add a file by a given name to the site. Well I added the file and finished the process. A bit later I took a look at the IIS logs and found this (slightly edited):

12:36:46 72.14.194.33 - ... 69.49.230.86 80 GET /GOOGLE[...].html   - 200 0 Google-Sitemaps/1.0
12:36:46 72.14.194.33 - ... 69.49.230.86 80 GET /noexist_[...].html - 404 2 Google-Sitemaps/1.0
12:36:48 72.14.194.33 - ... 69.49.230.86 80 GET /google[...].html   - 200 0 Google-Site-Verification/1.0
12:36:48 72.14.194.33 - ... 69.49.230.86 80 GET /noexist_[...].html - 404 2 Google-Site-Verification/1.0
12:36:48 72.14.194.33 - ... 69.49.230.86 80 GET /google[...].html   - 200 0 Google-Sitemaps/1.0
12:36:48 72.14.194.33 - ... 69.49.230.86 80 GET /google[...].html   - 200 0 Google-Site-Verification/1.0
12:36:48 72.14.194.33 - ... 69.49.230.86 80 GET /noexist_[...].html - 404 2 Google-Sitemaps/1.0
12:36:48 72.14.194.33 - ... 69.49.230.86 80 GET /noexist_[...].html - 404 2 Google-Site-Verification/1.0

Why the heck does Google need to load the same file 4 times? And why do they ask for another (nonexistent) file 4 times in a row. OK, yeah they have bandwidth to burn but it still seems a bit sloppy.

Bayesian statistics in the general media.

This page needs more visibility. The take away is that, way to often, peoples first guess is wrong when it comes to statistical problems.

Creative Phrasing

Found in a Police Daily Activity Log July 8, 2009, 20:48

A moose is in the field, between Rolling Hills area and Moser, was in a yard. Escorted from the city.[Emphasis added]

I like the way that's phrased...

The Consequences of Deciding and Timeing

This article on the consequences of not deciding brought to mind a story about one of the US presidents (sorry I don't remember where I heard it or the president's name): When asked to make a decision, he would ask how long he could wait to make it. Then he would ask the person to come back in that amount of time and then he would make the decision. Almost always he would have better information to decide with and sometimes all but one of the options where clearly wrong that that point. The trick here is that he needed to get a correct answer to his question; how long could he wait without causing other problems or adversely effecting his options. The upshot is, make decisions as soon as you must, but no sooner.

Group size and unity.

This essay brings up some interesting points about group size and group dynamics. This kinda sorta ties into an idea I'd love to see tried: build a loose group of small highly specialized businesses set up to cheaply collaborate on projects. Each small business would be about 3-8 people and 3 or 4 of them (say a programming shop, a graphical design shop and an electrical engineering shop) would work closely together on a project with a few more acting as support (say a fab shop, a legal office and a secretarial service).

The essay at the top lends a bit of empirical support to this idea based on group sizes effecting how well a group will work together. As for this actually working, these people seem to think something in the same ballpark is a good idea.

Beating CAPTCHA can be a good thing.

Anyone who has been around for a while has run across CAPTCHAs. These are one of the current state of the art weapons in the detecting-bots-arms-race. CAPTCHAs general boil down to finding problems that people solve easily and computers are really bad at and asking your user to solve it. One of the interesting things about this arms race is that CAPTCHAs can be designed so that successfully breaking one requires creating a better program for solving a problem that is valuable in the real word.

One example of this is reCAPTCHA. They take the best OCR they can get there hands on, find text it can’t read, make the text even harder to read and then fork it out for bots to do there best with. For someone to beat this, they would have to make a better OCR program. This has two interesting effects. First if the bot gets into general circulation (and it will sooner or later) reCAPTCHA can just start using it in there OCR system and be back on top. Second it furthers the state of the art in ORC and that is valuable in it’s own right.

This thought has some interesting implications. More generally what a CAPTCHA does is use problems that are hard to solve but easy to check the solution on to make automatic access to a resource to expensive. How about doing this more directly? How about find commercially valuable computational problems that can easily be broken up into chunks that have this attribute and can be solved in a few seconds and checked in microseconds. Then the bots would need to expend a few CPU seconds per page load to access a site.

One implementation of this could be a browser plug-in that allows you to bypass the CAPTCHA on a site. The publisher of the plug-in would push out code packets that the plug-in would be required to run. Sites that run the CAPTCHA could even get paid to use it (some fraction of what the central server gets after expenses) and to make things fun, the whole things is open so that anyone who wants can try to write better solutions to the problem. One neat trick would be to try to set the price paid by the central guy so that if you can improve the solver enough, you can make money by getting your own account and just solving problems after problem. Or if you that doesn’t make enough money fast enough for you, just sell your solution to the central guy.

Stackoverflow Flair widget

I have made up a quick hack of a page to add a Stackoverflow Flair Widget to a blogspot blog.

Note to the stackoverflow team: you have my permission to use that page wholesale if you want.

Open source; not just for software anymore.

This comapany in the UK (I think) is making an "Open source" hydrogen car.

I think this is a really cool idea and I'm interested in how it will pan out. I have thought it would be interesting to do something like this but I had always thought along the lines of a DARPA grand challenge like project or something fictional like a the spaceship Michael.

Serialization for D part 6 of n

The latest and greates for my library is out. The new stuff for this edition is support for arrays and (limited, somewhat clumsy) support for 3^rd party types.

The array support is transparent but the 3^rd party type support adds some new stuff to the API. I went with the function pointer approach and have a simple interface for attaching a pair of function to a given type.

I'm thinking that a number of use cases will be common enough that I should create some boiler plate implementation for them. The first that comes to mind is serialization the same way that the rest of the types are; that is serialize all the members. Other cases would be to pull only selected members or to use a constructor to build the object rather than member assignment.

I'm looking for ides for other cases so comments are welcome.

Looks like the bad guys are winning....

I wish we would see more people thinking like this fellow with regards to fear over terrorist using services like Google Earth to plot attacks rather than the people he is quoting.

If it weren't for the fear that I'd see it done, I'd write a satire about a terrorist cell that attacks systems they want shut down by using those same system to attack other targets they don't even care about.

Thank goodness Linux != Probable cause

It's nice to see people making rational decisions in the legal system. For instance: running Linux is not Probable cause for a search warrant

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.

Serialization for D part 5 of N

I figured out why the hard-link stuff wasn't working as I was expecting; I had the annotation on the referring type rather than the referenced type. Fixing that wasn't much of a problem and cleaned up some other code in the process.

Well, with that, I think I'm done with all the easy parts.

The next bit I'm planning on tackling is 3^rd party types. That is how to serialize types that you don't control and can't add stuff to.

I don't really like any of the options I've come up with but I think I've got something that will work. If anyone has any better ideas, I'm interesting in hearing them.

The Compile Time Option

It would be nice to make it just a call to function like Serialize(value,sink); but that only works as long as all the overloads are all in the same module.

module t1;
int Baz(int){return 1;}

---

module t2;
int Baz(float){return 2;}

---

import t1;
import t2;
import std.stdio;

void main() { writef("%d, %d\n", Baz(cast(int)0), Baz(cast(float)0)); }

---

m.d(5): Error: t1.Baz(int) at t1.d(2) conflicts with t2.Baz(float) at t2.d(2)
m.d(5): Error: undefined identifier Baz

Several other ideas also fall afoul of this issue forcing me to conclude that their is no way to, at compile time, cooperatively resolve overloads. That is, at some single point in the code, the user needs to fully state every source of overloading. I really don't want this.

The Run Time Option

The next thought is to use run time lookup (an AA based on T.stringof or T.mangleof) to locate the processing functions. I already use this to extract derived types. In that case I at least know that everything in question is an Object but for this case I don't. Another issue I don't like here is that I ether need to do unsafe casts on function pointers, data pointers or return types. I think I can make sure this is valid if all access is thought template accessors but I'd rather not have to. And finally, this option is to hard to test because you can't be sure it's right until you exercise every type, including those in third party libs that might change on you.

The Boot Time Option

The option I think I'll go with sort of fakes the run time option but with better compile time support. The way I'm planning on working this is to have a ThirdPartyAccess(T) template that defines global function pointer variables for Serializing and Deserilizing. These function pointers are accessed freely at run time to do the work. As for the derived type setup, these will be populated at program startup by static constructor generated when the used defines what function to use for a given type:

module TheirTypes;

import SomeTypeLib;

void SerSomeType(SomeType, Sink!(char)) { ... }
SomeType DeserSomeType(Source!(char)) { ... }

mixin WorkWith!(SomeType, SerSomeType, DeserSomeType);

I still don't like this because I can't figure out a clean way to be sure each and every function pointer is populated exactly once. The best I have come up with is to have a -debug switch that turns on check code in a static destructor to verify all the pointers are non-null. This has the odd side effect or making it a good idea to put in a quick start-n-stop feature to exercise this code. At least, a with static constructor ordering, this will fail reliably when things are wrong.

The Link Time Option

Now, I think I can make the boot time option work but I don't like it that much better than the run time option so I'll sketch out a feature I'd like to have for this use case. For lack of a better name I'll call it extern templates. The idea is stolen from C's extern global variable. In effect, let the user use whatever variable they want, define them wherever they want and let the linker sort it all out:

module a;
template Foo(T) { extern int V; }

int SomeFn()
{
   writef("%d, %d\n", Foo!(int).V, Foo!(float).V); // prints "5, 6"
}

---

module m1;
import a;

Foo!(int).V = 5;

---

module m2;
import a;

Foo!(float).V = 6;

In the example code, the template allows references to a variable and the code in m1 and m2 actually provides the definition. When compiled, m1.obj and m2.obj would contain the symbols and a.obj would only contain external references to them. I'm sure there are some interesting corner cases that make this not so nice (and the definition syntax is down right ugly) but it sure would help in some cases.

Oh, Man I want one of these!!

This "in house" print on demand system prints books faster than some places can make you coffee (and they call it the "Espresso machine")

Serialization for D part 4 of N

There added isn't much this time. The biggest thing is support for repeated objects (think hardlinks). Aside from that it's mostly cleanup and renaming (breaking changes, sorry) and a few tweaks to the Source/Sink interfaces.

One of these days, I really need to get around to improving the comments...

source link

Serialization for D part 3 of N: with Code!

I have published reasonably working version posted here. It's very much alpha and I haven't documented it much at all.

What works is user defined types (structs and classes) where every member is to be serialized. The one fun case that works is driveled classes (that wasn't as hard as I though it would be) as long as the base class is also serializable.

A quick tutorial

First, invocation:

void main()
{
 // something to work with
 SS ss = SS(42, 2.717, new DS(1));

 // A data sink
 Si c = new Si();

 //------- Run the serializer
 marshal(c,ss);

 // show the data
 writef("%s\n", c.get));

 // make a Source from that data
 So s = new So(c.get)

 //------- deserialize stuff.
 SS sd = SS.DemarshalMe();

 // show the results
 writef("%s\n"%s\n", sd);
}

To serialize something, you need a data sink to dump it into and to deserialize something you need a source to pull from. In this example, I use an basic sink that just stores into a buffer and a source that pulls from one.

Next, The data types.

/// A struct to serialize
struct SS
{
 mixin Serializable!();

 int foo;
 float bar;
 CS cs;

 char[] toString() { return format("<%s,%s,%s>", this.tupleof); }
}

/// a base class to serialize
class CS
{
 mixin Serializable!();

 int i = 5; float j = 3.1415926;

 this(){}
 this(int) { i++; j++; }

 char[] toString() { return format("<%s,%s>", this.tupleof); }
}

/// a derived class to serialize
class DS : CS
{
 mixin Serializable!();

 real f = 2.717;

 this(){}
 this(int) { f++; super(0); }

 char[] toString()
  { return format("<%s,%s>", super.toString()[1..$-1], this.tupleof); }
}

Serialization for D part 2 of N

Well I did a quick hack and got a really basic version going. It only handles XML (with some ugly formatting restrictions) as the format and is restricted to structs, classes that are used like structs, and basic numeric types.

The up side is that the API/usage is just like I was expecting to do it and I didn't run into any problems. The down side is that I was kinda expecting it to take longer that this (all hyped up and nothing to do).

The next bit I'm going to work on, is to loosen up the XML formatting, but that should be easy. After that I'm going to dive into making polymorphism work.
On that note, I've thought of a few more issues I will need to deal with:

Public and Private Base Class Members

The off the cuff solution is to call base.Serialize either before or after dealing with all the direct members. But that doesn't address how to figure out what the base class members are.

Template Types.

The primary problem here will be making sure the correct type is deserialized, a.k.a. error checking. For internal nodes of struct types this shouldn't be a problems because there it is all static so if it's correct at the top level, it's correct throughout.

Template Types + Polymorphism

This adds another wrinkle to that problem. The wrinkle pops up where a template class derived from a non template class. This can result in trying to deserialize a type that wasn't instantiated in the code doing the deserialization.

Unions

This one is going to be nasty. I think I'll just ignore it for now. Later some sort of callback might make it work. As I said, not now.

Reading between the lines.

I just ran across this news article. The up shot of it is that a 13 year old kid in Minnesota who is suffering from Hodgkin's lymphoma, attempted to refuse traditional treatment for it (possibly for religious reasons) apparently with the approval of his mother. Somehow it ended up with a court ruling that he could not refuse treatment because his doctors said he will die without it. After that,he and his mother fled for Mexico.

Now the fleeing the country bit might be illegal depending on the custody situations but who cares. The biggest piece of the story in my opinion is that a court decided that it has the authority to overrule someone on what happens to there own body! (and this is barely even mentioned until halfway down the page)

Now I'll grant that there might be more to it, for instance; dad says, do the treatment, mom says do what the kid wants and the court goes with dad. Even if that is true, from the way it's written it seem that the court ruled based on what it thought was best for the kid, not based on who it thought should decide. And from the way it's written, it seems the author this that is just fine.

Finally, some rational thought in mainstream media!

This guy, who seem to known what he's talking about most of the time, got quoted by CNN about post 9/11 airport security.

As he puts it, the mentality seems to be "cover your ass". Nobody in a position to do anything is willing to say "no" for fear that something will happen and they won't be able to say they did everything they could.

This sort of reminds me (by contrast) of the time I was talking to a Philosophy masters student and after a bit of back and forth I asked him the question "Would you rather have security measures that make you feel safe, that you know are utterly useless or ones that don't make you feel safe and actually make you safer?" To my utter shock, he asked for the first.

Serialization for D part 1.1 of N: comments

This is as much notes to my self as anything:

• Thanks to Chad for pointing out that I need to consider what license I will be using. (I'm planning of being very permissive there.)
  
• Several other people have pointed me at their own work. I guess I'll have to check what license they use. OTOH, while I really want to make a good usable library, this is just as much a "lets have fun with template" project.
  
• Tim Matthews pointed out another source/sink I will want to consider: databases. Being able to use a byte array would cover that one I think.
  

Serialization for D part 1 of N

I'm planning on starting work on a template based serialization liberty for D. The objective is to be able to, from a single line or two of code per type, generate the needed function to stuff complex types into a file, network socket, byte buffer or whatever. At this point I'm still puzzling out what the interface will be.

1. What will using this library with a type look like?
2. What will invoking the code look like?
3. What format will be generated?
4. What will the source or destination for the data look like?
5. How to work with polymorphic types?
6. What types of limitations will it impose?

Taking each of these in the order I thought of them in

Usage

Ideally I want using the library to be a simple as possible, a single line of code would be best. For built in types, this is easy as the system should "just work". User defined types will be the more interesting case. I expect I will want to build several different solutions for different cases. For example, in the case where everything should be just slurped up or spit out, it should be as a simple as no arguments mixin:

 class C
 {
  int i;
  someClass c;
  mixin Serializable!();
 }

Other cases, for instance where some values need to be omitted or where proper use of constructors needs to be observed, could use other approaches.

• Process only the members on a given list
• Process only the members not on a given list.
• Deserialize by calling a constructor on the given values
• Tag nodes on the way out and resolve references so that multiply referenced objects come through correctly resolved.
• Various combinations of the above

One other bit that might work is a module level "make everything serializable" template that does default serialization of every type in the module. The problem with this is that to make it work the system as a whole will need to deal with both external and internal definitions of serialization functions. On the other hand, this will be needed anyway for built in types and maybe, 3^rd party library.

One minor point is how to structure everything. Because it has a lot of redundancy in the different combinations, some way to reuse code is needed.Something like the recursive self mixin trick might do well.

Invocation

The hard part here is the naming (one of the two most difficult tasks in programming). For now I'm just going to go with the simple solution:

 MyType myType;
 myType = MyType.Deserialize(source);
 myType.Serialize(sink);

If anyone has a better idea what to name them I'm open to suggestions.

The other side is how to structure adding serilization for external in types. Built in types are easy, a simple template function that get called if T.Serialize doesn't exits (or the other way around). The harder cases is 3^rd part types as (last I checked) getting template to overload from several sources is hard.

Format

For this there is a few interesting option classes:

1. Machine specific binary
2. Machine neutral binary
3. Text: XML/Jason/YAML/CSV

For starters, I'm going to do just XML as I can read it so debugging will be easier. After that, I might go for a machine specific binary format and try to abstract out the rendering parts to reduce redundancy.

Data Source/Sink

This is one point I'm not sure on. What should be the primitive source and skink? A Phobos or Tango stream would be one option, but it would be nice to be Phobos/Tango agnostic. Also, might other systems be desirable? I think I'll try and keep the implementation dependent code for this loosely coupled and well contained so switching later is easier.

Derived Types

One major problem will be how to handle polymorphic instances. The best I can think of is to have them embed a type tag into the output stream and then use some sort of tag to delegate map to deserialize the stream. This has some interesting implications on the operation; for instance with XML, it indicates that the outermost tag of a type should, at least in part, be serialized by the child type but deserialize by the parent type. One options is, given these types

 class C { }
 class D : C { int i; }
 class E : C { float x;}

 struct S { C ofTypeC; }

an instance of type S is serialized as:

 <S><ofTypeC typeis="D"><i>42</i></ofTypeC></S>

This would have S.Serialize output up to the attribute and then hand off via a virtual Serialize call to the member. On the other hand, S.Deserialize, would consume the full ofTypeC tag and then use the attribute to call the correct Deserialize function. This clearly ends up adding a some annoying overhead so some way to detect (or indicate) that no derived types will be used (and check to make sure that is so) would be nice.

Limitations

One thing I'm not going to handle is marching references for aliasing and slicing of arrays. Just because something is a slice of something else on one side, doesn't make it so on the other.

Aside from that, I don't known what limitations I'm going to impose, but I'm sure I'll find out as I go along.

Automatic Discretization of a 2D Geometric Obstacle Map

The following is a report I put together for a Technical writing class about some work I did for an "AI for mechanical engineer" class.

Abstract:

The problem of routing pipes and wires around real world obstructions falls under the category of path finding and as such tends to be a computationally complex problem. It can become even more complex than the classical single path problem if many paths need to be found and the choices for them interact, for instance thought space constraints, electronic interference or crosstalk. One approach to reducing the computational load is to reduce the geometric map to an abstract discreet graph and select and evaluate options categorically. This report considers and evaluates techniques for doing this conversion.

Introduction

A number of system layout problems can be broken down into two steps; positioning the major components, and routing the connections between the components. In order for the results from the first step to be automatically evaluated, the second has to be automated. This problem is known as the path finding problem and is known to in general, be of exponential complexity. One way to make this problem more tractable is to convert the obstacle map into a much simpler mathematical graph resulting in a much smaller exponential complexity problem. This will allows more options to be considered and more complex problems to handled.

I have considered two solutions to this problem and, after producing partial solutions to both, determined that one was significantly better and continued that solution to a fully working proof of concept.

The final results only demonstrate a concrete implementation of the concept showing that it is reasonable to compute and that it generates reasonable results. The implementation doesn’t attempt to be more than reasonably efficient.

Discussion

Options Considered

I considered two basic operation principles. The first principle works by finding local maxima for the closest obstacle function. That is to locate positions that can’t be moved away from any nearby obstacles without moving closer to another one. Intuitively this is like inflating a balloon until it fills some region and calling its center a node. These positions were located My implementation used simple hill climbing but partial swarm optimization or simulated annealing might provide better performance.

The second solution worked by locating “pinch points” and treating them as region boundaries. This can be though of as defining rooms by picking what will be counted as a door. The pinch points (doors) were identified by selecting from the lines of closest approach between pairs of obstacles.

General Results

The balloon solution was simpler to implement and, based on preliminary results, tended to generate reasonable results. To generate reliable results over the full map it required many starting locations. This caused it to run very slowly, hampering its usefulness. This might be overcome if some type of dynamic density function could be uses to select more starting locations in smaller passages and fewer in open areas.
The pinch point solution was more complicated to implement but also generate reasonable results and ran many times faster. Based on these results, I chose to only finish implementing this solution.

Restrictions
The final algorithm assumes an input map consisting of non overlapping, convex polygons. The implementation imposes a few more restrictions:

1. The line of closest approach between any two polygons must not share an endpoint with any other for another pair or polygons.
   
2. The map must be bounded by a known set of polygons, in a known order.
   

In practice these might be unnecessary restrictive, for instance some concave polygons might work and some cases of shared line endpoints will work, but the exact conditions where this is allowed are harder to define. Also, improvements in the implementation could allow further relaxation of these requirements.

Methods



Figure 1: The example input map

I tested the program on an example map was selected to provided a variety of features and scales. These test helped in the development of the program by giving concrete results and by reveling a number of flaws (that were fixed) and limitations (that need to be avoided) during the development process.



Figure 2: Minimal separation lines

The algorithm operates in several stages. The first stage is feed the initial map and finds the shortest line between each pair of obstacles. Only lines that don’t cross inside of another obstacle are kept.


Figure 3: Region boundary selections resulting in a plainer graph.

This set is then filtered to remove crossing lines with a preference for keeping the shortest lines. This results in a plainer graph with the obstacles as nodes and the lines as edges.


Figure 4: Map with node selection

The interior regions are then identified from this. My implementation does this using a wall following technique. Because all the connecting edges don’t connect to a single point this is somewhat complicated and somewhat of a kluge. To ensure that all interior regions are found, the edges are scanned and each one is traversed exactly once in each directions (this can also be thought of as on both sides) skipping over cases where the edge has been traversed from a previous starting point. This requires either that the exterior edges all be marked from the start as traversed or that the wall following method correctly follow the outside as well.


Figure 5: Final graph with nodes and connections

Once the interior sections are identified, the connectivity graph can be found by connecting any two nodes that are bounded from the same link.

Complexity Analysis

1. Finding all links and filtering on overlap with polygons: O(n³) maybe closer to O(n²)
    The number of links is O(n²) and each needs to be checked with each polygon giving the upper case. Better data structures could reduce the cost of the intersection test but not to a constant cost.
   
   
2. Filtering links for overlap: O(n³) maybe closer to O(n²)
    Each of the O(n²) links needs to be checked with each previously accepted link. Given that the result is a plain graph, only O(n) links can be accepted giving the upper bound. Again, with better data structure this might go even lower, but not to a constant.
   
   
3. Region selection: O(n)
    Each of the O(n) links will be traversed twice and each traversal has a cost (for finding the next link) proportional to the O(1) average number of edges per node.
   
4. Connect the regions: O(n)
    This can be done in constant time per link.
   

The worst case, the solution is O(n³), however this might be able to drop to nearer O(n²). Given that this is a precursor to a O(b^d) operation and is cutting back on both b and d, even the worst case result is a clear win for any reasonably sized problem.

Conclusion

My work has show that the basic algorithm of segmenting the map along lines of closets approach is sound. However it also reveals some weaknesses in my implementation. The largest weakness is that the wall following solution is not robust enough to deal with the edges of the map. As this part was not my primary interest I didn’t put much work into it. For a production implementation, it would be worth while to spend some time exploring better options.

Hm... this sounds familiar

Jon Skeet: Coding Blog -- Language proliferation

Sounds like MS is creating support of a large number of languages on .NET. They are still GPLs but it's looking where I think they should go.

I think I started with the wrong lable on this one, what I'd like to see is not a pile of domain specific languages (DSLs) but special purpose languages (SPLs).

Turnabout's fair play

Quoting from a letter to Scientific American by Oscar Estévez about Creationism, Intelligent Design (ID) and the theory of evolution:

The questions they [students] should ask are, Does ID make predictions? And can those predictions be tested? If the answers to both are negative, they themselves can conclude that ID is "only a nonscientific theory."

I'll ask the same in return:

Does the theory of evolution make predictions? And can those predictions be tested? If the answers to both are negative, you can conclude that the theory of evolution is "only a nonscientific theory."

I challenge Mr. Estévez to point to point to a predictions made by the theory of evolution that can be tested and where the test will show it to be either true or false.

Note that there are a number of predictions made by the theory of evolution than can be show to be true but can't be show to be false. For example, failing to demonstrate the creation of new species can always be discounted on the grounds of "We just didn't run the experiment long enough" or "we haven't found the right fossil yet".

Pilotless airplanes and securety implications.

This article brings up some thoughts from Israel about making airlines without a cockpit. The tone is a bit condescending (I don't think the author likes the idea, and I'd be hesitant to fly on one my self) but down at the bottom is a comment that is down right caustic, starting with:

I hope those science engineers had figured out the motives of Al Queda for taking control of one of these unmanned planes.

and continuing with concerns about someone getting remote access to the airplane and using it for mischief. Now that is one thing I'm not to concerned about. For one, the flight program on an unmanned airliner would be one of the most carefully designed programs ever written. If you can count on anything, ti would be that it can't be overridden remotely. As for other attacks, in this day and age, if you can access the avionics software of a plain, I'll bet you can lockout all the cockpit controls and fly it into whatever you want so I don't think there is any more risk cropping up here than we have right now. Frankly, I suspect physical takeover of a maned plane is more likely.

"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;
}

Some musings on David Weber's world.

A while back I finished off all the available Honor Harrington books. The last one has a foreword that mentions that there are already two more books fully written and in the pipe. So having a mind that just will not shut down, I started pondering what will happen. It doesn’t help that their author, David Weber, finally dropped a cliff hanger on his fans. Any way I realized that I’m in an interesting position; I have a theory as to where the next books are going and they are already fixed so I can’t influence them. So what I’m going to do is throw my speculation out here on my blog and in a few months when the books come out see how it matches. If it does, well cool. If not, it’s kind of fun anyway.

For starters, I have no special knowledge of Mr. Weber’s plans. All I know is what I have read in his books and a little on-line research. (So Mr. Weber, if I get this all spot on, don’t sue me or you will validate it). All of this is based on speculation and the two rules of good story telling:

1. The story must be reasonable and believable.
   
2. The story must be entertaining (or addictive)
   

It wouldn’t be believable for Manticore to come out to easily (and with no peril it wouldn't be fun either) and watching you team get utterly crushed would drive the fans away (and coming back from that wouldn’t be believable either) so it will be somewhere in between. Also that leads to some very fun sub plots that can come in.

Last we saw, the Sollies were about to hit Lynx like a ton of bricks on a hard floor and Mesa was about to drop a pile of pods in on Manticore. On a side note, I’m a bit surprised Weber didn’t bring out that option earlier. He could have had 8^th fleet drift in a few pods or mistletoes while the destroyer/scout/decoys were playing their shell games in various Haven system. It sure would have resulted in some funky head games not to mention cost the Peeps dearly in Moriarties and trained crews. Anyway the question is what happens next. Here’s my theories:

The first interesting thing (and more or less a given) is when the Sollies attack the Lynx terminus. As with the ton-o-brick vs. floor, the floor wins. To counter it Honor and 8th fleet is sent through to Talbott putting a substation portion of the Apollo equipped ships and their auxiliaries in Lynx. While they are out of position (leaving, gone or on the way back; I'm not sure where Weber will put them), the Oyster Bay ballistic pods attack, and severely damage most of the Manticore yards and many of home fleet ships that didn't go to Lynx. I can't spot how it could be worked in but I it would be handy if the yard tech crews get out somehow (massed builders trials might do it but that seems a bit clumsy).

As a result of the fleets being out of position at home, Oyster Bay is blunted to some extent but still hurts Manticore a lot. Somewhere in all this, the Mesa spider drive ships attack. The partial failure of the ballistics component cause a less than complete success by the manned elements. As to what happens to the Mesa units, I’m inclined to go with them taking a royal beating including most of the units getting capture or more likely, destroyed. I’m, not sure which book that will happen in because it doesn't fit in the mold that seems to be set up for Torch of Freedom but Missions of Honor comes out second and it would play better if the reader doesn’t get a preview.

One Bit that would have to be in Torch of Freedom is whatever Zilwicki and Cachat have been up to. (I’m really glad Mr. Weber let Mr. Flint play with his toys, those two characters are some of the most enjoyable I have come across (in any storyline) and, based on the Storm from the Shadows foreword, they may have, in real life, saved Honor’s life) It doesn't take much guess work to figure out that they are going to be infiltrating Meas. What I suspect the upshot of that will be, is they learn of Oyster Bay, Mesa's other plans and both the spider and streak drives. They won't get the full story as it seems Mesa's plans are going to be parceled out over a few books at the least. On the other hand, the tech stuff is going to come out soon enough anyway so they will capture documentation, hardware or complete examples of a spider drive. At a minimum, they will get enough to, probably with a little magic on Hemphill's part (or Foraker's, keep reading ;-), figure out how to detect the spider drive. The first real question mark is the streak drive. Henke and the rest of the Talbott crowd is starting to twig to the fact that the "Mesan's mail is running a bit faster than every one else's" so I suspect that will come out also. It would fit their swashbuckling ways for Zilwicki and Cachat to capture a functional Mesa streak drive courier ship and make a run in it for Manticore via Lynx. The next question mark is the timing. They can't arrive to soon or the ship yards could be saved, but to late and it looses some dramatic/tragic weight. I'm going to guess they will show up in time to do some good regarding the manned units or just after the dust settles. (The other option is in time to save the yard dogs but not the yards them selves. For that to work the pods need to be really hard to spot or a pattern of nukes could soft kill them even with lousy target locks).

Now this is getting really speculative, but if Torch of Freedom ends with Zilwicki and Cachat on the way from Mesa to Manticore that would solve the problem of springing Oyster Bay without a preview.

Anyway As for the aftermath in Manticore; Elizabeth, with information from Zilwicki & Cachat, a Manty/Solly war looming and devastated ship yards, will do the "I still hate the Peeps but I need to ignore that" bit and make an abrupt command decision to send Honor directly (and uninvited) to Haven to offer not only peace but an alliance. Honor arrives with a very small task force (on the order of a single Apollo wall’er and a few screen ships to make sure they get Havens attention) as a pointed reminder that Manticore can still hurt them but isn't. Honor does here usual thing of steamrolling her way into what she wants by, with impeccable manors, assuming that she will get it. In this case, what she gets is immediate talks (as in least time to Haven orbit and "meet me at the shuttle pad" immediate) face to face with Pritchart. After hearing what Honor (and maybe Cachat) has to say Pritchart jumps in on the spot.

In a nice political whiplash, Haven sends units to help protect Manticore (some joyfully hated people all but die of indignation at this). In the other direction (and to the great displeasure of a few Havenites) Manticore sends tech crews displaced from the Manticore yards to Bolthole along with the Zilwicki and Cachat's finds. This would lay the ground work for a few threads like getting Hemphill and Foraker working together and the fun, technological and sociological, they could create. (I just realized, I don't think we have ever actually met Hemphill.)

That's about as far as I’m willing to lay out details but I'm actually more comfortable with the big picture further down the line than the details in close. The Mantcore/Haven alliance has two problems. First the Sollies want to pound Manticore and will be running scared when they notice that the only advantage they have left is quantity. The other is whatever Mesa is up to. As the old truisms goes; one problem, is one problem, but two problems, can be two solutions. In line with that, they begin attempting to use Mesa’s operations to turn groups of Sollies away from war. Some sectors immediately jump on board or get out of the way and others get caught in a meat grinder when Mesa plays hard ball. Other sectors governments are clearly to invested and will have to be removed by force. Some of them will fall to Mesa, others to Manticore and Haven. Either way the Sollies fracture along the lines of what Honor outlined in Storm From the Shadows. As for Mesa, the less than total success of Oyster Bay and the Zilwicki/Cachat debacle puts them in a bit of a bind but they invoke the "no plain survives contact with the enemy" line and continue on with a nice show of operational agility, pragmatism and determination.

Now that I look at all of that, I'm think I've covered both the books in the pipe and started in on the next one on the main line. So who knows, some of this might effect the story after all.

This seems a bit "off" to me.

I'm haven't dug into this at all but something is not right here:

FBI Defends Disruptive Raids on Texas Data Centers

The up shot of it is that the FBI raided a few data co-location centers based on a fraud claim by AT&T and Verizon (basically unpaid bills for accounts that my have been set up with falsified information) and walked out with hundreds of servers who's only crime might well be that they were in the same co-location building a servers used for a crime... maybe.

If this was a Hollywood drama/comedy I can just imagine the ending:

FBI spokesman, a year or so down the line: We'er sorry about putting those businesses into bankruptcy by taking there servers because we couldn't tell tell they weren't owned by the bad guys we were after and didn't bother listening to the site manger when he told us exactly that.

I don't think it will be that bad but I'm sure someone should feel ashamed of how they ran this little operation.

Another DSL*.NET language idea

I just came across this post and it made me think of yet another language I would want in a DSL*.NET system: A secure language. That would be a language (probably a scripting type language and a set of them to boot) that are intentionally crippled so that my program can safely run them without having to set up sandboxes.

To follow Mr. Haack's example, a language that is flexible enough to construct a DOM but can't do much else would be rather doable by something like dropping parts of the using semantics so that the code can only interact with objects passed into it and with statics that it defines.

It's not a finished and polished idea but you can see where I'm going with it.

The problem with being overly literal minded.

A number of time I can recall saying (or typing) something and then noting that while what I actually said is exactly what I meant, most people will read between the lines and get something else out of it that is not what I meant. The first example of this I can think of is years ago, asking my dad "Do you know where the whatever is?" Now when he (or most anyone, including my self once in a while) asked that sort of question he would expect people to if they could, help him look for whatever it was he was looking for. The problem was I was asking "Do you know where it is" and exactly nothing more, in fact in that cases asking more would have been rude.

I have run into the same sort of thing a few other places where I ask one question that usually is an implicit request for something else but in a situation where that something else would be rude to ask for. A more recent example would be asking a question on a forum where I could Goggle for the answer in about five minuets. Asking someone to go do my research for me would clearly be rude but what about a question that someone who knows the topic could answer in 15 seconds? I sort of end up stuck in this corner; do I burn five minutes on Goggle trying to find what terms to ask for? Or do I risk sounding rude and selfish on the (fairly good) chance that someone who knows the answer will help me out?

What I often end up doing is spending about half my words explaining what I'm not asking for and it always comes out awkward. I think the whole problem for me comes because (I think) I tend to form loose concept associations. There's the idea of what I want to ask, and the words I use to ask it and because I get the first fully formed before I start in on the second, the implications of the phrase I end up wanting to use don't enter in the decision of whether to ask the question at all.

I'm not trying to change the world (I can't) and I'm not expecting the world to treat me different (it won't) and I'm not even asserting I'm smarter than other people (that's a sort of useless topic to begin with in my book). It's just an interesting thought I had at a way I keep getting tripped up.

The advantages of O(b^d)

The punch line is that the advantages of exponential time complexity is that even small improvements in performance are not so small.

For instance; When I finely got the alpha-beta pruning correct (I think) on my Connect 4 AI and it's effective complexity went from O(7^{0.7 d}) to O(7^{0.6 d}). For d = 13 that's 49 million leafs to 3 million leafs.

This is the same principle that make this idea reasonable

How true it is.

If you belonged to the world, the world would love you as one of its own. But because you do not belong to the world and I have chosen you out of it, the world hates you.

John 15:19

A friend of mine ran smack into this down in the Dominican Republic. What I find "interesting" about this is that I rarely hear about this sort of thing with other faiths, just with Christianity.

Irony: the Alanis Morissette kind

Actually, I find it more funny than ironic, but whatever it is, it is a little annoying.

I was searching for literature on Mandatory Work First ordering and guess what, I'm the top hit for "Mandatory Work First" min max. Lot of help that does me.

It's sort of like being your own sys admin when things go wrong:

Computer: "The system has crashed. Please contact the system administrator"
Me: "Ok self, fix it"

fun with AI's

My connect 4 AI has improved yet again. This time around I just tweaked it so that I compute the full score for each state in the BFS potion of the tree and sort each group. With this improvement, I'm running to a depth of 12 in less than 30 seconds. I've still got a bit of tuning to do (some ad-hoc testing shows that running the BFS to a depth of 3 is several times faster than a depth of 4 on the single core machine I was using)

After that's done, the next bit is to figure out how to do a sliding depth scale to leverage all the remaining time. I expect that the progress vs time plot is going to be rather interesting.

On another front, I am back in the lead; I figured out how to beat the AI while playing second!

My AI is working (mostly)

As I posted a few days ago, I'm working on a connect-4 AI as a class project. It turns out that counting the children works and the whole thing performs well (at least as fast as the single threaded version)

The solution ends up working by keeping a count of how many unpropagated children each node has. When this goes to zero, the nodes value is propagated up the tree another level. The only tricky part is building the tree in the first place. The issue here is that you can't propagate stuff while the tree is being built so it has to happen as an intermediate step before the leaf processing.

Once all that gobly-goop is done the main evaluation runs just fine. However I still haven't figured out how to do any better than evaluating the leafs in the order they fall in (fact is I haven't even coded anything yet, only puzzled over it). That works very well because, most of the time, both threads are working on nodes that share a parent so alpha-beta pruning works correctly. At 2 threads, I suspect that I'm running at almost 100% efficiency but if I stared using more threads (say more than the branching factor) I would expect that to drop a lot.

The next thing I'm planning on trying will be to run my heuristic function on all the nodes and sort each group of children as they are generated. I hope that this will better optimize the alpha beta pruning and might even give an order where I can get something closer to ideal while adjusting the depth based on time renaming.

In asking around for others solutions I was pointed at this paper that mentions something called "mandatory work first" that might mesh well with my stuff if I can figure out how to sort based on it.

Anyway, the code functions and beats me easily. On the other hand I have a few more tweaks I want to try. Fun!

Fun from the code lines.

My current school project is an AI for playing Connect-4 using minimax. The first bit was fun, lost of low level bit twiddling, building bit adders, monster functions that do recursion without recursion, finding bazaar optimizations... all the kinds of stuff crazy people like me enjoy.

After I got it to the point it could beat me, the real fun started!

So far I have, at least twice, found places where I had the AI’s playing the wrong side ("Here, let me help you win!") and then spent the better part of two days trying to figure out where the typo in a fundamentally broken algorithm was.

The thing was that I was looking to speed it up by going multi threaded. The way I was planning on doing this was

1. Run the first few levels of the min-max tree in a breadth first evaluation


2. Sort the leafs based on how good they look


3. Have several threads do the normal depth first bit on each leaf


4. Stuff the data back up the tree.

The theory here was that I could start running deep and watch the clock to known when and how much I need to back off the depth to use up all my time. However I managed to step on several severe problems with it.

First that form can’t do alpha beta pruning at all, so I drop a lot of performance right there. After being annoyed at that for a minute or two, I dug in to update the min-max tree on the fly after each leaf is evaluated. That shouldn’t be to hard, each time I get a value check to see if it is less/grater-than its parent and if so update and repeat.

The better part of two days later I was frustrated as all get-up and then noticed that this doesn’t work (I told you it was a fundamentally broken algorithm) Cases like this provide a counterexample:

First the 10 goes in, and the left min node and the max node go to 10. Then the 5 goes in and the left min node goes to 5 but the max node stays at 10. Oops...

Anyway, I think by counting children and a bit of fancy footwork I can solve that problem, but the result of that is the alpha beta pruning is going to be really funky. I’ll have to play around how things get sorted and whatnot to see what works.

Right now I’ve got the leaf evaluation and mix-max push working correctly but things go wacky when a win or loss shows up above the leafs. Fun, fun, fun. What I really need is another set of eyes to go over my code. Unfortunately given that it’s homework...

Why is .NET built as GPLs?

The CLI (basically .NET) has shown that Microsoft has what it takes to integrate several different language so tightly that it just works. You could almost roll dice to pick your language for each function and never notice problems. Given that they can make inter opt that easy, why is Microsoft primarily building GPL's * on top of it? Why don't they leverage that interoperability and start building a pile of very small, very special purpose languages? These language could be tuned for very specific cases and, by avoiding corner-cases and compromises, could be made very clean. The theory would be that points in code that transition from one domain to another are good candidates for functions anyway.

I'm thinking of languages like:

A control structures language

This would provide all the ifs, foreachs, switchs and whatnot.

A math processing language

this would define precise math semantics and advanced math expressions

An systems-of-equations language

Think Maple or EES. This would provide no control structures, or define order of evaluation (not to be confused with order of operations) but would rather compute solutions for a system of equations (math for sure, maybe logical and bit-wise) given a number of inputs

An SQL like language

aside from small cases, why should LINQ even be part of C#?

Etc.

...

* Sorry there dosn't seem to be an http://en.wikipedia.org/wiki/General-purpose_programming_language right now, it redirect to the DSL page :b

Regarding the gunman (or maybe gun-boy) in Waiblingen, Germany:

Searching his bedroom, the police found violent computer games — in which, experts say, players digitally clothe and arm themselves for combat — plus brutal videos and play weapons that fire small yellow pellets, said Siegfried Mahler of the Stuttgart prosecutors' office.

Surce: International Herald Tribune (I found it first in the March 13, New York Times)

My question is: why are they so cagey about saying what they found? Sounds to me like they found the kid plays WoW (or something like it) and Air Soft. If that was the case, why don't they come out and just say so? The only reason I can think of is it wouldn't sound as dangerous.


I guess I should throw in a token "Don't blame the game" Reddit link (By the way, I'm not saying I lean either way on that one.)

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.

Happy Birthday to you know who you are.

:-)

My company is releasing some software I wrote

The release notice

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!

So I started a blog this afternoon...

I hope I can think of stuff to say...