Fossil

Check-in [2dd25909]
Login

Check-in [2dd25909]

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Performance optimization on the delta generator.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 2dd25909dab7e1d1f04d9f25672e3e7d519d8b04
User & Date: drh 2015-12-25 14:46:13
Context
2015-12-25
15:13
Enhance the test-delta-analyze command to show the size of the delta. ... (check-in: 138313df user: drh tags: trunk)
14:46
Performance optimization on the delta generator. ... (check-in: 2dd25909 user: drh tags: trunk)
13:42
Fix the "fossil import --git" command so that it does delta compression on the fly, and hence uses much less temporary disk space. Also show progress information unless --quiet is used. ... (check-in: 063779a1 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/delta.c.
︙︙
103
104
105
106
107
108
109
110
111
112

113
114
115
116
117
118
119

** Initialize the rolling hash using the first NHASH characters of z[]
*/
static void hash_init(hash *pHash, const char *z){
  u16 a, b, i;
  a = b = 0;
  for(i=0; i<NHASH; i++){
    a += z[i];
    b += (NHASH-i)*z[i];
    pHash->z[i] = z[i];
  }

  pHash->a = a & 0xffff;
  pHash->b = b & 0xffff;
  pHash->i = 0;
}

/*
** Advance the rolling hash by a single character "c"








|
<

>








103
104
105
106
107
108
109
110

111
112
113
114
115
116
117
118
119

** Initialize the rolling hash using the first NHASH characters of z[]
*/
static void hash_init(hash *pHash, const char *z){
  u16 a, b, i;
  a = b = 0;
  for(i=0; i<NHASH; i++){
    a += z[i];
    b += a;

  }
  memcpy(pHash->z, z, NHASH);
  pHash->a = a & 0xffff;
  pHash->b = b & 0xffff;
  pHash->i = 0;
}

/*
** Advance the rolling hash by a single character "c"
︙︙
128
129
130
131
132
133
134


















135
136
137
138
139
140
141


/*
** Return a 32-bit hash value
*/
static u32 hash_32bit(hash *pHash){
  return (pHash->a & 0xffff) | (((u32)(pHash->b & 0xffff))<<16);
}



















/*
** Write an base-64 integer into the given buffer.
*/
static void putInt(unsigned int v, char **pz){
  static const char zDigits[] =
    "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz~";








>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>








128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159


/*
** Return a 32-bit hash value
*/
static u32 hash_32bit(hash *pHash){
  return (pHash->a & 0xffff) | (((u32)(pHash->b & 0xffff))<<16);
}

/*
** Compute a hash on NHASH bytes.
**
** This routine is intended to be equivalent to:
**    hash h;
**    hash_init(&h, zInput);
**    return hash_32bit(&h);
*/
static u32 hash_once(const char *z){
  u16 a, b, i;
  a = b = 0;
  for(i=0; i<NHASH; i++){
    a += z[i];
    b += a;
  }
  return a | (((u32)b)<<16);
}

/*
** Write an base-64 integer into the given buffer.
*/
static void putInt(unsigned int v, char **pz){
  static const char zDigits[] =
    "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz~";
︙︙
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344

  */
  nHash = lenSrc/NHASH;
  collide = fossil_malloc( nHash*2*sizeof(int) );
  landmark = &collide[nHash];
  memset(landmark, -1, nHash*sizeof(int));
  memset(collide, -1, nHash*sizeof(int));
  for(i=0; i<lenSrc-NHASH; i+=NHASH){
    int hv;
    hash_init(&h, &zSrc[i]);
    hv = hash_32bit(&h) % nHash;
    collide[i/NHASH] = landmark[hv];
    landmark[hv] = i/NHASH;
  }

  /* Begin scanning the target file and generating copy commands and
  ** literal sections of the delta.
  */








|
<
<








346
347
348
349
350
351
352
353


354
355
356
357
358
359
360

  */
  nHash = lenSrc/NHASH;
  collide = fossil_malloc( nHash*2*sizeof(int) );
  landmark = &collide[nHash];
  memset(landmark, -1, nHash*sizeof(int));
  memset(collide, -1, nHash*sizeof(int));
  for(i=0; i<lenSrc-NHASH; i+=NHASH){
    int hv = hash_once(&zSrc[i]) % nHash;


    collide[i/NHASH] = landmark[hv];
    landmark[hv] = i/NHASH;
  }

  /* Begin scanning the target file and generating copy commands and
  ** literal sections of the delta.
  */
︙︙