Breadth is sometimes better than depth

re: Breadth is sometimes better than depth

Clinton Pierce — Mon, 27 Sep 2004 18:51:00 GMT

Back in the day, many many moons ago when the web was young and I had more time than common sense (c. 1995): I worked for a Large Domestic Auto Manufacturer that was beginning to experiment with putting documentation and instructions onto an internal web. The problem was that this largely unoffical web didn't have any kind of search facility. An "official" search solution was still many months away.

Our group had a good network pipe, some spare unix boxes, and a dangerous amount of Perl knowledge.

So I built my own.

At its heart was a crawler and an indexer. The indexer was largely uninteresting as it pulled apart html pages, threw away stopwords, and built tables in the filesystem based on hashes of keywords and pointers to the original URLs.

The crawler originally was a depth first recursive program, designed to grab the top page, linked pages, and then follow those all the way down (excluding pages already searched). I had two problems right away: I ran out of memory (swap! swap! crash!) and regularly ran web servers into the dirt.

The solution to both was the same. I modified the crawler to keep a queue of "places that I need to explore" externally on disk. As I visited a place removed from the head of the queue, I'd put the links found onto the end of the queue. (A further refinement was to take sites that came up twice in a row in the queue and throw the second site back onto the end of the queue.) The change from recursion to a queue was trivial.

Now the crawler worked in a mostly breadth-first fashion because the new links from the page explored wound up at the end of the queue. If you're searching more than one site you'll alternate between those in a balanced fashion without having to put the breaks on the process to throttle it. The more important pages tended towards the top of the sites anyway and would get indexed first.

The added benefit was when it crashed, I knew exactly where it left off (the head of the queue). I built a restart facility using cron. and if crawler/indexer crashed twice on the same URL, I'd throw that into a "broken" queue and remove it from the work queue.

re: Breadth is sometimes better than depth

Christian Romney — Mon, 27 Sep 2004 19:24:00 GMT

The queue idea is very slick. Perhaps now I can convince my wife that breadth is better than depth! ;)

re: Breadth is sometimes better than depth

Eric Lippert — Mon, 27 Sep 2004 19:42:00 GMT

Indeed, depth-first is a bad way to search the web. There are branches of the web which are for all practical purposes infinitely deep, but very few pages are infinitely broad.

re: Breadth is sometimes better than depth

Dave — Mon, 27 Sep 2004 21:29:00 GMT

Why not use .push() and .shift() instead of the manual array manipulation in the second example? Unless you're using IE 5.01 of course. :)

re: Breadth is sometimes better than depth

Eric Lippert — Mon, 27 Sep 2004 22:00:00 GMT

Shift is an array copy. If there are a thousand items in the array, that's a thousand property creations, a thousand property deletions and a thousand value copies _every_ time it's called. _Very_ expensive.

re: Breadth is sometimes better than depth

B0rG — Mon, 27 Sep 2004 22:05:00 GMT

This is a trade off - like with everything else in life: would you trade the simplicity in coding for the memory eaten by your stack? When the 200G drives are becoming a normal thing what would be amount of files and folders you have to "push" and "pop"?

My 20G logical drive for "all things work" has 20 000 folders sometimes up to 20 deep - i like my folders organised...

I do agree, however, that one should look at recursive functions in the morning somewhere between the second cup of cofee and lunch.

re: Breadth is sometimes better than depth

Dan Shappir — Mon, 27 Sep 2004 22:15:00 GMT

Recently I needed to extend our build process to perform a simple textual manipulation on some files: replace a placeholder with the version text. I implemented this step as a .wsf file using JScript and the BeyondJS library. The reason: BeyondJS made it very easy to perform a sequence of operations on all the files in a subdirectory that matched a particular pattern. For example, this code snippet performs the same operation as Eric's second sample (it's breadth-first):

File.recurse(".").foreach(alert);

"alert" in this case is a wrapper function for WScript.Echo. Yes, I've cut a few corners: it *is* recursive and I've neglected the try-catch. I still think it's cool.

Here is the code to output only .htm or .html files:

File.recurse(".").filter(/\.html?$/i).foreach(alert);

re: Breadth is sometimes better than depth

Eric Lippert — Mon, 27 Sep 2004 22:44:00 GMT

> would you trade the simplicity in coding for the memory eaten by your stack?

I'm not following your point. Perhaps I am misunderstanding you.

JScript isn't tail recursive, and in fact typically will blow the stack after about 600 recursions. Using an explicit "heap based" stack uses LESS memory and is MORE robust than using recursion to manage the call stack for you.

re: Breadth is sometimes better than depth

Dan Shappir — Mon, 27 Sep 2004 23:01:00 GMT

JScript may not have tail recursion, but Cocoon's Rhino-based JavaScript implementation does. It even sports continuations:

http://wiki.apache.org/cocoon/RhinoWithContinuations

re: Breadth is sometimes better than depth

Eric Lippert — Mon, 27 Sep 2004 23:08:00 GMT

That's pretty darn cool -- but of course in this case the point is moot because this isn't an algorithm that can be made tail recursive.

To be tail recursive, the function can't do any work that needs the state of the local variables after the recursive call, but in this algorithm, the state of the enumerator is needed after the recursive call.

re: Breadth is sometimes better than depth

Centaur — Tue, 28 Sep 2004 05:55:00 GMT

Breadth is better than depth especially in cases where the tree being traversed is potentially infinite. Breadth-first, each node will eventually be visited. Width-first, the algorithm will dive into the first infinite branch and never return.

With file systems, infinite trees emerge from circular symbolic links (aka junction points). Of course, any practical file system scanner must detect loops and not visit the same directory twice. Which brings a question: What is the best way to determine that C:\foo is the same as C:\foo\foo is the same as C:\foo\foo\foo?

re: Breadth is sometimes better than depth

Christian Mogensen — Tue, 28 Sep 2004 10:46:00 GMT

Canonicalization would be an obvious answer to that. Canonical("C:\foo\foo\foo") --> "C:\foo"

Now with URLs you have a problem, since you can't know that "http://foo.com/bar" and "http://www.foo.com/baz" are actually the same thing - two names for the same item.

Life is complicated... :-)

re: array pop and shift

Dave — Thu, 30 Sep 2004 15:58:00 GMT

Eric, are you sure about how shift works? Here are my timing results for shifting/popping an array of 5000 numbers and 5000 relatively large objects. The times are almost identical regardless of the type of element (in seconds):

operation, numbers, strings, objects
pop, 3359, 3360, 3343
shift, 12796, 12844, 12829

If it was actually copying the whole (remaining) array on each iteration of shift I would have thought the difference would be much more than 3.8x slower, and that times would vary by element type. Here's the code:

var a = [];
var n = 5000;
for ( var i=0; i < n; i++ )
a[i] = i-12;
var t1 = new Date();
for ( var i=0; i < n; i++ )
t = a.shift();
var t2 = new Date();
alert(t2.getTime()-t1.getTime());

re: Breadth is sometimes better than depth

Eric Lippert — Thu, 30 Sep 2004 16:48:00 GMT

* Yes I'm sure! Geez!

* On my box, the differential is a factor of five, and my timings are slower than yours. You must have a fast box!

* I would expect that numbers, strings and objects would give roughly the same timings. The copy itself isn't the expensive part. Copying a number is just a memory copy, copying an object is a pointer copy and a call to addref, copying a string is an allocation off the OLE Aut small string heap, which is optimized for exactly this situation. OA caches small strings; if an allocation comes in for a string of the same size as one that was just freed, it reuses the memory. Very fast. (This complicates memory leak detection, see Larry Osterman's recent blog on the subject.)

* The reason why the differential is so low is because the fixed cost of calling any method on an array object is high. In part, it's because you could assign the pop method to an object other than an array. Let me break "pop" down for you:

1) verify that a "this" argument was passed
2) convert the "this" argument to its object form if it is not already
3) verify that the object form is a JScript object, not an external COM object
4) extract the value of the length property
5) convert the value of the length property to an integer
6) from the length, figure out what index string is the one to pop
7) Look up that value -- if it exists, delete it and decrement the length property

Actually deleting the property is a tiny amount of work compared to all the rest. Similarly with shift and unshift, except that with shift and unshift, there's a big overhead followed by a big cost.

* Everything I just said in the previous point was a lie. Why? Because nowhere did I factor in the cost of doing the garbage collection. Most of the time spent in the pop operation is in the GC, cleaning up those 5000 elements.

This needs a much deeper analysis to understand what's going on.

re: Breadth is sometimes better than depth

Dave — Mon, 04 Oct 2004 16:22:00 GMT

Thanks for the info, Eric. The reason I originally asked the question was because it seemed odd to avoid shift() given that it's the logical compliment to pop().

I'm working with a black box, so timing is about all I can do to see the differences. A .shift() version of your second example ran almost the exact same time on my box when I crawled an entire system drive (10GB and 88,000 files); it looks like disk I/O is the bottleneck in that case. For smaller tests where the disk info could be cached the .shift() version was about 70% slower. I didn't see any major difference in memory usage observing Task Manager.

re: Breadth is sometimes better than depth

Eric Lippert — Tue, 05 Oct 2004 17:06:00 GMT

Indeed, questions of performance are best answered by trying it out!

In JScript classic, asymptotic performance is n^2 for both algorithms because it's gated on the behaviour of the garbage collector. Given n allocations, there are O(n) collections and each takes O(n) time to mark and sweep.

In JScript .NET, which uses a more efficient generational GC, the pop algorithm has this performance on my box:

n = 5000 : 140 ms
n = 10000 : 156 ms
n = 20000 : 171 ms

and the shift algorithm is:

n = 5000 : 203 ms
n = 10000 : 954 ms
n = 20000 : 2078 ms
n = 40000 : 10547 ms

Clearly shift is growing way, way faster than pop as we go asymptotic. If we did a proper and careful study we'd see that pop grew as O(n) and shift grew as O(n^2) once we mitigate the cost of the GC.