Skip navigation

Following the 0.0.1 release of Freekick and an update to 0.0.2, I started noticing some problems in the implementation that showed a need for code refactoring. There were certain issues that implied I should find out about the internal workings of Haskell, as in, trying to figure out how the language and the implementation I use (Glasgow Haskell Compiler) works in general, especially with regards to threading, scheduling and performance.

The first issue I ran into was about my physics engine. I had defined a maximum velocity for my players of 8 m/s, but after some measurements I found out they were instead quite a bit slower. (A tip for the future: implement a debug panel for having such information when you need it. Measuring something like that shouldn’t be necessary.) This implies that the physics engine has serious flaws. I improved the engine slightly and it works slightly better now (but still not as well as it should), but the improvements lead not only to faster players, but also to strange twitching, a flicker-kind of effect on my SDL client.

To figure out what causes the flicker, I needed to check the code for networking. The way my networking code works at the moment is that the server (physics engine) only sends the positions of the players to the clients but no velocity or acceleration, and my SDL client doesn’t calculate the velocity of the player but only places the player where the server tells the client to. This is the simple method used in Quake that lead to problems back in 1996 when 56k baud modems were fast: with a lag of 200 milliseconds and occasional packet loss the client would spend most of the time not knowing where the moving objects (a.k.a. targets) were exactly located. The remedy that id came up with (a technique that was also used in Duke Nukem 3D) was brought to life in QuakeWorld, where the client would “assume” where the players would be located in based on their current/last known position and velocity. This made Quake playable (and a huge online success) even with slower connections (at the time I had a mere 14.4k modem). The technique is called client side prediction and there’s a small section written about it in Wikipedia.

Now, since I don’t expect a crowd of modem using people starting to play Freekick over the Internet, I didn’t implement client side prediction. Since I have the Freekick server and client running on the same computer lag shouldn’t be the cause for twitching anyways. But to make sure the client was receiving updates about the match state fast enough, I raised the server refresh rate, that is, the frequency with which the physics engine sends the match data to the client(s). The delay between refreshes was 40 milliseconds (using threadDelay), which should actually be enough, but I dropped it to 20 milliseconds for testing. Now, with the lightweight threads that Haskell offers (using forkIO) the refresh rate went up indeed, but the flicker stayed. I tried compiling with the “-threaded” parameter, which made the situation only worse, as the minimum thread delay time using “threadDelay” went up to 40 milliseconds on my computer. In the end I stayed with the lightweight threads, which doesn’t really affect my single core anyways, but this points out a problem when optimising the engine for multiple cores.

However, the problem persisted. Since my CPU was still nowhere near 100%, I figured the problem has something to do with how Haskell handles high precision timing. I’ve tried Frag (a 3D shooter written in Haskell) on my computer, and while I was overall impressed by the game, it was hard not to notice how Frag was twitching with regular intervals as well. As I don’t know if there exists a remedy for the problem, nor if the cause indeed is something Haskell specific or just some obscure bug in SDL or in my client, I wanted to go for a completely different approach.

That’s where C++ comes into play. I’ve actually had quite negative opinions about object oriented programming as well as C/C++ in the past, but on the other hand there are some rather impressive and useful libraries available where bindings to Haskell don’t exist and can only be implemented with a lot of work. The library that I thought of first was OGRE, the massively powerful 3D graphics library written in C++. There are actually a couple of articles about calling C++ functions from Haskell (see here and here), but binding a library like OGRE to Haskell using the described methods is not really something I’d like to spend my free time with.

I know that using OGRE for the client side would

a) make the client run faster and with no flicker, and

b) maybe even look a bit nicer

than the current client implementation using SDL, Haskell and 2D pixel-by-pixel drawing methods. The middle way would be to use the apparently very well written Haskell bindings to OpenGL, but I didn’t really enjoy OpenGL very much the last time I used it five years ago and after seeing OGRE in action and realising using OGRE is actually easier than using OpenGL I don’t really have the motivation. Of course, the biggest reason to use OpenGL would be that I could keep on writing the client in Haskell, but in the end it’s probably easier and more effective using C++ and OGRE.

That being decided, the next thing to do was to freshen up my C++ knowledge. I actually never had much of formal education to C++, instead I was using it much like “C with classes”. Even though that was the primary objective of C++ in the beginning, modern C++ is a completely different subject that I somehow had failed to miss until now. So I went and got me the book The C++ Programming Language by Bjarne Stroustrup and studied it through. I can imagine that a lot of people who have no or very little experience with C or object oriented programming find the book confusing, but for me as someone with good knowledge in C and some idea what C++ is about the book was perfect: it explained all the ways C++ can be used to make programming more efficient and less error prone.

I think it’s time for a small analysis about programming languages. After using C and assembly language I’ve gotten a pretty good picture about what the lower-level job of compilers is: shuffling around with the registers, allocating and keeping track of memory, testing for bits and so forth. Languages like C build on top of this, making the whole resource and control flow management easier to write and read.

On the other hand, Haskell approaches the problem from the other side. Haskell is designed from a mathematical point of view while trying to improve the efficiency of the programmer without clinging to the requirements and constraints of the machine, making Haskell code elegant and robust. To me, writing code in Haskell is almost like using a perfect programming language. Between C and Haskell, there’s C++. My impression about C++ was originally (unsurprisingly) that it is not far away from C, but after seeing how C++ improves on C and adds language features that allow the use of completely new programming paradigms (to C), C++ seems more and more Haskell-like to me.

With Haskell I learned to love the fundamental functional programming features that first seemed a little strange to me (like currying, higher order functions, lambdas etc.). I thought with C++ I’d be giving them away in exchange for pointer arithmetic, buffer overflows and unsafe typing, but fortunately I couldn’t have been more wrong. Nearly all of the C features that don’t seem to fit to modern software development are completely unnecessary in C++, and a lot of functional concepts and other features I’d miss from Haskell are brought in either as built-in C++ features (e.g. safer typing, better mutability control), the standard library (lists, currying, higher order functions) and Boost libraries (smart pointers for memory management, lambdas, serialization).

If you check out the Programming Language Shootout, you’ll see that C++ is (as expected) usually faster than Haskell (but the difference is not tremendous). As is also very well known, there exist about ten thousand times more libraries for C++ than for Haskell. In my opinion, those are pretty much all the aspects where C++ is “better” than Haskell. On the other hand, Haskell code is easier to reason about, significantly shorter and therefore easier to read (in my opinion, at the very least) and the concept of type classes is something C++ and the templates still have a lot to learn from, making generic programming far easier and simpler in Haskell than in C++. However, when writing a client for Freekick, performance as well as external libraries do play an important role in the end, and therefore I’ll go for C++. I’m glad I’ve seen Haskell as the finest example on how elegant code can be written, and I’m also glad it’s easy to use the same concepts in C++.

The next thing I’m going to do is read some more about object oriented design (I’ve got Design Patterns waiting for me) and then go and implement a simple Freekick client using OGRE. For that I need to reimplement the Freekick library in C++ as well, which is a nice exercise for OO design (you should plan to throw the first one away anyway, right?). Having the library in C++ would in theory also make it possible to rewrite the server part in C++, in which case I could use a top notch physics library like Bullet as well. But first we’ll see how the client turns out…

About these ads

17 Comments

  1. Any chance you’ll make your Haskell code available, so we can see what the issues were?

  2. Hi Don,

    I have a darcs repository for freekick available at http://code.haskell.org/freekick/

  3. The issue you are seeing reminds me of when I tried game programming with an old version of Java. The garbage collector for the particular version of Java I was using caused the game to “twitch” on occasion. The pauses corresponded to the garbage collection pass. As I recall this was a “stop the world” style garbage collector which, well, stopped all threads during the garbage collecting phase. The pass also took 10 through 15 milliseconds, which was definitely noticeable.

    I think GHC 6.8′s garbage collector has the same behavior while GHC 6.10′s garbage collector does not. [1] In addition, there are some runtime parameters you can pass that can be used to reduce the severity of the GC pauses. [2]

    Have you looked into the behavior of the garbage collector during these twitches?

    1. http://hackage.haskell.org/trac/ghc/wiki/Status/October08
    2. http://www.haskell.org/ghc/docs/latest/html/users_guide/runtime-control.html

  4. Thanks for posting the code. Did you try producing runtime profiles to get a sense of what your code was doing?

  5. If the OGRE and Bullet bindings were already done for you, do you still think you’d switch to C++?

  6. @Corey: thanks for the info, I’ll look into it. I hadn’t really thought it would be GC’s fault, and it does make sense at least with Frag, but with the SDL client the performance seems overall slow so I’m not so sure if it comes down to GC.

    @archhaskell: I haven’t done any profiling regarding CPU (I had to do some when chasing space leaks), because the CPU usage isn’t really that high and I thought profiling wouldn’t bring much. But you’re right, it could be helpful and point out if the code was doing something unexpected.

    @Jason: I can’t really say… But probably not, since having the library bindings in Haskell could save me quite a lot of work when compared to programming everything in C++. I can’t see how such object oriented libraries could be bound to or used in Haskell, though.

  7. @jason

    Profiling would state precisely what amount of time is spent on GC, and whether that’s actually the cause of any jitter/delay. You’d also get precise numbers on how fast/slow the SDL or OpenGL calls were, and if that was the cause. In short, a lot more data to work with, helping you make an informed choice.

    There’s a nice (imo) chapter on profiling in RHW,

    http://book.realworldhaskell.org/read/profiling-and-optimization.html

  8. i was taking a look at bullet just this weekend. if you have the inclination, nvidia’s visSim-4.0.6.0.7 may not be bad reference code. it’s a b* to get to compile on linux. in fact, i finally got it working — but then it just loaded up with like this red screen and four pictures in the four corners so i was like f* this. but it may not be so bad for reference if you go the c++ route.

    i am actually in the process of writing a graphics engine (i was like going to do it all software-based. like muli3d. and while muli3d did prove to be much more valuable as a learning tool than any of the opengl books i read before it. i’ve finally found that opengl is actually the way to go.) but yeah, i’m more interested in simple (antialiased, highly subpixelly accurate) UI stuff. i’ll post my code eventually once it’s in order. also, akeley’s lectures at stanford on opengl, just fyi, are THE BEST. after all, he did kind of author it.

    but anyway, just thought i’d chime in. that vissim code uses Lesson43 from nehe for rendering text — and i, after like a year’s worth of messing around (everything from rendering text in AGG and then mapping it to a texture, e.g., which doesn’t make a whole lot of sense), found myself using lesson43 as well. finally understanding antialiasing makes a huge difference. so anyway, it’s always nice to see other people with similar interests.

    i’ve also gotten into haskell somewhat recently as well. and i think based on some SPJ interview, i got clued into FRP and conal elliott and everyone else’s work on that. i mean from my perspective, that would be ideal. to have all aspects of ui related to signals, etc. and every programmer wants code concision because we all know the power of it…

    i would love to use opengl and haskell (i don’t know if you’ve seen the ‘beautiful code’ pdf, but yeah). the only thing is that opengl is so entirely sequential by nature, that having a functional programming toolbox buys you significantly less than other tasks. that’s just my overall feel though — i mean i’m still not done with this c++ engine, so what do i know. but i’ve felt that if haskell can compile into .o files — maybe it can be used sort of like plugins for the more analytical aspect of the engine. (e.g., the only somewhat serious haskell experience i’ve had so far is with a poker simulator — which was indeed much more fun and clear in haskell than c++.)

    but yeah, i think if you become an expert in haskell, you’d probably be ok either way. but if you think about it — where c++, imho, gets its power/performance is through its firm grounding in c. it adds metaprogramming and oo in very important ways (i am just not a fan of do-it-yourself virtual function tables in lieu of compiler-based oo like gtk or something; or macros where templates are more appropriate and compiler-checked). but haskell does the same thing (i.e., extend c). with type classes, some serious list/recursion syntax, and first-class functions (and in term, monads, functors, arrows, the like). it does it in a slightly different way (i.e., ghc uses the heap a lot, i would think). but it too is based on c. it’s like c++++++++++. or maybe (*new c)++. so my only point in this long post is that maybe they’re both kind of complimentary.

  9. re-reading this (sorry for the length), was thinking maybe c== might be more appropriate. i forgot that haskell lends so much being ‘pure’. i think spj was involved in something called c– or something? but the sequential (what i like to think of as a posteriori) aspect of the increment or decrement operator really has less to do with haskell (as it it exists currently, afaik). i suppose it depends on what one means by increment. or i suppose you could just call it haskell.

  10. Funny, I recently started some ‘work’ in c++ as well, after doing a few things in haskell (and years of perl and ruby), and I too found modern* c++ quite enjoyable. You do have to use it wisely; I see how it can get messy really fast, esp when used as ‘C with classes’, but that’s a feature of every powerful enough language (including perl and haskell).
    So maybe doing the client in c++ and the server in haskell does give you the best of both worlds, and at the very least working in those two very different languages will keep you sharp and critical.

    * modern c++: proper use of STL and Boost, ignoring the C legacy features as much as possible.

  11. C++ just seems like another one of those horrible gnarly type-unsafe languages that expose you to buffer overflows, stray pointer dereferences, bogus casts, etc. I’ve gotten interested in, oh my, Ada. It really seems to fix C’s problems from the other direction. I haven’t programmed anything in it yet but I’ve flipped through a textbook about it and am pretty eager to try using it on a real problem pretty soon (I use Python at my day job).

    http://adahome.com/Ammo/cpp2ada.html (an article introducing Ada to C++ programmers) looks pretty interesting.

  12. Haskell may be the most “theoretically correct” language around in terms of conciseness and the ability to reduce programmer error. But as is often the case with highly abstract languages, there is a performance cost involved. Ultimately it’s because there is a lossy correlation between the abstractions and their final representations in hardware.

    Real-time graphics is one of the few cases where the abstraction cost is too high: the user can *see* allocations and garbage collection happening before his eyes, in the form of the framerate stuttering and glitching.

    If C++ did not exist, it would have to be invented. It provides the optimal strategy for managing resource, called RAII (google it). When applied wholesale to a project, from top to bottom and right into all object aggregates, the result is a special kind of “correctness”.

    If Haskell is “correct” with abstractions, then C++ is “correct” with resources. Resource acquisition and release of a fully-RAII application looks like this: a1 * a2 * a3 * … * a3^-1 * a2^-1 * a1^-1, where the aN’s represent object constructors and their inverses represent the respective destructors. It is mathematical, and it is the correct way to manage resources. The consistent use of RAII in C++ *guarantees* this behavior.

    So C++ is, in this sense, complementary to Haskell — correctness from the flip side.

  13. > So I went and got me the book The C++ Programming Language by Bjarne Stroustrup and studied it through

    Out of curiosity, how closely did you ‘study it through’? Did you read the whole book? How long did it take you? Did you work through the exercises?

  14. I read most of the book. The most interesting parts for me were II and IV – abstraction mechanisms and design using C++. I already knew C and had used C++, so some chapters like parts of part I, basic facilities, were relatively uninteresting for me and I ended up skipping the things I was already familiar with.

    The exercises in the book are rated 1-5 based on the required effort. I did some of the exercises, but mostly the ones rated 1-3, so I didn’t spend much time with them. I think the exercises in the book are great in general, but some of them require quite a large amount of time – for example Ch12.11, “Design and implement a library for writing event-driven simulations”. I spent the time implementing my soccer game instead.

    I can’t really remember anymore how long it took for me to work through the book, but I think I was done in some weeks. Having spent time with STL and C++ before helped a lot of course, the book helped me most of all in understanding how to do object oriented design in an efficient manner. Of course, whenever I had a problem when designing a class hierarchy or such, I went back to the book for reference.

    But if you’re wondering how long it’ll take to learn C++ (or programming in general), check out http://norvig.com/21-days.html – “Teach Yourself Programming in Ten Years”, an insightful article on the topic by Peter Norvig.

  15. Dear All

    I recently tried, to interface Haskell with Irrlicht, a modern 3D engine, an experience report with example can be found here:

    http://www.althainz.de/haskell-irrlicht-interface.html

    For my perspective, as soon, as we get a complete C++ Haskell interface builder, like SWIG running, things would become much easier.

    • Dear All

      there is an update available, I followd on creating a more elaborate wrapper technology and bound Ogre to Haskell. This works fine and I will successively add other libs. Look at http://www.althainz.de/HGamer3D.html .

      It is actually still a pain, to wrap C++. I figured out, that a common denominator is C.

  16. It may take me a although to finish reading by means of all of your posts, but I can already tell that I truly like your writing style. I hope to hear far more from you!


One Trackback/Pingback

  1. By Top Posts « WordPress.com on 19 Oct 2008 at 12:12 am

    [...] On Haskell and C++ Following the 0.0.1 release of Freekick and an update to 0.0.2, I started noticing some problems in the implementation [...] [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: