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

hg init repo
cd repo
echo foo > foo
hg ci -qAm 'add foo' -d '0 0'
echo >> foo
hg ci -m 'change foo' -d '0 0'
hg up -qC 0
echo bar > bar
hg ci -qAm 'add bar' -d '0 0'
hg log
cd ..
hg init copy
cd copy

echo '% pull -r 0'
hg pull -qr 0 ../repo
hg log

echo '% pull -r 1'
hg pull -qr 1 ../repo
hg log

# this used to abort: received changelog group is empty
echo '% pull -r 1 again'
hg pull -qr 1 ../repo