Jeremey's Weblog

1 Million Processes in 98 Characters

For the #twitcode contest (see: Twitter contest: what can you code in 130 characters?)

This Erlang code (98 characters) spawns N processes in a ring and sends a message through the entire ring. Try N=1000000 (1 million processes!!). In 135 characters, I could pass M messages through the ring, but there was no way to get that under 130. So this passes 1 message.

a(N)->X=b(self(),N),X!m.
b(P,0)->P;b(P,N)->b(spawn(fun()->l(P)end),N-1).
l(N)->receive T->N!T end.

Complete with module definition and export:

-module(r).
-export([a/1]).
a(N)->X=b(self(),N),X!m.
b(P,0)->P;b(P,N)->b(spawn(fun()->l(P)end),N-1).
l(N)->receive T->N!T end.

To run:

$ erl +P 2000000
Erlang R13B (erts-5.7.1) [source] [smp:2:2] [rq:2] [async-threads:0] [kernel-poll:false]

Eshell V5.7.1  (abort with ^G)
1> c(r).
{ok,r}
2> P=spawn(fun()->r:a(1000000) end).
<0.39.0>
3>

It should run in under a minute (w/ 1 million processes) on most machines, maybe noticeably less. Obviously 1000 processes or so is instantaneous.

Technorati Tags: programming, twitter, twitcode, erlang

Erlang FTW!

If you write code and you haven't learned Erlang, you should do so, right now. It will stretch your thinking, for sure, but it may do much more than that.

Erlang represents a fundamental shift in the way we think about solving problems. The fact that it is a functional language is part of the necessary reality that makes Erlang successful, but it is not the primary reason. What makes Erlang very special is its concurrency. Erlang is a language for "concurrent" programming and a virtual machine (like Java) for running compiled Erlang code.

The Java language is almost always considered in light of its runtime environment, the JVM. Erlang even more so, it would not be what it is without the runtime that implements it. So when I say Erlang, I mean the whole package, not just the language.

Erlang is oriented around concurrency on a massive scale. The fundamental unit of thinking in Erlang code is the process. One Erlang interpreter/virtual machine can handle millions of concurrent processes. The processes interact by passing immutable messages (everything is immutable BTW, Erlang uses single-assignment variables).

Guess what? The Internet IS concurrency. Practically any piece of software connected to a network these days must handle concurrency. Most languages do a pathetic job of this (or no job at all). They don't give us tools to build concurrent systems with any kind of ease. Most languages make it quite difficult, in fact.

Erlang makes it so easy and so natural that you begin to think about solving problems differently. The ability to run millions of concurrent processes can radically change your approach to a problem. What are social networking and large user-driven sites always running into? Scalability. How do you scale with all these users?

There are two problems here, the first being how do you scale to handle the load, and the second being what do you have to sacrifice in terms of code elegance, simplicity, etc. to get there? Will the complexity of your system grow with the scale? More little optimizations that disguise the real logic of the application?

What if you could run a unique process for every single user on your system? How would that change your approach?

That is what Erlang makes possible. Instead of a pool of workers crunching away in serial, individualized processes working in parallel, on a massive scale.

Plus, it is built to cluster, and all of its message-passing works identically across a cluster as it does locally. So if one machine can handle a million or millions of processes, how many processes could you handle on a large cluster?

One of the exercises in the Erlang book is to write a process ring benchmark. The idea is that you create a ring of N processes and then pass M messages through the ring and see how long it takes. On my Mac Pro (couple years old, quad-core 2.4GHz, 6G RAM), I ran the benchmark with 1000 messages and 1 million processes (!!). That means Erlang passed 1 billion messages. The benchmark ran in 8 minutes, which boils down to 2 million messages every second, or 2 messages every 1 microsecond. That's amazing. And powerful.

Another interesting tidbit: the statistics report "run" time and user time. User time was half of the run time. Why? Single-assignment + message passing = no locking, no contention = SMP-friendly. Erlang is built to run on multi-core computers. So it spent twice as much time "on processor" as it took in "real life" because it was using the multiple CPUs/cores offered by the Mac Pro.

Here's the code:

-module(ring).
-compile(export_all).

run(M,N) ->
   Pid = start(N,M,self()),
   statistics(runtime),
   statistics(wall_clock),
   send_messages(Pid, M),
   receive
      finished ->
         void
   end,
   {_, Time1} = statistics(runtime),
   {_, Time2} = statistics(wall_clock),
   io:format("~p ~p ~n", [Time1, Time2]).

start(N,M,RunPid) ->
   spawn(fun() -> start_master(N,M,RunPid) end).

send_messages(Pid, M) ->
   for(1,M,fun() -> Pid ! {init, message} end).

for(M,M,F) ->
   F();
for(N,M,F) ->
   F(),
   for(N+1,M,F).

start_master(N,M,RunPid) ->
   LastPid = start_ring(self(), N),
   master_loop(LastPid, RunPid, M).

start_ring(Pid, 1) ->
   spawn(fun() -> loop(Pid) end);

start_ring(Pid, N) ->
   NextPid = spawn(fun() -> loop(Pid) end),
   start_ring(NextPid, N-1).

loop(NextPid) ->
   receive
      stop ->
         NextPid ! stop;
      Any ->
         NextPid ! Any,
         loop(NextPid)
   end.

master_loop(Pid, RunPid, 0) ->
   RunPid ! finished,
   io:format("Finished~n"),
   receive
   after 100 ->
      Pid ! stop
   end;

master_loop(NextPid, RunPid, M) ->
   receive
      stop ->
         NextPid ! stop,
         io:format("Master stopping ~n");
      {init, Msg} ->
         NextPid ! Msg,
         master_loop(NextPid, RunPid, M);
      _Any ->
         master_loop(NextPid, RunPid, M-1)
   end.

Get Lisp? Not So Much

The Lisp function has called itself again, it seems. Or maybe it calls itself often, and I have just failed to notice it until now (see http://xkcd.com/297/). In any case, Lisp is the programming language that programmers are taught to venerate. Ogle its perfection, its code and data dual nature, its simplicity, its elegance, and so on.

I wholeheartedly support bashing new concepts into programmer brains using Lisp. However, I fail to see its appeal for writing real software. Part of developing software systems involves programmers typing in code, reading that code, and re-reading that code 6 months later. Other programmers are going to come along and read that code, too. If you've ever looked at the source code for a large Lisp system, you may notice that its syntax does not lend itself to being understood. It is difficult to read, and even more difficult to interpret, because there is SO MUCH LIST PROCESSING GOING ON (Lisp = List Processing).

Lisp is difficult, in part because it represents new concepts to most programmer brains, but also in part because it's just tedious. Very nice that you can represent every data structure as a list or list of lists, but that doesn't mean you should. Just because it is possible to treat all things as exactly the same and have no keywords doesn't mean it makes for better software. I think it just makes for easier compilers. Lists just aren't a natural way to represent data to humans.

All that list processing produces code that is syntax-heavy (parentheses and list processing) in a language that essentially has no innate syntax. It's difficult to read, just like almost every Perl script is difficult to read. There's a lot of syntax happening. Why? Because it makes the compiler's job really easy. Ummm, why do I care if the compiler has an easy time of things? The compiler should work hard to make my life easy, and to make it possible for me to write better, more maintainable, more legible, simpler code. In Lisp, the programmer is responsible for constructing the entire AST himself.

Programming doesn't have to be difficult to be powerful. I reject that notion as the supposition of lesser programmers who've bought into a culture that worships Lisp and its kin. Learning Lisp may grow your brain (a good thing), but deploying real software in it seems like less of a good idea. To think that we've failed to come up with any more good programming language ideas in 40 years is ridiculous.

The Lisp culture reminds me of the "if you only knew what we knew" arguments that get trotted out by "national security" people every so often.

Tell you what... let's have a contest. You (hypothetical Lisp worshiper) implement a Twitter clone in Lisp, and I will implement it in a language of my choice (NOT Lisp, probably Erlang). You must provide an HTTP-based API in addition to a pleasing web UI. Both must support username/password authentication. You must be able to demonstrate support for 500,000 concurrent users with sustained message rates over 1000 messages/sec. You must store all messages. 50% of the users will have 50 followers. 35% will have 200 followers. 10% will have 1000 followers. 5% will have 10,000 followers.

When both systems are complete, we will note how many hours (roughly) it took to build each system, and how many lines of code (this is not always a good metric, but we won't abuse its relevance), and what deployment requirements there are to reach the scalability goals.

Then we will take a good programmer who has not programmed extensively in either language, and ask him to understand each set of source code and ask him to make some modifications. We'll subjectively analyze how things go in each system.

I think we will find that the non-Lisp system is less code, more intelligible, easier to extend, faster, and easier to deploy.

Lisp as a religion needs to die. Lisp as a set of interesting ideas worth learning should stay.

Technorati Tags:
programming, software, lisp

Programmers and Philosophies

Dear programmers of the world: take your pet "philosophies" and shove them where the sun don't shine. You're building an app that you want to SELL and your "philosophy" prevents you from implementing a major feature that many users want? You can rot.

You want a philosophy? How about this: build great apps that people actually want to us and that solve real problems for people.

For instance, Twitter clients. I love Twitter. I hate Twitter client developers (except TweetDeck). Why? Because they don't bloody listen to users. TweetDeck has how many users? Despite the mega-suck AIR UI? Why? Because it solves a major problem (grouping Twitter users), and solves it well. Is it perfect? No. Is is 100,000 times better than every other Twitter client because it makes a decent attempt? Yes.

Would I buy TweetDeck? I might. Would I buy a fantastic Cocoa app that had a similar implementation of groups along with a nice UI, low memory footprint, etc.? Absolutely. I would pay $40 for a high-quality Cocoa Twitter client. Is there one? Nope. Not even one.

Tweetie looks fantastic, but it is DOA without groups. I love everything else about it, and it pains me to shut it off and start TweetDeck, but that's what I gotta do, because a beautiful interface to an un-grouped Twitter feed is like the most perfect baseball bat ever made when I need to chop down a tree. Sorry, it doesn't work. It's dead.

If you want to implement what people need and then make it perfect by beating Twitter into implementing groups and transition from your local implementation to an API-based implementation, fine. Just do it. What a waste of an opportunity.

Technorati Tags:
twitter, tweetie, programming, philosophy

Software Development Meme (8 Months Late)

@BrentO posted this over 8 months ago, and I just now saw it, while googling myself in the hopes of finding one of my old resumes laying around on the Internet!

Anyway, here goes... this is a very deep topic for me, so bear with me. :)

How old were you when you first started programming?

I think my first programming experience was in grade school, on TRS-80 machines ("trash-80s"), in BASIC. This was a mischievous child's dream, because although most people could bang out the programs the teacher wrote on the board, almost none of them knew what to do when their screen filled with the same lines of text over and over, ad infinitum. DoS (Denial of Service) at its best! (10 PRINT "YOUR MOMMA WEARS COMBAT BOOTS". 20 GOTO 10.) I vaguely recall building some incredibly simple game at the time, but it's been so long I may be making it up.

How did you get started in programming?

Not long after starting high school, our family got our first personal computer, a Leading Edge 8088 machine. It was awesome with its 640K of RAM. All we'll ever need, right Bill? :) Not long after, I produced a DOS manual for my parents, explaining the intricacies of things like "dir". Probably a year later (sophomore year?) I tried to teach myself Pascal. I had started working at a bicycle shop, so I had a little money, and I bought the Borland Pascal compiler which must have come with some introductory book, or something.

In any case, Pascal was a disaster. It was a very frustrating experience, mostly because the language felt so artificially limited. I did manage to program a little space game on our 4-color CGA display that would go into hyperspace and shoot laser beams, but I got tired of Pascal and let the whole thing sit dormant.

But, in the beginning of my senior year of high school, my mom began taking an intensive career-retraining course at DePaul University. It was a 9-ish month program designed to launch your career in IT software development (COBOL, JCL, etc.). I didn't pay much attention until she began taking a C programming class, got stuck, and asked me for help.

Let me tell you, to a born hacker not yet aware of his calling, who had only worked in BASIC and Pascal, programming in C was like injecting some kind of super-drug. THIS was freedom, this was power, this was programming. Pointers were what I'd been looking for. Raw, type-unsafe power, baby.

What was your first language?

Although I dabbled in BASIC and Pascal, I consider C my first language. It's the one I really learned, the one that clicked, the one that I didn't need to read books about or study. I just got it.

What was the first real program you wrote?

I would probably say the Oberon compiler I wrote in college was my first real program (I was taking Compiler Design). It was limited, and only worked on a subset of the language, but it was real. And it really compiled code. The assignment was to target a virtual machine platform with your basic operations, but my friend and I decided to target the real SPARC processor instead. This actually turned out to be fortuitous because the SPARC architecture included overlapping register windows, so I was able to implement all of the required functionality (we had to be able to compile a certain set of algorithms) without implementing a stack.

Very few things make you feel more like master of the universe than writing your own compiler and having it actually generate machine code for a real machine.

What languages have you used since you started programming?

Yikes. This is a long list, but here goes, in rough order of appearance:

• C
• C++
• ML
• SQL
• Visual Basic
• COBOL
• shell (bourne and c)
• lex and yacc
• Tcl
• HTML
• Lisp
• Python
• Java
• Javascript
• Perl
• PHP
• CSS
• Haskell
• Ruby
• Objective-C
• Smalltalk
• Erlang

What was your first professional programming gig?

In college I began working for some friends who formed a consulting company. They were working on a couple contracts with a pharmaceutical company and a bank. This was where I had the unfortunate experience of being subjected to Visual Basic. There was also some C work, but all of it was tedium. I quit not too long after joining, ostensibly to start my own company with another friend, doing more interesting stuff.

The first gig I enjoyed, and stayed at, was with a tiny startup in Silicon Valley. My professor at DePaul recommended me to a friend of his, we had one phone interview, and I left Chicago bound for Palo Alto, 2 days after my last class finished, sight unseen, etc. We were building tools to put scientific journals and magazines like Science on the web (yes, the web, in 1994, pre-Netscape).

If you knew then what you know now, would you have started programming?

Certainly. It's in my blood. I would start with different languages if I had it to do over again (well, I would still do C first, but Smalltalk would be soon after).

If there is one thing you learned along the way that you would tell new developers, what would it be?

One? Are you kidding? :) Here's a few things:

• When the C++ and Java programmers tell you how the world works, don't believe them. Their world is too small.
• Learn Smalltalk, Erlang, and Python.
• Study EJB 3.0+ and recent JBoss. They represent an enormous amount of mature thought on deploying real applications. There is much there to learn, whether used in that environment or not.
• Do something meaningful.
• You won't really be any good for ten years, at least.
• If you don't get it, find something you do get, and do that instead.

What's the most fun you've ever had ... programming?

Usually, whatever I'm doing right now, for any value of now. I've been very fortunate to work on interesting projects that continue to stretch me.

Though, if I had to pick one, handing a live phone call from VoIP to GSM and back with no break in audio was pretty sweet.

Who are you calling out?

I dunno, I'll figure that out later. :)

iPhone App!

I'm working with a friend on an iPhone game for toddlers (he's doing the graphics, I'm writing the code). I've learned a ton about the iPhone SDK over the past week and the game is coming along very nicely. I love the iPhone SDK. It's a dream.

Here's the splash screen, FWIW (running in the simulator):

Technorati Tags:
iphone, application, development

Smalltalk

I'm exploring the Smalltalk language, specifically GNU Smalltalk (Wikipedia link... go here for the code). Smalltalk is a very cool language accompanied by a very strange development environment. GNU Smalltalk implements the Smalltalk machine in a more traditional "write code in editor, then run it" approach... so I'm getting my feet wet that way. I dunno that I would really "get" the constant development IDE style (e.g. Squeak).

Smalltalk is pure OO (object oriented) to the core, but not the trashcan OO of C++ or Java. IMO Smalltalk may be the best language to learn programming with, and to model development in other languages on. For example, my Python code easily translates into Smalltalk semantics... I use Python because it fits in traditional Unix systems very nicely, but semantically, I love Smalltalk's elegance, power, and simplicity.

Smalltalk might even be good to teach to kids. There are some really interesting developments on that front, particular Scratch, which is built with/in/from/? Squeak. For anyone interested in Squeak, check out Squeak By Example (open PDF book).

If GNU Smalltalk turns out to be practical for Internet services and protocols, I might actually use it for real projects... even if not, learning Smalltalk is a fantastic way to train your programming brain to think better.

Technorati Tags:
smalltalk, programming, software

Symbian Goes Open Source

Symbian is going open source. This is a pretty interesting development, but I think it may be too little, too late, and it doesn't imply any major changes in the Symbian platform.

The real problem with Symbian isn't the fact that it's closed, it's the fact that it's Symbian. It's a difficult platform to develop for, its UI concepts are dated and accelerating towards antiquated, the "access point" scheme for managing IP connectivity is appallingly difficult for users, etc. Perhaps going open source will provide a catalyst for some serious changes and revolutions in the platform, that would be great. We'll see. Increasingly, the features of the Symbian platform that made it compelling are becoming unnecessary... the hardware platforms for mobile phones are no longer the exceedingly resource-constrained, battery-sipping environments they once were, and that will only become more true.

2010 is a long way off... the iPhone 3G ships in 3 weeks, Android phones this year. Developers finally get their hands on Symbian innards one year after that? I can't see that being very interesting to new developers.

It could be a huge boon for existing Symbian developers though, who've wished for access to deeper APIs, or even just to understand what is going on down deeper in the idiosyncratic Symbian brain. But again, in a year or two... it doesn't help now.

Interesting times!

Technorati Tags:
symbian, nokia, mobile

Great Talk on Bigtable

http://sites.google.com/site/io/under-the-covers-of-the-google-app-engine-datastore

Technorati Tags:
appengine, bigtable

Things I Learned About Python

Sockets

Turns out socket.socket() is not directly implemented by Modules/socketmodule.c. So you can't pass a socket.socket() into C and expect a PySocketSockObject*. You need to pass ._sock ... that's a PySocketSockObject*, i.e. the socket implemented in Modules/socketmodule.c.

Asyncore

Messages on unix domain datagram sockets trigger handle_connect() and then handle_read(). I just pass on the connect.

Embedding

Pyrex doesn't work as advertised. Simple direct embedding, however, works fine... but only if you build the shared python library (at least, that's the only consistent difference between working and non-working that I've noticed so far).

Extending

Writing a module in C is very easy.

Technorati Tags:
programming, python