BozoSort

DESCRIPTION: Using only two inverters and an unlimited number of AND and OR gates, create a circuit which accepts three inputs, and outputs the negation of each input. The AND and OR gates can have any number of inputs.

The instructions for updating your Go build on the official website will leave you with some errors if you follow them verbatim. It turns out, the permissions on some of the files when you run ./all.bash will leave you hanging with errors, so it’s necessary to run as root, but not quite, since you still need to be using an account with $GOROOT, $GOBIN, etc. all correctly set.

These instructions will get you updated without trouble:

$ cd $GOROOT
$ hg pull -u
$ cd src
$ sudo -E ./all.bash


Koinonia Texas New Student Welcome Night 2010 (trailer)

2010 Koinonia Austin NSWN Trailer from Gracepoint Berkeley on Vimeo.

Koinonia Texas is a Christian fellowship at the University of Texas at Austin, where students and non students alike are welcome to join on Friday Nights and Sudnay afternoons for times of games and fellowship.

Our 2010 New Student Welcome Night is going to be on August 25th, at 6:00 PM (hopefully in Jester Auditorium). Lots more information, and more videos at: nswn.org .

POP QUIZ
In Java, which of the following two code snippets will run faster?

1
2
3

for(int i=0; i < size; i++)
for(int j=0; j < size; j++)
     grid[i][j] = num++;

1
2
3

for(int j=0; j < size; j++)
for(int i=0; i < size; i++)
     grid[i][j] = num++;

I was having a conversation (okay, an argument) with a friend yesterday over the optimization capabilities of the Java compiler, and one of the aspects of optimization which I was totally convinced that javac was capable of is determining how data should be stored in memory when using multidimensional arrays (or matrices, if you prefer). Having been indoctrinated with Java ideals since my sophomore year of high school, I thought for sure it did not matter whether a Java programmer accessed data from a matrix in column major or row major order. For years and years I’ve been told not to worry about such things because I was constantly being told, “the java compiler is smarter than you and can optimize your code better than you can”. So it never occurred to me that perhaps I should pay more attention to my code than just the Big-O running time. It turns out my jaded, almost ?? views of javac were blatantly incorrect, and here is a quick benchmark test which demos the importance of accessing data in row major as opposed to column major order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class Benchies
{
	public static void main(String[] abc)
	{
		System.out.printf("n\t\tRowMaj\t\tColMaj  (msecs)\n");
		for(int k=1; k<10002; k+=500)
			majorOrderTest(k);
 
	}
 
	public static void majorOrderTest(int n)
	{
		StopWatch sw = new StopWatch();
		int size = n;
		int[][] grid = new int[size][size];
 
		sw.start();
		int num = 0;
		for(int i=0; i < size; i++)
			for(int j=0; j < size; j++)
				grid[i][j] = num++;
		sw.stop();
		System.out.printf("%d\t\t%d\t\t", n, sw.time());
 
		sw.start();
		num = 0;
		for(int j=0; j < size; j++)
			for(int i=0; i < size; i++)
				grid[i][j] = num++;
		sw.stop();
		System.out.printf("%d\n", sw.time());
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class StopWatch
{
	private long startTime;
	private long stopTime;
 
	public void start()
	{	
		startTime = System.currentTimeMillis();
	}
 
	public void stop()
	{
		stopTime = System.currentTimeMillis();
	}
 
	public long time()
	{
		return stopTime - startTime;
	}
}

Even on my blazing 2.83 GHz machine (with 12 MB of L2 cache) the results are pretty dramatic.

sqrt(n)		RowMaj		ColMaj  (msecs)
1		0		0
501		6		6
1001		5		6
1501		4		18
2001		7		39
2501		10		62
3001		16		98
3501		19		132
4001		25		184
4501		31		226
5001		39		301
5501		48		363
6001		58		453
6501		65		528
7001		74		665
7501		83		738
8001		98		867
8501		113		993
9001		123		1126
9501		137		1263
10001		151		1462

So there you have it. It would be really nice to say, “well of course Java doesn’t optimize out stupidity”, but really, that’s not the problem here. The problem is that it hasn’t been until now, my Junior year of college, that I was formally introduced to the importance of how data is read from memory into the different levels of cache.

I, like most other people, enjoy listening to music while I’m working, surfing the internet, or surfing the internet while pretending to be working, so it should come as no surprise that I use services like Pandora, Last.fm, and Digitally Imported for my free music needs. However, none of these services allow users to listen to specific songs when they want to. Instead, they allow choices between types of genres, and even let you rate songs good or bad which can affect how often you hear them. The ability to rate songs and govern their frequency is nice, but what would be even nicer is the ability to select a certain song I want to listen to and be able to play it. Even better than that would be the ability to create an entire playlist of songs that I want to listen to, all without having to actually pay for or illegally download those songs. And that’s the role that YouTube has in my life. But up until just recently, YouTube has had a series of miserable mechanisms for organizing playlists of videos. There has been playlist support for a while, but making makeshift playlists on the go was not supported. Then the “queue” feature was added, which was sort of nice, where one could check certain videos, and then have them added to a queue, and then you could start playing the queue. However, the queue did not support adding music on the go, or listening/watching videos out of order.

Now however, things are different.

That ribbon on the bottom is drag & drop capable, meaning users can now add videos on the fly, remove videos at will, and rearrange playlist order while the playlist is in play mode. That’s a pretty huge leap forward, and one that was badly needed. So thanks, YouTube. Now you just need to work on getting enough bandwidth so that I don’t keep getting those annoying “video buffering” pauses.

Software is never “finished”, everybody knows that. Updates are pushed, design changes come and go, newer versions are released, all in the interest of the pursuit of a transcendent product. Or better profit margins. Either way, rarely are changes introduced which reduce functionality. Real people (excluding software developers, seemingly) always want more. More meat on subway sandwiches, more channels to watch on T.V., more ways to customize everything we own.

So why then, I ask, does it seem the Nautilus developers wish to reduce their very widely used file manager down to something which resembles a product of the Windows 95 era? The most prominent answer lies of course in the wild goose chase of simplicity in the use of software. Take a look at Macs, for example. They have become popular largely in part due to their simplicity and ease of use. But there in lies the problem with Nautilus. In their quest for “simple”, the developers (and self- proclaimed experts in user interface design, apparently) are mistaking “simple” for fewest buttons on the screen as possible.

Now would be a good time to read this blogpost by Garrett LaSage, which puts forward some of the proposed design changes being complained about here. I’d like to analyze some of the new ideas, and explain why I think they are all bad. Throughout this article, it’s important to realize that I am largely concerned with default settings. Most file managers in one way or another support a common set of features. It’s how those features are presented to users is what makes the difference in usability.

This is the current default layout for Nautilus (at least how it appears by default on Ubuntu 10.04, the most popular Linux distribution according to distrowatch).

There are two important things to notice right away. First, there are obvious buttons across the top toobar which enable the user to execute commands quickly using nothing but a mouse. In fact, I would venture to say that most programs on all platforms follow this basic design. Web browsers, Office suits, Email clients, Image editors, etc. Normal people like to use the mouse. They like to click buttons without sifting through menus. They like not having to type. Now let’s take a look at one of the proposed layout changes.

Now the only button available is a magnifying glass, which I assume is an alternative to hitting the “enter” key after you finish typing in your keywords into the search bar. So no more “up the hierarchy” button. No more list view button. No more refresh button. There isn’t even a file menu up top to go and change the default settings! Most annoyingly however, and this is my second observation from the previous paragraph, is the complete lack of a “Places” side bar. So now how is one supposed to move around between usb-drives, hard-drives, camera cards, and various other directories which would normally be conveniently listed in a panel? Are we supposed to search our flash drives by typing in UUID numbers or something?

Of course there are other proposed layouts, and none of them have been deemed final, but the general trend of Nautilus is undeniably heading towards: “reduce clutter by hiding or eliminating features.” Some have commented that the new Nautilus is looking quite a bit like Apples “Finder”, which I disagree. Here is Apples file manager:

And here is Explorer from Windows 3.1:

If I didn’t know any better, I would say the new Nautilus was trying to be a Windows 3.1 clone, but with more than 16 colors. I have no leverage in the Nautilus design process whatsoever, but I do wish for a simple, yet powerful window manager. The fact that one of the objectives of the new Nautilius is to ” remove ‘filesystem’ in the UI ” just baffles me. The whole point of the file manager is to manage my file system!! How the hell else am I going to move files around? The command line? If the objective of Nautilus is to make using my computer simple, just what kind of craptastic job is it doing if I have to resort all the way down to the command line?

Also in the queue for removal is, “Everything in the sidebar other than Places: including Tree, History, Emblems and Notes.” Yep, as I addressed before, that extremely convenient window pane on the left with links to your removable media, commonly used folders, folders on other computers, etc. is being removed. Wiped out. Gone. Bye-bye. Now you get to use the revolutionary new search tool, where you can resort to your using keyboard and typing in things you remember about the directories that you want to visit. Because that’s so much more advanced than just navigating with the command line. **cough** find / -name keywords **cough**.

The comments on LeSarge’s blog are of mixed reaction. Some people seem to love the idea of achieving simplicity through reduced functionality, some are in favor so long as features X and Y are not removed, while others (like me) think the idea is the product of poor judgment on the real world target audiance of Gnome/ Nautilus. Let’s face it. The target audience of this file manager (if you can even call it that anymore) is undeniably skewed towards power users. Power users who could, if need be, default to utilizing the command line, but would rather use a modern and effective graphical user interface.

Intel has announced their annual Threading Challenge for the year 2010. This time, there are two levels: Apprentice and Master. Since this is my first time participating, I’ll be participating in the Apprentice category. The first problem set is open from May 31st to June 21st, so there’s still some time left to join in.

I currently have the first part of the problem solved using an algorithm that runs in O(n), and can do calculations on extremely large datasets in a fraction of a second. The problem is with file IO. You see, Intel is including file IO in the total execution time of each program, which means this contest actually has very little to do with threading, and very much to do with choosing a language that can read from a file very very quickly. Unfortunately for me, it seems that Java was not designed with high performance file IO in mind.

The purpose of the contest is to promote the Intel Threading Building Blocks API, but I have a feeling the winning algorithm will not need to be multi-threaded at all, but rather will be able to read input data from a file very quickly.

This is from episode 3×12, where Ted picks up the yellow umbrella after the St. Patrick’s day party. I’m betting that the women in the picture ends up being Ted’s wife. There’s no name to pick up on, but her voice is very distinct. The following episode shows Stella for the first time, Ted’s almost- wife who leaves him on their wedding day.

I use an MSI Wind Nettop 100 as a server, which sits in a dark corner of my bedroom underneath a router. It’s powered by an Intel Atom 330N which is perfect for a low noise, yet capable server, running things like this wordpress blog and my personal bugtracker. However, quiet just isn’t quiet enough. I wanted something silent, so I set out to reduce the noise even more. The stock machine uses a passive cooler for the CPU, and a small fan at the back which pulls air in from the opposite side of the case. Under no load, the machine is near silent, but when the load goes up, the speed of the fan increases significantly, along with the noise it produces. So my solution was to reduce the fan noise by eliminating the throttling feature on the case fan in addition to using a small, quiet, dedicated CPU fan.

I picked this up at fry’s for a ripoff.. but it is exactly what I wanted. A tiny, virtually silent fan that has just enough cfm to push air through the fins of a passive CPU heatsink. Sadly it’s not perfectly silent still when under full load, but a few additional resistors might be able to help that.

There’s an immediate problem upon inspection of the heatsink. The hard drive caddy places the end of the hard drive directly where we want the fan to go. I can’t help but wonder how bad of a design this is in regards to cooling. All the heat from the cpu is rising into the hard drive, quite possibly shortening its lifespan.

That’s an 80 gig Western Digital Caviar Blue, which I picked up for $30 on Newegg. On the left you can see the single stick of SO-DIMM (laptop) RAM. At 2Gb it is very much overkill for a headless server that spends 99% of its life doing nothing.

One thing I really like about this computer is the ability to completely remove the hard drive caddy, which makes working on individual components much easier. Fortunately, I have no use for the 5.25″ drive bay, so I bought the appropriate mounting hardware to mount the hdd in that slot, which opens up the vertical space above the CPU heatsink. If I ever add another harddrive, I will purchase a 2.5″ laptop drive and use mounting brackets to mount it in the 3.5″ bay, which should allow the vertical space above the CPU to remain free. Of course, with only ~4% of 80 Gb used so far, that day might be a long, long way away.

In the above right picture you can see the SanDisk 2Gb Compact Flash card which is plugged directly into the motherboard. I use this as my backup drive. The important files and databases are tar’ed, zipped and moved to the CF card every day at midnight. I once considered installing the OS itself to the card, but that would actually be a bad idea, since these cards have a (comparatively) very limited read/write life. The CPU Fan is simply glued to the heatsink using hotglue. Sound like a bad idea? Possibly, but it hasn’t melted off so far, so I’ve been happy with it. While the case was open, I decided to eliminate the hardrive activity and power indicator LEDs. They aren’t particularly informative, and they light up my bedroom at night.

The two wires NOT to cut are the WHITE and BLACK wires leading to where my thumb is gripping the plastic. Those wires go to the power switch. The colored wires only power LED lights. They can be cut without fear of damaging something important.. or making things explode.

Now that the case fan is no longer throttled by the motherboard, it would run full speed all the time, which is extremely counter productive to the point of this mod. To remedy this, I added a resistor in series with the fan so as to limit the voltage going across the motor. I chose a 110k ohm resistor, calculated by closing my eyes, walking up to the wall of resistors at Fry’s, and picking the first one I grabbed. In retrospect my choice isn’t too far from optimal, though I think I’ll add another pair of resistors in parallel in series with the resistor that’s currently there. That’ll reduce the noise just a bit more while still providing adequate airflow.

It isn’t until looking at this picture that I realize how dangerous it is to leave that resistor bare. The case itself is grounded, so if that positive lead touches any part of the case, it will cause a short in the motherboard, which would likely (according to Murphy’s law) kill all of the electronics that are connected to it. I should probably go fix that.

Finishing up: The hard drive caddy goes back in place, the power adapter is plugged in, and a sanity check is performed before putting the case back together. Luckily everything still worked. All there is to worry about now is the hot-glue which is holding the fan in place melting, and also that bare resistor touching the case. But that’s a fix for a rainy day, and it isn’t raining today.

My server and the Linksys WRT54G router that sits on top of it are in a perpetual uptime contest. It’s like a staring contest, but for nerds. And machines. The router runs the Tomato firmware while the server runs Turnkey Linux, which is a convenience- oriented derivative of Ubuntu Server 8.04LTS.

I like Ubuntu. I like Chrome. I like being able to middle click my mouse wheel to scroll webpages. Unfortunately, Google decided that such a combination of nice things was just too great for the world. Fortuantely, there’s an extension to remedy this called AutoScroll. It is available in this hidden little corner of the internet: AutoScroll for Google Chrome – Works on Linux!