Archive for February, 2008

Profiling with SBCL

Friday, February 29th, 2008

My Bézier curve code was not optimal, so I decided to learn how to profile with SBCL. In particular, I was not yet doing a binary search of the sampled points, neither was I doing an interpolation to recover the parameter t. Finally, I was sampling the curve at a fixed high frequency (probably too high for most cases). So I changed a list to an array, implemented binary search and interpolation to recover t, and set the sample frequency at 2x the number of division points.

SBCL profiling is very easy. The overall performance here is probably bound by the file write, which explains why the overall time for the top level function is more or less constant. But check out the other function timings and the “consed” column. The sample frequency change is clear in the number of calls to DECASTELJAU.

Before:

VECTO-TEST> (watch '(tenths-test-bezier "test.png"))
  seconds  |   consed   |  calls  |  sec/call  |  name  
----------------------------------------------------------
     0.278 | 26,952,592 |       1 |   0.278034 | TENTHS-TEST-BEZIER
     0.093 | 10,288,576 |  26,576 |   0.000004 | VEC-LENGTH
     0.037 | 10,236,064 |  26,525 |   0.000001 | POINT-DISTANCE
     0.015 |  1,607,920 |  12,624 |   0.000001 | INTERP-SINGLE
     0.003 |    385,024 |  32,990 |  0.0000001 | MAKE-POINT
     0.002 |          0 |  92,607 |  0.0000000 | XCOORD
     0.000 |          0 |       1 |   0.000000 | BEZIER-POINTS
     0.000 |  1,834,496 |      51 |   0.000000 | FIND-BEZIER-PARAM
     0.000 |     36,864 |       1 |   0.000000 | POLYLINE-LENGTH
     0.000 |     73,664 |       1 |   0.000000 | SAMPLE-BEZIER
     0.000 |      8,192 |      51 |   0.000000 | BEZIER-POINT-AND-NORMAL-AT
     0.000 |    339,968 |   1,001 |   0.000000 | DECASTELJAU
     0.000 |      8,192 |      51 |   0.000000 | NORMAL
     0.000 |     16,384 |      51 |   0.000000 | NORMALIZE
     0.000 |     16,384 |      51 |   0.000000 | SCALE
     0.000 |     40,960 |      51 |   0.000000 | ROTATE
     0.000 |  2,076,672 |   6,312 |   0.000000 | INTERP
     0.000 |     16,384 |      51 |   0.000000 | -POINT
     0.000 |          0 |  92,607 |   0.000000 | YCOORD
----------------------------------------------------------
     0.428 | 53,938,336 | 291,603 |            | Total

After:

VECTO-TEST> (watch '(tenths-test-bezier "test.png"))
  seconds  |   consed   |  calls |  sec/call  |  name  
---------------------------------------------------------
     0.439 | 26,773,984 |      1 |   0.438705 | TENTHS-TEST-BEZIER
     0.004 |    253,952 |    912 |   0.000005 | INTERP
     0.004 |     12,288 |    101 |   0.000035 | POINT-DISTANCE
     0.000 |     16,384 |      1 |   0.000000 | BEZIER-POINTS
     0.000 |     32,768 |    393 |   0.000000 | FIND-BEZIER-PARAM
     0.000 |     24,576 |      1 |   0.000000 | SAMPLE-BEZIER
     0.000 |     16,384 |     51 |   0.000000 | BEZIER-POINT-AND-NORMAL-AT
     0.000 |     32,768 |    101 |   0.000000 | DECASTELJAU
     0.000 |     57,296 |    152 |   0.000000 | VEC-LENGTH
     0.000 |          0 |     51 |   0.000000 | NORMAL
     0.000 |      8,192 |     51 |   0.000000 | NORMALIZE
     0.000 |     16,384 |     51 |   0.000000 | SCALE
     0.000 |          0 |     51 |   0.000000 | ROTATE
     0.000 |    175,856 |  1,824 |   0.000000 | INTERP-SINGLE
     0.000 |          0 |     51 |   0.000000 | -POINT
     0.000 |          0 |  2,535 |   0.000000 | YCOORD
     0.000 |          0 |  2,535 |   0.000000 | XCOORD
     0.000 |     16,384 |  1,166 |   0.000000 | MAKE-POINT
---------------------------------------------------------
     0.446 | 27,437,216 | 10,028 |            | Total

A couple of “it would be nice ifs” struck me while writing this code: IWBNI LOOP could collect into any sequence, not just a list; and IWBNI there was a CL equivalent of Haskell’s scanl. Both of these lacks could be solved (if they aren’t already and I’ve just overlooked them) but my CL macro skills aren’t all that yet.

Modern Correspondence

Friday, February 29th, 2008

I’ve set aside my usual time for checking on my email.
Penis enlargement… penny stocks… pretending to be female…
Apparently my gas bill’s ready for an online look,
And Amazon have managed (finally) to ship my book.
An urban legend warning from some well-intentioned kin:
I’ve told them about snopes.com, but still they’re taken in.
An ex-colleague invites me to keep up to date with Plaxo;
I never really liked him – kind of glad he got the sack – so…
Hey, I’m a lotto winner? But I never bought a ticket!
I’m sure that link is suspect, so I don’t think I will click it.
An invitation to attend some friend-of-friend’s new play;
A mangled Chinese subject that the program can’t display;
And endless special offers from the online stores I’ve used,
While the comments section on my blog is once again abused.
But the Reverend Bayes can save me, so I mark it all as spam,
And with any luck I’ll never see another email scam.

Some interview questions I’m thinking about

Thursday, February 28th, 2008

I’m thinking about the following questions. They are to be completed using pencil and paper (or marker & whiteboard) only (and for questions 1 and 2, I’d accept the method and not worry about the actual calculated answer). At the moment, only one of them is a question I’ve actually given at interview. And I only use these questions for new graduates, as a way of gauging mental horsepower. If I’m interviewing someone with a few titles under their belt, for the best use of time I usually hit other areas.

Question 1. What is the sum of the multiples of 3 less than 1000? What is the sum of multiples of 3 or 5 less than 1000? [This is Project Euler problem 1]

Question 2. What is the smallest integer that is evenly divisible by the numbers 1 through 20? [This is Project Euler problem 5]

Question 3. How many trailing zeroes are there in the (decimal!) number 100 factorial when it’s fully written out?

Experimenting with (cubic) Bézier subdivision

Wednesday, February 27th, 2008

As you know, a Bézier curve (here meaning specifically a cubic Bézier) is often used for drawing all kinds of things in vector graphics. It has the nice property that the endpoints and control points form a bounding box, and deCasteljau’s algorithm is a nice numerically stable way of evaluating the curve at a particular point. Of course, the same algorithm trivially gives the tangent to the curve at that point and from there it’s a hop and a skip to find the normal.

All well and good so far. The problem I wanted to tackle was that of spacing points equally along the curve (and incidentally, pushing these same points out along the normal), so that I can easily modulate a pattern (e.g. sawtooth, square wave) on to an arbitrary Bézier curve.

But there’s a slight problem with the naive method for doing this. Recall that a Bézier curve is in fact a parametric curve, specified by the parameter t which varies from 0 to 1 along the curve. The problem is that a linear increment of the parameter t does not correspond to a linear step along the curve length. For some curves, it’s not a bad approximation, but the more “curvy” the Bézier, the worse the discrepancy. This picture is a clear illustration of this problem.

bezier-subdiv-wrong

The picture shows points (and points pushed along the normal) plotted on the curve, as t increments linearly from 0 to 1. As you can see, stepping along with constant increments of the parameter t gives the wrong result. These points are not equally spaced along the curve.

So far, I have a naive “correct” solution to this problem as follows: I sample the curve at a high frequency (say 1000). Each segment between points I then treat as a straight line, and I compute the length of the curve (simply the sum of the Pythagorean distance between successive points). I can then step along the curve linearly with respect to the curve length, and recover the parameter t (to actually evaluate the curve at a given point) by a simple calculation (binary search and interpolation between nearest neighbours). The result of this approach:

bezier-subdiv

Much better.

Sneak preview

Tuesday, February 19th, 2008

This is a sneak peek at my current personal project. A bit of computerised heraldry.

8 way test

(“Sable a [ordinary] ermine.” Left to right, top to bottom: chief, fess, pale, cross, bend, bend sinister, chevron, saltire. Yeah, I know; charges on a bend should be bendwise. It’s a work in progress.)

Book sale time again

Saturday, February 16th, 2008

Last night I got an email from the library mailing list about another book sale this morning. We snagged a lot of books, including many SF paperbacks. Mini-Elbeno also got a ton of new titles. Not many computer titles this time around, but I got a book on python and The Man who Knew Infinity, a biography of the brilliant and unconventional Indian mathematician Ramanujan.

Life defined by Lunch

Monday, February 4th, 2008

I am a creature of habit and habitual comforts. Never more so than at lunchtime. I’m also a big fan of breakfast, it’s true, and I couldn’t really care less about dinner most of the time. But lunch is where the routine kicks in. I could happily eat the same thing every day for lunch, and for much of my life, I have. Here’s a rundown of my life, marked by what I was having for lunch at the time.

When I first started taking control of lunch myself, my standard lunch was a chicken sandwich. Roast chicken off the carcass (and there was always at least one carcass to be picked – I lived my teenage years in a pub), between sliced white bread, salted. But what with one thing and another, I often forewent lunch entirely. Sometimes I would arrive home at 4.45pm practically fainting with very low blood sugar, and I got in trouble after this happened quite a bit. My mother phoned my housemaster and I effectively got lunchtime detentions where I was forced to eat lunch.

When I was 16 or so I spent a summer or two working for my dad typing up documents on the computer, and later making my first forays into application programming. He was managing a salesforce and putting together a training programme at the time. We would walk into town every day and grab lunch from Marks and Spencer. I always had the same thing: BLT, orange juice and chocolate-covered raisins. The M&S BLT is still one of the best BLTs I’ve had. Malted granary bread FTW!

When I went up to university, lunchtimes became more social affairs with my small group of friends. Lectures ended at 1pm and just around the corner from the New Museums Site was Cornucopia, a sandwich shop and bakery. I don’t remember my usual sandwich (perhaps ham & cheese?) but I do remember always having a caramel slice. In my second year, a favourite was the baked potato van, and I always had baked beans and cheese on mine. A group of us would get potatoes and take them back to a friend’s room and play video games. Another lunch high point of uni was a cooked brunch for elevenses on a Sunday after an all-nighter in the lab.

During my second summer break, I got a job in London (in the City, just off Bishopsgate). My pay included luncheon vouchers – £2 per day! This was just enough to cover a chicken or ham salad roll from a Benjy’s round the corner.

When I graduated and first entered the workforce proper, I worked about half a mile from a huge Tesco, so I went back to my old favourite and picked up a packaged sandwich, juice and chocolate-covered raisins each day. I couldn’t always get a BLT though, so it varied a bit. ISTR coronation chicken, or ham, cream cheese and pineapple being possibilities.

Around 1997 we moved to new offices, so Tesco was no longer the lunch place. Instead, there were two sandwich shops up the road. I initially patronised one, but switched to the other (which was also a bakery) fairly quickly, and joined a couple of other guys who drove there. Driving there was the height of laziness – it was only 5-10 minutes’ walk. Once again I always had the same thing: chicken salad baguette, no tomato, and a bakewell tart. This was also the era of the Friday lunchtime outing, and up to a dozen of us frequented “the sausage pub”. I discovered its real name – The Royal Oak – only months later. Every fine Friday from April to September we’d sit in the sun and eat steaming plates of sausage, mash and vegetables with onion gravy. The sausages were from a local butcher and were really nice – pork and apple; pork and leek; pork and garlic.

In 2000 we moved offices again, and this time the company had its own subsidised cafe. The best part of this was that we could email sandwich orders in the morning and pick them up at noon, bagged and tagged with our email. Since the emails were printed verbatim, I took to typing my name in 72-point font, blue, for easy recognition of my sandwich. A variant of this tactic was soon adopted by everyone. Since the cafe was shared by about 500 people, we saw a gradual hastening of lunchtime for those that weren’t ordering ahead. When we moved in, most people (as is normal in the UK) were used to taking lunch at 12.30 or 1pm. This pretty swiftly moved up to noon to try to beat the rush, or even as early as 11.40 at times. Long lunchtimes became the norm – heading down at noon, eating and chatting until 1pm, then starting “second lunchtime” as it were and playing a game of Quake until 2pm. The post-game chat would then regularly take us until 2.30pm before anyone sat down to actually work again. Combine this regime with getting to work at 10am and spending a while checking email and browsing the web, and it meant that some people started real work at about 3pm!

Perhaps it was this schedule, among other things, that sapped my motivation, so I switched companies and started working in London at the end of 2001. My office was on Blackfriars Road, over the road from an Italian cafe (Cafe Pronto) and a convenience store. The cafe did wonderful paninis – garlic chicken with mozzarella and sundried tomatoes. I tried to keep it to 3 a week, because they were really calorific. A mean slice of carrot cake was also on the menu. Mrs Elbeno would often meet me for lunch because she loved the paninis too. A coke was my drink of choice. My other alternative was to hit the convenience store, and if anything this was even less healthy – it usually meant me eating a whole packet of biscuits that afternoon.

After a little over a year, I moved offices (although not companies) to leafy Godalming, and we were situated in a fairly quiet area out of the town centre and behind a huge supermarket – this time Sainsbury’s. Of course, I went back to my old favourite the BLT (which I could get most days). Chocolate-covered raisins were in short supply this time around, but luckily Sainsbury’s in-store bakery more than made up for the lack with their chocolate orange muffins. These were incredibly delicious and sometimes I’d eat two! It was probably a good thing for my waistline that in mid 2003 I was hired away to Los Angeles.

Which brings us to the present day, where I am once again frequenting the company cafe. My favourites now are not things I can get every day, but when they are on, I always get them. Anything with the word “curry” in it is good, especially the curried chicken Waldorf salad sandwich that they do (on toasted white bread). I’d have that every day if I could. Barbecues (every Thursday) are a bit hit and miss. There is always the sandwich bar and soup choices, or something from the grill at a pinch, so most days I find something appetising.

An experiment

Sunday, February 3rd, 2008

Gearation Timelapse

Participatory Culture

Sunday, February 3rd, 2008

My photo of Sydney’s Fort Denison was included in the Schmap Sydney guide.

Arc’s debut

Sunday, February 3rd, 2008

(Seems like this is just about what’s happened)

Paul Graham: Behold, Arc! (disclaimer: blah blah blah)

Rest of the Lisp-speaking world: Dude, weren’t you working for like 5 years on this? Now you give us a wrapper on Scheme?

PG: Look, I know it’s a bit pre-alpha, but give it a go! You might like it.

ROTLSW: Looks like a lisp with everything that makes actual real-world programming possible removed. Oh and some weird fairly pointless syntax changes?

PG: It made the code shorter. Look, a web app in five lines!

ROTLSW: …and five thousand lines of libraries. Even non-lispers can do that.

PG: *sigh* You’re just not getting it. All other lisps are Blubs now! I’m going back to John McCarthy’s papers…

ROTLSW: OK, call us when Arc can solve some real problems – see you in another 5 years then? Good luck with the web angle. We’ll be off playing with Vecto and other neat stuff in CL.