treemanifests: remove _loadalllazy when doing copies
'before' here is https://phab.mercurial-scm.org/D4845 (not the committed/rebased
version)
diff --git:
repo | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
------+---+---+------------------------+-----------------------+------------
m-u | | | 1.329 s +- 0.011 s | 1.320 s +- 0.010 s | 99.3%
m-u | | x | 1.316 s +- 0.005 s | 1.334 s +- 0.018 s | 101.4%
m-u | x | | 1.330 s +- 0.021 s | 1.322 s +- 0.005 s | 99.4%
m-u | x | x | 87.2 ms +- 0.7 ms | 86.9 ms +- 1.5 ms | 99.7%
l-d-r | | | 203.3 ms +- 7.8 ms | 199.4 ms +- 1.8 ms | 98.1%
l-d-r | | x | 204.6 ms +- 2.8 ms | 201.7 ms +- 2.1 ms | 98.6%
l-d-r | x | | 90.5 ms +- 11.0 ms | 86.2 ms +- 1.0 ms | 95.2%
l-d-r | x | x | 66.3 ms +- 2.0 ms | 66.4 ms +- 0.9 ms | 100.2%
diff -c . --git:
repo | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
------+---+---+------------------------+-----------------------+------------
m-u | | | 239.4 ms +- 2.0 ms | 241.7 ms +- 4.6 ms | 101.0%
m-u | | x | 128.9 ms +- 1.9 ms | 130.9 ms +- 7.7 ms | 101.6%
m-u | x | | 241.1 ms +- 1.6 ms | 240.1 ms +- 1.4 ms | 99.6%
m-u | x | x | 133.4 ms +- 1.5 ms | 133.4 ms +- 1.2 ms | 100.0%
l-d-r | | | 84.3 ms +- 1.5 ms | 83.5 ms +- 1.0 ms | 99.1%
l-d-r | | x | 200.9 ms +- 6.3 ms | 203.0 ms +- 4.4 ms | 101.0%
l-d-r | x | | 108.1 ms +- 1.4 ms | 108.7 ms +- 2.1 ms | 100.6%
l-d-r | x | x | 190.2 ms +- 4.8 ms | 191.6 ms +- 2.0 ms | 100.7%
rebase -r . --keep -d .^^:
repo | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
------+---+---+------------------------+-----------------------+------------
m-u | | | 5.655 s +- 0.029 s | 5.640 s +- 0.036 s | 99.7%
m-u | | x | 5.813 s +- 0.038 s | 5.773 s +- 0.028 s | 99.3%
m-u | x | | 5.593 s +- 0.043 s | 5.589 s +- 0.028 s | 99.9%
m-u | x | x | 648.2 ms +- 19.2 ms | 637.3 ms +- 27.7 ms | 98.3%
l-d-r | | | 673.3 ms +- 8.0 ms | 673.2 ms +- 6.8 ms | 100.0%
l-d-r | | x | 6.583 s +- 0.030 s | 5.721 s +- 0.028 s | 86.9% <--
l-d-r | x | | 277.8 ms +- 6.7 ms | 276.0 ms +- 2.7 ms | 99.4%
l-d-r | x | x | 1.692 s +- 0.013 s | 720.9 ms +- 13.3 ms | 42.6% <--
status --change . --copies:
repo | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
------+---+---+------------------------+-----------------------+------------
m-u | | | 220.9 ms +- 1.6 ms | 219.9 ms +- 2.2 ms | 99.5%
m-u | | x | 109.2 ms +- 1.0 ms | 109.4 ms +- 0.8 ms | 100.2%
m-u | x | | 222.6 ms +- 1.7 ms | 221.4 ms +- 2.1 ms | 99.5%
m-u | x | x | 113.4 ms +- 0.5 ms | 113.1 ms +- 1.1 ms | 99.7%
l-d-r | | | 82.1 ms +- 1.7 ms | 82.1 ms +- 1.2 ms | 100.0%
l-d-r | | x | 199.8 ms +- 4.0 ms | 200.7 ms +- 3.6 ms | 100.5%
l-d-r | x | | 85.4 ms +- 1.5 ms | 85.2 ms +- 0.3 ms | 99.8%
l-d-r | x | x | 202.6 ms +- 4.4 ms | 208.0 ms +- 4.0 ms | 102.7%
status --copies:
repo | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
------+---+---+------------------------+-----------------------+------------
m-u | | | 1.941 s +- 0.014 s | 1.930 s +- 0.009 s | 99.4%
m-u | | x | 1.924 s +- 0.007 s | 1.950 s +- 0.010 s | 101.4%
m-u | x | | 1.959 s +- 0.085 s | 1.926 s +- 0.009 s | 98.3%
m-u | x | x | 96.2 ms +- 1.0 ms | 96.4 ms +- 0.7 ms | 100.2%
l-d-r | | | 604.4 ms +- 10.6 ms | 602.6 ms +- 7.1 ms | 99.7%
l-d-r | | x | 605.7 ms +- 4.1 ms | 607.4 ms +- 6.1 ms | 100.3%
l-d-r | x | | 182.4 ms +- 1.2 ms | 183.4 ms +- 1.2 ms | 100.5%
l-d-r | x | x | 150.8 ms +- 2.0 ms | 150.6 ms +- 1.0 ms | 99.9%
update $rev^; ~/src/hg/hg{hg}/hg update $rev:
repo | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
------+---+---+------------------------+-----------------------+------------
m-u | | | 3.185 s +- 0.027 s | 3.181 s +- 0.017 s | 99.9%
m-u | | x | 3.028 s +- 0.021 s | 2.954 s +- 0.010 s | 97.6%
m-u | x | | 3.168 s +- 0.010 s | 3.175 s +- 0.023 s | 100.2%
m-u | x | x | 317.5 ms +- 3.5 ms | 313.2 ms +- 2.9 ms | 98.6%
l-d-r | | | 456.2 ms +- 10.6 ms | 454.4 ms +- 5.8 ms | 99.6%
l-d-r | | x | 9.236 s +- 0.063 s | 757.9 ms +- 9.2 ms | 8.2% <--
l-d-r | x | | 257.6 ms +- 2.3 ms | 261.2 ms +- 1.7 ms | 101.4%
l-d-r | x | x | 1.614 s +- 0.013 s | 478.0 ms +- 14.3 ms | 29.6% <--
Differential Revision: https://phab.mercurial-scm.org/D4875
/*
bdiff.c - efficient binary diff extension for Mercurial
Copyright 2005, 2006 Matt Mackall <mpm@selenic.com>
This software may be used and distributed according to the terms of
the GNU General Public License, incorporated herein by reference.
Based roughly on Python difflib
*/
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include "bdiff.h"
#include "bitmanipulation.h"
#include "compat.h"
/* Hash implementation from diffutils */
#define ROL(v, n) ((v) << (n) | (v) >> (sizeof(v) * CHAR_BIT - (n)))
#define HASH(h, c) ((c) + ROL(h, 7))
struct pos {
int pos, len;
};
int bdiff_splitlines(const char *a, ssize_t len, struct bdiff_line **lr)
{
unsigned hash;
int i;
const char *p, *b = a;
const char *const plast = a + len - 1;
struct bdiff_line *l;
/* count the lines */
i = 1; /* extra line for sentinel */
for (p = a; p < plast; p++)
if (*p == '\n')
i++;
if (p == plast)
i++;
*lr = l = (struct bdiff_line *)calloc(i, sizeof(struct bdiff_line));
if (!l)
return -1;
/* build the line array and calculate hashes */
hash = 0;
for (p = a; p < plast; p++) {
hash = HASH(hash, *p);
if (*p == '\n') {
l->hash = hash;
hash = 0;
l->len = p - b + 1;
l->l = b;
l->n = INT_MAX;
l++;
b = p + 1;
}
}
if (p == plast) {
hash = HASH(hash, *p);
l->hash = hash;
l->len = p - b + 1;
l->l = b;
l->n = INT_MAX;
l++;
}
/* set up a sentinel */
l->hash = 0;
l->len = 0;
l->l = a + len;
return i - 1;
}
static inline int cmp(struct bdiff_line *a, struct bdiff_line *b)
{
return a->hash != b->hash || a->len != b->len ||
memcmp(a->l, b->l, a->len);
}
static int equatelines(struct bdiff_line *a, int an, struct bdiff_line *b,
int bn)
{
int i, j, buckets = 1, t, scale;
struct pos *h = NULL;
/* build a hash table of the next highest power of 2 */
while (buckets < bn + 1)
buckets *= 2;
/* try to allocate a large hash table to avoid collisions */
for (scale = 4; scale; scale /= 2) {
h = (struct pos *)calloc(buckets, scale * sizeof(struct pos));
if (h)
break;
}
if (!h)
return 0;
buckets = buckets * scale - 1;
/* clear the hash table */
for (i = 0; i <= buckets; i++) {
h[i].pos = -1;
h[i].len = 0;
}
/* add lines to the hash table chains */
for (i = 0; i < bn; i++) {
/* find the equivalence class */
for (j = b[i].hash & buckets; h[j].pos != -1;
j = (j + 1) & buckets)
if (!cmp(b + i, b + h[j].pos))
break;
/* add to the head of the equivalence class */
b[i].n = h[j].pos;
b[i].e = j;
h[j].pos = i;
h[j].len++; /* keep track of popularity */
}
/* compute popularity threshold */
t = (bn >= 31000) ? bn / 1000 : 1000000 / (bn + 1);
/* match items in a to their equivalence class in b */
for (i = 0; i < an; i++) {
/* find the equivalence class */
for (j = a[i].hash & buckets; h[j].pos != -1;
j = (j + 1) & buckets)
if (!cmp(a + i, b + h[j].pos))
break;
a[i].e = j; /* use equivalence class for quick compare */
if (h[j].len <= t)
a[i].n = h[j].pos; /* point to head of match list */
else
a[i].n = -1; /* too popular */
}
/* discard hash tables */
free(h);
return 1;
}
static int longest_match(struct bdiff_line *a, struct bdiff_line *b,
struct pos *pos, int a1, int a2, int b1, int b2,
int *omi, int *omj)
{
int mi = a1, mj = b1, mk = 0, i, j, k, half, bhalf;
/* window our search on large regions to better bound
worst-case performance. by choosing a window at the end, we
reduce skipping overhead on the b chains. */
if (a2 - a1 > 30000)
a1 = a2 - 30000;
half = (a1 + a2 - 1) / 2;
bhalf = (b1 + b2 - 1) / 2;
for (i = a1; i < a2; i++) {
/* skip all lines in b after the current block */
for (j = a[i].n; j >= b2; j = b[j].n)
;
/* loop through all lines match a[i] in b */
for (; j >= b1; j = b[j].n) {
/* does this extend an earlier match? */
for (k = 1; j - k >= b1 && i - k >= a1; k++) {
/* reached an earlier match? */
if (pos[j - k].pos == i - k) {
k += pos[j - k].len;
break;
}
/* previous line mismatch? */
if (a[i - k].e != b[j - k].e)
break;
}
pos[j].pos = i;
pos[j].len = k;
/* best match so far? we prefer matches closer
to the middle to balance recursion */
if (k > mk) {
/* a longer match */
mi = i;
mj = j;
mk = k;
} else if (k == mk) {
if (i > mi && i <= half && j > b1) {
/* same match but closer to half */
mi = i;
mj = j;
} else if (i == mi && (mj > bhalf || i == a1)) {
/* same i but best earlier j */
mj = j;
}
}
}
}
if (mk) {
mi = mi - mk + 1;
mj = mj - mk + 1;
}
/* expand match to include subsequent popular lines */
while (mi + mk < a2 && mj + mk < b2 && a[mi + mk].e == b[mj + mk].e)
mk++;
*omi = mi;
*omj = mj;
return mk;
}
static struct bdiff_hunk *recurse(struct bdiff_line *a, struct bdiff_line *b,
struct pos *pos, int a1, int a2, int b1,
int b2, struct bdiff_hunk *l)
{
int i, j, k;
while (1) {
/* find the longest match in this chunk */
k = longest_match(a, b, pos, a1, a2, b1, b2, &i, &j);
if (!k)
return l;
/* and recurse on the remaining chunks on either side */
l = recurse(a, b, pos, a1, i, b1, j, l);
if (!l)
return NULL;
l->next =
(struct bdiff_hunk *)malloc(sizeof(struct bdiff_hunk));
if (!l->next)
return NULL;
l = l->next;
l->a1 = i;
l->a2 = i + k;
l->b1 = j;
l->b2 = j + k;
l->next = NULL;
/* tail-recursion didn't happen, so do equivalent iteration */
a1 = i + k;
b1 = j + k;
}
}
int bdiff_diff(struct bdiff_line *a, int an, struct bdiff_line *b, int bn,
struct bdiff_hunk *base)
{
struct bdiff_hunk *curr;
struct pos *pos;
int t, count = 0;
/* allocate and fill arrays */
t = equatelines(a, an, b, bn);
pos = (struct pos *)calloc(bn ? bn : 1, sizeof(struct pos));
if (pos && t) {
/* generate the matching block list */
curr = recurse(a, b, pos, 0, an, 0, bn, base);
if (!curr)
return -1;
/* sentinel end hunk */
curr->next =
(struct bdiff_hunk *)malloc(sizeof(struct bdiff_hunk));
if (!curr->next)
return -1;
curr = curr->next;
curr->a1 = curr->a2 = an;
curr->b1 = curr->b2 = bn;
curr->next = NULL;
}
free(pos);
/* normalize the hunk list, try to push each hunk towards the end */
for (curr = base->next; curr; curr = curr->next) {
struct bdiff_hunk *next = curr->next;
if (!next)
break;
if (curr->a2 == next->a1 || curr->b2 == next->b1)
while (curr->a2 < an && curr->b2 < bn &&
next->a1 < next->a2 && next->b1 < next->b2 &&
!cmp(a + curr->a2, b + curr->b2)) {
curr->a2++;
next->a1++;
curr->b2++;
next->b1++;
}
}
for (curr = base->next; curr; curr = curr->next)
count++;
return count;
}
/* deallocate list of hunks; l may be NULL */
void bdiff_freehunks(struct bdiff_hunk *l)
{
struct bdiff_hunk *n;
for (; l; l = n) {
n = l->next;
free(l);
}
}