I have had a Kindle Fire now for a few days. I am an Apple guy and an iPad owner but that doesn’t stop me from liking this little device. Lets first start of with some of the things I like about it.

• Size. It is so easy to hold in the hand and carry around. Typing on it is in many ways easier than iPad if you don’t have it on your lap. You can type with two thumbs which isn’t possible with iPad.
• Integration with Amazon. Lets face it, while iBooks has a great interface, it simply does not have the same selection as Amazon and you can’t read the books on as many devices. I can read my kindle books on iPad, Kindle, iPhone, my Mac etc. On the Kindle Fire I can buy books conveniently through a special application. No need to browse the Amazon web interface like on iPad.
• The Android back button. I love this concept. On iOS you can only browse back and forth within an app. On Android back means back to whatever was you previous screen, even if that was another application. A nice use for this is when you click links to web pages in your email application. You look at the linked web page but then you want to go back to the email and click another link. Easy, just click the back button. On iPad this would require either double click home and select email application among running apps or single click home and select email among all the apps.
• Price. It is a really good price for what you get and this makes tablets accessible to a lot of other people.

Now for the things I didn’t like so much. The carousel thing was mainly annoying. I found it quite messy to have applications, books, movies and everything all in one. It is also about as useless as the Windows 7 exposé copy. It doesn’t give any quick overview over what you have. There was no obvious way to see what applications were running and quitting them. There was a sort of process manager but that was not very accessible and felt more like a geek tool.

But the most annoying thing was probably that there was no physical buttons for frequent operations like going to the home screen or going back. I found it really awkward and slow to have to tap my screen once to get the toolbar at the bottom with the home button each time I wanted to click the home button. A button used that often should be super quick and easy to click.

Apart from that as a user of Apple products I am used to a lot of polish on the products. These are things which are hard to explain but comes down to getting very minute details right. On Kindle I feel there are a lot of these small details which are not done properly as on an iPad. When you move an icon on the home screen of iOS you see the other icons move to the side. On Kindle Fire moving icons on the favorites shelf looks more like they get teleported from one place to the other. This is confusing because you don’t get the same feedback and feel for where things are moving from and too. If you scroll to far in a list there is just some sort of flash to indicate that you went to far. In iOS you actually continue to move past the list but the list snaps back as soon as you let go. I think it is a much clearer feedback. This is common issue I have with Android. You just don’t get the same quality feedback on everything you do. I often click, scroll etc and don’t know if the system registered my action or not.

There is also a lot of indirect manipulation instead of direct manipulation. E.g. I expected to be able to move an item from the carousel down into the favorites. You can’t. Instead you have to press and hold. This will get you a menu where you can chose to add to favorites, which exists visually right below you. This feels unnatural. A lot of things are like that on the Kindle Fire.

It is all these little details which add up to create the smooth experience on iOS, but which makes Android not feel quite right. But more importantly I prefer iPad overall because it is much more versatile. The bigger screen opens up the possibilities for more kinds of applications. While I loved the back button and think iOS should steal that idea there are simply too many other areas where iOS interaction works better. Application switching, management and organization is done more elegant IMHO.

Details like physical placement of buttons is done much better.  E.g there are no volume control buttons on it. Volume is something you usually have to change very quickly. So it should be very quick to access. It is infuriating using e.g. phones where you suddenly realize you got too low volume while speaking to someone and you have to put them on hold while you try to navigate the system settings to find volume control.

This ought to be simple right? 

My very first thought is that we are potentially looking at every string to find the right one. So it is O(N). But wait. For each string we loop through each character of that string. We got two loops. So maybe it is O(N^2) ?

But lets think about this more carefully. Each loop is looping over different kinds of data. The outer loop are strings while the inner loop are characters. So why no use the same units everywhere? Meaning let’s look only at the characters. How many character comparisons do we have to do?

Say the string list contains a total of N characters. The string we are searching for is made up of M characters.
Consider a worst case. Every string in list are the same as the search string except the last character. The string list then contains N/M strings. That is, each string is M characters long. How many comparisons do we do? For each of the N/M strings we do M comparisons. That totals (N/M)*M = N comparisons.  So it is linear. Really? How can that be, we have to go trough every character in the search word multiple times. We got two loops. How can it not be O(N^2)?

The key observation is that in the string list we are never looking at a character twice. If we only look at the number of comparisons we do in total. We don’t do more than N comparisons between a character in the string list and a character in the search string.

Consider some of the other extremities. N = M, that is the search string contains as many characters as there are characters in the string list in total. And say the string list only contains one string. Obviously its is O(N) comparisons. At the opposite extremety each string in the string list is only 1 character. We compare with N strings, but for each of these comparisons M - 1 characters in the search string will never be visited. 

This example illustrates that when considering big O it is not enough to merely look at the number of loops nested inside each other. One has to think about what are exactly the elements which are being processed. 

Today there is a lot of talk about iPhone and Android apps. They were not supposed to have happened because the future belonged to the web. It happened anyway.

At a Java conference today I talked to some software managers at different consulting companies. They all seemed convinced that the app was a fad and HTML5 would take over. I think they are going to be wrong again. It is understandable why they think so, because the web is really ITs wet dream:

• You can do all updates, configuration and maintenance in one place
• Just one platform to support
• Develop once and run everywhere
• Easy deployment. All you the clients need is a web browser.

But wanting something doesn’t make it so. Consumers have shown that they don’t care about how great web apps are for IT people. Consumers want slick, smooth and rich applications. And unfortunately the people in the IT departments has no idea of what this really is.

Fundamentally this isn’t really about the web at all. Instead it is the age old struggle between native applications and cross platform applications. Naturally IT likes cross platform. It has always been like this and they are always going to want it that way. They want to write their stuff once and use it everywhere.

But this is not what the consumer wants. The consumer choose a platform because they think that platform is better. This goes for personal computers, phones and game consoles. Each platform will have unique strengths and abilities to make themselves attractive to the consumer. The consoles want to offer unique interactions that the other platform can’t afford or be able to produce richer graphics than the other platform. Phones want to be easier to use, offer a unique eco system, have unique ways for interaction and so on.

It is never going to be a game purely about the amount of memory, speed of microprocessor and number of extension ports.

Cross platform toolkits like Swing, Qt and HTML5 will always have to play catchup to the native toolkits. In the software managers dream HTML5 is just about to catch up with the native kits. Just you wait. In short time all she need HTML5 to present users with the same experience as the native kids. Of course this is all wishful thinking. They assume a static world were each platform stays still why cross platform tools rapidly advance. This is not the case. Neither Qt nor Swing can provide all the bells and whistles of the native toolkits. They never have. Each time they caught up new native functionality was added.

Just as it has for decades cross platform and native apps will continue to exist side by side. One side is not going to kill off the other. It is simple really. We live in a market economy. As soon as someone makes some great application in a cross platform toolkit be it Qt or HTML5, there are going to be someone who makes the same app in Cocoa, win32 or whatever. That app will run faster, have tighter integration with the host OS, offer nice UI elements that don’t exist in the cross platform toolkits. Users are going to buy this app because to them it is better they don’t care that it is not how IT wants it to be.

You might ask what more can native kits offer? Computers are already fast enough to run anything you want to run through HTML5. Before the iPhone came out they probably said the same thing. But suddenly your UIs had to be fluid, animated and highly interactive. By the time phones are fast enough and HTML has gotten enough features to do what the first iPhone did, there will be something new. And then it is the catchup game all over again.

When your code is tightly coupled it is hard to change one part of the code without affecting other parts. When your modules are loosely coupled they can be modified or removed independently with ease. 

I just came across a blog run by the guys behind BitSquid, a new high end game engine. They have some great entries about numerous things related to game development. But today I thought I’d highlight the tree blog entries by Niklas about managing coupling: 

• Intro and using IDs to reduce coupling
• Polling callbacks and events
• Duck typing in C++

This is not your regular advice on how to manage coupling in an OOP setting, where you would talk about usage of abstract interfaces, composition, which classes should know about each other etc.  The kind of stuff Java developers would be used to. Rather this is a data oriented design, which is very C-style and low level.

Using IDs to reduce coupling

Niklas details why you should refer to objects most of the time using IDs rather than pointers. An ID is typically just a 32 bit integer. Unlike pointers IDs can be moved to different CPUs or cores using different address space, serialized to disk etc. The naive approach would be to create a hash table or STL map to lookup pointers based on integer ID. But the blog entry shows how we can do very quick lookup by storing offsets inside the ID. Noel at Games from Within also talks about using IDs instead of pointers in Managing Data Relationships. I think you should read these before starting to use GUIDs e.g.

Event management

In the second blog post Niklas has the novel idea that instead of you pushing events to an event handling system where stuff happens, each subsystem just stores events as they happen and the higher level system then polls the lower level system for events. This way you don’t couple any low level system to a specific events notification system.

I have worked with these kind of problems before. You might have global loggers or message objects, so that in your algorithms you might write something like:

  if (wrong)
    Msg::Error("Something wrong happened!")


Or you might have some logger object or singleton class:

  if (wrong)
    Logger::GetLogger("error")->Log("Something wrong happened");

The problem with this approach is that your algorithms gets strongly coupled to your framework or particular way of sending messages. You also lose control over how and when to display messages. Niklas doesn’t go into details but one way I have found useful is to pass a message handling object to functions or objects and have them fill this message handling object with messages or events:

  void process(MsgObj *msg) {  
    if (wrong) 
      msg->addError("Something wrong happened!");

Apple’s Cocoa API often uses a similar approach for dealing with errors. In the Visualization Toolkit, VTK, they extensively use an observer pattern. A lot of software has classes that represents algorithms. When the algorithms want to report on progress to the main UI or report errors they would typically use a central message object. Often using a global function or singleton. In VTK they make algorithm objects observable. That way progress and errors are reported by sending messages to observers rather than to a centralized object. These approaches should not be confused with what Niklas talks about because these are OO solutions to similar problems that he outlines. 

Duck Typing in C++

In the duck typing in C++ blogpost Niklas talk about stuff that might seem a bit similar to QVariant class found in the Qt application and UI framework. With QVariant you can also create arbitrary data structures by combining simple QVariant types with QVariantMap and QVariantList. But Niklas show an interesting twist in how you can in a way define something that can best be described to a Qt developer as a QVariantMap template for QVariantMap objects with fixed number of members. This allows very efficient storage of each variant map. Niklas doesn’t talk about Qt at all, but that is a way you might think about it. You have similar mechanism in Clojure and other LISPs and Scheme versions.

Hey I was looking at your wrapping c++ classes in lua article, I must say its been the biggest help in understanding some of the details to me.

The first part I got working no problem, the second part gets me a little stuck. Basically the extra argument isn’t getting passed (I think) Calling Sprite.new(..) only seems to pass the 4 arguments and not the table, what have I missed.

Thanks,

Phil.

That is easy, you have simply used “.” instead of “:”. 

    Sprite:new(...)

is syntatic sugar in lua for

    Sprite.new(Sprite, ...)

That is how you get the table in as first argument.

Neither Go nor Clojure are object oriented in the sense that they provide implementation inheritance. With Go you can create what it essentially classes without inheritance. Created with keyword “struct” in Go. These “classes” can used wherever an interface is required if a subset of the classes methods match all the methods defined in the interface.

In similar fashion Clojure has what is called a data type created with keyword “defrecord”, which is similar to a Go “class” in that it does not support inheritance. But while a Go “class” automatically implement any interface  which is a subset of its methods, in Clojure you have to specifically list which interfaces a Clojure “class” implements:

(defprotocol Payroll
  (paycheck [emp hrs]))

(defrecord HourlyEmployee [name rate]
  Payroll
  (paycheck [emp hrs] (* rate hrs)))

(defrecord SalariedEmployee [name salary]
  Payroll
  (paycheck [emp hrs] (/ salary 12.0)))

In Go listing implemented interfaces is neither possible nor needed:

type Payroll interface {
  paycheck(hrs int)
}

type HourlyEmployee struct {
  name string
  rate float
}

func (emp HourlyEmployee) paycheck(hrs int) float {
  return emp.rate * hrs
}

type SalariedEmployee struct {
  name string
  salary float
}

func (emp SalariedEmployee) paycheck(hrs int) float {
  return emp.salary / 12.0
}

Since Clojure doesn’t really have methods per say, you can’t define other protocols with the same function names. That would just override the meaning of that function. This should not necessarily be interpreted as Clojure being less flexible then Go here. Clojure has a number of different ways to dispatch a function call based on the type or value of the arguments.

(defmulti paycheck :type)
(defmethod paycheck ::hourly-employee [emp]
  (paycheck [emp hrs] (* rate hrs)))

(defmethod paycheck ::salaried-employee [emp]
  (paycheck [emp hrs] (/ salary 12.0)))

I am not going into the details but we assume here that emp is hash table with a :type key. Multimethods allow dispatch on multiple arguments. However given two existing unrelated classes A and B, you can define an interface C in Go which covers a subset of methods in both A and B and then you can define a function f(obj C) which can do similar processing of some instances of A or B. This approach is a bit more involved in Clojure. You would probably have to define a new set of multimethods which in effect would represent interface C. These functions would have to forward to the correct function for A or B.

Beyond this Go starts falling short of the flexibility of Clojure for building abstractions since Clojure is a LISP and thus supports powerful means of abstraction like macros. There is nothing remotely similar in Go.

Go on the other hand is more capable when it comes to low level tuning of your application. Memory layout of datatypes can be controlled in detail which is not possible in either Java or Clojure. This is quite important given that cache is increasingly important to the performance of applications. In Go it is easy to place elements accessed together close in memory so that they are likely to be pulled into the cache at the same time.

IMHO that means Go is more poised to take over areas traditionally dominated by C/C++, while Clojure will be fighting in areas currently dominated by Java, C# or script languages, like enterprise systems. E.g. Go wasn’t designed to be used for game engines but I can imagine if a game engine developer had to chose they’d chose Go over Glojure, simply because they want much more low level control over their resources. In other respects they are overlapping in appeal. At Google there seems to be C++, Java and Python mainly used. For most tasks Python will simply be much quicker to use. When more performance is needed Java or C++ is used, which requires longer development time. Go appeals to those who want Python like ease of programming with C++ like performance. But Clojure gives Java like performance for those who want Python like ease of programming. Well, not entirely true but it can be tuned to get close and it is in perhaps most respect more powerful and faster to develop in than Python.

Who will succeed? Clojure advantages:

1. Part of the huge Java ecosystem.
2. Support more powerful abstraction mechanism.
3. Functional programming is gaining momentum and developers might see it as crucial that their next programming language supports this paradigm.
4. Support for REPL based development. Basically this means you can interactively develop a program. Clojure like any LISP gives you a sort of command line shell were you can write clojure code and test calling individual functions. You can load a file with clojure code into the shell and call individual functions to test them or redefine some of the function while the program is running.

Go advantages:

1. Syntax which is much more familiar to most developers. And we know this has been very important for the success of languages in the past.
2. More options for performance fine tuning (memory layout).
3. Imperative programming paradigm is better known and understood by the majority of developers.
4. Huge organization behind it (Google).
5. A very easy to understand concurrency model. Clojure also has great support for concurrency. Probably better in many ways, because it gives more options and is a functional language. However goroutines used for concurrency in Go is just dead simple to get started with.

I love LISP’s but my prediction is that both Go will become bigger than Clojure eventually. Simply because I don’t know of any time where a language with unusual syntax became a big success. Smalltalk, LISP, Objective-C etc never became big successes, mainly due to their unfamiliar syntax IMHO. I am guilty of this myself. I looked at Objective-C very early on when I had started learning C++ and rejected it almost immediately because I thought the syntax looked so weird. As a young developer I confused complexity of language with syntax. I had the crazy idea that C++ was somehow a simpler language to understand than Objective-C, because it looked more like C. This seems to be a common fallacy.

The STL is a very well designed library, and iterators is a powerful concept. Unfortunately you can not fully utilize the power of iterators unless you write generic code:

template<typename Iterator>
myfunc(Iterator begin, Iterator end) {
  // Do stuff
}

Now the function does not depend on the type of the iterator being used in the call. However C++, being a multi-paradigm language means you might be writing OO code and not generic code. E.g. you might have defined an interface on one of your classes:

class MyInterface {
  virtual void GetStuff(int count, vector<int>::iterator out) const = 0;
};

I can’t define interface methods to be template based. The problem with the interface above is that I force the receiver to use a particular kind of iterator. E.g. I have to write code like this:

vector<int> buffer(count);
myvar->GetStuff(count, buffer.begin());

But what if I need buffer to be of any of these alternative types?

 int * 
 QVector<int> 
 vector<int, myallocator>  

Then I would be screwed, because they all have a different concrete iterator type. However if we change the interface to:

class MyInterface {
  virtual void GetStuff(int count, int *out) const = 0;
};

Then we can use any kind of vector type:

vector<int> buffer(count);
myvar->GetStuff(count, &buffer[0]);

This code does not care which type buffer is as long as it represents an array of data in contiguous memory.

These observations give a few rules of thumb for when to use iterators and when to use pointers. * Never use iterators to receive data. Use pointers. * Let your internal data be accessed only through STL style iterators, but only ever use these iterators with generic functions. This will allow you to change internal container type without breaking code. If you use non-template functions you will break code.
* Never return pointers to your internal data. Instead push or pull data to/from external buffers through pointers. Non-generic functions should interface with pointer based methods.

So say I have a polygon class I should be able to do stuff like:

// generic function so use iterators
std::sort(poly.beginVertices(), poly.endVertices());
std::vector<Vertex> buffer(10);

// setting and getting values, so use pointers
poly.getVertices(&buffer[0], poly.size());
poly.setVertices(&buffer[0], poly.size());

// Non-template based class, so use pointers
vertexProcessor->doStuff(&buffer[0], poly.size());

// If class was template based, then we could to it like this
vertexProcessor.doStuff(poly.beginVertices(), poly.endVertices());

I know the first objection you probably have is that the pointer solution leads to a lot of unnecessary copying of data. That is potentially a performance bottleneck, right? Not necessarily. Typically you don’t need to try to optimize this. If it proves to be a problem the solution is fairly simple. Copy out only small chunks at a time. E.g. fetch 10 elements, do some processing, fetch the next 10 elements. Rinse repeat.

If you have a small fixed size buffer you keep pull data into, it will most likely stay in cache and it will be very fast to copy the data into it.

Clojure is a lisp like language built on top of the Java virtual machine. It lets you interact with and use existing Java libraries. Nu is a lisp like language built on top of the Objective-C runtime, which gives easy interaction with the Cocoa libraries. On the surface it then seem very similar. However they are radically different. Mostly because their goal and reason for existance is radically different. 

Clojure is an attempt at creating a modern new language with emphasis on concurrent programming, functional programming and ability to use the vast selection of Java libraries. It is supposed to be able to stand on its own feet. It is efficient enought to write large programs entierly in it.

Nu on the other hand is a fairly slow interpreted language. There is no special emphasis on things like concurrency or functional programming. On the face of it Nu then sounds inferior and quite worthless. But concluding that means misunderstanding its intentions. Nu is meant to help you write Objective-C programs. It is a glue and prototyping language. The idea is that you prototype a program in it or glue together different Objective-C components to create a program. This is the reason why Nu is not as much like lisp as Clojure. It is a lot closer to scripting languages like ruby. Where Nu shines compared to traditional scripting languages like perl, python and ruby is that integration with C libraries is trivial. All you have to do is to provide a Objective-C wrapper around your C library, which is easy, because Objective-C mixes freely with C. Nu uses the same object model and runtime as Objective-C so it can instantly interact with Objective-C objects.

 Nu can use a tool called nubake which will translate Nu code into Objective-C. This allows you to quickly start rewriting Nu code into Objective-C code. Generated Objective-C code is obviously not very efficient, so you will have to do some hand coding, but it does away with a lot of tedious translation work. This way you can start writing a program in Nu and then use  nubake to translate and optimize portions of your code into Objective-C where it is slow. So while Clojure is meant to be used for the whole program, Nu is always meant to be used in tandem with Objective-C. That is why performance is not so critical for Nu.

Nu in the grand scheme of things

Nu reminds me of the Genie and Vala programming languages targeting the GNOME object model. Rather than binding Python and C# to Gtk+ directly they have chosen to create to language that look like Python and C# but which integrated tightly with the Gnome object model and compiles to C code rather than bytecode. Because Objective-C is dynamic unlike C, Nu can run directly without compiling to C or Objective-C. It just needs to send messages to the Objective-C runtime. But all 3 languages represent and alternative to using a Virtual Machine or Common Language Runtime. I think this is the only path that Apple can go down with its development environment. Creating something similar to .NET is unthinkable. It is a huge undertaking and Apple is too far behind to compete with established platforms like Java and .NET. But Cocoa is a very well designed framework and the Objective-C runtime allows fairly easy interaction with other dynamic languages. Microsoft was never in such a fortunate position. Creating a COM object was far more complicated than creating an Objective-C class. That made .NET more of a necessity.

Apple is more likely to build on the Objective-C runtime in similar fashion to Nu  and MacRuby. MacRuby is built on top of the Objective-C runtime but uses LLVM to generate code. So it can be precompiled or JITed unlike Nu. My prediction is that if Apple has a new more modern language in the works for rapid application development on Mac, it will be based on LLVM and the Objective-C runtime like MacRuby, but will take the same approach as Nu  in that it will be designed from the groundup to work with Objective-C and complement it. Here are some things I think will be features in such a language:

• It will basically be dynamic like Objective-C but with better support for static typing when desired.
• Strong support for concurrency programming like Go, Erlang and  Clojure but built on top of Grand Cental Dispatch.
• JITed on LLVM
• Type inference when using static typing
• Native support for Closures, based on blocks as used in Grand Cental Dispatch
• Smalltalk or Objective-C like syntax in that arguments will be named. The reason being interaction with the Cocoa API which is awkward without similar syntax.
• Garbage collection as standard, not as an option
• The beginnings of some higher level abstraction on top of LLVM to allow interaction between multiple languages built on top of that abstraction beyond message passing compatible with the Objective-C runtime.

I don’t think it will contain any revolutionary new features we haven’t seen before but it will follow the general software trend towards concurrency, more functional programming and ability to write shorter more succint code as we have seen in script languages like Ruby and Python an which has recently been copied by Go. There isn’t really any reason why Nu couldn’t morph into something like this but I think Apple will go for a more traditional syntax and more ephasis on static typing to cater more towards what the majority of programmers seem to want.

I think if Apple does this, they wont be in a disadvantage compared to Microsoft with respect to development environment. And they should to this while people are willing to learn Apple technologies to get onto iPhone development. 

I am currently in the process of rewriting a simple 2D game engine from C++ to C. Having always been a C++ programmer I am used to think in terms of classes. So I have done this in C as well. So here is an excerpt from how I originally wrote my header file for dealing with 2D vectors.

typedef struct _Vec
{
  real x, y;
} Vec;

//- Constructors
Vec vec(real x, real y);

//- Calculations
Vec  vecAdd(Vec u, Vec v);
Vec  vecSub(Vec u, Vec v);
Vec  vecMul(Vec v, real factor);

This is pretty much how a C++ guy would do it. Data definition and associated operations are put in the same place. Most other “classes” which takes 2D vectors as input would include this header file. However it gradually dawned upon me that this was completely unnecessary. Those other header files only needed to know the memory layout of a 2D vector. They didn’t need to know the associated functions. So I moved the struct definition out of the file and only included that in other header files which defined functions accepting 2D vectors. An example is my 2D matrix class. The excerpt below shows how it was originally. The header file included all the 2D vector functions (as a C++ class would).

#include "geometry/vec.h"

Mat matIdentity();
Mat matTranslate(Vec v);
Mat matMul(Mat m, Mat n);
Vec matMulVec(Mat m, Vec n);

But with my new realization geometry/vec.h was replaced by geometry/types.h which defined all the structs for geometry types like 2D vector, 2D matrix, circle, rectangle etc. geometry/vec.h was instead included in mat.c. This has major implications for large programs where compile times often can get very high because header files are re-processed countless times. I am not claiming this is any ingenious insight of mine. It is not by a long stretch. On the contrary it should be pretty darn obvious and a lot of C programmers are probably laughing at me for pointing out such an obvious thing, but having done C++ programming for too many years might have caused some brain damage. But hopefully this was worthwhile being pointed out to other brain damaged C++ developers.

Nor am I saying that this problem can’t be solved in C++, but it requires a lot more diligence. The Visualization Toolkit (VTK) is a good example. They mandate that you only use pointers to objects. That way you can forward declare everything, except the class you inherit. Most big C++ projects probably wont realize this until it is too late, and they have by then gotten too used to using nice STL and Boost stuff which doesn’t play well this mindset.