ReadOnly

I’ve been working on another project that I haven’t yet written about: Randomized Image Matching. At a high-level, this project uses a greedy algorithm with simulated annealing to reproduce an image using overlapping semi-transparent polygons.

In English, that means that the program will randomly lay out semi-transparent triangles or squares and then randomly move them around to try to get the resulting image to look as much like the selected image as possible. The way to understand it is to watch it in action:

From left to right:

1. Last: the iteration the program is trying out right now.
2. Best: the closest match so far.
3. Error: how far away is best match is from the original? White pixels are farther away.
4. Original: the image that we’re trying to match.

As the program runs, the Last image will change rapidly as the program tries out many slightly different variations (in the screenshot, it was averaging about 86 iterations per second). When it finds a version that has less error (meaning that it is closer to the original), that version will become the current best image.

This project is inspired by Roger Alsing’s Evolisa. When I first saw Roger Alsing’s version, I thought it was quite an interesting idea and definitely something that would be fun to work on and optimize. I, of course, figured that I could create a version that iterates and converges faster. I also thought it would be a good project to try running in parallel across multiple processors and multiple machines.

Implementations

I’ve developed two different implementations: one in OCaml and C that runs on *NIX (but could probably be ported to Windows using cygwin and OCaml for Windows) and another version using F#/C# that runs on Windows (but could probably use Mono).

OCaml/C

The first version one uses a combination of OCaml and C. The high-level logic such as generating permutations and displaying the preview is all in OCaml, which is well-suited for that sort of task. Lower-level logic is delegated to C. The main branch delegates the actual image processing (drawing triangles, calculating error, etc.) to ImageMagick, a C library with a convenient OCaml bindings. I’m working on a new branch with my own implementations of image processing and error calculations. That will hopefully be faster and will definitely be more fun.

The biggest limitation with this version is the lack of real multi-threading in OCaml. If I want to use all four cores in my machine, I need to run multiple processes. In response to that, I started work on a simple distributed OCaml map/reduce framework. It sounds fancy, but it’s pretty simple. It uses an RPC library to create a simple networking interface that clients use to connect to a central server to retrieve work items, process the item, then upload the results back to the server. My goal is to include git-based distribution with the framework so that clients can automatically update, rebuild, and reconnect after someone pushes an update.

F#/C#

This version uses a combination of F# and C#, with most of the logic and display in F# and the parts that deal with pointers in C# using unsafe. This is the first real F# program that I’ve written, so it was a good learning experience. I know the .NET APIs very well so I was able to focus just on the language.

The program shows a real-time display of the image as it evolves. This helps really understand what’s happening behind the scenes and looks very cool. The preview also gave me a chance to try out OpenTK (which I’m quite happy with) and to dust off my OpenGL skills.

This version uses rectangles rather than triangles to make the drawing code simpler. I don’t think it will affect the speed of convergence. I’ve limited it to grayscale for simplicity and performance. Permutations are generated by randomly moving edges of existing polygons or changing their color. After a certain number of iterations, a new rectangle is added even if it decreases fitness (this is almost simulated annealing).

What’s Next?

• Optimizations to improve the speed of iteration
  • Evaluate new image drawing methods
    • Draw on GPU using OpenGL, then fetch rendered image back to main memory
    • Draw rectangles to bitmap in memory, then compare each pixel against original. This might be faster for larger numbers of squares. An object pool will prevent rapidly churning memory.
  • Faster color blending during drawing
    • Precomputed alpha
    • C version of blend function to use SSE or MMX
• Try to to profile the program to identify slowdowns.
• Distributed version that runs on multiple computers at once.
• Enhancements to the display:
  • Add a chart showing fitness over time and the rate of convergence
• Tweak heuristics for faster convergence
  • Change annealing to move rectangles in addition to slowly adding them.
  • Change the rate of rectangle addition and vary it by the number of total iterations. I’m not sure yet if it should get faster or slower over time, but I think it should start out much faster than it does now.
• Enable color
• UI to select the target image and maybe control some of the constants (annealing rate etc.)

A few months ago, stared noticing how consistently slow my blog was. More than 3 seconds per page load is just terrible. That’s slow enough that some people would think the site just isn’t working and would navigate elsewhere. Being an engineer, I decided to see what I could do to improve the load times without paying a ton for fancy hosting. This a list of things that I used to improve this blog’s performance.

Use tools to find bottlenecks

• Chrome Developer Tools: Network Panel
• Firebug
• YSlow

These tools were invaluable throughout the process. Very often I need to check something like the load times for a resource or make sure that the page was using the CDN correctly. The network graph also allows you to easily see the slow resources. For example, I was able to see exactly how much of the time was spent just my blog’s index.html file.

YSlow was quite helpful. It pointed me in the direction of many of the items on this list such as combining/minifying CSS and using gzip.

Caching blog plugins

I originally used WordPress for powering this blog. It’s just packed with features and quite easy to use, but it renders each page dynamically in PHP, which isn’t fast on low-cost hosting. When I first profiled the page, the majority of the page load time was spent waiting for WordPress to render pages, before it even started sending back any content.

I only found one caching plugin that worked well with my hosting provider since they impose limitations on PHP for security that break most caching plugins: Quick Cache. I found that it reduced the html index load time from about 3 seconds to 1.5 seconds (very rough numbers). I didn’t notice any downside and never had issues with cache invalidation. More aggressive caching plugins such as WP Super Cache will even generate static HTML which would probably speed it up even more.

Switch hosting provider

I switched from GoDaddy to NearlyFreeSpeech. Both are low-cost shared hosting providers. The switch seemed to help, but I forgot to benchmark before moving so I can’t really say how much.

GoDaddy

• Truly horrible management interfaces
• Mediocre performance
• Acceptable prices at about $5/month

NearlyFreeSpeech

• Good management interfaces for advanced users ex: phpmyadmin for MySQL and SSH and SFTP access
• Mediocre performance
• Very low cost at about $0.04/day for a small site.
• PHP safe_mode is always on
• No mod_gzip in Apache

Switch blogging software

I switched from WordPress to MovableType. MovableType serves up static HTML pages that are only regenerated when publishing a new entry. The removes the overhead of loading PHP and executing a script and making database queries for every page request. This was probably the single most dramatic performance increase, but also the one the took the longest time, even with MovableType’s import feature.

Serve gzip compressed files.

Gzip is an easy way to reduce transfer size and therefor time. mod_gzip makes this brain-dead easy, but my hosting provider doesn’t support it. The solution I found is to manually run a script to compress every file from file.ext to file.ext.gz. Combine that with an Apache rewrite rule and you’ll automatically serve compressed files for browsers that support it. The annoying part is that I have to manually rerun the script after changing any file.

Combine/minify CSS and JavaScript

I used Closure for JavaScript and YUI Compressor for CSS. They both reduced the sizes dramatically. I don’t think the minification helps too much for desktop browsers with broadband connections, but it’s quite easy to do and probably helps more for mobile browsers. Combining the scripts helps more, I think, since it reduces the number of round-trips from the browser to the server even though some of those requests can be made in parallel.

Use a content delivery network

I’ve always thought of this as an advanced technique only used for very popular websites, but then I found out that Amazon CloudFront is actually extremely inexpensive if you only need small amounts of traffic since Amazon only bills by usage. I’m using it for small static content such as images, CSS and JS so the overall size of the transfers is tiny. The speed up is tremendous— those files pretty much disappear from the load times graph. It’s definitely worth the pennies per day that it costs.

Setting up CloudFront was easier that I expected. Amazon gives you a randomized domain name that acts like a fast proxy for your real domain. The only thing you have to do is change the links in your HTML from http://www.example.com/styles/style.css to http://E123456.cloudfront.net/styles/style.css. Gzip compression is transparently passed-through. There are a couple of ways to do invalidation, but I’ve opted for the easiest— just change the URL when changing the content.

If you’ve found a file opened with CreateFile() for writing only to be slow over a network, try instead opening for reading and writing. I ran up against this today and found it about 100 times faste.

From MSDN:

When an application creates a file across a network, it is better to use GENERIC_READ | GENERIC_WRITE for dwDesiredAccess than to use GENERIC_WRITE alone. The resulting code is faster, because the redirector can use the cache manager and send fewer SMBs with more data. This combination also avoids an issue where writing to a file across a network can occasionally return ERROR_ACCESS_DENIED.

I’ve updated StudyPlannr with even more cool AJAX-style interactivity. Now everything on the edit schedule page can be edited without requiring a page refresh.

Overall, I found this to not be as difficult as I had thought it would but. The main issue was translating the Jinja server-side python templates to client-side Javascript templates. I spent a long searching around and I ended up using ICanHaz.js. I like the automatic HTML escaping by default and that it allows me to include the templates directly in the HTML. ICanHas doesn’t have the same impressive feature list as Jinja, but that’s OK. I don’t like the syntax very much. I don’t look forward to having to maintain the funky characters- I have to look them up in the manual constantly. It feels like they’re trying to save a few characters for no reason and that feels like Perl, which isn’t a good thing.

Example Jinja:

{% for item in items %}
    {% if not item.is_break %}
        <p>text here {{item.variable}}</p>
    {% endif %}
{% endfor %}

Example ICanHaz:

{{#items}}
    {{^is_break}}
        <p>text here {{variable}}</p>
    {{/is_break}}
{{/items}}

This new version uses IcedCoffeeScript almost exclusively for the client-side stuff. I’m really digging it. I like the syntax much better than JavaScript and the await stuff is just icing on the cake. I think I’d probably still prefer some language that didn’t just compile to JavaScript (like Python or Ruby) but interoperability with amazing JavaScript libraries like JQuery would definitely be required.

For example, here’s the code that adds a new subject to a schedule:

$('#add-subject-form').submit (event) ->
    event.preventDefault()
    url = $('#add-subject-form').attr('action')
    post_data = { name: $('#add-item-name-textbox').val() }
    await $.post url, post_data, defer response_data, status, xhr
    FullRerender response_data
    $('#add-item-name-textbox').val(null)

I’ve updated StudyPlannr with some new slickness. Now, most schedule editing operations don’t require page reloads since they use cool AJAX stuff. Behind the scenes, I’ve updated to use new the python 2.7 GAE runtime and the high-replication datastore.

One of the big announcements this week is Google Dart, Google’s new language that’s aimed at replacing or at least supplementing JavaScript. I haven’t tried it out yet (I’m waiting until it is at least implemented in Chrome), but I’m so far pretty optimistic about it.

Validation of user input is a pretty essential component of almost any application. Ideally, it is a quick and unobtrusive way to give the user feedback and help guide them through the application.

If you’ve spent much time working with WPF or Silverlight, you’ve probably run into the MVVM (Model-View-ViewModel) pattern before. It’s probably the most popular pattern for designing WPF/Silverlight applications. In this series of posts, I’m going to go over what I’ve found to be the best way to structure WPF applications. The first post is going to be a broad overview of my take on MVVM and what I’ve found works best. Further posts will dive deeper into each section and start to explain why I’ve made the decisions I have. Any feedback, questions, or comments are of course welcome.

• Added iPad support.
• Added the ability to save the drawings to the photo album to email, print, or just keep them around.
• Improved performance.
• Added a simple About screen.
• Added support for older versions of iOS (iOS 3.0 or later).

Get it here.

CrazyPaint is now available in the App Store! It’s a very simple painting application that’s a bit inspired by Kid Pix. I’m using it to teach myself iOS development.

Version 1.0 took a while to get approved (submitted it last Sunday) so I’m already on my way to version 1.1 which includes a iPad support. I think the iPad will be much easier to draw on, but I unfortunately don’t have one to test it out so I have to rely on the simulator.