← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/diff-delta.c

  • Committer: John Arbash Meinel
  • Date: 2009-03-19 06:01:53 UTC
  • mto: (3735.2.157 brisbane-core)
  • mto: This revision was merged to the branch mainline in revision 4280.
  • Revision ID: john@arbash-meinel.com-20090319060153-p0e7qedqdq9vd8iq
Now we are able to weave 'add_source' into the existing index.
This brings 'bzr pack' time down to ~23.6s (with debugging on).
According to lsprof time for 'add_delta_source' overall dropped from ~5s down to
about 300ms, and now the time for 'add_source' dropped 5s->3.3s->1.6s.
Next thing is to probably bump the number of free slots.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/diff-delta.c
209
209
 
210
210
static struct delta_index *
211
211
pack_delta_index(struct unpacked_index_entry **hash, unsigned int hsize,
212
 
                 unsigned int num_entries, const struct delta_index *old_index)
 
212
                 unsigned int num_entries, struct delta_index *old_index)
213
213
{
214
 
    unsigned int i, j, hmask, memsize;
 
214
    unsigned int i, j, hmask, memsize, to_copy, fit_in_old, copied_count;
215
215
    struct unpacked_index_entry *entry;
216
216
    struct delta_index *index;
217
 
    struct index_entry *packed_entry, **packed_hash, *old_entry;
 
217
    struct index_entry *packed_entry, **packed_hash, *old_entry, *copy_from;
218
218
    struct index_entry null_entry = {0};
219
219
    void *mem;
 
220
 
 
221
    hmask = hsize - 1;
 
222
 
 
223
    if (old_index) {
 
224
        fprintf(stderr, "Packing %d entries into %d for total of %d entries"
 
225
                        " %x => %x\n",
 
226
                        num_entries - old_index->num_entries,
 
227
                        old_index->num_entries, num_entries,
 
228
                        old_index->hash_mask, hmask);
 
229
    } else {
 
230
        fprintf(stderr, "Packing %d entries into a new index\n",
 
231
                        num_entries);
 
232
    }
 
233
    /* First, see if we can squeeze the new items into the existing structure.
 
234
     */
 
235
    fit_in_old = 0;
 
236
    copied_count = 0;
 
237
    if (old_index && old_index->hash_mask == hmask) {
 
238
        fit_in_old = 1;
 
239
        for (i = 0; i < hsize; ++i) {
 
240
            packed_entry = NULL;
 
241
            for (entry = hash[i]; entry; entry = entry->next) {
 
242
                if (packed_entry == NULL) {
 
243
                    /* Find the last open spot */
 
244
                    packed_entry = old_index->hash[i + 1];
 
245
                    --packed_entry;
 
246
                    while (packed_entry >= old_index->hash[i]
 
247
                           && packed_entry->ptr == NULL) {
 
248
                        --packed_entry;
 
249
                    }
 
250
                    ++packed_entry;
 
251
                }
 
252
                if (packed_entry >= old_index->hash[i+1]
 
253
                    || packed_entry->ptr != NULL) {
 
254
                    /* There are no free spots here :( */
 
255
                    fit_in_old = 0;
 
256
                    break;
 
257
                }
 
258
                /* We found an empty spot to put this entry
 
259
                 * Copy it over, and remove it from the linked list, just in
 
260
                 * case we end up running out of room later.
 
261
                 */
 
262
                *packed_entry++ = entry->entry;
 
263
                assert(entry == hash[i]);
 
264
                hash[i] = entry->next;
 
265
                copied_count += 1;
 
266
                old_index->num_entries++;
 
267
            }
 
268
            if (!fit_in_old) {
 
269
                break;
 
270
            }
 
271
        }
 
272
    }
 
273
    if (old_index) {
 
274
        if (fit_in_old) {
 
275
            fprintf(stderr, "Fit all %d entries into old index\n",
 
276
                            copied_count);
 
277
            return NULL;
 
278
        } else {
 
279
            fprintf(stderr, "Fit only %d entries into old index,"
 
280
                            " reallocating\n", copied_count);
 
281
        }
 
282
    }
220
283
    /*
221
284
     * Now create the packed index in array form
222
285
     * rather than linked lists.
230
293
        return NULL;
231
294
    }
232
295
 
233
 
    hmask = hsize - 1;
234
296
    index = mem;
235
297
    index->memsize = memsize;
236
298
    index->hash_mask = hmask;
258
320
             * old_index->hash_mask? Would it make any real difference?
259
321
             */
260
322
            j = i & old_index->hash_mask;
 
323
            copy_from = old_index->hash[j];
 
324
            to_copy = 0;
261
325
            for (old_entry = old_index->hash[j];
262
326
                 old_entry < old_index->hash[j + 1] && old_entry->ptr != NULL;
263
327
                 old_entry++) {
264
328
                if ((old_entry->val & hmask) == i) {
265
 
                    *packed_entry++ = *old_entry;
 
329
                    to_copy += 1;
 
330
                } else {
 
331
                    /* We reached the end of a string of entries that should
 
332
                     * be copied. Copy the group, and then move the pointers.
 
333
                     */
 
334
                    if (to_copy > 0) {
 
335
                        memcpy(packed_entry, copy_from,
 
336
                               sizeof(*old_entry)*to_copy);
 
337
                        packed_entry += to_copy;
 
338
                        to_copy = 0;
 
339
                    }
 
340
                    /* Don't copy *this* entry, and start the copy after this */
 
341
                    copy_from = old_entry + 1;
266
342
                }
267
343
            }
 
344
            if (to_copy > 0) {
 
345
                memcpy(packed_entry, copy_from,
 
346
                       sizeof(*old_entry)*to_copy);
 
347
                packed_entry += to_copy;
 
348
                to_copy = 0;
 
349
            }
268
350
        }
269
351
        for (entry = hash[i]; entry; entry = entry->next) {
270
352
            *packed_entry++ = entry->entry;
292
374
 
293
375
 
294
376
struct delta_index *
295
 
create_index_from_old_and_hash(const struct delta_index *old,
296
 
                               struct unpacked_index_entry **hash,
297
 
                               unsigned int hsize,
298
 
                               unsigned int num_entries)
299
 
{
300
 
    unsigned int i, memsize, total_num_entries, num_nulls;
301
 
    struct unpacked_index_entry *entry;
302
 
    struct delta_index *index;
303
 
    struct index_entry *packed_entry, **packed_hash, null_entry = {0};
304
 
    struct index_entry *copy_from_start, *copy_to_start, *old_entry;
305
 
    size_t total_copy, to_copy;
306
 
    unsigned int num_ops;
307
 
    unsigned int bytes_copied;
308
 
    void *mem;
309
 
    /*
310
 
     * Now create the packed index in array form
311
 
     * rather than linked lists.
312
 
     */
313
 
    total_num_entries = num_entries + old->num_entries;
314
 
    memsize = sizeof(*index)
315
 
        + sizeof(*packed_hash) * (hsize+1)
316
 
        + sizeof(*packed_entry) * (total_num_entries + hsize * EXTRA_NULLS);
317
 
    mem = malloc(memsize);
318
 
    if (!mem) {
319
 
        return NULL;
320
 
    }
321
 
 
322
 
    index = mem;
323
 
    index->memsize = memsize;
324
 
    index->hash_mask = hsize - 1;
325
 
    index->num_entries = total_num_entries;
326
 
 
327
 
    mem = index->hash;
328
 
    packed_hash = mem;
329
 
    mem = packed_hash + (hsize+1);
330
 
    packed_entry = mem;
331
 
 
332
 
    total_copy = 0;
333
 
    bytes_copied = 0;
334
 
    num_ops = 0;
335
 
    copy_from_start = copy_to_start = NULL;
336
 
    num_nulls = 0;
337
 
    for (i = 0; i < hsize; i++) {
338
 
        /*
339
 
         * Coalesce all entries belonging to one linked list
340
 
         * into consecutive array entries.
341
 
         * The entries in old all come before the entries in hash.
342
 
         */
343
 
        packed_hash[i] = packed_entry;
344
 
        old_entry = old->hash[i+1];
345
 
        /* Find how many NULL items are in this hash section */
346
 
        old_entry--;
347
 
        num_nulls = 0;
348
 
        while (old_entry >= old->hash[i] && old_entry->ptr == NULL) {
349
 
            old_entry--;
350
 
            num_nulls++;
351
 
        }
352
 
        old_entry++;
353
 
        to_copy = (old_entry - old->hash[i]);
354
 
        if (to_copy > 0) {
355
 
            /* This next range can be copied wholesale. However, we will wait
356
 
             * until we have to insert something from the new data before we
357
 
             * copy everything.
358
 
             * So for now, just reserve space for the copy.
359
 
             */
360
 
            if (total_copy == 0) {
361
 
                copy_from_start = old->hash[i];
362
 
                copy_to_start = packed_entry;
363
 
            }
364
 
            packed_entry += to_copy;
365
 
            total_copy += to_copy;
366
 
            assert((packed_entry - copy_to_start) == total_copy);
367
 
            assert((old_entry - copy_from_start) == total_copy);
368
 
        }
369
 
        for (entry = hash[i]; entry; entry = entry->next) {
370
 
            /* We have an entry to insert, so flush the copy buffer */
371
 
            if (total_copy > 0) {
372
 
                assert(copy_to_start != NULL);
373
 
                assert(copy_from_start != NULL);
374
 
                memcpy(copy_to_start, copy_from_start,
375
 
                       total_copy * sizeof(struct index_entry));
376
 
                bytes_copied += (total_copy * sizeof(struct index_entry));
377
 
                total_copy = 0;
378
 
                copy_from_start = copy_to_start = NULL;
379
 
                num_ops += 1;
380
 
            }
381
 
            *packed_entry++ = entry->entry;
382
 
        }
383
 
        if (total_copy == 0) {
384
 
            /* We inserted some entries, copy the null entries to the end */
385
 
            for (; num_nulls > 0; --num_nulls) {
386
 
                *packed_entry++ = null_entry;
387
 
            }
388
 
        } else {
389
 
            /* We haven't done an insert yet, so just queue the null entries
390
 
             * for copying.
391
 
             */
392
 
            total_copy += num_nulls;
393
 
            packed_entry += num_nulls;
394
 
            assert((packed_entry - copy_to_start) == total_copy);
395
 
            assert((old->hash[i+1] - copy_from_start) == total_copy);
396
 
            num_nulls = 0;
397
 
        }
398
 
    }
399
 
    if (total_copy > 0) {
400
 
        assert(copy_to_start != NULL);
401
 
        assert(copy_from_start != NULL);
402
 
        memcpy(copy_to_start, copy_from_start,
403
 
               total_copy * sizeof(struct index_entry));
404
 
        bytes_copied += (total_copy * sizeof(struct index_entry));
405
 
        num_ops += 1;
406
 
        for (; num_nulls > 0; --num_nulls) {
407
 
            *packed_entry++ = null_entry;
408
 
        }
409
 
    }
410
 
 
411
 
    /* Sentinel value to indicate the length of the last hash bucket */
412
 
    packed_hash[hsize] = packed_entry;
413
 
 
414
 
    assert(packed_entry - (struct index_entry *)mem
415
 
           == total_num_entries + hsize * EXTRA_NULLS);
416
 
    index->last_entry = (packed_entry - 1);
417
 
    return index;
418
 
}
419
 
 
420
 
 
421
 
struct delta_index *
422
377
create_delta_index(const struct source_info *src,
423
 
                   const struct delta_index *old)
 
378
                   struct delta_index *old)
424
379
{
425
380
    unsigned int i, hsize, hmask, num_entries, prev_val, *hash_count;
426
381
    unsigned int total_num_entries;
494
449
    total_num_entries = limit_hash_buckets(hash, hash_count, hsize,
495
450
                                           total_num_entries);
496
451
    free(hash_count);
 
452
    if (old) {
 
453
        old->last_src = src;
 
454
    }
497
455
    index = pack_delta_index(hash, hsize, total_num_entries, old);
498
 
    index->last_src = src;
499
456
    free(hash);
500
457
    if (!index) {
501
458
        return NULL;
502
459
    }
 
460
    index->last_src = src;
503
461
    return index;
504
462
}
505
463