underdevelopment

So a little while back ibuildings had this fun contest to build a path finding program that would solve a traveling salesman like problem. The constraints where pretty simple, you got a CSV file with latitude/longitude locations. You started at a certain location and you should end at a certain location. The application should then find the shortest route that touched all locations.

Now I’ll be the first to say that PHP is really not the language for that. A few years back I wrote a pathfinding tool for use with a game called EVE online in which I calculated certain trade routes based on data you could export from the game. After seeing PHP’s performance I switched to Python and more or less sliced the processing time in half if not more. Mainly because Python has specific array like types and PHP just has generic array’s, which with large data sets matters a lot. Perhaps also because my pathfinding-foo was still rather weak

However, back to now and the ibuildings challenge. The challenge would be rated on 3 criteria. Speed, lines of code and code complexity. Personally I could care less about the latter two and focused purely on speed. In the weeks that followed I had a great time comparing execution times with Remi and Andries. I think this was also key to keep diving into it and tweaking it until it was as fast as I could get it.

Sadly, my submission actually had a off-by-one bug in it which more or less instantly disqualified my entry. Yes, bit of a bummer, but such is life.

Now I had already decided to publish my code after the contest, however sadly I never really found the time to type this up. So a bit late but here is the code for my solution for the ibuildings elephpant challenge.

Below is the submitted code, and a link to download the code and original test data file so you can try it out for yourself.

download the code – Just unpack and run via php contest.php elephpant_landmarks.csv

-edit-

Ok scratch the code, I’m having some trouble with getting it to play nice. Just download the tar.gz and view the code in your favorite editor.

admin PHP, software development code, performance, spielerij, techniques, traveling salesman

I recently switched hosting for my websites, and with that I of course made all those little changes again to fine tune my performance. This seemed like nice enough info to share with you. Most of the points are already widely known, but it never hurts to have them listed again.

First up in the list is gzip compression of text documents. It saves both time and preconscious bandwidth. For this you will need to enable a apache module that’s probably already available to you. mod_deflate

Depending on your distro/installation you can either enable this by adding it to your apache config, or by using the following command.

a2enmod deflate

After having enabled this module you should check its configuration. The configuration should either be in your main apache2 conf file, or in a file that gets included. It should look something like this.

AddOutputFilterByType DEFLATE text/html text/plain text/xml

Now the default is nice, but there are more files that are only text like CSS files and javascript files. So we edit that line to read the following.

AddOutputFilterByType DEFLATE text/html text/plain text/xml text/css application/javascript

Now all files with those mime types will be compressed, saving you precious bandwidth and transfer time.

Another tweak I made is the enabling of mod_expires. Add it just like you added mod_deflate. After adding this mod you should hunt around for default configuration options that will probably include “ExpiresDefault”. My ubuntu based installation didn’t have this, so I added it myself. You can just add this in the server configuration file if you want. Personally I created a /etc/apache2/conf.d/expires file, because that’s how my setup works.

ExpiresActive on
ExpiresDefault "now plus 1 months"
ExpiresByType text/html "now plus 1 days"

You will have to experiment with this to find the values that you are comfortable with, I prefer to set them pretty liberal. What this means is that the contents of the requested file will not be transferred to the client before that time has passed. Which again means less bandwidth and more speed.

In my case, all static resources like CSS, javascript and images will be cached for a month, and the document itself will be cached for a day.

There are many more performance tweaks to be made, but for now I’ll leave it at this.

admin apache2 apache2, mod_deflate, mod_expires, performance