Showing posts with label programming. Show all posts
Showing posts with label programming. Show all posts

Wednesday, 27 April 2011

Templates, inheritance and nested classes

I've recently had a world of fun and confusion with a strange combination of templating, inheritance and nested class in c++. The error messages along the way were rather weird, so in a bid to save time in future, here's the story:

Let's begin with a pretty standard templated class. It does useful things to some data which it keeps a hold of during its lifetime.
template <class T> class Foo
{
  public:
    Foo()  { /*...*/ }
    ~Foo() { /*...*/ }
    void SetStuff(T *data) { /*...*/ }
    void DoStuff(T *data) { /*...*/ }
    T *ViewStuff() { /*...*/ }
  private: 
    T *data;
}
OK, now let's assume that we have a set of helper functions that are only useful with the data in Foo while it's in Foo, and which should never be used externally but are always used whenever Foo wants to do stuff with the data. So we'll define a little nested helper class and squirrel the data away in it:
template <class T> class Foo
{
  public:
    Foo()  { /*...*/ }
    ~Foo() { /*...*/ }
    void SetStuff(T *data) { /*...*/ }
    void DoStuff(T *data)  { /*...*/ }
    T *ViewStuff() { /*...*/ }
  private:
    class DataWrapper
    {
      public:
        DataWrapper(T *data) { /*...*/ }
        ~DataWrapper() { /*...*/ }
        void HelperFunction() { /*...*/ }
        T *GetData() { /*...*/ }
      private:
        T *data;
    }
    DataWrapper *data;
}
Note that DataWrapper doesn't need to be templated; that's taken care of because it's already nested inside a templated class. Now let's imagine that SetStuff and DoStuff aren't safe methods to call all the time, and that sometimes you need to make sure that you can only use the safe methods, like viewing stuff. We just need a FooView. Fine, let's make a base class of Foo that has a copy constructor and only provides the safe methods. Then we can just take a FooView copy of Foo which we know is safe to hand over for use elsewhere. We want FooView to be the base of Foo, which is possibly slightly counterintuitive, because Foo does everything that FooView does and more besides.

template <class T> class FooView
{
  public:
    //Copy constructor to allow us to create views of a Foo
    FooView(FooView & source) { /*...*/ }
    ~FooView() { /*...*/ }
    T *ViewStuff() { /*...*/ }
  protected:
    //It doesn't make sense to create a FooView unless we give it something to 
    //copy. The descended Foo class will need a default constructor, though.
    FooView() { /*...*/ }
    class DataWrapper
    {
      public:
        DataWrapper(T *data) { /*...*/ }
        ~DataWrapper() { /*...*/ }
        void HelperFunction() { /*...*/ }
        T *GetData() { /*...*/ }
      private:
        T *data;
    }
    DataWrapper *data;

}
template <class T> class Foo : public FooView <T>
{
  public:
    Foo() { /*...*/ }
    ~Foo() { /*...*/ }
    void SetStuff(T *data) { /*...*/ }
    void DoStuff(T *data) { /*...*/ }
}

DataWrapper needs to be in the FooView class since both Foo and FooView need to understand it, but nothing else should (perhaps it's code that would be unsafe if used outside a FooView object). So far, so simple. But as soon as we try to implement anything in Foo that uses a DataWrapper, we end up in a world of pain.

Our first problem is that inside Foo, the compiler doesn't understand what a DataWrapper is. Let's add an implementation to SetStuff:
template <class T> class Foo : public FooView <T>
{
  public:
    Foo() { /*...*/ }
    ~Foo() { /*...*/ }
    void SetStuff(T * data)
    {
      DataWrapper *wrapper;
      wrapper = new DataWrapper(data);
      this->data = wrapper;
    }
    void DoStuff(T *data) { /*...*/ }
}

...which will result in the compiler error "DataWrapper was not declared in this scope". The issue is that we're in a templated class and the compiler doesn't know where to look for the definition of DataWrapper (which is also in a templated class). So let's give it a hint:

template <class T> class Foo : public FooView <T>
{
  public:
    Foo() { /*...*/ }
    ~Foo() { /*...*/ }
    void SetStuff(T *data)
    {
      FooView<T>::DataWrapper *wrapper;
      wrapper = new FooView<T>::DataWrapper(data);
      this->data = wrapper;
    }
    void DoStuff(T *data) { /*...*/ }
}

Which is pretty ugly. And leads to the baffling error "wrapper was not declared in this scope".

Huh?

But... but... that IS the declaration of wrapper!

Somehow the compiler has become so confused by the templating and whatnot that it's totally failed to parse
FooView<T>::DataWrapper *wrapper;
as a declaration. It's trying to perform some operation on wrapper as if it were already declared. I've no idea what. If you switch T for a type, the problem goes away -
FooView<double>::DataWrapper *wrapper;
works fine, apart from being a bit totally useless. So it seems that the compiler has missed the fact that
FooView<T>::DataWrapper
is a type name. Fortunately there's a keyword available to convince the compiler that no, honestly, it is a type name:

template <class T> class Foo : public FooView <T>
{
  public:
    Foo() { /*...*/ }
    ~Foo() { /*...*/ }
    void SetStuff(T *data)
    {
      typename FooView<T>::DataWrapper *wrapper;
      wrapper = new typename FooView<T>::DataWrapper(data);
      this->data = wrapper;
    }
    void DoStuff(T *data) { /*...*/ }
}

This is clearly absurd. If you're using DataWrappers in many places, your code is going to end up looking like it's been beaten to death with an ugly stick. Fortunately we can avoid all that nonsense by using a private typedef inside Foo:

template <class T> class Foo : public FooView <T>
{
  private:
    typedef typename FooView<T>::DataWrapper DataWrapper
  public:
    Foo() { /*...*/ }
    ~Foo() { /*...*/ }
    void SetStuff(T *data)
    {
      DataWrapper *wrapper;
      wrapper = new DataWrapper(data);
      this->data = wrapper;
    }
    void DoStuff(T *data) { /*...*/ }
}

And now you can just use DataWrapper inside Foo the same way as you would inside FooView - and as you probably expected to be able to use it in the first place. Obvious, eh?

EDIT - The typename keyword exists specifically to address this sort of situation, according to the description here. I guess it's one of those things that you either know (and hence will understand why you get an error about an undeclared variable from a line which you think is a declaration) or you don't and will be totally baffled by. It's not an error message that helps you towards an understanding of the source of the problem, that's for sure!

Monday, 28 February 2011

Mootools and the Closure compiler

I (and Dan over at teadriven) have been battling with the Google Closure Compiler for a few days now. I say "we". As the more javascript literate Dan has been doing the vast majority of the work while I poke things with sticks and apply googlefu to trying to find solutions to problems.

The first interesting thing is that, if you search for information about how mootools works with the closure compiler, you'll find next to nothing. There's a very brief post from 2009 claiming that mootools + closure compiler "behaves quite nicely", and a couple of posts stating that you can only use advanced optimisations on closure if you've designed your code for it, and you know what you're doing. Setting the "you need to know what you're doing" part of it aside for a moment the implication is that mootools and closure don't behave quite nicely together at all. This tallies with what we've seen. Initially we were thinking we just needed to provide an externs file for Mootools and we were a little surprised that one didn't exist in the closure contribs. Then Dan started trying to make one while I blithely disappeared to try to fix my bike, which is a whole different story. A story punctuated with increasingly irate/despairing IMs popping up on my phone as the fundamental differences of opinion between Closure and Mootools started to become apparent.

We're nearly at a point where our js has been hacked to work, but it's not a case of having made Mootools and Closure work well together. And here's some of the reasons why:

  1. Javascript sucks at object orientation. Why is that a problem? Because there's no standard way to do object orientation in javascript. Mootools and Closure approach the problem differently. Closure requires javadoc tags to help it to parse the javascript correctly, and there's currently no tag that allows you to describe a mootools-style object definition. Therefore Closure doesn't like Mootools.
  2. Closure doesn't like you messing with Element. More accurately, it doesn't like you overloading the w3c Element. Mootools does overload Element (I know, technically it doesn't, it redefines it). Therefore, Closure doesn't like Mootools.
  3. There is no externs file for Mootools. If you want to use Mootools without compiling it in to your code, you need an externs file. Currently, none exist. Therefore, Closure doesn't like Mootools. Until the other problems are solved, there's no point making one which I suppose explains this.
The last problem is relatively trivial but the first two are real issues. For the first, the best way I can see around it is for the Closure compiler code to make explicit provision for the Mootools way of doing things, probably through a specific javadoc tag. I'm sure this isn't high up the priority list for The Google. We've pulled the source, though, so there's at least the chance we'll find the time to attempt to hack such a thing in. You can sort of hack your javascript into line, though.

To create a class in Mootools, you pass in an object of properties and functions to the Class function, which then spits out a new one of the things defined by the object you passed in. There's nothing there that's inherently wrong from Closures point of view, except you need to somehow tell Closure that this is a class instantiation based upon the object you pass in (it is expecting you to be a little more traditional and create a class with a constructor function which you tag with a @constructor javadoc). Closure is, therefore, confused by what "this" you're referring to inside the class. This can hackily be resolved on a case-by-case basis by liberal use of the @this javadoc tag, which is messy. It'd be much nicer to be able to tag something as a mootools-style constructor in Closure, and that would also allow Closure to understand the object inheritance tree (which is sort of broken with this hack).

As for problem two - again, I can't really find anything on the web that talks about this. I suppose nothing else (other than mootools) really tries to overload Element, so no one else has this issue. Not entirely sure why Closure protests, or how one is supposed to tell it that you're overloading/redefining Element and no, really, that's fine. I suppose going through Mootools and renaming Element as "Mooliment" or something could, potentially, be a workaround.

Slightly frustrating to have no definitive resolution to tail this post, but there's so little information out there about this problem at time of writing that even a "mootools and closure don't work well together" post seemed like a useful contribution of sorts.

Monday, 11 October 2010

Browser game development.

For the past....oooh, three quarters of a year? I and a couple of friends have been working on a little project in our spare time. I've played a few browser based MMPORPG in the past, and I've often criticised them. In some cases - such as the now-defunct Nexus War - because I've just enjoyed the game so much that the bits that I'd do differently become huge in my mind. In others, like Shintolin it's more that I'm frustrated that the developer seems to have lost interest before an interesting concept has really reached fruition. There's also an element of arrogance, I suspect, in that I know best and all these people are doing it wrong (that's almost - but not quite - entirely a joke). Of course, it's easy to be a backseat coder so earlier this year I, with a couple of like-minded, foolhardy friends, decided to put my build chain where my mouth is and write a browser game. I liked the idea of a stone-age sandbox-y game so, with apologies to Shintolin, began work on a project currently bearing the working title "Henge".

There're quite a few things that I've learned along the way - work on the game has seen my try out (and hate) Seam, has seen me tinker with and discard Eclipse, Netbeans and ultimately Java itself. Which is noteworthy mainly because part of the motivation behind this project was to learn Java. Ho hum. On the other hand, my game has definitely been raised in the C# stakes - I've moved from rather disliking the language to an appreciation that it is, in fact, fricking cool. I've learned a lot about NHibernate, which was really handy for work. Sadly, despite it proving extremely useful for non-Henge purposes it became apparent (at least to two thirds of the team) that even with NHibernate, a SQL database was forcing too many compromises on us, so we ditched it almost entirely in favour of db4o. My word, there was a decision that led to a ludicrous amount of work. On top of that, Henge has allowed me to get to know and to love git. I've moved from cvs to subversion to git over the years and each step has been a massive leap forward. As much as I've championed subversion in the past I have to say - these days, if you're not using git you're almost certainly doing versioning wrong.

And after all that - and a lot more - we still don't have a playable game. As it stands at the moment, you can create a character, walk around a map, starve to death and drown. But it's getting there. There's an awful lot of architecture in place now. Hopefully one day you'll be able to play it and see what all this effort has been for. But one of the big things this has shown me? All those one-man bands who managed to design and build their own browser game, from the sophistication of Nexus War to the simplicity of Urban Dead and even the semi-complete mess (sorry, really I am, but look at the code. It needs a rewrite!) of Shintolin... they all all managed to do an amazing thing. Getting one of these things up and running is bloody hard work. Or, at least, that has been my experience of it so far.

Hopefully I'll find the time and motivation to write a little more about the design of henge before I forget too much about it; it's already started to happen - there are things that I've had to spend a long time figuring out twice because I forgot why we did them the way we did them in the first place. If not, I hope at least to get enough working to let some people poke it with sticks until it falls over.

Thursday, 16 July 2009

The Amazing Windows Specific Bug

I've just spent a week and a bit tracking down possibly the weirdest, most pernicious bug I've seen all year. It was obviously going to be a doozy - the application crashed only when the system had multiple cores, only when the input images were all of different sizes, and the crashes were both intermittent and unpredictable. Oh, and in the middle of code that had been seriously hammered in the past, and in the wild, and shown no signs of falling over.

Where to start?

Well, first of all, that intermittent crashing? That looks like a threading issue. It could just be memory corruption, but running on the exact same input data in the exact same order gave significantly different times to failure each run. It just feels like a threading issue. That plus it's only apparent on multi-core machines. A check of the code reveals some worker threads that are spawned in the midst of some number crunching to make use of all the available cores - so if there's only one core, there're no more threads. Aha, this looks likely. Right, so, if there's a weird issue going on here, we might be able to track it down using Valgrind, right? right?

Wrong. Because on Linux... there is no issue. Exact same source code. No crashing.

Here's a pseudocode version of the section of code in question:

In the main thread, for each image processed:
//Initialise the shared job queue (that all threads will pull jobs from)
this->jobQueue.Initialise(jobData);
//Initialise and resume the worker threads
for (i=0; i<threadCount; i++)
{
this->threads[i]->Initialise(data);
this->threads[i]->Resume();
}
while (true)
{
//Keep pulling jobs off of the shared job queue until there's no more work to do
job = this->jobQueue.GetJob();
if (job)
{
this->DoProcessing(job)
}
else break;
}

do
{
//Wait for the worker threads to finish
for (i=0; i<threadCount; i++)
{
busy = this->threads[i]->CheckBusy();
if (busy) break;
}
}
while (busy);
//Pause all the workers until we need them again
for (i=0; i<threadCount; i++) this->threads[i]->Pause();

And in each worker thread :
Thread::Initialise(data)
{
HandleData(data);
//Signal that the thread is now working
this->busy = true;
}


Thread::Entry()
{
while (!this->TestDestroy())
{
job = this->jobQueue->GetJob();
if (job)
{
this->CrunchNumbers();
}
else
{
//Signal that the thread is no longer busy
this->busy = false;
}
}
}

So, to explain a little, what we have here is a pool of threads that are created at one time and then re-used through the lifetime of the application. Whenever we get into the number crunching code, the threads have their operating data passed in and they're resumed. As soon as all the jobs are processed, the threads signal that they're finished. Once all the threads are done, the main thread pauses them all and the program goes on its merry way.

Anyone figured it out yet?

There's one last piece of interesting information, to do with the way that threads are paused on the two different platforms. On Linux, the thread won't honour the Pause() call immediately, but will pause the next time it gets to TestDestroy() (for those wanting to replicate this, I'm using wxThread though this behaviour is a result of the underlying threading of the target OS). On Windows, the thread is paused immediately.

The upshot of this is that you can't guarantee, when you resume a thread in Windows, where it's going to start execution from. Now, with this last piece of information, it should all fall into place. See where the thread sets its busy flag to false? Right, in your head pause the thread there. Now, next iteration the thread will be set up properly by the initialise call, which raises the busy flag... only for it to instantly lower the flag when the thread resumes. So now the thread is merrily doing its processing, but it's signalling that it isn't, and is ready to be paused.

That in itself, while worrying, isn't so bad. What can happen next is. The Pause() can now happen anywhere in the worker threads loop. So if the thread happens to still be working when the main thread starts checking the workers to see if they're ready to be paused, it's more than likely going to be paused in the middle of doing number crunching on the input data.

And then, next iteration, you change all the input parameters and resume the thread mid-calculation with totally different data. If you're lucky, that means you get garbage out for this one iteration. If you're not, and your worker is mucking around with variable length data, you just wandered off your allocated heap and into the wild unknowns of Segfault City.

There's an easy fix, of course. The issue only arises because when the thread is in a state that it flags as "pausable", it's still performing write operations on itself (constantly re-clearing the busy flag). If we consider that the pause, and any re-initialisation of the thread data, is asynchronous to the thread entry (which it is) then it's obvious this is going to cause trouble. Instead, we can make sure that once the thread has signalled it's ready to be paused it no longer performs any writes. Since it's not going to be writing, it's now safe to pause it, do some asynchronous writes, and then set it going again. (note: I say "safe". It's safe in this context. You could still really confuse the thread if it's checking badly-considered conditionals that you just monkeyed with the control parameters of, but let's take that as read).
Thread::Entry()
{
while (!this->TestDestroy())
{
//Make sure we don't keep setting the busy flag to false over and over
if (this->busy)
{
job = this->jobQueue->GetJob();
if (job)
{
this->CrunchNumbers();
}
else
{
this->busy = false;
}
}
else Sleep(1); //Oh, and may as well consume fewer resources while we're at it
}
}

Wednesday, 6 May 2009

Look at the state of your code

Recently I've been working to re-implement an application from scratch. Not normally a sensible thing to do, but the codebase of the original was so far from being maintainable that you couldn't see maintainable from the highest point of the code on a clear day. With a telescope. Ostensibly the main reason it was such a mess is that as the application rolled out, there were an ever-increasing number of tweaks, special cases and optional extras which needed bolting into it. After a bit of thought, though, it seems to me that this is almost entirely not the case.

The root of the problem is that the code was never really designed before it was written. There were no pen-and-paper diagrams, whiteboard sketches or rough attempts at figuring out a structure prior to getting "stuck in" and hacking out code. It's a common mistake, it seems, that writing code is the important, difficult bit. It's really, really not. Figuring out how the code should hang together, that's the important bit. And as part of that figuring out both what the job you need it to do is, and what it might need to do in the future is. Now, obviously, you could take that too far - abstract enough and you just specify a thing that does something. Can't really design that, right? Well... sort of. But you know the special case of what it needs to do right now. Abstract all those things: If you need to be able to accept an input from an edit box before you fire the McGuffin that does your big cool number crunching task, then isn't it a good idea to make sure that you don't care where you get your data from? Yes, in this case it's an edit box, but why make life difficult for yourself in the future? You're going to get your data from something and in your first cut, that something will be an instance of an edit box. Next week it might be a piece of custom hardware. Design the way everything hangs together right, though, and aside from writing the code that details internally how you get data from the hardware, none of the rest of your code changes.

So far, so obvious. I'd hazard that no one really disagrees with that approach. But what really struck me with this project is how cool state machines are, for doing the above but with your business logic program flow. What you see in a lot of projects is a section of code that tells your system to do stuff - either the main loop, or the equivalent for the subsystem that you're looking at. Within it you'll often find a collection of conditional or a case statement. With the project we started with here, that had... I hesitate to say "grown"... mutated into a gigantic cascade of conditionals. Following what the hell was going was difficult, because there was no easy to reference concept of what the system thought it should be doing at any given point. It becomes difficult to add functionality, because checking what conditional statements are going to be executed is far from trivial. And on top of that, where do you sensibly add your code? Most likely as another conditional in the big list - making it even harder to get the next revision in. And because you've had to mess with the internal flow of the entire system, you've potentially destabilised what you had to begin with - even sections of the code you didn't think you changed.

So, here's an alternative approach: Let's abstract our central functional loop. It's going to take some data into it, sit there performing some function until it's done, return some data which determines what needs to be done next then pass whatever data it thinks might be useful out to the next iteration which will do the same thing. So what do we need to do this? Let's define a generic state object which will take care of Doing Stuff. We don't care what it does. We can give it access to a message queue so it can throw data out to non-state based components of the system (such as a GUI or some hardware), so there's no worries about it needing to have access to data that the central class shouldn't really relinquish - we can just pipe data out through the central controller class. Equally, we can pipe data in through the main controller loop. As much data as we like, and of any type. The state object can decide what to do with it, or junk it if it decides it's irrelevant. All we really need to define for the generic state is a HandleData() a Run() and a member variable to tell us when it's finished, and ready to move on to the next state - and, ideally, give us an idea of how this state finished. A binary works well here (success/fail), but you could use anything I guess, provided you can keep track of your state progressions. Now, we can define our states totally independently. Chaining them together into an application is just a case of defining a flow tree for the controller which tells it what state comes next for a given exit condition on the current state. You can define that in XML or whatever and parse it at runtime - no coding involved. The main control class becomes trivially simple - it just sits in a loop piping data into and out of the current state until it's told that the state is finished, then looks up the next state from the flow table and makes it current.

The neat thing about all this is that you inherently know what the system is doing all the time - it's just a state machine. You want to know what code is running when it's in a given state? The code in that state object. You don't have to figure out what conditionals are valid right now - just look at what that state does. You need to add functionality? Either change how the relevant state works if it's a simple change, or add a new state if you want the system to do something new. Then just update your flow table. Need to take something out? Just edit the flow table. You maintain tight encapsulation of your business logic the whole time, but at the same time get a very extensible framework. And because you're not modifying the existing code at all, you've drastically limited your ability to kark something up by mistake - you've got to either mess up your state flow table, or pass garbage into a state while at the same time managing to convince it that the garbage isn't garbage. A well-designed state object should be pretty resillient to this, and a well designed controller should do at least some amount of sanity checking of the state flows it loads to give you confidence that you are trying to run a system that has a chance of being stable.

Now, there's a downside to this: you pretty much have to stop and figure out what you're trying to do as a state machine, rather than hacking in some conditionals. Well, I say downside. Figuring out an actual state machine is probably a good idea in many cases - you've had to formalise what you want to do before you go ahead and try to do it.

Obviously, you don't always want to take this approach - if you're writing heavily optimised, time critical code then you maybe have other considerations to worry about. And no pattern is going to be right all the time, but I would hazard that unless you've got a good reason not to design your code using state machine architecture then it's probably a good idea to at least consider taking this approach. Especially if you know that you're going to need to add or modify functionality in the future - it really does make modification amusingly easy.