# [PATCH] git-p4: improve performance with large files 10 messages from 2009-03-04 to 2009-03-07. Participants: Sam Hocevar, thestar@fussycoder.id.au, Junio C Hamano, Han-Wen Nienhuys. Thread: https://gitlist.dev/t/18138 ## Sam Hocevar, 2009-03-04 21:54 Subject: [PATCH] git-p4: improve performance with large files Message-ID: <20090304215438.GA12653@zoy.org> URL: https://gitlist.dev/e/20090304215438.GA12653%40zoy.org ``` The current git-p4 way of concatenating strings performs in O(n^2) and is therefore terribly slow with large files because of unnecessary memory copies. The following patch makes the operation O(n). Using this patch, importing a 17GB repository with large files (50 to 500MB) takes 2 hours instead of a week. Signed-off-by: Sam Hocevar --- contrib/fast-import/git-p4 | 5 +++-- 1 files changed, 3 insertions(+), 2 deletions(-) diff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4 index 9fdb0c6..09e9746 100755 --- a/contrib/fast-import/git-p4 +++ b/contrib/fast-import/git-p4 @@ -990,11 +990,12 @@ class P4Sync(Command): while j < len(filedata): stat = filedata[j] j += 1 - text = '' + data = [] while j < len(filedata) and filedata[j]['code'] in ('text', 'unicode', 'binary'): - text += filedata[j]['data'] + data.append(filedata[j]['data']) del filedata[j]['data'] j += 1 + text = "".join(data) if not stat.has_key('depotFile'): sys.stderr.write("p4 print fails with: %s\n" % repr(stat)) -- 1.6.1.3 ``` ## thestar@fussycoder.id.au, 2009-03-04 23:05 Subject: Re: [PATCH] git-p4: improve performance with large files Message-ID: <20090305100527.shmtfbdvk0ggsk4s@webmail.fussycoder.id.au> URL: https://gitlist.dev/e/20090305100527.shmtfbdvk0ggsk4s%40webmail.fussycoder.id.au In-Reply-To: <20090304215438.GA12653@zoy.org> ``` Quoting Sam Hocevar : > The current git-p4 way of concatenating strings performs in O(n^2) > and is therefore terribly slow with large files because of unnecessary > memory copies. The following patch makes the operation O(n). The reason why it uses simple concatenation is to cut down on memory usage. - It is a tradeoff. I think the modification you have made below is reasonable, however be aware that memory usage could double, which substantially reduce the size of the changesets that git-p4 would be able to import /at all/, rather than to merely be slow. That said, you do need to delete the data temporary array to cut down on memory. -- I would do this immediately after the "".join(data). > > Using this patch, importing a 17GB repository with large files > (50 to 500MB) takes 2 hours instead of a week. > > Signed-off-by: Sam Hocevar > --- > contrib/fast-import/git-p4 | 5 +++-- > 1 files changed, 3 insertions(+), 2 deletions(-) > > diff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4 > index 9fdb0c6..09e9746 100755 > --- a/contrib/fast-import/git-p4 > +++ b/contrib/fast-import/git-p4 > @@ -990,11 +990,12 @@ class P4Sync(Command): > while j < len(filedata): > stat = filedata[j] > j += 1 > - text = '' > + data = [] > while j < len(filedata) and filedata[j]['code'] in > ('text', 'unicode', 'binary'): > - text += filedata[j]['data'] > + data.append(filedata[j]['data']) > del filedata[j]['data'] > j += 1 > + text = "".join(data) > > if not stat.has_key('depotFile'): > sys.stderr.write("p4 print fails with: %s\n" % repr(stat)) > -- > 1.6.1.3 > -- > To unsubscribe from this list: send the line "unsubscribe git" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html > ``` ## Sam Hocevar, 2009-03-05 17:23 Subject: Re: [PATCH] git-p4: improve performance with large files Message-ID: <20090305172332.GF25693@zoy.org> URL: https://gitlist.dev/e/20090305172332.GF25693%40zoy.org In-Reply-To: <20090305100527.shmtfbdvk0ggsk4s@webmail.fussycoder.id.au> ``` On Thu, Mar 05, 2009, thestar@fussycoder.id.au wrote: > > The current git-p4 way of concatenating strings performs in O(n^2) > >and is therefore terribly slow with large files because of unnecessary > >memory copies. The following patch makes the operation O(n). > > The reason why it uses simple concatenation is to cut down on memory usage. > - It is a tradeoff. > > I think the modification you have made below is reasonable, however be > aware that memory usage could double, which substantially reduce the > size of the changesets that git-p4 would be able to import /at all/, > rather than to merely be slow. Uhm, no. The memory usage could be an additional X, where X is the size of the biggest file in the commit. Remember that commit() stores the complete commit data in memory before sending it to fast-import. Also, on my machine the extra memory is already used because at some point, "text += foo" calls realloc() anyway and often duplicates the memory used by text. The ideal solution is to use a generator and refactor the commit handling as a stream. I am working on that but it involves deeper changes, so as I am not sure it will be accepted, I'm providing the attached compromise patch first. At least it solves the appaling speed issue. I tuned it so that it never uses more than 32 MiB extra memory. Signed-off-by: Sam Hocevar --- contrib/fast-import/git-p4 | 10 +++++++++- 1 files changed, 9 insertions(+), 1 deletions(-) diff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4 index 3832f60..151ae1c 100755 --- a/contrib/fast-import/git-p4 +++ b/contrib/fast-import/git-p4 @@ -984,11 +984,19 @@ class P4Sync(Command): while j < len(filedata): stat = filedata[j] j += 1 + data = [] text = '' while j < len(filedata) and filedata[j]['code'] in ('text', 'unicod e', 'binary'): - text += filedata[j]['data'] + data.append(filedata[j]['data']) del filedata[j]['data'] + # p4 sends 4k chunks, make sure we don't use more than 32 MiB + # of additional memory while rebuilding the file data. + if len(data) > 8192: + text += ''.join(data) + data = [] j += 1 + text += ''.join(data) + del data if not stat.has_key('depotFile'): sys.stderr.write("p4 print fails with: %s\n" % repr(stat)) -- Sam. ``` ## thestar@fussycoder.id.au, 2009-03-06 00:01 Subject: Re: [PATCH] git-p4: improve performance with large files Message-ID: <20090306110107.cv3x1n7uskwg04cs@webmail.fussycoder.id.au> URL: https://gitlist.dev/e/20090306110107.cv3x1n7uskwg04cs%40webmail.fussycoder.id.au In-Reply-To: <20090305172332.GF25693@zoy.org> ``` Quoting Sam Hocevar : > On Thu, Mar 05, 2009, thestar@fussycoder.id.au wrote: > >> > The current git-p4 way of concatenating strings performs in O(n^2) >> >and is therefore terribly slow with large files because of unnecessary >> >memory copies. The following patch makes the operation O(n). >> >> The reason why it uses simple concatenation is to cut down on memory usage. >> - It is a tradeoff. >> >> I think the modification you have made below is reasonable, however be >> aware that memory usage could double, which substantially reduce the >> size of the changesets that git-p4 would be able to import /at all/, >> rather than to merely be slow. > > Uhm, no. The memory usage could be an additional X, where X is the > size of the biggest file in the commit. Remember that commit() stores > the complete commit data in memory before sending it to fast-import. > Also, on my machine the extra memory is already used because at some > point, "text += foo" calls realloc() anyway and often duplicates the > memory used by text. You are correct - sorry, got confused as I somehow got mistaken that that form (foo += bar) can potentially be optimized, but it doesn't. That's what I get for not paying enough attention to the language used... :( > The ideal solution is to use a generator and refactor the commit > handling as a stream. I am working on that but it involves deeper > changes, so as I am not sure it will be accepted, I'm providing the > attached compromise patch first. At least it solves the appaling speed > issue. I tuned it so that it never uses more than 32 MiB extra memory. That is definitely the ideal solution - I would hope that it gets accepted if you manage to cut down on memory usage - as it really is a limitation for certain repositories. (Infact, this is why I no-longer use git-p4). > > Signed-off-by: Sam Hocevar > --- > contrib/fast-import/git-p4 | 10 +++++++++- > 1 files changed, 9 insertions(+), 1 deletions(-) > > diff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4 > index 3832f60..151ae1c 100755 > --- a/contrib/fast-import/git-p4 > +++ b/contrib/fast-import/git-p4 > @@ -984,11 +984,19 @@ class P4Sync(Command): > while j < len(filedata): > stat = filedata[j] > j += 1 > + data = [] > text = '' > while j < len(filedata) and filedata[j]['code'] in > ('text', 'unicod > e', 'binary'): > - text += filedata[j]['data'] > + data.append(filedata[j]['data']) > del filedata[j]['data'] > + # p4 sends 4k chunks, make sure we don't use more > than 32 MiB > + # of additional memory while rebuilding the file data. > + if len(data) > 8192: > + text += ''.join(data) > + data = [] > j += 1 > + text += ''.join(data) > + del data > > if not stat.has_key('depotFile'): > sys.stderr.write("p4 print fails with: %s\n" % repr(stat)) > > -- > Sam. > -- > To unsubscribe from this list: send the line "unsubscribe git" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html > ``` ## Junio C Hamano, 2009-03-06 01:14 Subject: Re: [PATCH] git-p4: improve performance with large files Message-ID: <7vzlfzwiyn.fsf@gitster.siamese.dyndns.org> URL: https://gitlist.dev/e/7vzlfzwiyn.fsf%40gitster.siamese.dyndns.org In-Reply-To: <20090305172332.GF25693@zoy.org> ``` Sam Hocevar writes: > ... The ideal solution is to use a generator and refactor the commit > handling as a stream. I am working on that but it involves deeper > changes, so as I am not sure it will be accepted, I'm providing the > attached compromise patch first. At least it solves the appaling speed > issue. I tuned it so that it never uses more than 32 MiB extra memory. > > Signed-off-by: Sam Hocevar > --- I do not do p4, but the patch looks obviously correct. Comments? > contrib/fast-import/git-p4 | 10 +++++++++- > 1 files changed, 9 insertions(+), 1 deletions(-) > > diff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4 > index 3832f60..151ae1c 100755 > --- a/contrib/fast-import/git-p4 > +++ b/contrib/fast-import/git-p4 > @@ -984,11 +984,19 @@ class P4Sync(Command): > while j < len(filedata): > stat = filedata[j] > j += 1 > + data = [] > text = '' > while j < len(filedata) and filedata[j]['code'] in ('text', 'unicod > e', 'binary'): > - text += filedata[j]['data'] > + data.append(filedata[j]['data']) > del filedata[j]['data'] > + # p4 sends 4k chunks, make sure we don't use more than 32 MiB > + # of additional memory while rebuilding the file data. > + if len(data) > 8192: > + text += ''.join(data) > + data = [] > j += 1 > + text += ''.join(data) > + del data > > if not stat.has_key('depotFile'): > sys.stderr.write("p4 print fails with: %s\n" % repr(stat)) > > -- > Sam. > -- > To unsubscribe from this list: send the line "unsubscribe git" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html ``` ## Han-Wen Nienhuys, 2009-03-06 01:25 Subject: Re: [PATCH] git-p4: improve performance with large files Message-ID: <1d48f7010903051725v510f99f0h2a05b9381ff75ac1@mail.gmail.com> URL: https://gitlist.dev/e/1d48f7010903051725v510f99f0h2a05b9381ff75ac1%40mail.gmail.com In-Reply-To: <7vzlfzwiyn.fsf@gitster.siamese.dyndns.org> ``` I don't understand the point of trying to save the 32 mb, if people are sending you blobs that are that large. The approach to avoid sequences of appends looks sound. On Thu, Mar 5, 2009 at 10:14 PM, Junio C Hamano wrote: >> ... The ideal solution is to use a generator and refactor the commit >> handling as a stream. I am working on that but it involves deeper >> changes, so as I am not sure it will be accepted, I'm providing the >> attached compromise patch first. At least it solves the appaling speed >> issue. I tuned it so that it never uses more than 32 MiB extra memory. >> +            text += ''.join(data) >> +            del data i'd say data = [] add a comment that you're trying to save memory. There is no reason to remove data from the namespace. -- Han-Wen Nienhuys Google Engineering Belo Horizonte hanwen@google.com ``` ## Sam Hocevar, 2009-03-06 08:53 Subject: Re: [PATCH] git-p4: improve performance with large files Message-ID: <20090306085357.GA12880@zoy.org> URL: https://gitlist.dev/e/20090306085357.GA12880%40zoy.org In-Reply-To: <1d48f7010903051725v510f99f0h2a05b9381ff75ac1@mail.gmail.com> ``` On Thu, Mar 05, 2009, Han-Wen Nienhuys wrote: > i'd say > > data = [] > > add a comment that you're trying to save memory. There is no reason to > remove data from the namespace. Okay. Here is an improved version. Signed-off-by: Sam Hocevar --- contrib/fast-import/git-p4 | 13 ++++++++++++- 1 files changed, 12 insertions(+), 1 deletions(-) diff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4 index 3832f60..db0ea0a 100755 --- a/contrib/fast-import/git-p4 +++ b/contrib/fast-import/git-p4 @@ -984,11 +984,22 @@ class P4Sync(Command): while j < len(filedata): stat = filedata[j] j += 1 + data = [] text = '' + # Append data every 8192 chunks to 1) ensure decent performance + # by not making too many string concatenations and 2) avoid + # excessive memory usage by purging "data" often enough. p4 + # sends 4k chunks, so we should not use more than 32 MiB of + # additional memory while rebuilding the file data. while j < len(filedata) and filedata[j]['code'] in ('text', 'unicod e', 'binary'): - text += filedata[j]['data'] + data.append(filedata[j]['data']) del filedata[j]['data'] + if len(data) > 8192: + text += ''.join(data) + data = [] j += 1 + text += ''.join(data) + data = None if not stat.has_key('depotFile'): sys.stderr.write("p4 print fails with: %s\n" % repr(stat)) -- Sam. ``` ## Junio C Hamano, 2009-03-06 09:42 Subject: Re: [PATCH] git-p4: improve performance with large files Message-ID: <7vfxhrt2by.fsf@gitster.siamese.dyndns.org> URL: https://gitlist.dev/e/7vfxhrt2by.fsf%40gitster.siamese.dyndns.org In-Reply-To: <20090306085357.GA12880@zoy.org> ``` Sam Hocevar writes: > On Thu, Mar 05, 2009, Han-Wen Nienhuys wrote: > >> i'd say >> >> data = [] >> >> add a comment that you're trying to save memory. There is no reason to >> remove data from the namespace. > > Okay. Here is an improved version. > > Signed-off-by: Sam Hocevar Sorry, but that's not a commit log message, so signing it off does not add much value to the patch. ``` ## Sam Hocevar, 2009-03-06 10:13 Subject: [PATCH v4] git-p4: improve performance with large files Message-ID: <20090306101339.GB12880@zoy.org> URL: https://gitlist.dev/e/20090306101339.GB12880%40zoy.org In-Reply-To: <7vfxhrt2by.fsf@gitster.siamese.dyndns.org> ``` On Fri, Mar 06, 2009, Junio C Hamano wrote: > Sorry, but that's not a commit log message, so signing it off does not add > much value to the patch. I'm sorry, for some reason git format-patch is eating my commit messages (other commits appear just fine). As I'm doing this from a Windows machine, I smell CR/LF issues in msysgit. Here is a clean version: git-p4: improve performance when importing huge files by reducing the number of string concatenations while constraining memory usage. Signed-off-by: Sam Hocevar --- contrib/fast-import/git-p4 | 13 ++++++++++++- 1 files changed, 12 insertions(+), 1 deletions(-) diff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4 index 3832f60..db0ea0a 100755 --- a/contrib/fast-import/git-p4 +++ b/contrib/fast-import/git-p4 @@ -984,11 +984,22 @@ class P4Sync(Command): while j < len(filedata): stat = filedata[j] j += 1 + data = [] text = '' + # Append data every 8192 chunks to 1) ensure decent performance + # by not making too many string concatenations and 2) avoid + # excessive memory usage by purging "data" often enough. p4 + # sends 4k chunks, so we should not use more than 32 MiB of + # additional memory while rebuilding the file data. while j < len(filedata) and filedata[j]['code'] in ('text', 'unicod e', 'binary'): - text += filedata[j]['data'] + data.append(filedata[j]['data']) del filedata[j]['data'] + if len(data) > 8192: + text += ''.join(data) + data = [] j += 1 + text += ''.join(data) + data = None if not stat.has_key('depotFile'): sys.stderr.write("p4 print fails with: %s\n" % repr(stat)) -- Sam. ``` ## Sam Hocevar, 2009-03-07 12:25 Subject: [PATCH v5] git-p4: improve performance when importing huge files by reducing the number of string concatenations while constraining memory usage. Message-ID: <20090307122517.GA7325@zoy.org> URL: https://gitlist.dev/e/20090307122517.GA7325%40zoy.org In-Reply-To: <20090306101339.GB12880@zoy.org> ``` Signed-off-by: Sam Hocevar --- This is a properly formatted version of the previous patch. contrib/fast-import/git-p4 | 13 ++++++++++++- 1 files changed, 12 insertions(+), 1 deletions(-) diff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4 index 3832f60..db0ea0a 100755 --- a/contrib/fast-import/git-p4 +++ b/contrib/fast-import/git-p4 @@ -984,11 +984,22 @@ class P4Sync(Command): while j < len(filedata): stat = filedata[j] j += 1 + data = [] text = '' + # Append data every 8192 chunks to 1) ensure decent performance + # by not making too many string concatenations and 2) avoid + # excessive memory usage by purging "data" often enough. p4 + # sends 4k chunks, so we should not use more than 32 MiB of + # additional memory while rebuilding the file data. while j < len(filedata) and filedata[j]['code'] in ('text', 'unicode', 'binary'): - text += filedata[j]['data'] + data.append(filedata[j]['data']) del filedata[j]['data'] + if len(data) > 8192: + text += ''.join(data) + data = [] j += 1 + text += ''.join(data) + data = None if not stat.has_key('depotFile'): sys.stderr.write("p4 print fails with: %s\n" % repr(stat)) -- 1.6.1.3 ```