Hexinspector : Faster memcmp and memdiff

When focusing on the performance of hexinspector, I realised that one of the performance bottlenecks was probably the loading single bytes individually and comparing them, instead of working a word at a time.

For performance reasons the C versions of memcmp in glibc performes based on word at a time, although usually the assembly based versions are used.

Complicating matters is the inability of some architectures to fetch words non-aligned with the platform word size. In glibc when both pointers are not word aligned, this is overcome by aligning one of the pointers to word aligned and shifting the other pointer data (see memcmp_not_common_alignment).

As hexinspector is currently/unfortunatly aimed at x86 architectures which supports fetching words non-aligned, it is not a high priority of mine to implement the non-aligned version.

By moving from byte based to word based (see commit id b0049cc3363fb8de88fd5f26debf9701633d2e87), the simple diff algorithm performance improved from 600mb/sec to 800mb/sec (when running on an 2 core Intel and the files are both in the cache).

Word-based finding two bytes the same

We realised that the while loop while the data is different could be implemented word-based instead of byte-based by using the Zero in Word technique discussed in Bit hacks by Sean Eron Anderson, which is a document well worth a read for any programmer.

The commit bb6c8298b95bd5650794c1790fc17e4751df358d implements this, basically as below


value = (*srcword) ^ (*dstptr);
if (((value - 0x01010101UL) & (~value) & 0x80808080UL) != 0) printf("Different");


Using this the performance of the finding two bytes the same increased on a dual core from 600mb/sec to 800mb/sec effectively the same as the compare performance.

One problem I noted, was that adding more CPU’s to the diff algorithm when the file was not in cache slowed it down. Question is, what’s the optimal way to access the same file using two or more cores?

Hexinspector

Since I haven’t really written about hexinspector before, I thought I would.

It started off as a project because I got tired of looking at binary diffs using hexdump and vimdiff. At the time people at work (EchoStar Europe) said a binary diff utility was impossible to do perfectly. While it is true that there is no accurate way of doing a binary diff 100% of the time, there are enough heuristics to make it a worthwhile tool, and hexinspector was born.

The ‘smart’ mode is basically the following algorithm (which is used as default)

1) Go through the file until you find a difference
2) When there are differences, try to slide a window of 16 bytes trying to find a match in the second file.
3) When that fails, try to use the Rabin-Karp algorithm (based on hashes fixed length bytes to find them)

Unfortunatly that algorithm isn’t perfect and isn’t that high performance, but it’s usually okay, and was for the primary dataset I was looking at at the time (mainly MPEG-2 transport streams)

I’m looking at improving it, both in terms of performance and accuracy.

As well as the ‘smart’ mode there is the ‘simple’ mode which doesn’t try to realign the data, and just calculates if it is equal or not.

For it’s warts it has become a useful tool at work, and is one of the better binary diff tools available (and probably the best one available on linux)

Anyway, hexinspector is available for download and is licensed under the GPL.

Restart of the blog

For years this blog has effectively been dead, i’ve gone through some of the old blog posts deleting the chaff. And am intended it to be reborn as a programming blog, mainly aimed at things like performance, multicore support and things I find out.

Directory of Chess Openings

I’ve been trying to learn some chess openings, couldn’t keep them in my head, so I created a mindmap of them all. I find most of the websites about openings unusable as a teaching aid, so much so I sometimes think about writing something myself.

Moving room to room

It’s taken a little while, as I’ve been distracted with other things, but backpack now has the ability to move room to room.

I think it needs another refactor in it’s core as the system is becoming unwieldly. At the moment the main system is linked together with the following three classes

• ObjectManager : Looks after all the objects
• World : Looks after the world view
• DSLParser : Looks after the DSL parsing

The three of these are tided together using masses of method_missing calls.

There’s also the problem where functions with similar names do widely differeing things

I’m not sure how best to rejig it. There is also the problem of inheritance in the CoreObjects, I’m not sure the best way to model it.

How the object based parser works.

The object based parser is now pretty robust in terms of functionality, it needs more work in terms of error handling.
The following is an example of how to declare the verb ‘help’ and connect it to the help function in ruby, simple enough.

module Backpack
  class SystemObject
    include Parser
    verb "help", :help
    def help
     puts "You need it"
    end
  end
end

And for strings with an object attached:

  class Item < BackpackObject
    verb "examine", primarynoun, :examine
    def examine
      puts self.inspect
    end

    verb "put", noun, ["into","in","inside","through"], primarynoun,:insert
    def insert(x)
      puts "insert %s" % x
    end
 end

It currently doesn’t support multiobjects, but that’s not to difficult to add. Unfortunately it has caused a slight rethink in how exits in Backpack are handled, and is causing a slight rewrite (as well as a tidy up).

The system also exposed an area of ruby which I wasn’t sure of before, inheritance and metafunctionality that is created when the class is loaded, the verb function adds a class variable and this is not visible to the child, this then has to be put back together when the verb is being parsed.

Breaking the Tradition of IF

I find most IF games very infuriating, and is likely why the genre died out in the commercial world. Why spend your afternoon trying to phrase things properly when you can blow up aliens.

Three Things annoy me greatly about IF.

1) What direction was I wanting to go in.
Why when I want to go into the Kitchen, do I have to find out what direction the kitchen is in, and then type ‘go east’. In the real world do you think “Hum, I want a yogurt, I’ll go to the kitchen, the kitchen is east, therefore I go east”, you think “Kitchen”

The only game where directions are useful seem to be the original Colossal Cave Adventure, and every game since still takes that design as a good one. I’m tempted to remove directions altogether from the standard setup of adventure backpack.

2) What verb was I looking for?

I needed a parser, so I took inspiration from Inform 6′s parser, but in my world view, I felt that the verb definitions should be done as part of the object (including inheritance).

Why:
You could ask an object what verbs are available for it (avoiding the what verb problem)
The code for declaring the verb would be in the same place as the code for handling the verb, which is much more maintainable.

3) Conversations in the system are very weakly done.

I’ve been exploring various IF games recently trying to find the style I like, all but the choosing a conversation number become very fiddly and difficult to know what you are doing. But the drawback of this (called the Lawnmower effect), is you choose responses randomly.

I’m tempted to take the same approach (as the default), of handling verbs where you can inquire what the person’s topics are, I know it breaks the fourth wall, but it makes it easier to work with.

Should I be doing this at all?

I’ve been reading the following, The Interactive Fiction Authoring System Developer’s Guide 0.99, and it quite correctly says that most people trying to create an IF authoring system will be wasting their time, as the current systems are quite versatile.

So why would I bother?

• It’s done in a general purpose programming language rather than a specialized one. The number of programmers out there who understand Ruby is probably 1000 times greater than the combined programmers in TADS 2 & 3, Inform 6 & 7. I dislike the idea of creating new languages and having to implement object models where a system is already available. Ruby already has a large amount of logistics behind it, and the mixin ability is rather cruicial.
• Since it’s based on a real-world programming languages, new options are available. You could have a paper in the game when you read it, would fetch the Guardian’s news stories and include them into the storyline. (Difficult to program realistically, but the option is open)
• Multiplayer IF is not well done in existing systems, and MUD systems are not really that expressive, and don’t have the advanced abilities that IF does.
• Graphics IF creation software is ad-hoc and not easy for indie productions. (Adventure Backpack original started out as a graphical IF system, but that was to complex). I intend to extend the system to add graphics (probably AJAX & SVG)
• It gives me an excuse to program in Ruby and mess around with DSL’s.
• I find the idea of Natural Language (Inform 7) programming abhorrent, unmaintainable and unartistic. The difficulties with programming are just as difficult with Natural Language programming as Non-Natural Language programming, but you have a new batch of guess the verb problems.

Continuing Adventures of Adventure Backpack

I added the inverse path generation (which was a doddle) create a list of directions and their opposite (invert that list) and then loop over the list.

I then added the existence of items, I’m played around with the syntax for creating items, I think my solution of creating the items in the rooms they are in is quite tidy and implies a lot more structure in the script file than inform does, and follows the DRY idiom (Don’t repeat yourself). The current code can be found at http://github.com/jenf/adventurebackpack/tree/master

room :Forest, "Deep in the forest" do
 description "Through the dense foliage, you glimpse a building to the west."
             "A track heads to the northeast."
 exit_northeast :Clearing

 item :Bird, "Baby bird" do
  description "Too young to fly, the nestling tweets helplessly."
  name ["baby","bird","nestling"]
 end
end

 

Object  forest "Deep in the forest"
  with  description
            "Through the dense foliage, you glimpse a building to the west.
             A track heads to the northeast.",
        w_to before_cottage,
        ne_to clearing,
  has   light;

Object  bird "baby bird" forest
  with  description "Too young to fly, the nestling tweets helplessly.",
        name 'baby' 'bird' 'nestling',
  has   ;

The biggest challenge to the system now has to be the natural language parsing.

Pet Project: Adventure Backpack

A while ago, I tried making a Ruby based graphical adventure system. As usual I bit more than I could chew. So I’ve decided to go back and try making a text-based system first to explore things, and maybe taking the ideas into a second version of the system. (Alternatively making a system that’d fit both text and graphical adventure games)

I’ve decided to make it as a DSL (Domain Specific Language), after getting my ruby programming back from the rusty part of my brain I managed to do quite a bit for 3 hours work. At the moment it allows you to move from room to room. The following is based on the Heidi example by Roger Firth and Sonja Kesserich

room :BeforeForest do
 description "You stand outside a cottage. The forest stretches east."
 short_description "In front of a cottage"
 exit_east :Forest
end

room :Forest do
 description "Through the dense foliage, you glimpse a building to the west."
             "A track heads to the northeast."
 short_description "Deep in the forest"
 exit_west :BeforeForest
 exit_north_east :Clearing
end

room :Clearing do
 short_description "A forest clearing"
 description "A tall sycamore stands in the middle of this clearing."
             "The path winds southwest through the trees."
 exit_up :TopOfTree
end

room :TopOfTree do
 short_description "At the top of the tree"
 description "You cling precariously to the trunk"
 exit_down :Clearing
end

start_room :BeforeForest

My next steps are

• Automatically generate the inverse paths
• Add actions (like on_entry)
• Add objects
• Add Natural language parsing (at the moment I can only say east up down)
• Add NPC communcation
• I need a better name.

Crumupant

The realisation that the crumpets are burning.

(Google doesn’t know about it)