2008-03-31

The Long and Winding Post

In which I have diverse, barely connected ideas and fail to create a structured narrative that ties them together.

Support Classes

Woopsi includes two of the most ubiquitous container classes, dynamic arrays and linked lists, as part of the main library code. Of these, only the dynamic array is used. Linked lists are in there partly for other peoples’ use, but mainly because I wanted to write a linked list template class to complement the dynamic array.

There’s no reason why the linked list class and its associated iterator class should be shipped as part of the Woopsi library code. It would be better if Woopsi came with a separate directory of optional support classes that could be added into applications as required. The linked list would be one such class, and I could add the SimpleScreen and SimpleWindow back into the distribution too (updated to support everything in the current gadget set).

Coding for Noobs

I didn’t explain the rationale behind removing the Simple classes and it is appropriate to mention it here. A few weeks ago I was pondering on how Woopsi’s target audience had completely changed since I began working on it. The original plan was to create a GUI library that would be used in the same way that a web developer works with HTML. You just work with what you’re given and, should you really feel the urge to create new UI components, you do it all yourself from scratch. You can’t subclass an HTML button.

I set out to make a library that included enough UI components to allow developers to cobble together interfaces quickly and, more importantly, easily. Even beginners should be able to assemble GUIs using a tiny amount of code. This is where the SimpleWindow and SimpleScreen classes came in - they wrapped up child gadget creation in tidy methods and reduced the amount of code needed to get a UI working. They also protected the child gadget arrays from external interference and actively prevented subclassing. Subclass prevention was prevalent in the early Woopsi code.

Over time, Woopsi has become less focused on providing a system for newbies and more focused on being a useful tool for a whole range of programmers. As such, it struck me that coding for beginners is counter-productive. Microsoft don’t dumb down their APIs so that beginners can code for them; they write what they need to and layer simple, optional abstractions on top.

Hashmaps

I bring all of this up because I’ve been looking into the other main container class - the map/hashmap/hashtable/etc. I’ve never written one before and, although I use them all of the time, I didn’t have a clue how they worked.

Turns out to be fairly easy. A hashmap is essentially an array. Data is added to the hashmap in key/value pairs. When an attempt is made to add data to the hashmap, the key is turned into a “hash”, or integer representation of that key, and the key and value are inserted into the array at the hash index. To retrieve an item from the hashmap by its key, we can just re-hash the key and return the item from the array at the hashed index.

For example, assume we’re inserting an object into the array with the key “myobject”. We take the hash of “myobject” (assume that the hash function in this case gives us the integer value 34). We then insert the key and value into array element 34. To retrieve the data represented by the key “myobject”, we just take the hash of “myobject” again (gives us 34) and return the data at element 34.

It gets a little more complicated when you try to compensate for potential “hash collisions”, or cases where different keys produce the same hash value, and a lot more complicated when you try to judge the efficiency of your hashing function.

Anyhoo, I have a hashmap and a hashmap iterator class working in VC++. It’s not the most efficient example of a hashmap, but it follows the coding style laid down in the dynamic array and linked list classes and thus fits in with the rest of Woopsi’s code. As soon as I’ve converted it to use the PALib type names (u16 instead of “unsigned short”, for example) I’ll add it to the (proposed) supporting class folder.

Coding for Programmers, Coding in Public

Coding a toolkit for programmers is totally unlike any programming I’ve done before. Ordinarily I don’t mind too much if my object model isn’t completely logical, or if I take shortcuts in order to get things done - the nature of the industries I’ve worked in demand that I produce working code as quickly as possible. As long as the code is commented, structured, follows a consistent style and has descriptive names for everything (such that a junior programmer can maintain it or I can pick it up again in 12 months), I’m generally reasonably happy. Naturally I’d prefer it if I could revisit the code, tidy it up and optimise it, but that’s rarely an option.

Coding for other programmers is entirely different. Every piece of functionality needs to not only work, but it also needs to be designed in such a way that it will make sense to everyone else who wants to use the toolkit. The object model must make sense. As Woopsi is being developed in public (open-source is, I think, the closest programming gets to a performance art) all mistakes are easily scrutinised by anyone who cares to download the source, and all mistakes affect anyone using the toolkit. It could be very easy to get into the situation where I second-guess every decision and development stagnates.

Even little things that don’t seem like major design decisions can turn out to be. One example is the way that the Woopsi hierarchy is responsible for deleting gadgets. John - another Woopsi user - noted that this makes it impossible (or at the very least, inadvisable) to create gadgets on the stack. As soon as the gadget goes out of scope it gets deleted, which will leave the hierarchy with (potentially) a lot of trashed pointers. It seemed like a perfectly reasonable idea at the time, but John pointed out that FLTK leaves responsibility for deletion with the user. FLTK UI components can be created on the stack.

There’s a good quote over at Jeff Atwood’s blog about programming for programmers:

“Reuseable components are three times as hard to build”

No kidding.

Although it is arguably more difficult, coding in public gives huge benefits. This blog currently has 215 posts, but this number is vastly outweighed by the number of comments from users - 555 at the current count. The most surprising thing is the signal-to-noise ratio. There are virtually no useless comments. Okay, so most of the comments are by one guy, but when you’ve got one great programmer contributing to your blog you really don’t care.

If I’d decided to keep Woopsi closed-source until it was done, I’d still be coding for beginners and it wouldn’t be anything like it is today. The SimpleWindow class would still be in there.

There’s also the advantage of getting feedback when things go to plan. Here’s a quote from the DSTalk blog, regarding Woopsi 0.30:

Overall I am very happy with the update! Not only are whole host of bugs fixed and new features available to me but in the process of updating my code was vastly improved and tidied up.

Great stuff.

Returning to Academia

Whilst on the subject of university projects, I got an email from my old university at the weekend - I’ve got a place on the MSc. The course appears to be assessed mainly by exam, and I haven’t taken an exam in about 7 years.

Yikes.

Comments

ant on 2008-03-31 at 22:42 said:

Yep, my hashmap description is intentionally simplistic. What my class actually does is use Bob Jenkins’ “one-at-a-time” hash, borrowed from Wikipedia, and it handles hash collisions using linked lists in each array index. I went for the bitmask approach to confining the hash value within the range of the array.

I agree about the stack - I said the same thing to John. If you’ve only got 16KB available the last thing you want to do is fill it up with heavyweight objects. On the other hand, I’ve made a couple of posts about how much I hate frameworks that force you to work in a particular way, and I’m doing the same thing myself. Gnnnk.

Regarding namespaces, everything is currently in the std namespace. Not good. The reason for this is that when I started using the vector class (having taken a break from C++ for a few years) I couldn’t figure out how to make it work without dumping everything into the std namespace. Now that I know how it works (prefix with “std::“) and I’ve removed the vectors anyway there’s no need for Woopsi to sit in that namespace. I’ve been tempted to create a new namespace for Woopsi; what do you think?

As for the “woopsi.h” problem, I’m fairly certain that I’ll use your WoopsiApplication pattern and resolve it that way. Just a matter of getting around to it…

Jeff on 2008-03-31 at 23:04 said:

Your hashmap description is a little simplistic. The implication behind most hashing solutions is that there can be many keys that hash to the same value - otherwise you might as well just use the raw keys as indices into a sorted list. So you shouldn’t be “compensating” for hash collisions - they are a part of the expected behaviour of the design. Usually, your slots are a linked-list of keys that match that particular hash, though there are other possibilities.

Also implicit is that the hash value is usually from a domain of integers that is far greater than the number of slots in your hashmap. I’ve seen multiple arguments on what the number of slots in your hashmap should be, and they seem contradictory.

The first suggests that you use a prime number of slots, so that you take the modulus of your hash value (ie, slot=hash%nslots) and that gives you a zero-based index into a fixed array of slots. This is a good idea, mathematically because division by a prime should still give a relatively good distribution of results

Imagine the trivial case of having two slots - you disperse your keys based on whether they are odd or even. Now, if you hash function is poor and tends to produce even numbers more often than odd (perhaps it cycles the top bits of the input ascii value into the bottom bit of the hash) then you will put all values into the one slot.

Having said that, if your hash algorithm is just: foreach ch (string) hash=hash*nslots+ch :then only the last character you feed in counts. Oops. Another good reason for primes - the likelihood that the multiplier in the hash algorithm is a factor of nslots becomes zero if nslots is prime.

By getting a good distribution of hash values, the linked lists should all be relatively similiar lengths, and your retrieval times should be similiar. If more keys are in one slot than another, then accessing records with that particular hash value will take longer (since you need to walk along the list looking for the exact match).

The second opinion is that the number of slots should be a power-of-2. The basis of this seems to be that the modulus operator, to find the corresponding slot, is slower than a bit-mask which can be used with powers-of-2. Personally, I suspect that the performance advantage will only be present if you have very well-distributed keys, with few entries per slot.

The system I use at work uses primes, and we have actually got a handy table of primes sitting around so we can increase the size of the tables appropriately. ie, software asks for a table with 300 slots, and we automatically bump it to 317 - which means that users can externally tune performance without being mathematically perfect.

Choice of a hash algorithm is also problematic. If you know the complete domain of keys that you might feed into a table, then there are “perfect hash generators” out there (http://www.gnu.org/software/gperf/)

On the other hand, if you take in arbitrary strings, you need to hope you chose a good one. Its important to remember that you want a function that gives you good randomisation relative to what you do with the hash. ie, if you are using the power-of-two approach, then you want to be sure that it randomises the bottom bits of the hash as well as the upper. A simple sum or xor might actually work better than a more complicated algorithm that multiplies and adds since the multiplied data tends to move up to the top bits in the result where bit-masking will ignore them.

Jeff on 2008-03-31 at 23:10 said:

If the Gadget destructor checked whether it still had a parent, and if it did, removed itself, I think the stack-based approach would work. Then, when the parent is deleting gadgets, it should just remove them from itself, then delete them.

Of course, that probably happens inside a vector delete at the moment, doesn’t it? Then again, you own the vector code, you could add to the delete logic quite easily.

On the other hand, I suspect that the desire to use the stack for objects may be a bit optimistic in the DS environment, recalling the problems that exist with DMA and the stack. If someone creates an object with an inline array (ie, char data[128];) as opposed to a dynamically created one (char *data = malloc(128);) then DMA operations on that member variable would fail in mysterious ways.

Personally, I would be creating a smart-pointer-oid class that created the onstack object - when that one goes out of scope, it could do all the right things to delete the “not-quite-stack” object.

Jeff on 2008-03-31 at 23:24 said:

I’ve been really happy with the results of my ‘makefile.lib’ approach to using Woopsi - once its built that way, it really doesn’t matter how many extra classes you dump into the product, with a few niggly exceptions.

The first is name clashes. You haven’t made all the class names ugly by putting “Woopsi” prefixes on them; this pushes the need for namespace protection back into the user of the library.

The second is header interdependency. You have been moving forward on this one, but “woopsi.h” still includes way more than it needs. This is another of those “the n00b can just include and it will all work” and I understand that. But moving the Woopsi class out of that file and into another one that woopsi.h then includes would fix the issue for me. I would include “woopsiobj.h” or whatever you chose to call it, and never include “woopsi.h” again…

Just to repeat, I have been really really happy with the way this has all gone - I have fearlessly used ‘svn update’, rebuilt Woopsi, then rebuild my other apps and its all just worked. You have done a really good job with a very well-maintained library; it is very simple these days to treat Woopsi as a mature, external component - despite its alpha status ;-)

Jeff on 2008-04-01 at 02:30 said:

I’m of two minds about the namespace - on the one hand, I’ve had no problems avoiding clashes already, and “if it ain’t broke, don’t fix it” seems to apply.

On the other hand, the purist in me suggests that tackling the problem today (before significant content depending on the ‘wrong’ behaviour appears) is smarter than leaving it. So, yes, I would consider having a Woopsi address space. That would address the issue of the Woopsi class really being Woopsi::Application ;-)

I’m a big big fan of eliminating the niggly little problems (like the library builds, keeping header files clean, setting up namespaces, etc) as soon as they appear rather than waiting for a ‘clean it up later’ phase to start - because its never glamorous and no-one ever wants to do it later (and as the pile of problems gets bigger, it becomes less attractive). And its always a false economy - you always suffer from forgetting that one thing you needed to change, that you nursed along by hand. Better to fix it now.

One thing that has caused me a little grief is in the library makefile - at the moment, I just copy all *.h files from Woopsi/ to libwoopsi/include/ - this is a bit overkill since there can be private header files in there that shouldn’t be part of the distribution library. The fix to this is to keep them (the public interfaces) in a seperate subdirectory.

I’m pushing forward with my makefile overhauls - its allowed me to cull 95% of the content out of any single applications makefile (at the expense of flexibility) - more importantly, its given me the slot such that I can start doing wifi in a consistent manner. If I define USE_WIFI in the top-level makefile, it actually builds a custom arm7 binary and automagically links that into my end result. And the build of the arm7 sources gets passed all the options that were selected in the arm9 (like USING_PALIB, etc) and can thus conditionally compile the support that they need, without forcing you to take more than you need.

On the horizon, I can see issues where a “woopsi-specific-arm7” might become a sensible option and the easier that is to get right, the better. By making the arm7 support purely mechanical and strongly supported right from the outset, I believe I’m best place to enhance it later on.

Jeff on 2008-04-05 at 08:02 said:

I accidentally took a look inside the hashmap code (don’t ask) and noticed that its a little inefficient.

template const s32 HashMap::getHash(const char* key) const { s32 hash = 0; s32 keyLen = strlen((char*)key); for (s32 i = 0; i < keyLen; i++) { hash += key[i]; … snip …

There is no need to use strlen() to retrieve the key length before iterating - by doing so, you make TWO passes over the string. Instead, use the null as your termination condition.

template const s32 HashMap::getHash(const char* key) const { s32 hash = 0; while (*key) { char ch = *key++; hash += ch; …snip…

only visits each character in the string once. Niggly, I know, but people using hash maps are typically using them for efficiency sake.

Secondly, when you add a new entry to the linked list, you APPEND which means you need to walk to the end of the list. Why not just insert at the head of the list? If you were keeping the lists in sorted order, it might make sense to work harder, but you aren’t.

ant on 2008-04-05 at 10:24 said:

I knew the strlen() was a bad idea, but checking the terminator didn’t occur to me. The list insertion didn’t occur to me either. I did consider adding in sorting based on probe quantities (every time an item in a list is retrieved, its “probe count” increases, and the list is ordered by probe count so that the most-queried items appear first), but that seemed like overkill. I’ll make both amendments. Thanks!

Jeff on 2008-04-06 at 13:30 said:

If you don’t insert too often, and you have a well-balanced hash table with relatively good spread of keys, then just doing a sorted insert into the list can be a good idea - all you need to do is find the first key greater than yours and insert prior to it. Speeds up hash-lookups as well, since you can bail out earlier when looking for a match. Inserts are a bit slower. Lookups are a bit quicker. Deletes are unaffected.

ant.simianzombie.com » Blog Archive » Still Alive on 2008-08-15 at 07:38 said:

[…] has been consumed by other activities of late. First off, there’s the impending university course. This in itself isn’t time consuming (yet), but it does mean I’m expending a lot of […]

ant.simianzombie.com » Still Alive on 2009-10-07 at 12:01 said:

[...] has been consumed by other activities of late. First off, there’s the impending university course. This in itself isn’t time consuming (yet), but it does mean I’m expending a lot of [...]