jdbartlett | mediumtext

TXJS Ear-Prickings & Burnings

2010-06-10T00:00:00-07:00

This post’s a slapdash review of the TXJS sessions I attended, adapted from my Moleskinings — things that pricked my ears and may burn the speakers’. If you weren’t able to attend, you may find the conference’s website more useful, where slideshows and videos are being accumulated as they’re uploaded.

@tomocchino: Front End Abstractions at Facebook

“Early flushing” isn’t a phrase I’d have elected to hear first thing after Friday night’s party ;) but Facebook’s doing some awesome stuff and I’m embarrassed I hadn’t properly looked into flushing techniques before — it’s even on Yahoo’s best practices list.

Facebook actually sends a skeleton of the page initially, and fills in the blanks progressively, using JavaScript to populate the skeleton as the server completes its tasks. The overall effect is a much faster experience for end-users, who can still view parts of the page even while it’s loading. Another Facebook Engineer very recently posted an in-depth article on this, and Stoyan has a good post on flush() itself.

I also liked Facebook’s live()like method of looking for mousedowns, checking to see if the event applied to an anchor (and also for some other conditions), and then attaching the click event handler if true.

@jeresig: JavaScript on the Mobile Web

“We’re on the cusp of the Golden Age of mobile web development.”

I’d forgotten all about playing with WML as a kid in 1999, but it came flooding back to me in a flash when John said that. Little over a decade later: Mobile Safari & Android. Pretty amazing, really.

But for JavaScript, the mobile web’s a rough place. John knows. But this session wasn’t just his war stories from working on jQuery Mobile, it was useful, relevant information for anyone who wants to understand how to target websites for mobile devices. He’s doing an incredible amount of work providing us, not just with a library that works on major supportable browsers, but with the tools to understand precisely what works, precisely what devices we need, and even grading devices and browsers so we can perform triage according to our needs and budgets.

A few things that stood out to me:

StatCounter and Gartner are the better sources for mobile browser stats.
But stats don’t differentiate between browser versions, or even between Opera Mini & Opera Mobile, which are completely different browsers.
Test Swarm is very very useful for automatic UI testing.
…but interaction testing must be done on a physical device. Even emulators are no substitute.

John’s releasing more information on jQuery Mobile very soon, including (I believe) his list of 13 devices (with a cost breakdown), and details on browser support and browser popularity.

@joemccann: Rapid Prototyping with JavaScript

Joe made a good case for JavaScript as a tool for prototyping apps. While people are using PhoneGap and Titanium to develop production applications, they and other JS tools are also useful for playing with desktop and mobile interfaces; for prototypes.

But Joe really caught my attention when he started talking about YQL, something that’s been on my “to investigate” list for too long. He demonstrated YQL’s ability to “query” a specific URL (and other data sources) in a SQL-like syntax and get back a JSON representation of your results; a sort of screen-scraper for the internet. Its application for prototyping is the rapid accumulation of oodles of real-life test data. Joe’s example was a mobile web app he built in 10 minutes that scraped crockfordfacts.com and worked on Android and iPhone.

Earlier this year, @codepo8 caught my eye with a post about querying the Guardian Data Blog using YQL, and the amount of data and possibilities that blog presents, with YQL’s help, are phenomenal.

@paulirish: 10 Things I Learned from the jQuery Source

Paul’s and Peter’s talks were both great for the many intermediate-but-intimidated JS users out there. Most of us started using libraries (Prototype, jQuery, Dojo, etc.) before we properly understood how they’re structured, or even how they work. Very often, we want to know precise information about something that jQuery does — information that’s only available in the source. Even if we don’t think we want to know, possibilities open up by simply reading the source (ah, jQuery devotionals) and learning its secrets.

I could write several blog posts trying to summarize the session, but the main message was that jQuery’s unminified source isn’t inscrutable. This talk’s a great leg-up for the many, many jQuery users who want to scrute it.

@stubbornella: The Top 5 Mistakes of Massive CSS

Something Nicole really stressed: "If there were a “CSS: The Good Parts”, specificity would be an Awful Part."

I only recently started using YSlow, and the first thing I hit upon was overqualified selectors, specifically “tagname.classname”, a habit I picked up from tweaking jQuery Sizzle selectors for performance. But Nicole made the case that CSS should describe visual patterns, and not just skins dependent on HTML for context.

Nicole talked about how CSS becomes bloated and unmanageable, usually by thinking in terms of stylesheets that reflect semantic markup instead of visual patterns. I’m sure she’ll have slides up soon, but here are some points that stood out to me:

Avoid selectors that target ID’s. You’re looking for visual patterns, not elements.
Avoid browser-targeting classes (e.g., .ie). Developers may not see these styles in Firebug, and may change the class it overrides in a way that breaks your site on the targeted browser.
Use grep to find patterns that have been overlooked:
- Colors that are commonly declared often belong to the same visual pattern.
- h1-h6 get overly declared. You should be able to merge these.
- Lots of floats in the CSS is an indication that you need to use grids.

Nicole also has a very cool sounding alternative to the overflow:hidden technique, that I hope she’ll blog about soon.

@sh1mmer: JavaScript Everywhere! A 100% JavaScript Web Stack

Slides from Tom’s talk are online.

“Progressive enhancement is free.”

Just one of the exciting possibilities of Node is code re-use between the server and client. Tom talked about YUI specifically, and why he feels that it’s a particularly good candidate for code reuse since so many of its modularized components are useful outside the context of the DOM.

But since I have no previous experience with YUI itself, Tom really caught my attention when he started talking about using Node to render HTML through DOM methods via jsdom and node-htmlparser, which Dav Glass supports in his YUI3 bootstrapper for Node. As Tom said, this makes progressive enhancement good as free. He demonstrated the YUI calendar control rendered by the server. With SSJS, users could see and interact with the calendar before the page had even finished loading. Another possibility Tom mentioned would have Tom Mocchino excited: using JavaScript to pull only the data for page requests, and render it with templates; through progressive enhancement, the server could draw complete pages if requested by direct URL’s.

@kangax: Dive into ECMAScript 5

Why, yes, it will be a while before we can safely use ES5 in all browsers. (To corrupt Crockford: IE 6, 7, 8, and 9 MUST DIE.) But we’ll see JSC & V8 support long before then, and it pays to be aware of any nice or nasty surprises, like arguments.callee being gone; yes, even .caller.

So, a confession: I haven’t paid enough attention to ES5, resting on my laurels knowing it’d be an age before I could use it on the front end. Unfortunately, a lot of Juriy’s talk went over my head at the time. If you have slides of it, please tweet me.

@phiggins: It’s Just JavaScript

Slides from Peter’s talk are online.

I thought this would be “10 Things I Learned from the Dojo Source”, but Peter took a different approach entirely. A main message of his session was that playing with JavaScript is the fun path to grokking it. He took us through some common language patterns (curring & binding and variations thereof, etc.) in the context of a library he’s been working as an experimental side-project. With a nod to Paul, he also covered a pattern for “duck punching” methods. These are conceptually complex patterns, and it’s helpful to have practical examples of their application. I read the section on currying several times in The Good Parts, and never really understood why I’d want to use it. Helpful session.

@getify: Web Performance & UI Architecture

I wanna use Node nao! But our company’s hugely invested in a Not-Node architecture. Among other things, Kyle presented a CVC (Client-View-Controller) architecture as it would apply to a mostly (or fully) JS web stack. Basically: the architectures we’re already using are capable of kicking out JSON, and many of us already build JSON API’s for our apps. Why not reduce our apps to black boxes that read JSON requests from and return JSON to JavaScript-based UI controllers & views? That way, we’ll still have the advantage of sharing the libraries we’d want to share between the server and the client, and we’d have a better separation between our application model and our views & controllers.

Kyle also talked a bit about LABjs, which I began using recently and plan to use for pretty much every project I start. Very useful to know that 2 or 3 .js files seems to be the sweet spot for parallel downloads.

Also

All this, and a Facebook sponsored before-party, a Media Temple sponsored open bar at lunch, and a Google sponsored .party:after.

An understatement: I learned a lot from TXJS. Equally valuably, I learned about a lot — things that’d never before entered my sphere of awareness; and I can’t learn about something until I know I don’t know it. The speakers I spoke to were magnanimous and passionate, and I think there’s something valuable too about being able to pin personalities to some of the tools and libraries I’ve been using and articles and books I’ve been reading these past few years. Aside from a couple of Bar Camp events, TXJS was my first proper tech conference, and I came away from it with an overwhelmingly positive perspective. Thanks again, @rmurphey and the entire yayQuery team, and of course all the speakers and sponsors and attendees.

BayesianAverage CakePHP plugin Performance Tests

2009-12-05T00:00:00-08:00

The BayesianAverage CakePHP plugin was written with performance as a consideration and documented to help developers avoid performance problems. However, when the values of C and m are left for the behavior to calculate, two queries must be run that present a performance bottleneck.

I decided to test the performance of these queries for medium-large data sets, so I’d know what to expect using the plugin in a production environment.

Environment & Method

These tests were all done locally on K9, my MacBook Pro: 2.4 GHz Core 2 Duo, 2 GB RAM, running MySQL Server 5.1.37.

This is the basic structure of the items table:


CREATE TABLE `items` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `ratings_count` int(7) unsigned NOT NULL,
  `mean_rating` decimal(5,4) unsigned NOT NULL,
  `bayesian_rating` decimal(5,4) unsigned NOT NULL
  PRIMARY KEY (`id`)
) ENGINE=MyISAM;

Neither of the “problem” queries examine the actual ratings table, so I won’t go into its structure except to say that about 125 million ratings were spread across 50,000 items in my largest test data set.

I decided to run my tests twice: against the basic table above (average row size: 25 bytes), and against a wider (but otherwise identical) table filled with random strings (average row size: 1.4 kilobytes). You can download the test template for the wider table, complete with data, from my drop.io.

I ran eight tests on both tables (25 byte rows and 1.4 k rows) for both “problem” queries. I ran each test 10 times and recorded the average performance as well as the best and worst performance. For the rest of this post, I’ll only discuss the average performance, but you can see the the other results in this Google Docs Spreadsheet.

Calculating C & m

The first “problem” query runs every half hour when someone adds or modifies a rating, and recalculates the values to cache for C and m if they aren’t set explicitly in the model. If the recalculated values differ from the cache by more than 10%, the cache is replaced, otherwise the behavior keeps the cache and waits another half hour (and until someone adds or changes another vote) and tries again. This can be useful if you have a small, volatile data set (e.g., a review site that’s only just launched), but as your data set grows, these values will become less volatile and you should consider making C and m explicit constants within your model to avoid performance problems.

SELECT AVG(`Item`.`ratings_count`) C, AVG(`Item`.`mean_rating`) m FROM `items` AS `Item` WHERE `Item`.`ratings_count` > 0 LIMIT 1;

Here’s how the query performed with my test data:

No of Items	Time w/25 byte rows	Time w/1.4 k rows
50k	41.8 ms	177.8 ms
30k	29.92 ms	122.4 ms
20k	26.07 ms	96.72 ms
10k	18.97 ms	69.38 ms
5k	13.58 ms	55.71 ms
2.5k	13.77 ms	52.26 ms
1k	12.43 ms	45.14 ms
500	11.69 ms	43.1 ms

As an experiment, I tried creating an index on the relevant fields (KEY `ratings_count` (`ratings_count`,`mean_rating`)), which reduced query time by more than 100 ms for the wider table at 50,000 rows.

Recalculating Items

The second query that could present an even more serious performance bottleneck updates the bayesian_rating for all items when the cache values for C and m are updated or created. Again, this query never runs if C and m are set manually, and only runs after the cache is updated or created. As your data set grows, C and m will become less volatile, meaning recalculated values will differ from the cache by less than 10%, and this query is unlikely to run.

UPDATE `items` AS `Item` SET `Item`.`bayesian_rating` = (`Item`.`ratings_count` / (`Item`.`ratings_count` + 2518.8187)) * `Item`.`mean_rating` + (2518.8187 / (`Item`.`ratings_count` + 2518.8187)) * 2.99895026 WHERE `Item`.`ratings_count` > 0;

Here’s how the query performed with my test data:

No of Items	Time w/25 byte rows	Time w/1.4 k rows
50k	220.7 ms	966.6 ms
30k	138 ms	680.7 ms
20k	94.38 ms	539 ms
10k	52.64 ms	407.3 ms
5k	33.81 ms	334.7 ms
2.5k	22.92 ms	297.7 ms
1k	15.56 ms	276.8 ms
500	12.51 ms	269 ms

Analysis & Recommendations

In a case where all bayesian ratings have to be recalculated, both the select and update queries must be run in the same request. With the longest, widest data set I tested (50,000 items; 1.4 k per item), the two queries together took just over a second to complete in a MyISAM table. I think that’s unacceptable given the environment; in fact, all the results for the 1.4 k/row table made me cringe a little. That said, the second query would run extremely rarely — probably never — for a long items table. The longer the list of voted items, the less likely it is you’ll have to recalculate all Bayesian averages.

These are my recommendations:

Once you’ve set C and m within your model, these performance concerns no longer apply. Set them when you can. If your results look wrong after setting them, you can remove the setting and the data will fix itself next time a vote is added. C is the average number of votes you expect per item, and m is the average rating an item is given (the median rating works in a pinch; e.g., “3” for a 5-star rating).
Create a single index for the two fields ratings_count and mean_rating. I found this improved the calculation of C and m dramatically.
If you have a wide “items” table and want to use BayesianAverageable in “magic” mode, you may want to do some normalization for the sake of performance.
If you have a wide “items” table and normalization isn’t an option, you may want to separate the ratings_count, mean_rating, and bayesian_rating fields into an item_averages table and add 'itemModel' => 'ItemAverage' to BayesianAverageable’s settings from your model.
Make sure caching is not disabled on your production environment. (The line Configure::write('Cache.disable', true); should be commented out in /app/config/core.php)
Set up a dedicated cache configuration to make sure the cache for C and m isn’t deleted.

A how-to for that last recommendation: CakePHP’s default cache configuration is set to expire after an hour. To add another cache configuration, open /app/config/core.php and add the following:


Cache::config('annual', array(
  'engine' => 'File',
  'duration'=> '+1 year',
));

Tell BayesianAverageable to use this Cache configuration instead of the default through the ‘cache’ setting:


var $actsAs = array('BayesianAverage.BayesianAverageable' => array(
  'fields' => array('itemId' => 'item_id'),
  'cache' => array(       // <=
    'config' => 'annual', // <= lookit!
  ),                      // <=
));

This should stop the cache file containing C and m from expiring, further decreasing the chances you’ll have to recalculate them.

For my part, I’m going to modify the way the “items” table is updated so that the query is either given a LOW_PRIORITY or run in batches so that select operations can continue. I’m also going to make it easier to delegate the “problem” queries to a shell task so they don’t delay a user’s request. Finally, I’ll update the plugin’s documentation to reflect the above recommendations.

Working with Time Zones in CakePHP

2009-08-27T00:00:00-07:00

Rule #1 of working with time zones is: don’t have users pick abbreviations like “GMT”. Instead, have them select their location or zoneinfo zone name. Abbreviated time zones are fickle. Look at England for example: its abbreviated time zone is currently “BST”, and in a few months it’ll be “GMT”, but its zone name is always Europe/London.

Here’s a helper to produce a $form->inputable array of times for various locations in the pattern “4:20 PM – New York City, United States”.

 1 <?php
 2 class TimezonesHelper extends AppHelper {
 3 	
 4 	function show() {
 5 		$zones = array(
 6 			'Pacific/Apia'             => 'Apia, Upolu, Samoa',                      // UTC-11:00
 7 			'US/Hawaii'                => 'Honolulu, Oahu, Hawaii, United States',   // UTC-10:00
 8 			'US/Alaska'                => 'Anchorage, Alaska, United States',        // UTC-09:00
 9 			'US/Pacific'               => 'Los Angeles, California, United States',  // UTC-08:00
10 			'US/Mountain'              => 'Phoenix, Arizona, United States',         // UTC-07:00
11 			'US/Central'               => 'Chicago, Illinois, United States',        // UTC-06:00
12 			'US/Eastern'               => 'New York City, United States',            // UTC-05:00
13 			'America/Santiago'         => 'Santiago, Chile',                         // UTC-04:00
14 			'America/Sao_Paulo'        => 'São Paulo, Brazil',                       // UTC-03:00
15 			'Atlantic/South_Georgia'   => 'South Georgia, S. Sandwich Islands',      // UTC-02:00
16 			'Atlantic/Cape_Verde'      => 'Praia, Cape Verde',                       // UTC-01:00
17 			'Europe/London'            => 'London, United Kingdom',                  // UTC+00:00
18 			'UTC'                      => 'Universal Coordinated Time (UTC)',        // UTC+00:00
19 			'Europe/Paris'             => 'Paris, France',                           // UTC+01:00
20 			'Africa/Cairo'             => 'Cairo, Egypt',                            // UTC+02:00
21 			'Europe/Moscow'            => 'Moscow, Russia',                          // UTC+03:00
22 			'Asia/Dubai'               => 'Dubai, United Arab Emirates',             // UTC+04:00
23 			'Asia/Karachi'             => 'Karachi, Pakistan',                       // UTC+05:00
24 			'Asia/Dhaka'               => 'Dhaka, Bangladesh',                       // UTC+06:00
25 			'Asia/Jakarta'             => 'Jakarta, Indonesia',                      // UTC+07:00
26 			'Asia/Hong_Kong'           => 'Hong Kong, China',                        // UTC+08:00
27 			'Asia/Tokyo'               => 'Tokyo, Japan',                            // UTC+09:00
28 			'Australia/Sydney'         => 'Sydney, Australia',                       // UTC+10:00
29 			'Pacific/Noumea'           => 'Nouméa, New Caledonia, France',           // UTC+11:00
30 		);
31 		$dateTime = new DateTime('now');
32 		foreach($zones as $zone => $name) {
33 			$zoneObject = new DateTimeZone($zone);
34 			$dateTime->setTimezone($zoneObject);
35 			$zones[$zone] = $dateTime->format('g:i A - ').$name;
36 		}
37 		return $zones;
38 	}
39 	
40 }
41 ?>

Call it from your view like this:

1 <?php e($form->input('time_zone', array(
2 	'options' => $timezones->show(),
3 	'default' => 'US/Eastern',
4 ))) ?>

Rule #2 is have your entire app and database work from one time zone, applying offsets only when interacting with users (e.g., in view files). You can go with your server’s default time zone, but if you’d like to secure your app’s use of UTC, follow these steps:

Getting the app itself to use UTC is easy: add the line date_default_timezone_set('UTC'); toward the top of /app/cofig/bootstrap.php.
Having MySQL report dates in UTC—and if you followed the first step, this one is important when you SELECT NOW() or do any date math—is a little more involved. I did it by copying /cake/libs/model/datasources/dbo/dbo_mysql.php to /app/models/datasources/dbo/dbo_mysql.php and adding the line $this->_execute("SET time_zone = '+00:00'"); to DboMysql::connect, just after it sets the encoding (line 387 in the current stable version of CakePHP 1.2). I was tempted to run the query directly from AppModel instead, but I’m not sure how robust that solution would be.

Again, the above steps are optional. Whatever time zone your app uses, you’ll need the current user’s GMT/UTC offset for the “userOffset” parameter in CakePHP’s Time helper. You may be tempted to calculate the value of this offset and store it in the database for each user, but remember daylight savings: UTC offsets aren’t static, so generate them in an afterFind (retrieve) instead of a beforeSave (create, update):

 1 <?php
 2 class User extends AppModel {
 3 
 4 	function afterFind($results) {
 5 		foreach ($results as $i => $user) {
 6 			$user_zone = new DateTimeZone($user['User']['time_zone']);
 7 			$user_time = new DateTime('now', $user_zone);
 8 			$results[$i]['User']['utc_offset'] = $user_zone->getOffset($user_time)/60/60;
 9 		}
10 		
11 		return $results;
12 	}
13 
14 }
15 ?>

If you use AuthComponent and the above afterFind, the current user’s UTC offset will be stored in Session.Auth.User.utc_offset, so you can easily apply its inverse before handling user input.

The above methods sacrifice performance for versatility and reliability. For scalability, you may want to cache UTC offsets, perhaps directly in the user table. But some variation on the above will give you the greatest amount of accuracy for the greatest number of time zones.

YourMom hasAndBelongsToMany

2008-07-28T00:00:00-07:00

One of my first tasks in CakePHP was to produce a paginated list of blog posts with each post’s tags on the same page. A straightforward couple of SQL queries would’ve done the job nicely, I kept reminding myself over the many hours wasted stumbling through poorly-structured documentation as I missed milestone deadlines. I was doing something very wrong.

Wu Wei is very important when you start off with a new framework. Your preconceptions will slow you down, especially if you’re very experienced with the framework’s language, or you’ve enjoyed another framework in the same language. When you find yourself thinking something as popular as CakePHP was made wrong or its behavior fails some expectation, the real problem is probably a prejudice on your part. Those carefree days of CodeIgniter, that Golden Age of frameworkless ignorance, are leading you to think Cake should act according to your expectations. Abandon that preconception and suddenly you’re free to swim with the flow of your framework instead of against it. Yes, in another metaphor I’d be asking you to drink the Kool-Aid, but not all Kool-Aid is poisoned/grape flavor. (Note: grape flavor is evil.)

The answer to my proximate problem wasn’t really in the manual. I didn’t find it in any other blogs, either. I found it by ignoring my expectations and paying attention to what I was writing in context of Cake, not PHP.

Here’s what I added to my PostsController::index:

1 <?php
2 $this->Post->PostsTag->bindModel(array(
3     'belongsTo' => array('Post'),
4 ));
5 $this->set('posts', $this->Post->PostsTag->find('all', array(
6     'recursive' => 2,
7     'group' => 'PostsTag.post_id',
8 )));
9 ?>

The relationship between PostsTag and Post doesn’t occur automatically, it must be stated explicitly. A little recursion then brings in all the missing post tags. If a Post has more than one tag, you’ll see it duplicated accordingly in your results set; easily solved with a little GROUPing. I’m doing straight find()s for these examples, but Cake makes it trivial to add pagination.

Let’s say you want to do the same thing—produce a list of Posts with Tags for each post—but you only want to display those Posts which have a certain tag. You can do pretty much the same thing, adding Tag to your bindings:

 1 <?php
 2 $this->Post->PostsTag->bindModel(array(
 3     'belongsTo' => array('Post', 'Tag'),
 4 ));
 5 $this->set('posts', $this->Post->PostsTag->find('all', array(
 6     'conditions' => array('Tag.name' => 'CakePHP'),
 7     'recursive' => 2,
 8     'group' => 'PostsTag.post_id',
 9 )));
10 ?>

You’ll note I’ve kept the GROUP in there. It’s unlikely you’ll allow users to give posts the same tag twice, but you may want to specify an OR condition, for example, in a simple tag-or-title search:

 1 <?php
 2 $this->Post->PostsTag->bindModel(array(
 3     'belongsTo' => array('Post', 'Tag'),
 4 ));
 5 $this->set('posts', $this->Post->PostsTag->find('all', array(
 6     'conditions' => array(
 7         'OR' => array(
 8             'Tag.name' => 'CakePHP',
 9             'Post.title LIKE' => "%CakePHP%",
10         ),
11     ),
12     'recursive' => 2,
13     'group' => 'PostsTag.post_id',
14 )));
15 ?>

One final note: if you’d like to avoid the constipation of binding directly from the controller, set up an expects() method within the PostsTag model, which you’ll have to create.

By the time I realized all this, I’d settled for a clunky, straight-SQL solution that’s already causing all sorts of unnecessary condition-checking in my view. While I’ve been swimming against the flow of the framework, my poop has been floating downstream and piling up under the sensitive noses of industrious, dam-building beavers. If I’d stopped thinking in terms of my existing skillset and instead become the uncarved block, I could be enjoying a delicious slice of Cake instead of fishing turds out my code. To paraphrase the ancient Taoist philosopher, Cypher:

You know, I know this cake doesn’t exist. I know that when I put it in my mouth, the Matrix is telling my brain it is icing-coated and delicious. Also, its documentation is very well-structured and explains things quite thoroughly without any vague or contradictory statements. Er, where was I?

PS: CakePHP is made of candy.

Tree Drawing with the Adjacency List Model

2008-01-15T00:00:00-08:00

Let’s not fake piety, we’ve all of us stuffed a few hierarchies into the adjacency list model. It’s so easy to add parent_id to the end of any table, and the performance issues seem negligible in small data sets. It’s only when we’re grabbing data to draw the hierarchical tree it represents that we maybe worry about recursion’s inherent performance drawbacks. For example, you’ve probably seen a method like this:

 1 <?php
 2 function get_children($parent) {
 3     $result = mysql_query("SELECT id
 4         FROM family
 5         WHERE parent='{$parent}'");
 6     while($child = mysql_fetch_object($result)) {
 7         $children[$child->id] = get_children($child->id);
 8     }
 9     return $children;
10 }
11 ?>

One obvious problem is that this function runs a query for every single node it discovers. Another is that the amount of recursion this function produces depends, not on the size of your data set, but on the complexity of the hierarchy your data represents; the more branches your tree has, the deeper its recursion goes. Even if you have a small number of rows such that preorder tree traversal seems overkill, the complexity of your tree may still demand a more efficient artist than get_children. I’d like to propose one alternative for producing a complete tree.

Here’s my data: two families of the animal kingdom:

Hapalemurinae
- Hapalemur
  - Hapalemur Alaotrensis
  - Hapalemur Aureus
  - Hapalemur Griseus
- Prolemur
  - Prolemur Simus
Lemurinae
- Eulemur
  - Eulemur Coronatus
  - Eulemur Fulvus
  - Eulemur Macaco
  - Eulemur Mongoz
  - Eulemur Rubriventer
- Lemur
  - Lemur Catta
- Varecia
  - Varecia Rubra
  - Varecia Variegata

To help emphasize the concept I’m promoting, I’m using taxonomic names as IDs and parents in the $family array I’m using to represent this data:

 1 <?php
 2 $family = array(
 3     array('id' => 'Eulemur', 'parent' => 'Lemurinae'),
 4     array('id' => 'Eulemur Coronatus', 'parent' => 'Eulemur'),
 5     array('id' => 'Eulemur Fulvus', 'parent' => 'Eulemur'),
 6     array('id' => 'Eulemur Macaco', 'parent' => 'Eulemur'),
 7     array('id' => 'Eulemur Mongoz', 'parent' => 'Eulemur'),
 8     array('id' => 'Eulemur Rubriventer', 'parent' => 'Eulemur'),
 9     array('id' => 'Hapalemur', 'parent' => 'Hapalemurinae'),
10     array('id' => 'Hapalemur Alaotrensis', 'parent' => 'Hapalemur'),
11     array('id' => 'Hapalemur Aureus', 'parent' => 'Hapalemur'),
12     array('id' => 'Hapalemur Griseus', 'parent' => 'Hapalemur'),
13     array('id' => 'Hapalemurinae', 'parent' => ''),
14     array('id' => 'Lemur', 'parent' => 'Lemurinae'),
15     array('id' => 'Lemur Catta', 'parent' => 'Lemur'),
16     array('id' => 'Lemurinae', 'parent' => ''),
17     array('id' => 'Prolemur', 'parent' => 'Hapalemurinae'),
18     array('id' => 'Prolemur Simus', 'parent' => 'Prolemur'),
19     array('id' => 'Varecia', 'parent' => 'Lemurinae'),
20     array('id' => 'Varecia Rubra', 'parent' => 'Varecia'),
21     array('id' => 'Varecia Variegata', 'parent' => 'Varecia'),
22 );
23 ?>

This still comes quite close to the result you might expect from a MySQL query.

Here’s the recursion-free method I’m proposing:

 1 <?php
 2 $branches = array();
 3 $tree = array();
 4 
 5 foreach($family as $child) {
 6     extract($child);
 7 
 8     if(!isset($branches[$id]))
 9         $branches[$id] = array();
10 
11     if(!empty($parent)) {
12         if(!isset($branches[$parent]))
13             $branches[$parent] = array();
14         $branches[$parent][$id] = &$branches[$id];
15     }
16     else $tree[$id] = &$branches[$id];
17 }
18 ?>

The results are stored in two arrays: $branches, which contains individual branches of the hierarchy indexed by parent; and $tree, which collects all branches in the context of a complete tree. print_r($tree) and you’ll see the whole structure; print_r($branches['Hapalemurinae']) and you’ll see only the children of Hapalemurinae.

In the real world, this code would be more complex—each node probably having more properties than its ID—but the underlying principle of assigning nodes to the tree by reference can be used to create a relatively inexpensive serialize()d tree-caching routine for small, complex data structures.