Mercurial > hg > mercurial-crew-with-dirclash
view hgmerge @ 2577:fa76c5d609c9
bdiff: improve worst case behavior by 100x.
on 5.8MB (244.000 lines) text file with similar lines, hash before
this change made diff against empty file take 75 seconds. this change
improves performance to 0.6 seconds. result is that clone of smallish
repo (137MB) with some files like this takes 1 minute instead of 10
minutes.
common case of diff is 10% slower now, probably because of worse cache
locality. but diff does not affect overall performance in common case
(less than 1% of runtime is in diff when it is working ok), so this
tradeoff looks good.
author | Vadim Gelfer <vadim.gelfer@gmail.com> |
---|---|
date | Fri, 07 Jul 2006 15:02:55 -0700 |
parents | 6a03cff2b0f5 |
children | e4480f2b61e9 |
line wrap: on
line source
#!/bin/sh # # hgmerge - default merge helper for Mercurial # # This tries to find a way to do three-way merge on the current system. # The result ought to end up in $1. Script is run in root directory of # repository. # # Environment variables set by Mercurial: # HG_FILE name of file within repo # HG_MY_NODE revision being merged # HG_OTHER_NODE revision being merged set -e # bail out quickly on failure LOCAL="$1" BASE="$2" OTHER="$3" if [ -z "$EDITOR" ]; then EDITOR="vi" fi # find decent versions of our utilities, insisting on the GNU versions where we # need to MERGE="merge" DIFF3="gdiff3" DIFF="gdiff" PATCH="gpatch" type "$MERGE" >/dev/null 2>&1 || MERGE= type "$DIFF3" >/dev/null 2>&1 || DIFF3="diff3" $DIFF3 --version >/dev/null 2>&1 || DIFF3= type "$DIFF" >/dev/null 2>&1 || DIFF="diff" type "$DIFF" >/dev/null 2>&1 || DIFF= type "$PATCH" >/dev/null 2>&1 || PATCH="patch" type "$PATCH" >/dev/null 2>&1 || PATCH= # find optional visual utilities FILEMERGE="/Developer/Applications/Utilities/FileMerge.app/Contents/MacOS/FileMerge" KDIFF3="kdiff3" TKDIFF="tkdiff" MELD="meld" type "$FILEMERGE" >/dev/null 2>&1 || FILEMERGE= type "$KDIFF3" >/dev/null 2>&1 || KDIFF3= type "$TKDIFF" >/dev/null 2>&1 || TKDIFF= type "$MELD" >/dev/null 2>&1 || MELD= # Hack for Solaris TEST="/usr/bin/test" type "$TEST" >/dev/null 2>&1 || TEST="/bin/test" type "$TEST" >/dev/null 2>&1 || TEST="test" # random part of names RAND="$RANDOM$RANDOM" # temporary directory for diff+patch merge HGTMP="${TMPDIR-/tmp}/hgmerge.$RAND" # backup file BACKUP="$LOCAL.orig.$RAND" # file used to test for file change CHGTEST="$LOCAL.chg.$RAND" # put all your required cleanup here cleanup() { rm -f "$BACKUP" "$CHGTEST" rm -rf "$HGTMP" } # functions concerning program exit success() { cleanup exit 0 } failure() { echo "merge failed" 1>&2 mv "$BACKUP" "$LOCAL" cleanup exit 1 } # Ask if the merge was successful ask_if_merged() { while true; do echo "$LOCAL seems unchanged." echo "Was the merge successful? [y/n]" read answer case "$answer" in y*|Y*) success;; n*|N*) failure;; esac done } # Clean up when interrupted trap "failure" 1 2 3 6 15 # HUP INT QUIT ABRT TERM # Back up our file (and try hard to keep the mtime unchanged) mv "$LOCAL" "$BACKUP" cp "$BACKUP" "$LOCAL" # Attempt to do a non-interactive merge if [ -n "$MERGE" -o -n "$DIFF3" ]; then if [ -n "$MERGE" ]; then $MERGE "$LOCAL" "$BASE" "$OTHER" 2> /dev/null && success elif [ -n "$DIFF3" ]; then $DIFF3 -m "$BACKUP" "$BASE" "$OTHER" > "$LOCAL" && success fi if [ $? -gt 1 ]; then echo "automatic merge failed! Exiting." 1>&2 failure fi fi # on MacOS X try FileMerge.app, shipped with Apple's developer tools if [ -n "$FILEMERGE" ]; then cp "$BACKUP" "$LOCAL" cp "$BACKUP" "$CHGTEST" # filemerge prefers the right by default $FILEMERGE -left "$OTHER" -right "$LOCAL" -ancestor "$BASE" -merge "$LOCAL" [ $? -ne 0 ] && echo "FileMerge failed to launch" && failure $TEST "$LOCAL" -nt "$CHGTEST" && success || ask_if_merged fi if [ -n "$DISPLAY" ]; then # try using kdiff3, which is fairly nice if [ -n "$KDIFF3" ]; then $KDIFF3 --auto "$BASE" "$BACKUP" "$OTHER" -o "$LOCAL" || failure success fi # try using tkdiff, which is a bit less sophisticated if [ -n "$TKDIFF" ]; then $TKDIFF "$BACKUP" "$OTHER" -a "$BASE" -o "$LOCAL" || failure success fi if [ -n "$MELD" ]; then cp "$BACKUP" "$CHGTEST" # protect our feet - meld allows us to save to the left file cp "$BACKUP" "$LOCAL.tmp.$RAND" # Meld doesn't have automatic merging, so to reduce intervention # use the file with conflicts $MELD "$LOCAL.tmp.$RAND" "$LOCAL" "$OTHER" || failure # Also it doesn't return good error code $TEST "$LOCAL" -nt "$CHGTEST" && success || ask_if_merged fi fi # Attempt to do a merge with $EDITOR if [ -n "$MERGE" -o -n "$DIFF3" ]; then echo "conflicts detected in $LOCAL" cp "$BACKUP" "$CHGTEST" $EDITOR "$LOCAL" || failure # Some editors do not return meaningful error codes # Do not take any chances $TEST "$LOCAL" -nt "$CHGTEST" && success || ask_if_merged fi # attempt to manually merge with diff and patch if [ -n "$DIFF" -a -n "$PATCH" ]; then (umask 077 && mkdir "$HGTMP") || { echo "Could not create temporary directory $HGTMP" 1>&2 failure } $DIFF -u "$BASE" "$OTHER" > "$HGTMP/diff" || : if $PATCH "$LOCAL" < "$HGTMP/diff"; then success else # If rejects are empty after using the editor, merge was ok $EDITOR "$LOCAL" "$LOCAL.rej" || failure $TEST -s "$LOCAL.rej" || success fi failure fi echo echo "hgmerge: unable to find any merge utility!" echo "supported programs:" echo "merge, FileMerge, tkdiff, kdiff3, meld, diff+patch" echo failure