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.

     1

#!/bin/sh

     2

     3

mkdir t

     4

cd t

     5

hg init

     6

echo a > a

     7

hg ci -Ama -d '1000000000 0'

     8

echo b > b

     9

hg branch b

    10

hg ci -Amb -d '1000000000 0'

    11

hg co -C 0

    12

    13

echo fast-forward

    14

hg merge b

    15

hg ci -Ammerge -d '1000000000 0'

    16

    17

echo bogus fast-forward should fail

    18

hg merge b

    19

    20

echo done