mtree does a full hierarchy walk when requested to update a (directory) structure.  This is unnecessary as mtree need only visit the directories or files in question.  This can have particular performance impact if the path's structure is extensive (i.e. /usr/local with 1000+ ports installed) and the structure to update is relatively short or when IO is slow (i.e. stacked unionfs).  

This has real world impact as this mtree command is run every time a port is installed.

Fix: The attached patch prevents a hierarchy walk if only an update is requested.  It simulated the structure returned from fts_read as required by compare.  

An improvement in performance could be implemented using chdir (as fts_* does) however that would require a pervasive change to existing code.  

Patch attached with submission follows:
How-To-Repeat: The following script simulates slow IO (using stacked unionfs).  Note that the time mtree takes is similar to find when unpatched but a fraction of the time (between 60% to 80% quicker [1 - new/old]).  I expect this performance to be better when the path is populated with extra content (e.g. installed ports).  

The script should be run as root in an empty root (the number of overlayed unionfs are specified as the first command, please see http://lists.freebsd.org/pipermail/freebsd-current/2010-January/015040.html for possible problems [system freeze, kstack overflow]).  

On my computer with 155 overlayed unionfs the performance I got:
# ./unionfs_mtree.sh 155 | tail -n 1
mtree 155:       123.77 real         0.03 user       112.67 sys (unpatched)
mtree 155:        29.94 real         0.00 user        29.81 sys (patched)

The script (unionfs_mtree.sh):

#!/bin/sh
set -e

mount_unionfs() {

  count=1
  while [ $count -lt $1 ]
  do
    mount -rt unionfs -o noatime $count top
    count=$(($count + 1))
  done

}

umount_unionfs() {

  count=$1
  while [ $count -gt 1 ]
  do
    count=$(($count - 1))
    umount top
  done

}

mkdir -p top

[ $# -eq 1 ] || (echo "Please specify directory count!!!"; false)

for i in `jot $1`
do
  mount_unionfs $i
  mkdir -p $i
  mount -t unionfs -o noatime $i top

  set +e
  trap "true" INT TERM EXIT
  echo -n "find $i:  "
  time find top > /dev/null
  status=$?

  if [ $status -eq 0 ]
  then
    echo -n "mtree $i: "
    time /usr/sbin/mtree -U -f /usr/ports/Templates/BSD.local.dist -d -e -p top
    status=$?
  fi
  trap - INT TERM EXIT
  set -e

  umount top
  umount_unionfs $i
  [ $status -eq 0 ] || (echo "Terminated"; false)
done