Lost In Permutation

JavaScript tail-call optimization decorator using exceptions

JavaScript does not have tail call optimization, at least until proper tail calls arrive in ES6, because of the existence of <function>.caller and <function>.callee. So, if you’re doing something crazy like implementing the lambda calculus from first principles, you’re gonna have a bad time.

Let’s consider a really simple recursive Node.js module, recurse.js:

We can then test recurse.js to see how many stack frames it takes to crash Node:

On my Linode, node bisect.js recurse.js prints:

Bounds: 16000 32000
16376
39 'processes created'

16,376 should be enough stack frames for anyone.

Unless you’re writing in a purely functional style, in which case recursion is the only way you can write a loop.

The way one usually gets out of this situation is by writing in trampoline style. (You can rewrite your compiler or interpreter to automatically use trampoline style, but V8 and Node.js are too big for me to consider it tonight.)

Instead of rewriting my functions, I just want to be able to call a decorator and have them trampoline without manual rewriting. JavaScript exceptions unwind the stack, and can be of any type. So let’s just throw a continuation to the trampoline.

throwup is the tail-call optimizing decorator around the original function; its return value should overwrite the original variable name. makecallable creates the trampoline in the form of a try{...}catch{...} statement.

Here’s an example:

And another one, which uses corecursion:

I ran node bisect.js tco.js to measure when exception-based tail-call-optimization fails. (I let it run to 32M before getting bored. (It took 2 minutes.))

The stack trace of the exception is allocated on the heap, so it cannot overflow the stack.

Trampolined functions must be called in tail position. Throwing an exception will blow away the surrounding context.

How is performance?

Comically bad.

Here are the results of wrapping the calls to recurse and throwup(_recurse) in for(var i=0;i<100000;i++):

Henry Baker describes an unpublished suggestion from Appel to have the compiler (in our case, throwup()) check the stack size and only return to the trampoline if the stack is about to overflow. This method “avoids making a large number of small [but slow] trampoline bounces by occasionally jumping off the Empire State Building.”

Implementation is left to the reader. Don’t forget your parachute!

Cheez Disconnected

My heart sank when Scott made the announcement on the first evening of CheezCon Winter 2012 -- he planned on leaving Cheezburger at the end of the year. Scott represented our department to the board and the rest of the executive team. He hired all but one of us. He built a culture around remote work, and set precedent in lots of subtle ways. For example, around 2010, while we were chatting about something, he proposed a change in the way we referred to teams: instead of naming them after the product manager the developers worked with, why not act like sports organizations and have team names? I thought it was a silly attempt at morale boosting, sort of like allowing posters on the cubicle walls*. But after trying it for a while, I realized that it made sense. A team shouldn't be renamed just because its linebacker retired, it should keep its name season after season. Thus were born Derpakiin, Adventure Team, the Hipsters, Da Bears, and IO. The team names were a great idea.

At the announcement, Scott went around the room and said one nice thing about each person in the department. He told me I was probably the smartest person in the room. (You know what they say about being the smartest person in a room.) I think he said "probably" because Stefan was also in the room, so he couldn't be sure. Just hearing all the short stories reminded me how we were networked together by a single node. Losing the node wouldn't destroy the network, but it would drastically reshape it. I couldn't imagine CheezTech without Scott. He ended up leaving before the year was up, in late November. They are replacing him with a pair of vice presidents.

I left mid-December. Five others left that month. Three more left this January. Half the Scott-CheezTech network has disconnected, and reconnected elsewhere. Motorsports, writing, a winery, events for kids, deep-space mining, consulting, big data, teaching.

There are a lot of smart people still on that network. I will miss visiting everyone in Seattle. I hope we connect again.

* Cheezburger does not have cubicle walls, even in Seattle HQ.

Laziness

Friday, Cam and I were trying to figure out why a new AJAX call was failing for logged out users, but not for logged in users. The exception logs weren't really helpful: somewhere deep inside .NET, the database was timing out after waiting 30s. The code that called the stored procedure is only used in one place in our code, and that code was nowhere near related to the AJAX call we were doing.

I resorted to inspecting the code line-by-line. I almost gave up, when something in the reptilian part of my brain made me reread the return statement:

return Json(new {ti, id = asset.AssetId});

That can't be it. We're just copying the information about the image into an anonymous object to serialize to JSON.

Although, if the serializer threw an exception, the call stack would be the same as the one we observed... I guess this deserves more attention.

But how would this line cause a crash?

asset.AssetId is a long; besides, it's an auto property, and those are safe.

ti is a TemplateImage. That is one of the earliest classes ever written at Cheezburger. It can't be crashing, can it?

Then I realized that TemplateImage had a User property, User had a UserStats, and UserStats had a property that called the stored procedure that was timing out. Suddenly it all made sense!

The JSON serializer was doing its job, making a deep copy of ti by traversing field and property members as deep as it could. Unfortunately, the UserStats properties were lazy-loaded from the database, and there were no attributes telling the serializer to skip them.

I've gradually begun to dislike lazy attributes because of how easy it is to forget how much work is going on under the covers. Now I'm convinced that this laziness is evil.

Why was this only affecting logged out users?

If you're logged out, the User object is set to a default value. When the database was queried for statistics, it was calculating those statistics across all the images that have ever been made by any logged out user. That's an awful lot of data to chug through.

What was the fix?

The quick fix is to serialize the one property we needed from ti, Url:

return Json(new {ti = new {ti.Url}, id = asset.AssetId});

I didn't have to change the Javascript receiver, and as a bonus, much less data is being sent over the wire. Later, I will refactor UserStatistics to get rid of the lazy properties.

How to get a job at Cheezburger

How do I get a job at icanhascheezeburger?

Well, first you remove that extraneous 'e' from icanhascheezburger. Also, it's generally considered disrespectful to call a company by one of its product names. That's like sending a letter to Cupertino asking for a job at MacBook.

OK, I get it, you like to hear the sound of yourself blogging. How do I get a job at Cheezburger?

You apply on the Cheezburger Job Board. Since you're asking me, I assume you're thinking about applying for the job "ASP.NET/C# Developer", which I am familiar with. Luckily, most of the requirements are right there on the job page, tersely.

Can you explain the requirements?

Experience in ASP.NET MVC
We don't have a lot of time to spend training people how to operate the tools we use. That being said, if you have experience in pretty much any web MVC framework, you will be able to pick up ASP.NET MVC in a day or two.
Experience developing consumer facing web sites
Cheezburger serves hundreds of thousands of requests a minute. Has your code ever faced the Internet... and survived?
Experience with Agile development practices
Some of our requirements are basically keyword matching. This is one of them. Is there any evidence that you have ever attended a scrum? Do you know the difference between pigs and chickens? Have you ever used XP (not from Microsoft)? I need to see that in your application.
A knack for consensus building through teamwork and collaboration
Blah blah buzzword blah blah leadership and communication. Do you have smart ideas? Of course you do, everyone does. The hard part is getting other people to listen to your ideas. How do you lead? Leadership is not the same thing as being a manager. Our intern last summer had some great ideas that took some coaxing, but eventually he was able to convince the team to change a very important process.
Passion for programming and making awesome software
I need you to be excited about your job. If you don't love your craft, I can't get excited about working with you.
A degree in computer science or related field
This is such a weak signal that I don't even bother checking for it when I screen resumes. I am really glad I got my double major in Software Engineering and Computer Science, but I don't think it's the only way people can learn how to make quality software.
Passion for programming and making awesome software
Since this is on our job posting twice, you should take that as a sign that you really need to make your passion clear when you apply.
Excellent written and verbal communication skills
My instructions are to read your cover letter and look for spelling and grammar mistakes. Does it look like you know how to communicate well? If you don't have a cover letter, I can't give you this point. Please write a paragraph or two that is not just a prose form of your resume. Tell me a story. You can even use this cover letter to nail the other requirements down, such as motivation or passion for programming.
Okay, that's pretty much it for the obvious requirements. Do you want to hear the secret requirements?

There are secret requirements?

Well, not after I hit "publish". But if you took the time to ask Siri, "how do I get a job at Cheezburger?", you've already proven yourself to be miles ahead of most of your job-seeking cohort. Therefore, I don't mind sharing these secrets with you.
Cheezburgler
I need some proof that you've used our sites and have a general feel for our different areas. Currently we have the Cheezburger Network blogs (such as I Can Has Cheezburger?, Memebase, and FAILBlog), Cheezburger Sites (create your own!) and Know Your Meme. A really easy way to get this point is to create a Cheezburger profile, play around with it, and fill in the box that says "My Cheezburger.com account username is..." It also helps to have at least a passing understanding of some popular Internet memes.
Hard core
Have you done anything that other developers would think of as hard? Some examples: wrote a real program in assembly, a device driver, an operating system, an interpreter. I need to know that you understand von Neumann architecture and recursion.
Motivation/Self-Directed Worker
This point is hard to discern, so you get goldstar.gif stamped on your resume if I see anything that tells me you can do work without somebody reminding you to.
Different
This point isn't asking about your religion, appearance, gender, sexual identity, political preference, veteran status, or other protected class. First, that's illegal. And second, we honestly don't care. What's important is a diversity of experience. This point is in direct competition with the "public facing web sites" requirement, because we also want to hire people who have done things that aren't public facing web sites. Did you write HFT algos for Morgan Stanley? Firmware for a racecar? Robotic control systems? A popular Flash game? Pizza delivery software? These types of experience mean you bring a fresh perspective to our problems.

That sounds like a whole lot of work.

Yeah, but this kind of thought will help you find out what kind of team you want to be a part of. You'll spend a whole lot of time at work - isn't it worth spending an hour tweaking your resume to make sure that time is spent exactly where you want to spend it?

I can has job?

Cute. You get the Cheezburgler point. The job page has everything else you need.

 

Specialization is organizational growth

A company cannot grow without specialzation. There are a certain number of logical roles that must be filled: design, cleaning bathrooms, testing, sales, accounts payable, shipping, bills, hiring, administration, development, etc. In a brand-new company, one physical person may fill a large number of roles (in the simplest case, the sole founder fills all the roles).

A good analogy is a building made of blocks. Each space on the ground is a role that the company needs to fulfill. The area of this footprint is limited on all sides, so the only way to build is up. The company hires new people to take over some of those responsibilities so the founders can focus on the things that provide the most value.

Each employee provides a certain number of blocks to the company's volume. They can spread their blocks around multiple roles, with limited height, or spend them all in a single column by dedicating their efforts to a single role.

A new employee takes over one or more roles that a previous employee already filled, giving the previous employee their blocks back to reallocate. The only realistic way to go is up, by specializing.

One implication is that you can't create new roles for people. All you can do is recognize where people are overstretched or poor fits for a specific role, and fill in the gaps. Another is that uneven specialization is risky, as it creates spiky towers that are unsupported by the others around them. But uneven specialization allows the highest point on the tower to rise higher than otherwise possible with a given volume.

Mucking Calls

Programming involves a lot of the same motions as horse stall mucking. We're all just shoveling parameters from one function call to the next. Occasionally, I can even see through a hole in the barn the types of work we are meant to be doing: galloping through the bluegrass.

Steve Jobs often said computers are like a bicycle for the mind. He was right, but only because we are still in the penny-farthing era of computation. My mind can go faster than this, I know it. I just don't know how the supersonic jet of the mind works, yet.

Compare and Contrast

Multiple Users in Google Chrome

Like Private Browsing, Chrome now has a feature where you can have multiple browser sessions running side-by-side. This is very excellent, because it means you can be logged in to the same site as two different users. I use it to keep my work bookmarks and Facebook account separate from my personal account. The most important piece of the puzzle fell into place today when I found out the keyboard shortcut for switching between accounts: Ctrl+Shift+M, or on Mac, ⌘-Shift-M. Now I can switch between accounts even more quickly.

iOS '86.0.1

Have you seen iOS '86? The idea behind it: what would happen if designers from the Macintosh System Software team in 1986 were to get their hands on a (somehow monochrome) iPhone 4S? It's a pretty neat idea, but I disagree with Anton on a few details. On the original Macintosh desktop, there are rounded rectangles in every corner to make the screen look less sharp and more friendly. Also, I don't think the Springboard bar would have a 3d effect, so I made it into a more contemporary shaded rectangle. I also disagree with the chosen icon weight: Susan Kare overwhelmingly chose to use white icons with black features, and inverting this pattern represented a selected item. In iOS '86, therefore, apps should appear mostly white until clicked.

Bokode prototype

I got an itch to reproduce MIT Media Lab's Bokode, a really clever optical hack. Their system uses an LED, a diffuser, an image screen, and a pinhole lens. I don't have the components on hand to make something as small as an actual Bokode, but I do have enough camping and cooking gear to smush together a prototype.

My light source was a MAGLITE® LED 3-Cell D Flashlight. I poked some holes in aluminum foil with a mechanical pencil, but I'm not nearly dexterous enough to make an actual QR code. Between the light and the aluminum foil, I inserted a sheet of Kleenex to act as a diffuser. Finally, I reused the pinhole lens I made for a previous experiment as the lens.

I metered, focused at infinity, and took this picture:

Neat!