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
/*
mpatch.c - efficient binary patching for Mercurial
This implements a patch algorithm that's O(m + nlog n) where m is the
size of the output and n is the number of patches.
Given a list of binary patches, it unpacks each into a hunk list,
then combines the hunk lists with a treewise recursion to form a
single hunk list. This hunk list is then applied to the original
text.
The text (or binary) fragments are copied directly from their source
Python objects into a preallocated output string to avoid the
allocation of intermediate Python objects. Working memory is about 2x
the total number of hunks.
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.
*/
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include "bitmanipulation.h"
#include "compat.h"
#include "mpatch.h"
/* VC9 doesn't include bool and lacks stdbool.h based on cext/util.h */
#if defined(_MSC_VER) || __STDC_VERSION__ < 199901L
#define true 1
#define false 0
typedef unsigned char bool;
#else
#include <stdbool.h>
#endif
static struct mpatch_flist *lalloc(ssize_t size)
{
struct mpatch_flist *a = NULL;
if (size < 1)
size = 1;
a = (struct mpatch_flist *)malloc(sizeof(struct mpatch_flist));
if (a) {
a->base = (struct mpatch_frag *)malloc(
sizeof(struct mpatch_frag) * size);
if (a->base) {
a->head = a->tail = a->base;
return a;
}
free(a);
}
return NULL;
}
void mpatch_lfree(struct mpatch_flist *a)
{
if (a) {
free(a->base);
free(a);
}
}
static ssize_t lsize(struct mpatch_flist *a)
{
return a->tail - a->head;
}
/* add helper to add src and *dest iff it won't overflow */
static inline bool safeadd(int src, int *dest)
{
if ((src > 0) == (*dest > 0)) {
if (*dest > 0) {
if (src > (INT_MAX - *dest)) {
return false;
}
} else {
if (src < (INT_MIN - *dest)) {
return false;
}
}
}
*dest += src;
return true;
}
/* subtract src from dest and store result in dest */
static inline bool safesub(int src, int *dest)
{
if (((src > 0) && (*dest < INT_MIN + src)) ||
((src < 0) && (*dest > INT_MAX + src))) {
return false;
}
*dest -= src;
return true;
}
/* move hunks in source that are less cut to dest, compensating
for changes in offset. the last hunk may be split if necessary.
*/
static int gather(struct mpatch_flist *dest, struct mpatch_flist *src, int cut,
int offset)
{
struct mpatch_frag *d = dest->tail, *s = src->head;
int postend, c, l;
while (s != src->tail) {
int soffset = s->start;
if (!safeadd(offset, &soffset))
break; /* add would overflow, oh well */
if (soffset >= cut)
break; /* we've gone far enough */
postend = offset;
if (!safeadd(s->start, &postend) ||
!safeadd(s->len, &postend)) {
break;
}
if (postend <= cut) {
/* save this hunk */
int tmp = s->start;
if (!safesub(s->end, &tmp)) {
break;
}
if (!safeadd(s->len, &tmp)) {
break;
}
if (!safeadd(tmp, &offset)) {
break; /* add would overflow, oh well */
}
*d++ = *s++;
} else {
/* break up this hunk */
c = cut;
if (!safesub(offset, &c)) {
break;
}
if (s->end < c)
c = s->end;
l = cut - offset - s->start;
if (s->len < l)
l = s->len;
offset += s->start + l - c;
d->start = s->start;
d->end = c;
d->len = l;
d->data = s->data;
d++;
s->start = c;
s->len = s->len - l;
s->data = s->data + l;
break;
}
}
dest->tail = d;
src->head = s;
return offset;
}
/* like gather, but with no output list */
static int discard(struct mpatch_flist *src, int cut, int offset)
{
struct mpatch_frag *s = src->head;
int postend, c, l;
while (s != src->tail) {
int cmpcut = s->start;
if (!safeadd(offset, &cmpcut)) {
break;
}
if (cmpcut >= cut)
break;
postend = offset;
if (!safeadd(s->start, &postend)) {
break;
}
if (!safeadd(s->len, &postend)) {
break;
}
if (postend <= cut) {
/* do the subtraction first to avoid UB integer overflow
*/
int tmp = s->start;
if (!safesub(s->end, &tmp)) {
break;
}
if (!safeadd(s->len, &tmp)) {
break;
}
if (!safeadd(tmp, &offset)) {
break;
}
s++;
} else {
c = cut;
if (!safesub(offset, &c)) {
break;
}
if (s->end < c)
c = s->end;
l = cut - offset - s->start;
if (s->len < l)
l = s->len;
offset += s->start + l - c;
s->start = c;
s->len = s->len - l;
s->data = s->data + l;
break;
}
}
src->head = s;
return offset;
}
/* combine hunk lists a and b, while adjusting b for offset changes in a/
this deletes a and b and returns the resultant list. */
static struct mpatch_flist *combine(struct mpatch_flist *a,
struct mpatch_flist *b)
{
struct mpatch_flist *c = NULL;
struct mpatch_frag *bh, *ct;
int offset = 0, post;
if (a && b)
c = lalloc((lsize(a) + lsize(b)) * 2);
if (c) {
for (bh = b->head; bh != b->tail; bh++) {
/* save old hunks */
offset = gather(c, a, bh->start, offset);
/* discard replaced hunks */
post = discard(a, bh->end, offset);
/* insert new hunk */
ct = c->tail;
ct->start = bh->start;
ct->end = bh->end;
if (!safesub(offset, &(ct->start)) ||
!safesub(post, &(ct->end))) {
/* It was already possible to exit
* this function with a return value
* of NULL before the safesub()s were
* added, so this should be fine. */
mpatch_lfree(c);
c = NULL;
goto done;
}
ct->len = bh->len;
ct->data = bh->data;
c->tail++;
offset = post;
}
/* hold on to tail from a */
memcpy(c->tail, a->head, sizeof(struct mpatch_frag) * lsize(a));
c->tail += lsize(a);
}
done:
mpatch_lfree(a);
mpatch_lfree(b);
return c;
}
/* decode a binary patch into a hunk list */
int mpatch_decode(const char *bin, ssize_t len, struct mpatch_flist **res)
{
struct mpatch_flist *l;
struct mpatch_frag *lt;
int pos = 0;
/* assume worst case size, we won't have many of these lists */
l = lalloc(len / 12 + 1);
if (!l)
return MPATCH_ERR_NO_MEM;
lt = l->tail;
/* We check against len-11 to ensure we have at least 12 bytes
left in the patch so we can read our three be32s out of it. */
while (pos >= 0 && pos < (len - 11)) {
lt->start = getbe32(bin + pos);
lt->end = getbe32(bin + pos + 4);
lt->len = getbe32(bin + pos + 8);
if (lt->start < 0 || lt->start > lt->end || lt->len < 0)
break; /* sanity check */
if (!safeadd(12, &pos)) {
break;
}
lt->data = bin + pos;
if (!safeadd(lt->len, &pos)) {
break;
}
lt++;
}
if (pos != len) {
mpatch_lfree(l);
return MPATCH_ERR_CANNOT_BE_DECODED;
}
l->tail = lt;
*res = l;
return 0;
}
/* calculate the size of resultant text */
ssize_t mpatch_calcsize(ssize_t len, struct mpatch_flist *l)
{
ssize_t outlen = 0, last = 0;
struct mpatch_frag *f = l->head;
while (f != l->tail) {
if (f->start < last || f->end > len) {
return MPATCH_ERR_INVALID_PATCH;
}
outlen += f->start - last;
last = f->end;
outlen += f->len;
f++;
}
outlen += len - last;
return outlen;
}
int mpatch_apply(char *buf, const char *orig, ssize_t len,
struct mpatch_flist *l)
{
struct mpatch_frag *f = l->head;
int last = 0;
char *p = buf;
while (f != l->tail) {
if (f->start < last || f->start > len || f->end > len ||
last < 0) {
return MPATCH_ERR_INVALID_PATCH;
}
memcpy(p, orig + last, f->start - last);
p += f->start - last;
memcpy(p, f->data, f->len);
last = f->end;
p += f->len;
f++;
}
if (last < 0) {
return MPATCH_ERR_INVALID_PATCH;
}
memcpy(p, orig + last, len - last);
return 0;
}
/* recursively generate a patch of all bins between start and end */
struct mpatch_flist *
mpatch_fold(void *bins, struct mpatch_flist *(*get_next_item)(void *, ssize_t),
ssize_t start, ssize_t end)
{
ssize_t len;
if (start + 1 == end) {
/* trivial case, output a decoded list */
return get_next_item(bins, start);
}
/* divide and conquer, memory management is elsewhere */
len = (end - start) / 2;
return combine(mpatch_fold(bins, get_next_item, start, start + len),
mpatch_fold(bins, get_next_item, start + len, end));
}