Mensa, Schmensa

Mensa is a society for people with high IQs, specifically for people with an IQ in the top 2 percent of the general population. In short, it’s supposed to be a society for smart people. A few months ago I had too much spare time on my hands and had to get my mind off a romantic tragedy so I decided that it might not be a bad idea to join them to distract myself. I passed their preliminary test but by the time they invited me to the real test I had a 60 hour work week and not too much time to kill, so I didn’t go. Mensa Austria is still sending me their publication “Diskussion”, though, of which I received another issue yesterday.

The puzzle column was a letdown, but I was used to that from the last issue I got. They seem to favor puzzles which are either entirely trivial or at best require a halfway competent programmer maybe an hour to solve with a computer.

What did surprise me was an article on “Morphic fields and human perception” (my translation). The German text actually talks about “morphogenetische Felder”, but they are clearly talking about Rupert Sheldrake’s morphic fields. The article is completely credulous on the existence of morphic fields and even discusses a purported practical application of them, remote viewing. It even tells the story of school teacher who, since asking students to remote-view exam questions in advance, reports much improved grades. The authors of the article are Karina Leitner and Viktor Farkas, the latter seeming to be a prominent conspiracy theorist and believer in (or at least proponent of) woo-woo ideas.

As anybody equipped with a web browser and a small dose of critical thinking can ascertain, there is absolutely no substance to either morphic fields, which are a ridiculous contruct invented to explain non-existant phenomena, nor to remote viewing, which has never been demonstrated in a well controlled setting. Specifically, the James Randi Educational Foundation will award anybody able to demonstrate remote viewing in a controlled study with a million dollars. The prize has been available for years and has not been claimed yet.

I wonder: Do they have no editorial process at all? And to add insult to injury the publication looks like it’s been typeset by a 3 year old on a PC with MS Word in 1992.

There is perhaps something to this quote, attributed to G. H. Hardy: “For any serious purpose, intelligence is a very minor gift.”

Nikon rocks!

Two days ago I wrote enthusiastically about the new Canon EOS 40D and yesterday Nikon had to turn the world upside down by announcing the D300. It does everything the 40D does, and then some:

  • A 100% viewfinder. That’s a first in a DSLR below the 4000 Euro mark.
  • The auto-focus system is kick-ass. 51 focus points, 15 of which are cross-type. Compare that to the 9 sensors (all of them cross-type) of the 40D. Plus it can track subjects not only with the focus points, but also by color, utilizing its metering sensor.
  • A 3 inch VGA resolution LCD – almost 4 times the number of pixels of the 40D.
  • Live view (which the 40D has, too), with contrast detection auto-focus (which the 40D hasn’t), i.e., auto-focus based on the sensor image, without having to pull the mirror down.
  • And to top it all off: a 12 megapixel sensor that goes to ISO 3200 without extension (6400 with extension)! Of course I’m very skeptical about this, and we’ll have to wait for in-depth reviews to see if the sensor can actually deliver that with a reasonable amount of noise.

So, not only does this camera, if it lives up to the specs, kick the 40D’s butt, it would even surpass the 5D in pretty much every way, easily making it the best DSLR to be had for less than 3000 Euros, which makes me rethink my decision to upgrade to the 40D. It seems I have three options:

  • Upgrade to the 40D, keeping all my lenses.
  • Selling all my lenses and upgrading to the D300.
  • Selling nearly all my lenses and upgrading to the successor of the 5D, which will hopefully be competitive.

Interestingly enough, the Nikon option is quite a bit cheaper than upgrading to a full-frame Canon. Considering that I’ll probably live with my next camera for the next 4 to 5 years I want to make sure to get the best the market has to offer at a reasonable price, which probably isn’t the 40D, and probably isn’t full frame, either, because I don’t consider that price reasonable, and who knows when Canon will announce that camera, anyway?

I guess all I can do right now is wait for the reviews of the 40D and D300 to come in and see how they measure up. In the meantime my 10D still captures pretty good photos.

My Next Camera

A few days ago Canon announced the EOS 40D, which is the successor to the successor to the successor to the camera I’m using primarily, which is the EOS 10D. The two cameras in between, the 20D and the 30D, didn’t provide reason enough for me to upgrade but the 40D finally seems to offer enough improvements to make it worth it. Here are the features which make the new camera very attractive to me, compared to my 10D:

  • The bigger viewfinder. Nikon has had this since the D200, now Canon has finally caught up.
  • Speed. Not so much the 6.5 frames per second, which I don’t really care much about, but the faster writing speed, deeper buffer, and especially being able to review photos immediately and not having to wait until they’ve been written to the CF card.
  • Better autofocus. I hope it’ll perform better in the dark than my 10D and it’s certain to perform much better for action shots like my runner photos.
  • Hopefully better high ISO performance and more dynamic range, especially in the highlights.
  • The big LCD. I love the big 2.5 inch LCDs of Canon’s newer DSLRs, so I can’t wait to use the new 3 inch one.
  • Live view might turn out to be very useful for macro photography.

Features which don’t really excite me:

  • I don’t care that much for the metapixels. I’d actually prefer a 6MP sensor delivering the quality that the 1D Mark III delivers to the 10MP sensor of the 40D.
  • The sensor cleaning system. Despite changing lenses pretty often I’ve never had big troubles with dirt on the sensor, and the more systematic tests of those systems have shown them to be not very effective, anyway.

What still pisses me off:

  • No sensor-based image stabilization. Sony has it, Pentax has it, and Olympus has it, too. Come on, Nikon, implement this, sell more cameras and force Canon to finally do it, too!

Otto’s Metapixel

Kim Mosaic

Metapixel is an application I wrote for creating photomosaics. It’s Free Software and if you run Ubuntu or Debian all you have to do to install it is type “apt-get install metapixel“, so give it a try!

A few days ago I got an email from the Hamburg, Germany based software development house that they’ve written a server application around Metapixel for a web-based photomosaic-creation application for the German company Otto Versand. You can upload your photo and it’ll build a mosaic out of photos of stuff you can buy there – pretty neat. There’s also a few mosaics of minor celebrities which you can browse and inspect in detail.

By the way: is looking for competent software developers willing to work in Hamburg!

A (Reader-)Lock-Free Sorted Array

Mono is a .NET jit-in-time compiler (JIT), which means that it translates .NET code (CIL code, to be precise) into native machine code on the fly. Something that happens very often is that it’s necessary to look up where the native code is for a given piece of .NET code (i.e. for a method). The opposite happens less frequently, namely looking up which method corresponds to a piece of native code. That need arises, for example, when walking the stack to find the method which should catch an exception, or when printing stack traces.

To that end Mono uses a lookup table which, until yesterday, required locking for readers and writers. Since the table isn’t used very often that’s not a real scalability problem. Paolo’s new garbage collector, however, requires unblocking read access to the table, so a new design was necessary.

The old JIT info table, as it is called, was a simple sorted array of pointers to the method’s JIT info structures, which in turn contain pointers to the methods for which they stand. The table was sorted by the addresses of the native code, so looking up a method given a native code address just required a binary search. Inserting and deleting elements required shifting elements up and down, but that was never a performance issue.

Being as lazy as I am, and considering that we always need to be careful about using space-efficient data structures, my first thought was whether it wasn’t possible to make the sorted array lock-free for readers. It turns out it is. Let’s pretend we only want to insert and never remove elements. If we are very careful we can insert an element and at each point during the process make the following two promises:

  • The array is always in a sorted state.
  • If an element is replaced by another one, then the replacement will be less or equal to the replaced element.

The implications of these two guarantees are that we can still do a binary search on the array while elements are being added. The worst thing that can happen is that we end up not exactly at the element we’re looking for but a little bit to the left of it (but never to the right), so we have to do a quick local linear search afterwards.

The way to add an element and keep those promises is by doing it in three steps:

  • Find the position where to put the new element.
  • Shift up the elements to the right of it, one by one, starting at the end of the array and working towards the left.
  • Put the new element in place.

As an example, let’s take this array:

2 3 5 7 11 17 19 23

and insert the number 13. The first step is easy and can be implemented with a binary search: the place for the new element is between 11 and 17. Now we shift up the elements one by one, first 23, then 19, then 17:

2 3 5 7 11 17 19 23 23
2 3 5 7 11 17 19 19 23
2 3 5 7 11 17 17 19 23

Note that we end up with duplicate elements during the process, but the array remains sorted. Now we just need to insert the 13 at its correct place and we end up with:

2 3 5 7 11 13 17 19 23

So far so good. Now, how do we delete elements? Doing the same process in reverse breaks our promises and the binary search wouldn’t work anymore without locking. For such cases lock-free algorithms use a trick called “tombstones”. Instead of removing the element, we turn it into a tombstone, essentially just marking it dead. It’s still there, so our promises still hold, but when we look for an element we have to make sure to ignore the tombstones.

Using tombstones leads to another problem, however, namely the fact that if we never really remove elements the table can only grow and never shrink. Upon closer inspection we have to deal with a similar problem anyway, namely an overflow of the array, which can only be allocated with a limited size. In such a case we simply allocate a new, bigger, array, copy the whole table over there, without the tombstones, and then, in one atomic step, replace the old table with the new one. We have to make sure not to throw away the old table just yet, though, because there might still be other threads reading from it. That’s a problem I’ll be talking about further down.

The shifting up step in the insertion process has to be done in exactly the way described, so memmove() cannot be used because there’s no guarantee over how it goes about its business. Furthermore, we have to make sure that the writes to the array are visible to all other threads in the correct order, which require a write barrier after every shift step, and that’s very expensive. Too expensive, as it turns out, because that implementation results in a significant overall slow-down.

To avoid shifting so many elements Paolo suggested splitting up the table into a number of small fixed-size chunks. The implementation is quite similar to a B+-tree, the main difference being that it is always two levels deep and the root node can grow as big as necessary. In this data structure, insertions are local, so only a few elements need to be shifted. When an overflow in one of the chunks occurs, we have several strategies:

First, we count the number of non-tombstone elements in the whole table. If it’s below a certain mark (relative to the capacity of the table) or above a certain mark, we reallocate it completely, making sure that not too much space is wasted and that we still have enough room to grow.

If we don’t reallocate the whole table we have to deal with the overflowing chunk locally. We inspect it to see if it contains any tombstones. If it does, we reallocate only the chunk, leave out the tombstones and insert the new element.

If the chunk does not contain any tombstones it really is full. In that last case we split it up into two chunks, which also requires reallocating the root node, but none of the other chunks. There might even be a way to handle this case without reallocating the root node, using an insertion strategy similar to the one we use in the chunks, but I didn’t go that far.

Using this new data structure improves performance to the point where there shouldn’t be a noticable difference to the old, locking, implementation.

I’ve mentioned above that when we replace the table with a new copy we have to make sure that we free the old table only when there are no more reader threads using it. To achive this without locking we use hazard pointers. A hazard pointer is a very cheap and simple way for a thread to signal that it’s using some data structure. Read Maged Michael’s paper for details

There are some further details I won’t go into here. For example, the JIT info table doesn’t map from exact locations to methods, but from code regions, i.e., intervals, which complicates things a bit, but not very much.