Behdad Esfahbod's daily notes on GNOME, Pango, Fedora, Persian Computing, Bob Dylan, and Dan Bern!

Archives

July 2003

August 2003

October 2003

November 2003

December 2003

March 2004

April 2004

May 2004

July 2004

August 2004

September 2004

November 2004

March 2005

April 2005

May 2005

June 2005

July 2005

August 2005

September 2005

October 2005

November 2005

December 2005

January 2006

February 2006

March 2006

April 2006

May 2006

June 2006

July 2006

August 2006

September 2006

October 2006

November 2006

December 2006

January 2007

February 2007

March 2007

April 2007

May 2007

June 2007

July 2007

August 2007

September 2007

October 2007

November 2007

December 2007

January 2008

February 2008

March 2008

April 2008

May 2008

June 2008

July 2008

August 2008

October 2008

November 2008

December 2008

January 2009

March 2009

April 2009

May 2009

June 2009

July 2009

August 2009

November 2009

December 2009

March 2010

April 2010

May 2010

June 2010

July 2010

October 2010

November 2010

April 2011

May 2011

August 2011

September 2011

October 2011

November 2011

November 2012

June 2013

January 2014

May 2015

Current Posts

July 2003

August 2003

October 2003

November 2003

December 2003

March 2004

April 2004

May 2004

July 2004

August 2004

September 2004

November 2004

March 2005

April 2005

May 2005

June 2005

July 2005

August 2005

September 2005

October 2005

November 2005

December 2005

January 2006

February 2006

March 2006

April 2006

May 2006

June 2006

July 2006

August 2006

September 2006

October 2006

November 2006

December 2006

January 2007

February 2007

March 2007

April 2007

May 2007

June 2007

July 2007

August 2007

September 2007

October 2007

November 2007

December 2007

January 2008

February 2008

March 2008

April 2008

May 2008

June 2008

July 2008

August 2008

October 2008

November 2008

December 2008

January 2009

March 2009

April 2009

May 2009

June 2009

July 2009

August 2009

November 2009

December 2009

March 2010

April 2010

May 2010

June 2010

July 2010

October 2010

November 2010

April 2011

May 2011

August 2011

September 2011

October 2011

November 2011

November 2012

June 2013

January 2014

May 2015

Current Posts

McEs, A Hacker Life

Friday, June 29, 2007

Congrats on Releases
Congrats to the FSF for releasing GPLv3.

Congrats to Greg Wilon and Andy Oram for their new book Beautiful Code : Leading Programmers Explain How They Think. Looking forward to read it. Greg, thanks for the party yesterday!

I blogged about Greg's previous book Data Crunching. Andy's interesting article The desktop I'd like to see.

Congrats to Greg Wilon and Andy Oram for their new book Beautiful Code : Leading Programmers Explain How They Think. Looking forward to read it. Greg, thanks for the party yesterday!

I blogged about Greg's previous book Data Crunching. Andy's interesting article The desktop I'd like to see.

Labels: AndyOram, book, code, fsf, gplv3, GregWilson, programming

Thanks p.g.o
I enjoyed reading p.g.o last night at 6am when I had problem sleeping. Thank you all.

Luis's GPLv3 FAQ series was intense but a very good read.

Iago's first post on p.g.o made me discover Igalia's GNOME Build Bot which is amazingly useful. It performs code coverage analysis for the test suite on all GNOME modules. Ashamed by Pango's lack of any test suite, but cairo's doing pretty good. Thanks Iago.

Clare, good point about mail boxes. And "Planet GNOME-rs" are called Pigeons.

Jamin, good job. I wish I could sing Cash.

Heading to Ottawa/Montreal tomorrow morning for Canada Day and Montreal Jazz Festival. Hope to see the OLS crowd too.

Luis's GPLv3 FAQ series was intense but a very good read.

Iago's first post on p.g.o made me discover Igalia's GNOME Build Bot which is amazingly useful. It performs code coverage analysis for the test suite on all GNOME modules. Ashamed by Pango's lack of any test suite, but cairo's doing pretty good. Thanks Iago.

Clare, good point about mail boxes. And "Planet GNOME-rs" are called Pigeons.

Jamin, good job. I wish I could sing Cash.

Heading to Ottawa/Montreal tomorrow morning for Canada Day and Montreal Jazz Festival. Hope to see the OLS crowd too.

Labels: buildbot, gplv3, igalia, pgo

Wednesday, June 27, 2007

UK
My UK visa arrived this morning at 9. I sent the package out to Ottawa the day before yesterday, in the afternoon! Very, very, nice of them.

So I'm going from my deferred schedule to original schedule. all things going as planned (and not much is left), I'll be at Text Layout 2007 / aKademy, LUG Radio Live!, and last but not least, GUADEC.

**Interviews:**

Interview with Hans Reiser in prison. Quite touching, particularly the closing.

Mehdi, an Iranian Free Software evangelist interviewed me a few weeks ago, it's up on Hezardastan (Persian).

So I'm going from my deferred schedule to original schedule. all things going as planned (and not much is left), I'll be at Text Layout 2007 / aKademy, LUG Radio Live!, and last but not least, GUADEC.

Interview with Hans Reiser in prison. Quite touching, particularly the closing.

Mehdi, an Iranian Free Software evangelist interviewed me a few weeks ago, it's up on Hezardastan (Persian).

Labels: akademy, guadec, lrl, reiser, textlayout, travel, uk

Wednesday, June 20, 2007

Debian Patch Review
Thanks everyone for comments on JDS patch review yesterday. Thanks to lool for the link, I reviewed Debian's pango and vte patches this morning on the way to office.

Who's next? It could be you!

- 10_scan-module-files-in-dirs.patch: This is filed as bug 355985 already, thanks.
- 11_module-files-append-module-files-d.patch and 12_module-files-append-compat-module-files-d.patch: They should be reconsidered when the bug above is fixed.
- 04_dsp_non_alias.patch: Similar to the wrong vte patch from JDS. It helps if someone who knows the problem gives detailed description of it upstream.
- 12_python_reaper.patch: Filed as bug 320127, but please see discussion in bug 112172.
- 41_from_upstream_fix_nvi_scrolling.patch: Chris tells me that a better fix has been committed upstream.
- 60_fix-ctrl-dash.patch: Filed as upstream bug 448259. Hopefully someone will review and commit it soon.

Who's next? It could be you!

Tuesday, June 19, 2007

JDS Patch Review
(Note: After receiving two comments and rereading my previous post, I removed it in accordance to CoC which I have volunteerly signed. Well, we're cool now.)

Seeing people commenting on JDS patches for their packages, I couldn't help but checking pango, cairo, and vte patches they ship. Having reviewed them, I thought I should provide some feedback :). I'm posting here, hoping that other GNOME hackers pick this up too. Later we can move on to collectively review other vendors' patches too, and help the over-busy maintainers push the right patches upstream and drop/fix the wrong ones. Not every project has a sebuild, right? ;) Brian Cameron has been doing a great job doing that for opensolaris already, but there's more room.

All in all, very good for cairo, but can do better for vte and pango.

Seeing people commenting on JDS patches for their packages, I couldn't help but checking pango, cairo, and vte patches they ship. Having reviewed them, I thought I should provide some feedback :). I'm posting here, hoping that other GNOME hackers pick this up too. Later we can move on to collectively review other vendors' patches too, and help the over-busy maintainers push the right patches upstream and drop/fix the wrong ones. Not every project has a sebuild, right? ;) Brian Cameron has been doing a great job doing that for opensolaris already, but there's more room.

- pango-01-fullwidth-space.diff: I'm interested to have a Pango bug requesting what this tries to fix, as I'm not sure about what the patch tries to achieve. Other than that, both changes in the patch are wrong. The first one is adding an entry for 0x0020 after 0x2000 in a table that is supposed to remain sorted. Moreover, characters below 0x2000 are not looked up in that table at all, that's why the table starts at 0x2000. The other change too adds an entry, for 0x3000, but does not remove the old entry for 0x3000. Both can confuse the bsearch routine.
- pango-02-pua.diff: Is a very weird attempt that I believe is trying to fix bug 443206 that was fixed upstream two weekes ago. Other than that, the patch touches public pango API, something that should be avoided at all costs. It adds a new enum value PANGO_SCRIPT_OTHER that makes no sense. Just use the upstream patch please, or wait for next stable release.
- pango-03-no-xrender.diff: Removes check for xrender from pango's configure check for pangoxft. If that check is not necessary, and there's a use in compiling without it, please file a bug agaist Pango and I'll be more than happy to commit it upstream.
- cairo-01-uninstalled-pc.diff: Submitted to upstream bugzilla already. Only if someone could tell me how exactly the -uninstalled pkg-config files are used...
- cairo-02-8bit-fix.diff: This works around the infamous cairo 8-bit issues. The patch has been posted upstream. Carl has been working on getting this fixed, but it's not easy, and a clean fix is even harder.
- cairo-03-full-hinting.diff: I'm interested to hear what the patch tries to achieve. I assume this relies on custom changes to fontconfig.
- cairo-04-mediaLib.diff: In the works in upstream bugzilla already.
- cairo-05-remove-buggy_repeat.diff: Committed upstream already.
- vte-01-fcconfig.diff: According to Owen, patch is clearly wrong, and I agree. The issue is more of a fontconfig misconfiguration IMO, but not enough detail is given, so I can't test. Needs someone debugging what's going on, instead of blindly cut it out.
- vte-03-cut-copy-paste-handle.diff: The patch looks interesting. I don't remember seeing any upstream report about it, and I'm not sure what problem it tries to solve, but I like to know!
- vte-04-selection-perf-improve.diff: Well, this was submitted upstream and rejected. It removes vte's regular expression matching functionality and hardcodes hand-written matching of common URL schemes. There are many other ways to improve vte's selection performance without sacrificing functionality. Needs someone to profile/debug it.

All in all, very good for cairo, but can do better for vte and pango.

Labels: cairo, jds, pango, vte

Tomato Paste
Nice photo of Iranian woman making tomato paste, by Amin Nazari here.

(Update: the embedded image was not working; linked now.)

(Update: the embedded image was not working; linked now.)

Tuesday, June 12, 2007

Sunday, June 03, 2007

12 or 13 Cairo Demo
Speaking of puzzles, remember the 12 or 13 puzzle? (solution).

Back then I wrote some PyCairo code to illustrate it. Finally pushed it into cairo-demo CVS repo. Browse here. It helps understanding exactly how the puzzle works, and you can design your own ones. Just missing animated-GIF support in cairo to save the result...

Back then I wrote some PyCairo code to illustrate it. Finally pushed it into cairo-demo CVS repo. Browse here. It helps understanding exactly how the puzzle works, and you can design your own ones. Just missing animated-GIF support in cairo to save the result...

Saturday, June 02, 2007

PUZZLE SOLUTION: Group Strategy
This is the solution to the puzzle Group Strategy that I posted a few weeks ago. Make sure you give it a try before reading further.

**Intro:**

There are multiple ways one can approach the solution. Some need more combinatorial background than the others. One intuitive way that Carl Worth suggested was: what should the strategy look like if we want to make sure that the identity permutation always leads to success? Easy, each man should make sure to look into the box numbered as himself. Now what if the permutation is not identity, but identity plus one swap? Continue...

Another approach is probabilistic. Any strategy that has each man's rate of success in finding his number be probabilistically independent of the others is destined to fail with a total success rate of at most 2^-2k. So, in any winning strategy, the success rate of the men are not independent. A corollary is that no man should know which boxes he's going to open until after he entered the room. Think about it (and no, don't think about random strategies).

**Strategy:**

So here is the winning strategy: Each man enters the room, opens the box numbered as himself and reads the paper inside; while not found, he then opens the box with the number written on piece of paper in the last box he opened.

Of course, every man still has the exact same rate of individual success: 1/2, but what the algorithm does is to kinda "align" their success runs together so as a group they succeed with a surprisingly huge probability: more than 30%!

**Proof:**

The algorithm becomes a lot more intuitive if one imagines the graph representation of the permutation that the boxes represent. The graph representation of our permutation has 2k nodes, and node i has an edge towards node j if number j is in box i. This is a directed graph.

Permutation graphs are always a set of (possibly size 1) cycles because each node has in and out degrees of exactly one. The man numbered i wants to find the node that has an outgoing edge to i. Well, looking at the problem this way, the strategy is trivial: start from node i and follow the cycle, until you get back to i. That's all everyone has got to do!

The success probability of the group is equal to the probability that the permutation graph has no cycle longer than k. And since there are only 2k nodes and each node is in exactly one cycle, there can exist at most one cycle longer than k. The question is: what is the probability that a cycle longer than k exists. This is the failure probability.

Getting this far you can claim having solved the puzzle! Now to get a tight bound: I used straight counting. Failure probability is the sum of probability that a cycle of size c exists, for c from k+1 to 2k. The probability that such a cycle exists is the number of permutations with such a cycle divided by total number of permutations (2k!). Finally lets count how many such permutations exist: Choose c members for the cycle and divide by c because the order is not important: 2k! / ((2k-c)! * c). Finally permute the remaining members: (2k-c)!. It simplifies drastically and at the end, failure probability becomes exactly H(2k) - H(k), where H(n) is the n'th Harmonic number. A tight upper bound to this failure probability is ln(2k) - ln(k), which is ln(2). So, success probability is not less than 1 - ln(2), which is a bit over 30%.

The math set using my embedded TeX engine (click for other sizes):

There are multiple ways one can approach the solution. Some need more combinatorial background than the others. One intuitive way that Carl Worth suggested was: what should the strategy look like if we want to make sure that the identity permutation always leads to success? Easy, each man should make sure to look into the box numbered as himself. Now what if the permutation is not identity, but identity plus one swap? Continue...

Another approach is probabilistic. Any strategy that has each man's rate of success in finding his number be probabilistically independent of the others is destined to fail with a total success rate of at most 2^-2k. So, in any winning strategy, the success rate of the men are not independent. A corollary is that no man should know which boxes he's going to open until after he entered the room. Think about it (and no, don't think about random strategies).

So here is the winning strategy: Each man enters the room, opens the box numbered as himself and reads the paper inside; while not found, he then opens the box with the number written on piece of paper in the last box he opened.

Of course, every man still has the exact same rate of individual success: 1/2, but what the algorithm does is to kinda "align" their success runs together so as a group they succeed with a surprisingly huge probability: more than 30%!

The algorithm becomes a lot more intuitive if one imagines the graph representation of the permutation that the boxes represent. The graph representation of our permutation has 2k nodes, and node i has an edge towards node j if number j is in box i. This is a directed graph.

Permutation graphs are always a set of (possibly size 1) cycles because each node has in and out degrees of exactly one. The man numbered i wants to find the node that has an outgoing edge to i. Well, looking at the problem this way, the strategy is trivial: start from node i and follow the cycle, until you get back to i. That's all everyone has got to do!

The success probability of the group is equal to the probability that the permutation graph has no cycle longer than k. And since there are only 2k nodes and each node is in exactly one cycle, there can exist at most one cycle longer than k. The question is: what is the probability that a cycle longer than k exists. This is the failure probability.

Getting this far you can claim having solved the puzzle! Now to get a tight bound: I used straight counting. Failure probability is the sum of probability that a cycle of size c exists, for c from k+1 to 2k. The probability that such a cycle exists is the number of permutations with such a cycle divided by total number of permutations (2k!). Finally lets count how many such permutations exist: Choose c members for the cycle and divide by c because the order is not important: 2k! / ((2k-c)! * c). Finally permute the remaining members: (2k-c)!. It simplifies drastically and at the end, failure probability becomes exactly H(2k) - H(k), where H(n) is the n'th Harmonic number. A tight upper bound to this failure probability is ln(2k) - ln(k), which is ln(2). So, success probability is not less than 1 - ln(2), which is a bit over 30%.

The math set using my embedded TeX engine (click for other sizes):

**Update:**

Proof that the bound is tight: While failure probability is not more than ln(2k) - ln(k), using the same idea, it's not less than ln(2k+1) - ln(k+1). So, success probability is between 1 - ln(2) and 1 - ln(2 - 1/(k+1)).

Friday, June 01, 2007

I'm a Coffee Fool!
It all started when I decided to drink dark and bitter. I soon realized that only coffee from the best coffee shops can be consumed that way without stinking.

Then in the microwave bug Karl Lattimer pointed out the humorous Coffee Making Howto, which then led to me finding and carefully reading the Coffee FAQ. And soon after I hit the Coffee Fool page that accurately describes my syndrome.

Since then coffee has become one of my main interests. At this time I'm still experimenting and trying to find out which machine suits me best.

Then in the microwave bug Karl Lattimer pointed out the humorous Coffee Making Howto, which then led to me finding and carefully reading the Coffee FAQ. And soon after I hit the Coffee Fool page that accurately describes my syndrome.

Since then coffee has become one of my main interests. At this time I'm still experimenting and trying to find out which machine suits me best.

Enjoyable Sharpness of Being
After losing my last pair of glasses during camping two weeks ago I finally got my new shiny ones today. Enjoying all the sharness and all, be it the girl walking in subway or the cup of coffee. Love this feeling every time.

(Also means I don't have to stare at the monitor anymore, not unless it's really late at night)

(Also means I don't have to stare at the monitor anymore, not unless it's really late at night)

Labels: life