I have spotted the biggest bottleneck in "bdiff.c". Actually it was pretty easy to find after I recompiled the python interpreter and mercurial for profiling. In "bdiff.c" function "equatelines" allocates the minimum hash table size, which can lead to tons of collisions. I introduced an "overcommit" factor of 16, this is, I allocate 16 times more memory than the minimum value. Overcommiting 128 times does not improve the performance over the 16-times case.

#!/bin/sh

# 0-2-4
#  \ \ \
#   1-3-5
#
# rename in #1, content change in #4.

hg init t
cd t

touch 1
touch 2
hg commit -Am init -d "0 0"  # 0

hg rename 1 1a
hg commit -m rename -d "0 0" # 1

hg co -C 0
echo unrelated >> 2
hg ci -m unrelated1 -d "0 0"  # 2

hg merge --debug 1
hg ci -m merge1 -d "0 0" # 3

hg co -C 2
echo hello >> 1
hg ci -m unrelated2 -d "0 0" # 4

hg co -C 3
hg merge -y --debug 4

hg co -C 4
hg merge -y --debug 3