{ work }

Web Timing Anatomy

Premature optimization may be the root of all evils in the go to environment of the 1960s but these days it may well be the difference between Friendster and Facebook.  Performance is important.  Some say it's a feature.  I've been working on some performance related issues the last few days and thought I'd share some thoughts.  In particular, how to measure page loading and rendering using Navigation Timing, Selenium WebDriver and Chrome Content Scripts extensions.

It's easy enough to measure server latency and response times:  launch some ec2 instances, run a few scripts.  I did this to compare curl pretransfer times for a few hosting services.  To my surprise, googleapis was the slowest.

I was somewhat hesitant to say that Google was slow but it looks like Pingdom came to similar conclusions.  Should be noted that this may not tell the whole story.  Google may have better geo edge distribution, uptime, transfer bandwidth, etc. 

What is more tricky is measuring performance from a real user's perspective as seen through the browser.  To do this, I had to dig a little deeper into Navigation Timing and how browsers load and render pages. This is the general model of web timing (click for larger version),

1. Fetch start, browser makes request for some URL (GET http://www.foo.com/bar.html)
2. Time it takes to do DNS lookup for foo.com.
3. Time it takes to establish TCP connection (SYN, SYN-ACK, etc) with foo.com.
4. Time for the SSL handshake if applicable.
5. Time to send the HTTP GET to foo.com, wait for foo.com to respond with first byte.
6. Time for response to complete.  Browser now has the content of bar.html.
7. Browser creates the DOM and the DOM is "loading."
8. Time for browser to parse the DOM.  This includes getting external CSS and Javascript.  Browser can begin progressive rendering but will block while CSS and Javascript resources are fetched.
9. Once DOM parsing is done the DOM is "interactive."
10. DOM content is loaded.  For example, deferred scripts are fetched.
11. DOM completes loading.  For example, all the images on the page.
12. DOM is "complete."
13. Various post load events.  Loaded event is fired.

I've created a pagespeed test page to help see things in action.   Fill in the various download values to simulate slow downloading of Javascript, CSS and images.  Some examples,

• Slow CSS in the head will block and give you empty page for a few seconds.
• Slow defer Javascript will not block.
• Slow Javascript below the fold will block but progressive rendering helps with perception.
• Slow image download does not block.

You can enter in combinations.  For example, slow Javascript in the head and even slower CSS at the bottom (wait for the text to turn green).

This is interesting and all, but how can we measure it?  Using Selenium WebDriver and the PerformanceTiming interface.  Here is a little demo video.  The web timing script does the following,

1. Launch the Chrome browser.
2. GET a dummy page (green background).  This is just so the delay is more noticable since all you'll see is a green background until the test page is rendered.
3. GET my pagespeed test page with the following delays,
   
   • 3 seconds to download the head Javascript.  This will block the page from progressively rendering and you'll see the green dummy page for 3+ seconds.
   • 10 seconds to download a head defer Javascript.
   • 5 seconds to download the bottom CSS.  You'll noticed the text won't turn green until this CSS is loaded.
4. Get the timing information from the PerformanceTiming interface [timing = driver.execute_script("return performance.timing")]

I do this thrice then display the averages, which for this run with my bad Comcast internet are,

dns lookup avg                       148
conn time avg                        59
ssl handshake avg                    1335773222840
response latency avg                 122
transfer time avg                    0
DOM parse time avg                   5420 (includes blocking js/css, does not factor in progressive rendering)
fetch to interactive time avg        5757 (time from fetch to page being interactive)

*** page is rendered ***
defer scripts time avg               4977
remaining image loading time avg     0
post load time avg                   0

fetch to loaded time avg             10736

elapsed fold avg                     3487
elapsed total avg                    5420

Took 148ms to do the DNS lookup for tinou.com.  Then waited 122ms for my slow server to response.  The response is so small that it didn't really capture any transfer time.  It took about 5.4s to parse the DOM, which aligns with the 5 seconds it takes download the bottom CSS.  Since the defer Javascript was loaded in parallel, the defer script time is only 4.97s, not the full 10s.  The fetch to load time is 10.7s (when everything is loaded) due to the defer Javascript taking so long.

What about the elapsed fold average and elapsed total average?  Those measurements are tricky.  The PerformanceTiming interface don't capture these values.  Even though it took 5.4s to render the page (due to the bottom CSS), the user is able to see everything above the fold in 3.5s (due to the head Javascript).

I was able to capture those numbers with a Chrome extension.  I could have edited my pagespeed page to calculate the numbers directly but wanted to capture these values unobtrustively, without changing the page.  The Chrome extension uses Content Scripts.  I tell Chrome to inject some Javascript at "document start."  The script does the following,

1. Record the start time.
2. Every 10 millisecond look for elements (by ID) that represent the fold and the page bottom.  Since pages typically have sections (content, footer, etc.) and sections typically have IDs (<div id="main_content">...</div>) this is straightforward and unobstructive.
3. If the element is fold, record the time it was found.

Then it's just simple math to get the time from the start to when the fold was displayed and when the page bottom was displayed.   Note, I am not fully aware of the impact of the extension code but it doesn't appear to cause noticeable issues (like hogging/freezing the page).  Ran it for bestbuy.com and amazon.com.  Here is amazon's 3 run result,

runs 3
http://www.amazon.com
Amazon.com: Online Shopping for Electronics, Apparel, Computers, Books, DVDs & more

dns lookup avg                       118
conn time avg                        92
ssl handshake avg                    1335777335397
response latency avg                 164
transfer time avg                    461
DOM parse time avg                   668 (includes blocking js/css, does not factor in progressive rendering)
fetch to interactive time avg        1052 (time from fetch to page being interactive)

*** page is rendered ***
defer scripts time avg               22
remaining image loading time avg     541
post load time avg                   13

fetch to loaded time avg             1628

elapsed fold avg                     266
elapsed total avg                    648

 

So it took about 260ms for amazon.com to render above the fold and another 400ms or so for the rest of the page to finish.  Here's the Amazon video.

So there you have it, a simple way to get web timing and see how your pages are performing from the users perspective.

 

Log Structured File System for Dummies

Although I've never used Riak, have been a distant fan just because it's written in Erlang.  Erlang, systems that never stop! ® In one of Basho's whitepapers they mention the use of the Log-structured Merge Tree (LSM-tree) data structure for fast indexing. So what's a LSM-tree?  It's a "disk-based data structure designed to provide low-cost indexing for a file experiencing a high rate of record inserts (and deletes) over an extended period."  Riak is often used in write heavy environments so it's important that indexing is fast.  So what's a LSM-tree again? Hmmm, LSM-trees is inspired by the Log-structured File system (LSF), so I better first learn a little more about LSF.

The driving force behind the Ousterhout and Rosenblum's Log-structured File system was (is) the mechanical limitations of the disk drive.  Unlike processor or memory, disk drives have mechnical moving parts and is governed by the laws of Newtonian physics.  To read or write to disk  the arm first has to move to the desired track, then there's a rotational delay until the disk spins to the relevant sector.  This access time is in the milliseconds, which is an eternity compared to memory speed or processor cycles.  Access time overhead is exasperated when the workload is frequent, small reads and writes.  More (relative) time is spent moving the the disk head around than actual data transfer.

[Aside. Slow disk drives is one of the reasons I prefer to develop on desktops and not laptops.  You get a fancy new MacBook Pro with the latest processor and a shit load of RAM only to be bounded by I/O.  Money is better spent on the fastest disk drive you can buy.]

The situation for reads is "easily" solved with file cache.  More memory, bigger caches, better hit rates, less read requests will have to go to disk.  But more memory does not help as much with writes.  File systems can buffer more writes to memory before flushing to disk but the flushes still need to be frequent to avoid data lost; and the writes still involve accessing random parts of the disk.

To see this clearly, below is a diagram of a traditional Unix File System involving writing two single-block files in two directories.

Unix FS involves 8 random, non-sequential writes (numbered, but not in that order).  4 to the inodes and 4 to the data blocks (2 directories, 2 files).  Half of these are synchronous writes to avoid leaving the file system in an inconsistent state.  The other half can be done with an asynchronous delayed write-back.  Newer file systems have many optimization to help with performance, like keeping inodes and data blocks closer together, but the point remains that these types of file systems suffer from the limitation of disk access time.

Ousterhout and Rosenblum's log-structured file system gets around this by avoiding random, non-sequential writes altogether.  Writes are done asynchronously in a large sequential transfer.  This minimizes the access time latency and allows the file system to operate closer to the disk's maximum throughput rate.  As the diagram shows, the same information is written to disk: 4 inodes and 4 data blocks (2 directories, 2 files).  But it's written sequentially by appending to the log.   Data (both metadata like inode and the actual file data) is never overwritten in-place, just appended to the log.

This is clever and all but how do we get the data back?!?  In the traditional Unix FS the inodes are at fixed location(s).  Given inode number 123 it's easy to calculate its disk location with a little math, and once we have the inode location we can get the data blocks.  This doesn't work with LSF since inodes are not fixed--they're appended to the log just like the data blocks.  Easy enough, create an inode map that maps inodes to their locations.  Wait a second, how can we then find the location of the inode maps?  Finally, it's time to write to a fixed location, the checkpoint region.

The checkpoint region knows the location of the active inode maps.  At startup we read in the checkpoint region, load the locations of the inode maps into memory, then load the inode maps into memory.  From then on, it's all in-memory.  The checkpoint region is periodically written to disk (checked point).  Once we have the inode maps read requests behave much like the traditional Unix FS: lookup the inode, perform access control, get the data blocks.

In summary, read requests don't change much and we can leverage file cache to improve performance.  Write requests, however, show dramatic improvements, especially for frequent, small write requests, since we always write sequentially in large chunks.

But the story doesn't end quite yet.  If we always append, never overwrite in-place, we will eventually run out of space unless we can reclaim free space.  Reclaiming free space, that sounds like memory garbage collection in programming languages; and that's exactly what the LSF does, garbage collect.

Imagine that segments 5 and 6 have both live and dead blocks (files that have been deleted).  The segment cleaner (garbage collector) can compact segments 5 and 6 then copy only the live blocks into an available free segment.  Each segment has a segment summary block (not shown) with information about itself to help in this process (which blocks are dead, etc.).  Then it's just a matter of moving the links in the segment linked list to restore the order.  I'm of course hand waving here as things are more involved.  Like memory garbage collection it's in the details and optimizations that will determine if the system is performant.  Issues like garbage collecting long-live objects (data), when to run the collector, etc. emerge.

There you have it, the Log-structured File system.  Next time, the Log Structure Merge Tree.

Memcached for Dummies

The other day I was chatting with a colleague about Memcached.  Eviction policy came up, and I casually mentioned that Memcache isn't strictly LRU.  But a quick Bing search said Memcache is LRU, like this Wikipedia entry.  Hmm, I was 99.9% sure Memcache is not LRU, something to do with how it manages memory, but maybe I was wrong all these years.  After reading through some Danga mailing lists and documentation, the answer is, Memcached is LRU per slab class, but not globally LRU.  

So what does this exactly mean.  Imagine starting Memcached with these command-line arguments to override the defaults,

memcached -vv -m 1 -I 1k -f 3 -M

-vv
for verbose output

-m 1
maximum 1 megabyte cache

-I 1k
1 kilobyte (1024 byte) page size

-f 3
chunk size growth factor of 3 

-M
return error on memory exhausted (rather than removing items)
just to see things more explicitly

The output will be something like this,

slab class   1: chunk size        96 perslab      10
slab class   2: chunk size       288 perslab       3
slab class   3: chunk size      1024 perslab       1
<26 server listening (auto-negotiate)
<27 server listening (auto-negotiate)
<28 send buffer was 9216, now 5592405
<29 send buffer was 9216, now 5592405
<28 server listening (udp)
<28 server listening (udp)
<28 server listening (udp)
<28 server listening (udp)
<29 server listening (udp)
<29 server listening (udp)
<29 server listening (udp)
<29 server listening (udp)

The visual representation below may be helpful, 

We have a cache with a max memory limit of 1 megabyte.  This 1 megabyte of memory is divided into 1 kilobyte (1024 byte) pages.  These 1024 byte pages are assigned, as needed, on a first come, first serve basis, to the three slab classes.  Page assignment to a slab class is permanent.  The three slab classes are determined by the page size and the chunk size growth factor.  If you change the page size and/or chunk size growth factor you'll get a different slab class configuration.

With our settings, slab 1 has a chunk size of 96 bytes (the smallest, initial chunk size).  There are 10 chunks per page (11 chunks would be more than the 1024 byte page size) in slab 1.  Slab 2 has a chunk size of 288 (96 x 3 growth factor).  There are only 3 chunks per page in slab 2.  Finally, slab 3 has a chunk size equal to the page size and obviously only 1 chunk per page.

Each chunk can hold an item up to its size.  By item, I mean the key, the value and some overhead.  The item's size determines which slab it is stored in.  Small items, say 40 or 60 bytes, are put in slab 1.  Leftover storage is wasted.  That is, putting a 60 byte item in a 96 byte chunk results in 36 byte wasted space.  These 36 bytes are not available for other use.  Slab 2 holds items between 96-288 bytes.  Slab 3 holds items between 288-1024 bytes.  With our arguments, we could not store items larger than 1024 bytes.

So that's an overview of how Memcached is layed out.  Pages, chunks, slabs.  Now imagine we store a bunch of small items and a bunch of large items but no medium items until all pages from the page pool are used.   

Slab 1 might have 800 pages and slab 3 might have 200 pages (those numbers are not exact, won't add up).  Everything is good, until we try to store a medium size item.

Memcached will give us an out of memory error (or won't store the item  w/o the -M option) because slab class 2 has no available pages to use.  Pages from slab class 1 and slab class 3 can't be re-assigned to slab 2.  You can think of Memcached as having separate internal caches defined by the slab classes.  

Finally, this brings us back to the LRU question.  Since each slab class is essentially a separate cache, there is no global LRU, only slab class LRU.  The least recently used item won't get evicted for a new item if the items are not in the same slab class.  Depending on your storage/access patterns, you could end up with one slab class constantly evicting recently used items, while another slab having a bunch of old items that just sit around. 

Which brings me to another point, items/chunks are not actively reclaimed/expired.  Memached does not have a background thread that explicitly expires items, reclaiming used chunks for new items.  When a slab needs a chunk and there are no more pages, Memcache will look at the queue tail for items to evict.  Memcache will make a best effort to evict expired items (items you've explicitly set to expire after some time).  In scenario 1, item 2, an expired item, is evicted.  However, in scenario 2, item 1, which has not yet expired, will be evicted, even though item 4 would seem like the better candidate.  But since item 4 is not near the tail, Memcached stops looking and just expires item 1. 

Another example of leaky abstraction?  The Memcached API is very simple, straightforward.  But at a certain point, you need implementation knowledge to make sure things are behaving as expected.

It's All Garbage

Amazon.com says I bought Programming Ruby (2nd edition) on November 4, 2004.  Seven short years of Java later I'm finally putting it to use.  One immediate question is, how does garbage collection work in Ruby?  Is it a tracing or reference counting collector?  Is it generational, and if so, how many generations?  These questions eventually led me to an interesting paper by David Bacon, Perry Cheng and VT Rajan on A Unified Theory of Garbage Collection.

Universally, garbage collectors are viewed as either tracing or reference counting.  The Sun HotSpot VM, for example, is a tracing collector.  It traverses the object graph from the roots, finding reachable live objects and reclaiming unreachable dead objects.  PHP, on the other hand, uses reference counting to decide which objects can be safely garbage collected.  This table summarizes the typical characterization of each collector type,

	Tracing	Reference Counting
Collection Style	Batch	Incremental
Cost per Mutation	None	High
Throughput	High	Low
Pause Times	Long	Short
Real Time	No	Yes
Collects Cycles	Yes	No

The first observation is, once optimizations are added to the basic tracing and reference counting collectors, they begin to converge.  For example, with deferred reference counting there is a periodic scanning of stack references to reduce per-mutation cost.  A generational tracing collector, on the other hand, imposes a per-mutation overhead but gains shorter pause times.  So even though collectors are typically described as one or the other, we should really view them as hybrids.

The second interesting observation is, tracing algorithms are the duals of the reference counting algorithms.  Both types of algorithms share the same structure.

	Tracing	Reference Counting
Starting Point	Roots	Anti-Roots
Graph Traversal	Forward from roots	Forward from anti-roots
Objects Traversed	Live	Dead
Initial Reference Count	Low (0)	High
Reference Count Reconstruction	Addition	Subtraction
Extra Iteration	Sweep Phase	Trial Deletion

Tracing collectors start at the root, traverse foward, finding live objects.  Initially all reference counts are zero (an underestimate) but live objects have their reference count incremented to their true value (keeping a bit flag is just an optimization of actual count).  Reference counting collectors start from non-root objects, traversing forward to find dead objects.  Reference counts are initially high (an overestimation that includes references from dead objects) but decremented until the true reference count is obtained.  Ultimately, the difference is just the initial value (an underestimate or overestimate) and whether we increment or decrement to obtain the true reference count.

So that was interesting, but lets return my the original question about Ruby garbage collection and add a few other languages in for fun.  Here's a quick summary.  Don't quote me on it, corrections appreciated. 

Language	Garbage Collection (for reference/popular implementation - others may be available)
Erlang	tracing - per process (very small processes), compacting then generational optimization
Haskell	tracing - generational (3), 512KB nursery
Java	tracing - generational (2), serial, concurrent, concurrent + incremental
Perl	reference counting - does not handle cycles
PHP	reference countng  - 5.3 handles cycles w/ "on the fly" cycle detector, prior versions did not
Python	reference counting - handles cycles w/ tracing cycle detector
Ruby	tracing - non-generational
Scala	see Java

Causal Atomic Broadcast

Spent the other day reading up on ZooKeeper a little.  ZooKeeper is a distributed, open-source coordination service for distributed applications.  Out of the box ZooKeeper can be used for name service, configuration and group membership.  Building on ZooKeeper's primitives, you can create barriers, locks, queues, etc.

Sounds interesting enough, but what got me really interested was ZooKeeper's atomic broadcast, the guts of ZooKeeper.  Atomic broadcast is very closely related to consensus (apparently equivalent in certain asynchronous systems).  Both are fundamental problems in distributed systems.

So what exactly is atomic broadcast?  To answer this, lets work our way from Reliable Broadcast.

Reliable Broadcast

Reliable Broadcast is the weakest type of fault-tolerant broadcast.  Informally, if a correct process broadcasts a message then all correct processes eventually receive that message.  Reliable Broadcast doesn't impose any message delivery ordering.

FIFO Broadcast

FIFO Broadcast is reliable broadcast that satisifies FIFO Order.  If a process broadcasts message m₁ before message m₂, then no correct process delivers m₂ before it delivers m₁.  For example, if message m₁ is a deposit of $100 into your banking account and message m₂ is a subsequent withdrawal of $75, you most definitely want FIFO Broadcast, otherwise your bank will charge you an overdraft fee (on top of their ridiculous $5 ATM fee).

Causal Broadcast

Sometimes FIFO Order is not enough because FIFO ordering too limited in context (a single process).  You need Causal Order to guarantee that if the broadcast of message m₁ "happens before" or "causally precedes" the broadcast of message m₂, then no correct process delivers m₂ before it delivers m₁.

For example, imagine three processes a, b and c.  Process a broadcasts m_1a, "Banks to charge $5 ATM fee."  Process b delivers m_1a then broadcasts message m_1b, "That's outrageous!"  Without Causal Order, process c could deliver message m_1b before m_1a,

m_1b : "That's outrageous!"
m_1a : "Banks to charge $5 ATM fee."

which doesn't make sense (what is outrageous?).  Causal Order requires delivery of m_1a before m_1b.

Atomic Broadcast

Causal Order imposes a partial ordering in the system, so messages without causal relationships are logically concurrent and do not have any delivery order guarantees.  This can be problematic in some cases.  For example, imagine two replicated databases DB₁ and DB₂.  Process a broadcasts message m_1a, "deposit $100."  Process b broadcasts message m_1b, "charge 10% fee."  Since there is no causal relationship between the messages, this situation may arise,

DB₁ : $0 + $100 - ($100 * 10%) = $90
DB₂ : $0 - ($0 * 10%) + $100 = $100

which is obviously not desirably.

Atomic Broadcast imposes a Total Order on the system so that all messages are delivered in the same order, whatever that order maybe.  So in this example, it's either $90 or $100 but never $90 in one database and $100 in the other.

We can further classify Atomic Broadcast by the actual ordering it imposes.  FIFO Atomic Broadcast is then Reliable Broadcast that is FIFO Order and Total Order.  Causal Atomic Broadcast is then Reliable Broadcast that is Causal Order and Total Order.  Causal Atomic Broadcast is the strongest guarantee we've examined.

Summary

This diagram nicely summarizes Reliable Broadcast and the orderings above (taken from "A Modular Approach to Fault-Tolerant Broadcasts and Related Problems," which the above is basically a summary of).

So there you have, atomic broadcast.

Sequential Random Sampling

Time flies when you're having fun (even when you're not).  It's been more than a year since my last work related blog.  Writing about random computer science and programming topics is like going to the gym; once you get off the routine it's very easy to just sit on your literal and figurative ass.

For my first topic back I want to relay some sequential random sampling algorithms I came across this week.  It started out when we needed some random samples from the database.  Performance issues aside, MySQL lets you do

select column from table order by rand() limit n

to select n random rows from a table.  The randomness of the rand() function aside, someting troubled me about this approach.  Won't your results be skewed toward the lower rows when you get duplicate random values?

So I was searching around for some random sampling algorithms and ran across a few from the works of Jeffrey Vitter I found rather interesting.

Algorithm S

Sequentially go through N elements to select n random samples.  For each element generate an independent random variable U between 0 and 1 and test that NU > n.  If true, skip, otherwise select for the sample and decrement n.  In either case decrement N.

Algorithms A-D

These algorithms optimize Algorithm S by skipping elements.  Define a skip function S(n,N) that will tell us how many elements to skip.

Algorithm S and its optimizations are for sequential sampling where N is known.  But sometimes N is not known or it's prohibitive to determine N.  Then we turn to reservoir samping. 

Algorithm R

There is a reservoir R of n sample elements.  The invariant is that the reservoir is a random sample of all the elements we've processed thus far.  To maintain the invariant, as we sequentially process each element generate an independent random variable between 0 and the current element.  Then either put the current element into the reservoir or ignore it.

Algorithms X, Y and Z

Optimization of algorithm R so we can skip over elements, much like Algorithms A-D.

 

Tries, John Mitchell, Memcache and Read-Only PHP Sessions

Too busy with work to blog lately, but here are some random thoughts I've been meaning to write about. 

Burst Tries

Several prominent (Google ranking) articles on implementing autocomplete suggest using a trie data structure.  Unfortunately, none of those articles point out how horribly space consuming tries are.  A naive, non-compacting trie structure is exponential in space.  With an a-z alphabet you have 26 exponent word length nodes.  That's a lot of nodes.  If you want the best of both worlds, the memory requirement of a binary search tree and the speed of a trie, try the burst trie.  Burst tries: A Fast, Efficient Data Structure for String Keys by Steffen Heinz, Justin Zobel and Hugh E. Williams.

John Mitchell

In my blog on F-Bounded Polymorphism I forgot to credit John Mitchell as one of the authors of F-Bounded Polymorphism for Object-Oriented Programming.  This was purely accidental and has nothing to do with the fact that he's a Stanford guy.

Memcached

Memcached is awesome.  Locks, CAS, is there anything it can't do?  PHP's support for memcached makes PHP just barely tolerable as a language.  The "M" in LAMP needs to be officially changed to Memcache, not MySQL.

PHP

What a mess of a language.  It has deviated too far from its original goals.  Really miss type safety, because, "after all, run time is a little late to find out whether you have a landing gear." (Eiffel dude)  Really miss all of Java's built in libraries.  I find it incredible that no one using PHP has had the need for a red-black tree, because I can't seem to find an implementation of one.  I do like PHP's request processing model better than Java's, though.  Adios threads, synchronized, volatile.   

Read Only Sessions

I find it really puzzling that PHP doesn't have a notion of read-only sessions.  Seems like this would be a no-brainer considering that PHP web apps are typically read dominant.  And you can't write your own quickly because there's no function to decode a session string, except to decode it and overwrite  the current session.  Someone did provide a function to decode the session string here, but I'm not sure if I fully trust it to decode everything correctly.

Think that's about it for now.

Pure Inefficiencies

Skimmed a paper titled "Pure versus Impure Lisp" by Nicholas Pippenger the other day.  Impure Lisp dialects allow mutations.  Pippenger wanted to know if pure Lisp, without mutation, was less "powerful".  Under two conditions he showed the following,  

A computation in impure Lisp upper bounded by O(n) is lower bounded in pure Lisp by big-omega n log n.  Basically, given the same problem there's a theoretical lower limit to pure Lisp's efficiency compared to impure Lisp. 

But then the guys at FP Lunch lead me to a follow-up paper titled "More Haste, Less Speed: Lazy Versus Eager Evaluation".  In it, Bird, Jone and de Moor showed that if you changed the pure Lisp evaluator to pure and lazy as oppose to Pippenger's original pure and eager then you can get the same linear time as the impure program.  Interestingly enough, the authors noted that lazy evaluation is often implemented with mutations behind the scenes (via memoization), so it's really a discussion of restricted mutation.  This is along the lines of an earlier posting I made about the problem with immutability and how compilers can, behind the scenes, solve some of the inefficiencies of immutability, but then it becomes a philosophical debate on what it really means to be immutable (or pure).

And that concludes another installment of interesting topics I'll never need to know.

Fail Fast, Debugging and Systems that Never Stop

If you're a Java guy you're probably familiar with the phrase "fail fucking fast" in the context of Iterators (I added the fucking part).  But fail fast is much more than just iterators, it's a general design principle--and a very important one at that. 

Jim Gray on fail fast: "it [the process] should either function correctly or it should detect the fault, signal failure and stop operating."  You can replace "the process" with component, class, etc.  Whatever you designate as your logical unit, the fail fast principle remains.  What you absolutely don't want to do is detect the fault, don't signal failure and continue.  This is why swallowing exceptions is one of my all time pet peeves.  Fail fast is often described in terms of fault detection latency, the time between initial error detection and the fault.  You want your latency to be small. 

There are two advantages to failing fast. First, easier debugging and analysis.  It complicates things greatly if your code detects errors but continues.  Eventually something will go wrong but now you can't easily track down the root cause.  I recently worked with a component (one that shall remain nameless) that doesn't follow the fail fast principle.  During initialization the component knew it was missing a configuration file but instead of halting it continued on.  When the component was finally invoked things obviously did not work, but the root cause was not obvious.  Ended up wasting two days tracking down the root cause, when it really should have taken 30 seconds. 

Second, ability to build "systems that never stop".  Failing fast is so important to building highly available systems that Joe Armstrong talks about it at great lengths in his presentation on "systems that never stop (and Erlang)."  In this presentation he presents 6 laws,

1. Isolation
2. Concurrency
3. Failure Detection
4. Fault Identification
5. Live Code Upgrade
6. Stable Storage

Without failure detection you can't fail fast, and if you can't fail fast you can't achieve isolation.  Real world example: Amazon S3's massive outage last year.  A huge embarrassment to Amazon's otherwise great cloud stack.  Their code didn't have adequate failure detection, allowing a single corrupt bit to propagate throughout the system.  The result was hours of downtime while engineers scrambled.  If Amazon had been able to detect the single corrupt bit then they could have isolated the failing component instead of letting the error bring down the entire system.

Few of us will be coding S3 like systems, but it doesn't mean we can't follow the fail fast approach.  It will make debugging easier and just might prevent similar embarrassments.  I think some programmers don't like to fail fast because they worry they'll be blamed for the failure, so just pretend things are good and pray nothing bad happens downstream.  I suppose it depends on how much you believe in God. 

WTF is F-Bounded Polymorphism

Here's an example of where I read random articles just because the title is very catchy: F-Bounded Polymorphism for Object-Oriented Programming by Peter Canning, William Cook, Walter Hill, Walter Olthoff and John Mitchell.  Polymorphism is already confusing enough.  Just look at the Wikipedia entry on type polymorphism: "this article may be confusing or unclear to readers".

There's parametric polymorphism, let-polymorphism, impredicative polymorphism, ad-hoc polymorphism, intensional polymorphism and subtype polymorphism.  So WTF is F-bounded polymorphism then.  If there's no Wikipedia entry does it really exist?  Despite no mention in Wikipedia F-bounded polymorphism is pretty important and I'm using it everyday without knowing it.

Lets start with "bounded quantification".  With bounded quantification you can do something like this

Moveable {
 Moveable move(int x, int y)
}

Moveable moveMeOneInch(Moveable m) {...}

The method moveMeOneInch takes in some a Moveable, moves it one inch, and returns a Moveable.  It is polymorphic and will work on Cars, Trains, Points--anything that's Moveable.  All good, except we'll have to do some unsafe type casting.

Car c = ...
Car movedCar = (Car) moveMeOneInch(c);

But with Java 5 we can do something like this

<T extends Moveable> T moveMeOneInch(T m) {...}

Car c = ...
Airplane p = ...

Car movedCar = moveMeOneInch(c);
Airplane movedAirplane = moveMeOneInch(p);

and get the type safety we want, because "run time is a little late to find out whether you have a landing gear".  What we've done is created an "F-bound".

F-Moveable[t] = { move : int, int -> t }
F-Moveable[Car] = { move : int, int -> Car }
F-Moveable[Airplane] = { move : int, int -> Airplane }

Note the type appears on both sides. 

Here's a real world example.  The Collections utility class has a max method that takes in a Collection of Comparables and return the max of the collection.

public static <T extends Object & Comparable<? super T>> 
 T max(Collection<? extends T> coll) {...}

//Integer implements Comparable<Integer>
Collection<Integer> ints = ...
Integer i = Collections.max(ints);

Here we bound the type of the collection and the type is part of the bound for Comparable.  A collection of integers, and integers are comparable to integers.

That's F-bounded polymorphism in a nutshell.  Now you can say, "yea, I like Java, it supports F-bounded polymorphism."