To pickle or not to pickle

My latest Core Python inspired post is about using repr() and pickle in Python. Oh and a few bits about JSON as well.

It's Called Script-A-Cu-Lus

Not script-a-licious! I wrote an article on script.acu.lous and it is now online at developerWorks.

Eclipse Day 2008

Congratulations to the Eclipse Foundation for releasing Ganymede today. As part of the festivities, Eclipse and Google collaborated on Eclipse Day yesterday. I was fortunate enough to be asked to speak at the event, and it was a great experience. I spoke about how we use Eclipse at eBay. The response was very enthusiastic with lots of folks amazed at how many tools we had built for our developers and how we had standardized tools across such a large development organization. I totally agree that our tools developers are amazing. For me, I don't know how we could survive without having all of the tools we have built! Here are the slides from my presentation, courtesy of SlideShare:

| View | Upload your own

I wanted to really thank Ian Skerrett from Eclipse for organizing everything. The folks at Google were excellent hosts, so I must also thank Robert Konigsberg from Google.

ACM Ajax Seminar

Today I taught a seminar on Ajax to the Bay Area chapter of the ACM. It was a lot of fun. The audience was great, asking lots and lots of excellent questions. The level of enthusiasm was very rewarding. I promised the folks there that I would provide download links. So here they are:

The Slides (OpenOffice format)
The Slides (One big PDF)
All Demo Code

The demo code also includes a Scriptaculous demo that I did not have time for. It uses Ruby on Rails. The Prototype demo uses PHP, and the other ones all use Java. A couple of the demos uses a database, and for those I used MySQL.

Finally I wanted to also thank Sang Shin and Doug Crockford for allowing me to use their material for the seminar.

Blogging about Books

I mentioned some new books that I am reading. The publisher of those books gave me the opportunity to blog about them while I read them. I thought that would be fun, and would give me extra motivation to read the books thoroughly. I am blogging about them directly on their site InformIT. Here is the RSS feed of my blog over there and here is the first post. It is on the Core Python book that I am reading.

Scala vs. Java Performance

Last week I wrote about the 'wallify' problem that was worked on at the BASE meeting. One thing that was mentioned there was that it seemed like a Scala implementation would not have performance that was as good as in Java. I decided to give this a test. I used the Scala code I wrote last week and compared it to Java code that used essentially the same algorithm.

To test, I created a driver. The driver would vary the numbers in the input list, basically 1..N where N was varied. It would then measure the time it took to wallify the list 100 times. The JVM was the 1.5 JVM for OSX with the -server flag set. I was also giving it 1GB of memory (more on that later.) Here is what it looked like in Java:

And in Scala:

Very similar. There was no noticeable performance loss in Scala. Of course there is an obvious problem here. This algorithm should have been linear with respect to the size of the list, N. This is clearly not linear! I took the logarithms of both the size and the time, and found a correlation of about 0.996. This algorithm is actually quadratic.

I thought that maybe my algorithm just sucked. I tried a couple of other Scala ones. One provided by Jorge Ortiz and one created by the group led by Bill Venners. The both had the exact same performance characteristics as my algorithm, i.e. they were quadratic as well.

The only thing I could think of was garbage collection. I put on gc:verbose and watched a lot of garbage being collected. I upped the heap to 1 GB, but it had no effect. So I am not sure if GC is really the culprit or not.

Update: James Iry had a great insight. Java's BigInteger computation is linear once things get big. To keep them small, you can use all 1's. Here is what the performance looked like then, just for my original Scala code.

Ok, that's not quadratic anymore. I wasn't sure if it was linear (I was paranoid about compiler tricks given the list of 1's that was being multiplied) either, so I actually extended the test with more data points. With a few more data points, I got a nice correlation of 0.993 for a linear fit. This confirms that the algorithm itself is linear for small numbers, but is quadratic for larger numbers where high performance integer math becomes significant.

New Books!

Wife: "you got a real heavy book in today by fedex."
Me : "I need to leave work early"

Yep, new books arrived today. Here is the new reading list:

Java Concurrency in Practice by Brian Goetz. I know, I know, I should have already read this. The S3 bulk uploader really convinced me of this.

Refactoring by Martin Fowler. I know, I know, I should have read this many years ago...

core Python. Good to have while hacking on GAE.

Don't Make Me Think by Steve Krug. Wouldn't it be great if designers understood programmers? I can't help with that, but maybe I can understand design? Probably not, but worth a try.

BASE Meeting

Last night I attended my first BASE (Bay Area Scala Enthusiasts) meeting. Organizer Dick Wall had a nice problem to solve for the attendees. The problem was to take a list of integers, and replace each element in the list with the product of all the other elements in the list. For example, if your input was (2,4,6,8) the output should be (4*6*8, 2*6*8, 2*4*8, 2*4*6) = (192, 96, 64, 48). If you want to solve the problem yourself, stop reading and come back when you are ready to read about the solutions.

There is an "obvious" brute force solution, which would be to implement the algorithm exactly as the problem is stated. This is an O(N^2) solution, not so good. You can do better by simply taking a product of all of the elements of the original list, and then replacing each member of the list with the product divided by the element. So for the example above, the product = 2*4*6*8 = 384, and thus the output should be (384/2, 384/4 , 384/6, 384/8). This is O(N) solution, and that is much better. This is the best you can do in terms of speed and space, as you only keep around one extra integer in memory (the product.) However, it doesn't always work.

The problem is when there is a zero in the list. Then the above algorithm will lead to division by zero errors. Dick pointed this out, and pointed out that there are really three casses. If there is exactly one zero, then every element in the return list will be zero, except for the one at the same index as the lone zero from the input list. If there are two or more zeroes, then every element in the return list will be zero. With that in mind, here was my solution:

def wallify(list:List[Int]):List[BigInt] ={
  val one = BigInt.int2bigInt(1)
  val noZeroes = list.filter(_ != 0)
  if (noZeroes.length == list.length){
    val prod = list.foldLeft(one){(p,e) => p*BigInt.int2bigInt(e)}
    list.map(prod/_)
  } else if (list.length - noZeroes.length == 1){
      list.map((el) => 
        if (el == 0) 
          noZeroes.foldLeft(one){(p,e) => p*BigInt.int2bigInt(e)} 
        else 
            0
      )
  } else {
    list.map((el) => 0)
  }
}

I had to leave early, and didn't finish my code until today. Here is the code that the group, led by Bill Venners:

def wallify(input: List[Int]): List[Long] = {
  def boringCalcProduct(longInput: List[Long]): Long = {
    var product = 1L
    for (ele <- longInput) {
      product *= ele
    }
    product
  }

  def calcProduct(input: List[Long]): Long =
    // input.foldLeft(1L)(_ * _)
    (1L /: input)(_ * _)
  
  val zeroCount = input.filter(_ == 0).size
  val longInput: List[Long] = input.map(ele => ele.toLong)
  zeroCount match {
    case 0 =>
      val product = calcProduct(longInput)
      longInput.map(product / _)
    case 1 =>
      val noZero = longInput.filter(_ != 0)
      val product = calcProduct(noZero)
      longInput.map(ele => if (ele == 0) product else 0)
    case _ =>
      input.map(ele => 0L)
  }
}

iPhone 3G

It was fun to watch the WWDC keynote today on MacRumors. It was even more fun to watch things on summize as Twitter held up admirably during the keynote. I was impressed with the new iPhone. I really like the white version, as it seems like a nod to the original iPod to me (an owner of the original.) It made me think, should I get rid of my Blackberry 8830 and switch to the iPhone?

iPhone 3G

• The screen on the iPhone is awesome. The Blackberry's is nice, but it's not really close.
• Much better for listening to music. Blackberry is functional for this, but hardly elegant.
• Web browsing is much better on the iPhone, especiall now that it has a 3G network. The Blackberry browser is good, and Opera works great, but mobile Safari is very nice.
• The iPhone has a camera. I miss having a camera, even if the iPhone's is crummy (as are most phone cameras.)
• The iPhone has wi-fi. I often use my Blackberry's network access in places that have free wi-fi.

Blackberry 8830

• I have tried the iPhone keyboard, and greatly prefer my Blackberry's keyboard. This one is not even close.
• The GMail app for the Blackberry is excellent. On the iPhone you can use the GMail as IMAP, but that is not as good, not even close.
  
• Of course the Blackberry receives my email and calendar from my work's Exchange servers. This is the main appeal of Blackberry for many. If I had an iPhone, I think I would have to run a client from my desktop computer at work. Co-workers have told me that this is a problem because our desktop computers run the 64-bit version of Windows 2003, and a lot of Apple's software has issues with this.
• Google Maps is also very nice on the Blackberry, even if Verizon screws us over and doesn't let it access the device's GPS. Then again I have used GPS on phones (both mine and my wife's) and it is useful, but definitely not a replacement car GPS. Anyways, Google Maps on the Blackberry seems a lot better than accessing the web application on the iPhone.

Hmm, it doesn't seem like a slam dunk either way. It seems like the calendar/email push advantage may be negated, depending on the OS issues. If Google made iPhone apps, especially for GMail, it would almost clinch it for me. I've used GMail as IMAP provider with Mail.app and did not like it very much. Blackberry GMail is a killer app for me. Given Google's investment in Android, it seems unlikely that they will create a similar app for the iPhone... I think I will stick with my Blackberry.

Sports, sports, and more sports

The Belmont Stakes
I used to be a really big horse racing fan. I was introduced to it while at Caltech, as we were just a few miles from Santa Anita, one of the world's greatest tracks. I had my favorites back then: Lure, the two-time winner of the Breeders' Cup Mile and Bertrando who should have won the 93 Classic if it wasn't for the shocking upset by Arcangues, who was more than 100-1. In 96, I had the trifecta for the Kentucky Derby, a trifecta that paid $10K+ ... but didn't play it because I didn't have the money to cover all the possibilities (needed $120, too much for me to bet.) I was also a big fan of Holy Bull. I never liked Cigar, as Cigar beat Holy Bull in the race that the Bull broke down... Ultimately it was horses breaking down that really made it hard for me to enjoy horse racing. Horses were clearly becoming more brittle, mostly because of inbreeding. Drugs were being used as a band-aid, but it was obviously a bad situation that would only get worse.

Still, I try to watch some of the big races still each year, and of course that includes the Triple Crown races. I had no particular love of Big Brown, but of course it seemed appealing to have a Triple Crown winner. One of the first videos that I ever watched online was a video of Secretariat winning the Belmont and thus the Triple Crown. I get chills just thinking about, it was such an awesome feat. Anyways, it was sad to see Big Brown lose and disturbing to see his jockey pull him up as soon as he realized that Big Brown was not going to win. Something did not sit right about that to me, like he knew the horse was not sound and should not have been racing. Anyways...

NBA Finals
Good guys 2, forces of evil 0. What more is there to say? Amazingly the Lakers are huge favorites to win in Game 3, and I wouldn't be surprised if they were still being favored to win the series. There is always a Los Angeles bias in Las Vegas. After all, Vegas makes the line based on money bet, not based on their opinion or some other kind of 'actual' odds. Casinos play down the middle, take a cut from boths sides and always profit with no risk.

French Open
Nadal vs. Federer renewed... I could not believe how easily Nadal won this time. I am still unconvinced that these guys are really that great, and that their success is not more attributable to poor compettition. Nadal vs. Borg? Nadal is certainly athletically superior, and there is the racquet technology factor. And I still think that many of the big servers of the 90s would give either one of these guys huge problems, though maybe not on clay.

Gears and Flash

Tonight I launched up Firefox 3, and it informed there was an update to Gears ready to install. I went for it, and sure enough Gears was now working with Firefox 3! I didn't find any official announcement about this, but I didn't let that stop me from finishing an idea I had last week: getting Gears and Flash to work together.

This was not too hard. It is just a matter of using ExternalInterface to create a bridge between the two worlds. I wrote a quick POC, using a simple DB table for storing name/value pairs. I think it would be fun to re-implement the flash.data package that is normally only available in AIR apps...

Here is the JavaScript code:

function dbCall(sql, args){

    var db = google.gears.factory.create('beta.database');
    var rs = null;
    try{

        db.open('database-test');
        db.execute('create table if not exists little_table (key varchar(20), value varchar(100))');
        rs = args ? db.execute(sql, args) : db.execute(sql);
        data = [];
        while (rs.isValidRow()){

            row = {};
            for (var i=0;i<rs.fieldCount();i++){

                var name = rs.fieldName(i);
                row[name] = rs.field(i);
            }

            data.push(row);
            rs.next();
        }
        return data;
    } finally {

        rs.close();
    }
}

Here is the ActionScript code:

import flash.external.ExternalInterface;
 

[Bindable]
private var rs:Array = [];
 
private function load():void{

    rs = ExternalInterface.call('dbCall', 'select * from little_table');

}
private function save():void{
    var key:String = keyIn.text;
    var value:String = valueIn.text;
    ExternalInterface.call('dbCall', 'insert into little_table values(?,?)', [key, value]);
    keyIn.text = "";
    valueIn.text = "";
    load();

}
private function clearData():void{
    ExternalInterface.call('dbCall', 'delete from little_table');
    load();

}

And here is the MXML I used to test it out:

<?xml version="1.0" encoding="utf-8"?>

<mx:Application xmlns:mx="http://www.adobe.com/2006/mxml" layout="absolute" initialize="load()">
    <mx:DataGrid x="202" y="59" id="grid" dataProvider="{rs}">

        <mx:columns>
            <mx:DataGridColumn headerText="Key" dataField="key"/>
            <mx:DataGridColumn headerText="Value" dataField="value"/>

        </mx:columns>
    </mx:DataGrid>
    <mx:Label x="10" y="251" text="Key"/>

    <mx:TextInput x="74" y="249" id="keyIn"/>
    <mx:Label x="242" y="251" text="Value"/>

    <mx:TextInput x="285" y="249" id="valueIn"/>
    <mx:Button x="460" y="249" label="Save" click="save()"/>

    <mx:Button x="243" y="298" label="Clear" click="clearData()"/>

</mx:Application>

Good vs. Evil '08

No, this is not about Barack Obama vs. John McCain. This is about something much more benign: basketball. So maybe the Magic did not make it too far in the playoffs. You can't be too surprised by Celtics vs. Lakers, and probably not too unhappy either. These are the classic teams of the NBA. However it is much more than that this year. It is good vs. evil.

Good is Kevin Garnett. If either of my sons wanted to become basketball players or play sports compettitively at all, I would have no problem with them idolizing Kevin Garnett. The Celtics have not always played beautifully during the playoffs, but you can never be bored watching KG play. He's all out on every play. He'll do anything for his team and teammates. He's unselfish, almost too a fault. Everytime he plays, he demonstrates the characteristics that you hope that children learn from sports.

Evil is Kobe Bryant. Too harsh, you say? Let's not forget this guy is a rapist. Let's not forget when he sliced open Manu Ginobili's face while trying to draw a foul at the end of a game. Let's not forget all the times that he would react to criticism about shot selection by refusing to shoot during games. Let's not forget that he forced Phil Jackson and Shaquille O'Neal out of town. Let's not forget that Phil Jackson said that Kobe was uncoachable. Let's not forget that prior to this season, he was demanding a trade because the Lakers were losing.

I won't go as far as to say that Kobe embodies everything bad about pro-sports -- that would not be true. But he embodies a lot of bad things. He's not just selfish, he's a borderline sociopath. Yes he seems like a great guy this year, now that the Lakers are winning, he's making commercials again (the rape has faded from sponsors' memories), and he won the MVP award.

I remember the Celtics-Lakers series of the 80's. I always rooted for the Lakers back then. Magic Johnson was not only a great player, but completely likeable. Plus everybody where I lived rooted for the Celtics because they had so many white guys.

I used to go to Lakers games all the time when I was in college in Los Angeles.

I would love to root against the Celtics, just because Boston has enjoyed too much success this year. The Red Sox won the last World Series, and the Patriots went undefeated in the regular season.

However, the past must be put aside. The stakes are bigger. Boston's gotta win this one. Go Celtics.

Party Unity

Yesterday the Democratic Party decided to "settle" the issue of what to do about the Florida and Michigan primaries. Their decision was obviously intended to appease Hillary Clinton to some degree, while still assuring that Barack Obama clinches the Party's nomination. I support Obama over Clinton, but I am not pleased with this decision. Here is why.

First, by cutting the number of delegates in half, the Party has essentially said that a Floridian's vote is worth half as much as say a Californian's. Second, the Party decided to give 40% of the votes of Michigan to Obama. This was a practical matter, because Obama was not on the ballot in Michigan. If he would have been, he would have probably done much better than that, but it is still wrong for the Party to decide how people voted, instead of letting people actually vote.

The other thing that I object to is all of this business about party unity. I hate that term, because I hate party unity. Party unity is the key to the two-party system that forces us all into picking the lesser of two evils. Let's take a look at the current Democratic contest. Obama does not do well with union workers, and what is wrong with that? Why does he have to do well with union workers? Oh, because if he doesn't get the support of union workers, minorities, women, etc. then he can't beat the Republicans' coalition of religious groups, nationalists, upper middle class, etc.

Personally I would love to see the Democratic Party break apart. I would also love to see the Republican Party break apart. I think it would be great to see coalitions formed on more of an issue-by-issue basis. Is there any doubt that we would already be out of Iraq if that was the case? I think most Republicans know it is a mistake to be there, but party unity subverts democracy. If we didn't have party unity, we could probably agree on some kind of pollution credit system to protect the environment.

Party unity is the key to the success of divisive politics. You can use such issues only when you are assured it will not cause you to lose votes from your own party -- i.e. only when you have party unity. Do you think Republicans would bring up things like abortion, immigration, and stem cell research if they thought that they might lose some of the upper middle class voters they count on? No way. But when you know that your own constintuency will still vote for you even when you bring up issues they disagree with you on, then you are free to be evil.