From 6962e3326fd6ebc87685f7292b3a06efc268c003 Mon Sep 17 00:00:00 2001 From: Brandon Low Date: Sun, 13 Feb 2011 11:17:06 -0800 Subject: [PATCH] Move .idx file writing to C This was a remaining CPU bottleneck in bup-dumb-server mode. In a quick test, writing 10 .idx files of 100000 elements on my netbook went from 50s to 4s. There may be more performance available by adjusting the definition of the PackWriter.idx object, but list(list(tuple)) isn't bad. Signed-off-by: Brandon Low --- cmd/midx-cmd.py | 3 +- lib/bup/_helpers.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++ lib/bup/git.py | 69 ++++++++++++++++++++------------------------ lib/bup/t/tgit.py | 9 +++--- 4 files changed, 107 insertions(+), 45 deletions(-) diff --git a/cmd/midx-cmd.py b/cmd/midx-cmd.py index 9c6dcd4..7718549 100755 --- a/cmd/midx-cmd.py +++ b/cmd/midx-cmd.py @@ -6,7 +6,6 @@ from bup.helpers import * PAGE_SIZE=4096 SHA_PER_PAGE=PAGE_SIZE/20. -SEEK_END=2 # os.SEEK_END is not defined in python 2.4 optspec = """ bup midx [options...] @@ -87,7 +86,7 @@ def _do_midx(outdir, outfilename, infilenames, prefixstr): fmap.flush() fmap.close() - f.seek(0, SEEK_END) + f.seek(0, git.SEEK_END) f.write('\0'.join(allfilenames)) f.close() os.rename(outfilename + '.tmp', outfilename) diff --git a/lib/bup/_helpers.c b/lib/bup/_helpers.c index 4befda2..df104cf 100644 --- a/lib/bup/_helpers.c +++ b/lib/bup/_helpers.c @@ -412,6 +412,75 @@ static PyObject *merge_into(PyObject *self, PyObject *args) return PyLong_FromUnsignedLong(count); } +// This function should techniclly be macro'd out if it's going to be used +// more than ocasionally. As of this writing, it'll actually never be called +// in real world bup scenarios (because our packs are < MAX_INT bytes). +static uint64_t htonll(uint64_t value) +{ + static const int endian_test = 42; + + if (*(char *)&endian_test == endian_test) // LSB-MSB + return ((uint64_t)htonl(value & 0xFFFFFFFF) << 32) | htonl(value >> 32); + return value; // already in network byte order MSB-LSB +} + +static PyObject *write_idx(PyObject *self, PyObject *args) +{ + PyObject *pf = NULL, *idx = NULL; + PyObject *part; + FILE *f; + unsigned char *fmap = NULL; + int flen = 0; + uint32_t total = 0; + uint32_t count; + int i, j, ofs64_count; + uint32_t *fan_ptr, *crc_ptr, *ofs_ptr; + struct sha *sha_ptr; + + if (!PyArg_ParseTuple(args, "Ow#OI", &pf, &fmap, &flen, &idx, &total)) + return NULL; + + fan_ptr = (uint32_t *)&fmap[8]; + sha_ptr = (struct sha *)&fan_ptr[256]; + crc_ptr = (uint32_t *)&sha_ptr[total]; + ofs_ptr = (uint32_t *)&crc_ptr[total]; + f = PyFile_AsFile(pf); + + count = 0; + ofs64_count = 0; + for (i = 0; i < 256; ++i) + { + int plen; + part = PyList_GET_ITEM(idx, i); + PyList_Sort(part); + plen = PyList_GET_SIZE(part); + count += plen; + *fan_ptr++ = htonl(count); + for (j = 0; j < plen; ++j) + { + unsigned char *sha = NULL; + int sha_len = 0; + uint32_t crc = 0; + uint64_t ofs = 0; + if (!PyArg_ParseTuple(PyList_GET_ITEM(part, j), "t#IK", + &sha, &sha_len, &crc, &ofs)) + return NULL; + if (sha_len != 20) + return NULL; + memcpy(sha_ptr++, sha, 20); + *crc_ptr++ = htonl(crc); + if (ofs > 0x7fffffff) + { + uint64_t nofs = htonll(ofs); + fwrite(&nofs, 8, 1, f); + ofs = 0x80000000 | ofs64_count++; + } + *ofs_ptr++ = htonl((uint32_t)ofs); + } + } + return PyLong_FromUnsignedLong(count); +} + // I would have made this a lower-level function that just fills in a buffer // with random values, and then written those values from python. But that's @@ -552,6 +621,8 @@ static PyMethodDef faster_methods[] = { "Take the first 'nbits' bits from 'buf' and return them as an int." }, { "merge_into", merge_into, METH_VARARGS, "Merges a bunch of idx and midx files into a single midx." }, + { "write_idx", write_idx, METH_VARARGS, + "Write a PackIdxV2 file from an idx list of lists of tuples" }, { "write_random", write_random, METH_VARARGS, "Write random bytes to the given file descriptor" }, { "random_sha", random_sha, METH_VARARGS, diff --git a/lib/bup/git.py b/lib/bup/git.py index 78fb9ec..59e85a7 100644 --- a/lib/bup/git.py +++ b/lib/bup/git.py @@ -7,6 +7,7 @@ from bup.helpers import * from bup import _helpers, path MIDX_VERSION = 4 +SEEK_END=2 # os.SEEK_END is not defined in python 2.4 """Discussion of bloom constants for bup: @@ -909,9 +910,7 @@ class PackWriter: f.write(packbin) f.close() - idx_f = open(self.filename + '.idx', 'wb') - obj_list_sha = self._write_pack_idx_v2(idx_f, idx, packbin) - idx_f.close() + obj_list_sha = self._write_pack_idx_v2(self.filename + '.idx', idx, packbin) nameprefix = repo('objects/pack/pack-%s' % obj_list_sha) if os.path.exists(self.filename + '.map'): @@ -927,43 +926,37 @@ class PackWriter: """Close the pack file and move it to its definitive path.""" return self._end(run_midx=run_midx) - def _write_pack_idx_v2(self, file, idx, packbin): - sum = Sha1() - - def write(data): - file.write(data) - sum.update(data) - - write('\377tOc\0\0\0\2') - - n = 0 - for part in idx: - n += len(part) - write(struct.pack('!i', n)) - part.sort(key=lambda x: x[0]) + def _write_pack_idx_v2(self, filename, idx, packbin): + idx_f = open(filename, 'w+b') + idx_f.write('\377tOc\0\0\0\2') + + ofs64_ofs = 8 + 4*256 + 28*self.count + idx_f.truncate(ofs64_ofs) + idx_f.seek(0) + idx_map = mmap_readwrite(idx_f, close=False) + idx_f.seek(0, SEEK_END) + count = _helpers.write_idx(idx_f, idx_map, idx, self.count) + assert(count == self.count) + idx_map.close() + idx_f.write(packbin) + + idx_f.seek(0) + idx_sum = Sha1() + b = idx_f.read(8 + 4*256) + idx_sum.update(b) obj_list_sum = Sha1() - for part in idx: - for entry in part: - write(entry[0]) - obj_list_sum.update(entry[0]) - for part in idx: - for entry in part: - write(struct.pack('!I', entry[1])) - ofs64_list = [] - for part in idx: - for entry in part: - if entry[2] & 0x80000000: - write(struct.pack('!I', 0x80000000 | len(ofs64_list))) - ofs64_list.append(struct.pack('!Q', entry[2])) - else: - write(struct.pack('!i', entry[2])) - for ofs64 in ofs64_list: - write(ofs64) - - write(packbin) - file.write(sum.digest()) - return obj_list_sum.hexdigest() + for b in chunkyreader(idx_f, 20*self.count): + idx_sum.update(b) + obj_list_sum.update(b) + namebase = obj_list_sum.hexdigest() + + for b in chunkyreader(idx_f): + idx_sum.update(b) + idx_f.write(idx_sum.digest()) + idx_f.close() + + return namebase def _git_date(date): diff --git a/lib/bup/t/tgit.py b/lib/bup/t/tgit.py index bb38075..da7c63c 100644 --- a/lib/bup/t/tgit.py +++ b/lib/bup/t/tgit.py @@ -132,14 +132,13 @@ def test_long_index(): idx[0x11].append((obj2_bin, 2, 0xffffffffff)) idx[0x22].append((obj3_bin, 3, 0xff)) (fd,name) = tempfile.mkstemp(suffix='.idx', dir=git.repo('objects')) - f = os.fdopen(fd, 'w+b') - r = w._write_pack_idx_v2(f, idx, pack_bin) - f.seek(0) - i = git.PackIdxV2(name, f) + os.close(fd) + w.count = 3 + r = w._write_pack_idx_v2(name, idx, pack_bin) + i = git.PackIdxV2(name, open(name, 'rb')) WVPASSEQ(i.find_offset(obj_bin), 0xfffffffff) WVPASSEQ(i.find_offset(obj2_bin), 0xffffffffff) WVPASSEQ(i.find_offset(obj3_bin), 0xff) - f.close() os.remove(name) @wvtest -- 2.39.2