Friday, June 27, 2014

Devoxx4Kids Inspiration!!

Roy van Rijn makes the really really great Devoxx and Devoxx4Kids videos.  Really really upbeat and inspiring!

Next time, send your kids too!

Thursday, June 26, 2014

Lots of programmers make nests.

When you’re working alone on something, its very tempting to make a whole library of code to support yourself programming something.. to put off solving real problems and so on ;)

Here’s an example I read today of over-engining sprite sheets (been there, done that myself!)  That game looks absolutely stunningly awesome, of course!

But here’s a game engine I’ll call out as having potential: image

IceEntity by NicoM1; check it out!  A nest you might be comfortable sitting in yourself?

Seems from these links that I’m all nostalgic for a minimalist artsy XKCD-inspired platform puzzle adventure game… maybe an idea for LD30 August 22-25th 2014?

Wednesday, June 4, 2014

An Impartial Press

Well we all hear reports (on the BBC) about how the separatists in Ukraine are fed a distorted pro-Russian media diet… but generally the BBC tries to be objective.  However, this choice of “stock photo” jumped out at me:

Yes we know its just vapour, but I think we’re in the minority… the overall spin this picture gives the story for the general reader is rather different?

See also: Salami Tactics

Tuesday, June 3, 2014

Compressing Scrabble Dictionaries

The newest rec.math Al Zimmermann Programming Contest is a solitaire Scrabble puzzle called ‘Alphabet City’.

Wait, what do you mean you’re not entering that programming contest??  Its a really really nice clean problem and it’s addictive as 2048!

To lookup scrabble words quickly, people use a GADDAG.  The GADDAG is a tree data-structure.  Each node represents a character, and has pointers to all the child nodes that continue all possible words.

The key thing is that every rotation of each word is stored in the GADDAG.  To have a GADDAG of the words ALL, BALL and CALL, for each word we add all rotations.  This is LLA@, LA@L, A@LL for ALL, and LLAB@, LAB@L, AB@LL, B@ALL for BALL and so on.  (@ is my choice of ‘start-of-word’ marker; its a good choice because in ASCII its the character before A.  When you have arrays of child nodes [A..Z], this can easily be extended to have a slot pointing at the start-of-word node [@..Z].  And it looks nice enough in the graphs too.)

To speed up Scrabble searches, the prefix of each word is stored reversed which facilitates ‘hook’ searches.  To search for all words with one letter then A then another empty then L (?A?L), you start with the first known letter - A - and look for all those with one character in front (a child with a @ child), terminated by an L.

A naive sparse implementation of a GADDAG takes absolutely loads of memory: over a GB is not startling.  Almost all those nodes will be duplicates of other parts of the tree and almost all possible children will exist.  So we really want to get the memory usage down if we want to avoid our program waiting on main memory all the time: bottom cache is typically in the tens of nanoseconds away, whereas main memory is around a hundred nanoseconds away.  Getting the GADDAG small enough to fit into cache, even the bottom level cache (as in slowest and biggest), can mean an order of magnitude speedup!  So its well worth compressing your GADDAG.

The original paper describes compression and gives an example of partial compression.  I will talk these through with graphs:

image

Here’s the uncompressed tree.  Sorry it takes so much screen space .. it has a lot of nodes in it, which is a point I want to make :)

3 words, 11 rotations and 27 nodes.

Lets start compressing it:

The first thing to note is that, unlike the ALL, BALL, CALL example on NullWords blog, I am storing the terminating characters (the blue nodes) in a separate set off the node.  This is how the prefix LLA is followed by a single node with both B and C in it.

Read More

Thursday, May 22, 2014

pycon 2014 Sweden: the bad bits

I’m just back from pycon 2014 Sweden.

And all the tweets and commentary will be positive, as they always are. If you want to say something negative its best to not say it at all?

Hmm, not me.  Someone has to give this feedback; we can’t sweep it under the carpet.

Read More

Friday, May 2, 2014

Making Image Mosaics

imageAs followers of the blog know (thx for the mails!), I’ve been making mosaics of Ludum Dare contest entries.  It started basic, and its got better.  Each of the ‘pixels’ in the Mona Lisa is actually a screenshot of a game!  Here’s how:

We have an target image, for example the Mona Lisa, and we have some large number of small input images which we want to arrange so that, when squinted at from a distance, it approximates the target image.

Read More

Wednesday, April 30, 2014

UPDATE: blog post describing how these mosaics are made

I knew my mosaic script was doing a poor job of placing the images.

The approach it’d be taking was greedy: it’d place the closest matching image on its tile, and then the next closest matching and so on.  The outcome in in the middle column above.

After talking a bit with Roy, I couldn’t really leave it doing such a poor job.

So in what way is the greedy approach sub-optimal?  It may be that swapping two images or three or more images around will lead to a lower overall error score.

And what’s the simplest improvement to make?  Rather than tackling the true dynamic programming or other classic approach to optimisation, I simply went for random swaps.

The script will now perform random swaps if they improve the image, until you interrupt it with ^C.

And the results, as seen in the left column above, are stunning :)

Tuesday, April 29, 2014

The mosaic is made (sourcecode) from the screenshots from Ludum Dare 29, to the theme “Beneath the Surface”.  The green turtle is from wikipedia.

Monday, April 7, 2014

I’m giving a Mill CPU talk in Växjö, Sweden 2014-04-25

There are perhaps a few seats available to interested members of the public if you’re in or near Växjö at the end of the month :)

Announcing a presentation at 13.00h, Friday, April 25 at: 

Linnéuniversitetet (Linnaeus University) 
Vejdes Plats 6, Linnéuniversitetet 
Building B, Room 3021 
352 52 Växjö Sweden 

The new Mill CPU architecture 

A presentation by Will Edwards (Mill Computing) 

The new Mill CPU architecture brings DSP-like efficiency and performance to general purpose computing. Offering a 10x power/performance gain over conventional out-of-order superscalar architectures, the Mill family of CPUs scales from phones to supercomputers. 

The Mill is an extremely wide-issue VLIW design, able to issue up to 33 operations per cycle. The Mill is inherently a vector machine and can vectorize and pipeline almost all loops. The Mill is a belt machine (as distinct from a stack or register machine) and has a fine grained 
security model that facilitates microkernels without performance penalties. 

This talk will give a high-level introduction to the Mill programming model, with an opportunity for the audience to ask more detailed 
questions in areas of interest.

Tuesday, March 25, 2014 Wednesday, March 12, 2014

Russia’s Salami Tactics in Crimea

Well worth a re-watch all the way through :)

Snowden was right about encryption - so what can programmers do about it?

Right now, the NSA - and China, France, Britain, Russia and doubtless all others - hoover up and store every byte.  And they go fishing.

We need to move back to a world where they have to break into your computer - something they’ll only do if they target you personally, not generally - to spy on you.

And we can do that by encrypting everything.  Everything.

Encrypted data cannot be compressed and is therefore much harder to store.  And if they do invest in storing it anyway, forward privacy can hopefully keep much of it private in the future too.

How to encrypt everything?  Normal websites won’t adopt TLS unless forced to; browsers should show very nasty banners on HTTP connections, perhaps?  Big brands won’t want that floating over them.

Browsers should only use encrypted comms to do DNS lookup too.  So much is in the hands of the browsers.

CDNs should rewrite everything to be TLS.

Also, the *ahem* porn industry ought to adopt TLS outright.  They don’t want their customers scared away, right?

BitTorrent has traditionally used encryption to prevent ISPs from traffic shaping.  But BitTorrent encryption is obfuscation at best, and the ciphers picked were picked to minimise CPU.  These days, we have more CPU.  BitTorrent needs strong encryption.

How else can big swathes of the internet be encrypted quickly?

Wednesday, March 5, 2014

Table-based Template Translation in C++

This is a great technique I devised for simplifying the optimization of translation functions.  Its broadly applicable to performance-critical code beyond software graphics.  I’d love to know if there’s a proper name for this pattern, and if anyone else has ever used it and for what?

At UIQ (a Symbian smartphone UI maker) we needed really fast bitmap blitting performance in the Symbian software graphics library and we just weren’t getting it.

If two bitmaps are the same format, you can just memcpy (or blend or whatever) pixels from one to the other.

If two bitmaps are different formats, you have to translate the source bitmap’s pixels to the destination bitmap’s format.

However, the Symbian libraries themselves were shooting us in the foot.  There were some special-cased blits for same-format source and destinations, and a hand-coded special-case for 16-bit colour with a separate 8-bit alpha mask bitmap into a 24-bit destination with 32-bit alignment, and that was it.

All other conversions went via two virtual method calls… one to convert from source to a 32-bit RGBA universal internal format, and the other to convert to destination format.

Who would use virtual inheritance per-pixel for critical-path colour conversion on a constrained device?  I know their name ;)

Read More

Monday, February 24, 2014

Flame Graphs!

A long time ago now I made a novel little sampling profiler for Python:

Well, I was just looking through the excellent slides about Linux and Solaris performance, and stumbled across Flame Graphs

There are fundamental differences, particularly on the x axis, but still.. :)

Monday, February 17, 2014

obiwan type-checker for Python 1.0.1 released!

Obiwan actually has a very small - but very active - community :)

So I’ve put it on pypi.  Its my first Python package but it works.  Here, perhaps, it might be more accessible to more people.

You can use lambdas as checkers e.g.:

template = {
   ...
   'month': lambda x: x in ["jan","feb","mar",...],
   ...
}

You can specify options for dictionaries such as strict keys (extra unspecified keys not allowed) and subtype.

Subtype is cool - you can specify that a dictionary template should inherit the specification of any number of parent templates!

You can also specify that a duck inherits its attributes from any number of parent ducks too.