{"thread":{"id":"18138","subject":"[PATCH] git-p4: improve performance with large files","startedAt":"2009-03-04T21:54:38Z","lastAt":"2009-03-07T12:25:17Z","messageCount":10,"participants":["Sam Hocevar","thestar@fussycoder.id.au","Junio C Hamano","Han-Wen Nienhuys"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"107007","messageId":"20090304215438.GA12653@zoy.org","threadId":"18138","inReplyTo":null,"subject":"[PATCH] git-p4: improve performance with large files","fromName":"Sam Hocevar","fromEmail":"sam@zoy.org","sentAt":"2009-03-04T21:54:38Z","receivedAt":"2009-03-04T21:54:38Z","isPatch":true,"sender":{"key":"sam@zoy.org","avatar":"https://gravatar.com/avatar/1fc1e5d8c3a8d737f14572135671adfbc0e61ffba5c3bc1d1b8a6f4aac764470?d=mp&s=160"},"body":" The current git-p4 way of concatenating strings performs in O(n^2)\nand is therefore terribly slow with large files because of unnecessary\nmemory copies. The following patch makes the operation O(n).\n\n Using this patch, importing a 17GB repository with large files\n(50 to 500MB) takes 2 hours instead of a week.\n\nSigned-off-by: Sam Hocevar \n---\n contrib/fast-import/git-p4 | 5 +++--\n 1 files changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4\nindex 9fdb0c6..09e9746 100755\n--- a/contrib/fast-import/git-p4\n+++ b/contrib/fast-import/git-p4\n@@ -990,11 +990,12 @@ class P4Sync(Command):\n while j < len(filedata):\n stat = filedata[j]\n j += 1\n- text = ''\n+ data = []\n while j < len(filedata) and filedata[j]['code'] in ('text', 'unicode', 'binary'):\n- text += filedata[j]['data']\n+ data.append(filedata[j]['data'])\n del filedata[j]['data']\n j += 1\n+ text = \"\".join(data)\n \n if not stat.has_key('depotFile'):\n sys.stderr.write(\"p4 print fails with: %s\\n\" % repr(stat))\n-- \n1.6.1.3\n"},{"id":"107008","messageId":"20090305100527.shmtfbdvk0ggsk4s@webmail.fussycoder.id.au","threadId":"18138","inReplyTo":"20090304215438.GA12653@zoy.org","subject":"Re: [PATCH] git-p4: improve performance with large files","fromName":"","fromEmail":"thestar@fussycoder.id.au","sentAt":"2009-03-04T23:05:27Z","receivedAt":"2009-03-04T23:05:27Z","isPatch":true,"sender":{"key":"thestar@fussycoder.id.au","avatar":null},"body":"Quoting Sam Hocevar :\n\n> The current git-p4 way of concatenating strings performs in O(n^2)\n> and is therefore terribly slow with large files because of unnecessary\n> memory copies. The following patch makes the operation O(n).\n\nThe reason why it uses simple concatenation is to cut down on memory usage.\n - It is a tradeoff.\n\nI think the modification you have made below is reasonable, however be \naware that memory usage could double, which substantially reduce the \nsize of the changesets that git-p4 would be able to import /at all/, \nrather than to merely be slow.\n\nThat said, you do need to delete the data temporary array to cut down \non memory.\n -- I would do this immediately after the \"\".join(data).\n\n>\n> Using this patch, importing a 17GB repository with large files\n> (50 to 500MB) takes 2 hours instead of a week.\n>\n> Signed-off-by: Sam Hocevar \n> ---\n> contrib/fast-import/git-p4 | 5 +++--\n> 1 files changed, 3 insertions(+), 2 deletions(-)\n>\n> diff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4\n> index 9fdb0c6..09e9746 100755\n> --- a/contrib/fast-import/git-p4\n> +++ b/contrib/fast-import/git-p4\n> @@ -990,11 +990,12 @@ class P4Sync(Command):\n> while j < len(filedata):\n> stat = filedata[j]\n> j += 1\n> - text = ''\n> + data = []\n> while j < len(filedata) and filedata[j]['code'] in \n> ('text', 'unicode', 'binary'):\n> - text += filedata[j]['data']\n> + data.append(filedata[j]['data'])\n> del filedata[j]['data']\n> j += 1\n> + text = \"\".join(data)\n>\n> if not stat.has_key('depotFile'):\n> sys.stderr.write(\"p4 print fails with: %s\\n\" % repr(stat))\n> --\n> 1.6.1.3\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n>\n"},{"id":"107084","messageId":"20090305172332.GF25693@zoy.org","threadId":"18138","inReplyTo":"20090305100527.shmtfbdvk0ggsk4s@webmail.fussycoder.id.au","subject":"Re: [PATCH] git-p4: improve performance with large files","fromName":"Sam Hocevar","fromEmail":"sam@zoy.org","sentAt":"2009-03-05T17:23:33Z","receivedAt":"2009-03-05T17:23:33Z","isPatch":true,"sender":{"key":"sam@zoy.org","avatar":"https://gravatar.com/avatar/1fc1e5d8c3a8d737f14572135671adfbc0e61ffba5c3bc1d1b8a6f4aac764470?d=mp&s=160"},"body":"On Thu, Mar 05, 2009, thestar@fussycoder.id.au wrote:\n\n> > The current git-p4 way of concatenating strings performs in O(n^2)\n> >and is therefore terribly slow with large files because of unnecessary\n> >memory copies. The following patch makes the operation O(n).\n> \n> The reason why it uses simple concatenation is to cut down on memory usage.\n> - It is a tradeoff.\n> \n> I think the modification you have made below is reasonable, however be \n> aware that memory usage could double, which substantially reduce the \n> size of the changesets that git-p4 would be able to import /at all/, \n> rather than to merely be slow.\n\n Uhm, no. The memory usage could be an additional X, where X is the\nsize of the biggest file in the commit. Remember that commit() stores\nthe complete commit data in memory before sending it to fast-import.\nAlso, on my machine the extra memory is already used because at some\npoint, \"text += foo\" calls realloc() anyway and often duplicates the\nmemory used by text.\n\n The ideal solution is to use a generator and refactor the commit\nhandling as a stream. I am working on that but it involves deeper\nchanges, so as I am not sure it will be accepted, I'm providing the\nattached compromise patch first. At least it solves the appaling speed\nissue. I tuned it so that it never uses more than 32 MiB extra memory.\n\nSigned-off-by: Sam Hocevar \n---\n contrib/fast-import/git-p4 | 10 +++++++++-\n 1 files changed, 9 insertions(+), 1 deletions(-)\n\ndiff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4\nindex 3832f60..151ae1c 100755\n--- a/contrib/fast-import/git-p4\n+++ b/contrib/fast-import/git-p4\n@@ -984,11 +984,19 @@ class P4Sync(Command):\n while j < len(filedata):\n stat = filedata[j]\n j += 1\n+ data = []\n text = ''\n while j < len(filedata) and filedata[j]['code'] in ('text', 'unicod\ne', 'binary'):\n- text += filedata[j]['data']\n+ data.append(filedata[j]['data'])\n del filedata[j]['data']\n+ # p4 sends 4k chunks, make sure we don't use more than 32 MiB\n+ # of additional memory while rebuilding the file data.\n+ if len(data) > 8192:\n+ text += ''.join(data)\n+ data = []\n j += 1\n+ text += ''.join(data)\n+ del data\n\n if not stat.has_key('depotFile'):\n sys.stderr.write(\"p4 print fails with: %s\\n\" % repr(stat))\n\n-- \nSam.\n"},{"id":"107120","messageId":"20090306110107.cv3x1n7uskwg04cs@webmail.fussycoder.id.au","threadId":"18138","inReplyTo":"20090305172332.GF25693@zoy.org","subject":"Re: [PATCH] git-p4: improve performance with large files","fromName":"","fromEmail":"thestar@fussycoder.id.au","sentAt":"2009-03-06T00:01:07Z","receivedAt":"2009-03-06T00:01:07Z","isPatch":true,"sender":{"key":"thestar@fussycoder.id.au","avatar":null},"body":"Quoting Sam Hocevar :\n\n> On Thu, Mar 05, 2009, thestar@fussycoder.id.au wrote:\n>\n>> > The current git-p4 way of concatenating strings performs in O(n^2)\n>> >and is therefore terribly slow with large files because of unnecessary\n>> >memory copies. The following patch makes the operation O(n).\n>>\n>> The reason why it uses simple concatenation is to cut down on memory usage.\n>> - It is a tradeoff.\n>>\n>> I think the modification you have made below is reasonable, however be\n>> aware that memory usage could double, which substantially reduce the\n>> size of the changesets that git-p4 would be able to import /at all/,\n>> rather than to merely be slow.\n>\n> Uhm, no. The memory usage could be an additional X, where X is the\n> size of the biggest file in the commit. Remember that commit() stores\n> the complete commit data in memory before sending it to fast-import.\n> Also, on my machine the extra memory is already used because at some\n> point, \"text += foo\" calls realloc() anyway and often duplicates the\n> memory used by text.\n\nYou are correct - sorry, got confused as I somehow got mistaken that \nthat form (foo += bar) can potentially be optimized, but it doesn't. \nThat's what I get for not paying enough attention to the language \nused... :(\n\n> The ideal solution is to use a generator and refactor the commit\n> handling as a stream. I am working on that but it involves deeper\n> changes, so as I am not sure it will be accepted, I'm providing the\n> attached compromise patch first. At least it solves the appaling speed\n> issue. I tuned it so that it never uses more than 32 MiB extra memory.\n\nThat is definitely the ideal solution - I would hope that it gets \naccepted if you manage to cut down on memory usage - as it really is a \nlimitation for certain repositories. (Infact, this is why I no-longer \nuse git-p4).\n\n>\n> Signed-off-by: Sam Hocevar \n> ---\n> contrib/fast-import/git-p4 | 10 +++++++++-\n> 1 files changed, 9 insertions(+), 1 deletions(-)\n>\n> diff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4\n> index 3832f60..151ae1c 100755\n> --- a/contrib/fast-import/git-p4\n> +++ b/contrib/fast-import/git-p4\n> @@ -984,11 +984,19 @@ class P4Sync(Command):\n> while j < len(filedata):\n> stat = filedata[j]\n> j += 1\n> + data = []\n> text = ''\n> while j < len(filedata) and filedata[j]['code'] in \n> ('text', 'unicod\n> e', 'binary'):\n> - text += filedata[j]['data']\n> + data.append(filedata[j]['data'])\n> del filedata[j]['data']\n> + # p4 sends 4k chunks, make sure we don't use more \n> than 32 MiB\n> + # of additional memory while rebuilding the file data.\n> + if len(data) > 8192:\n> + text += ''.join(data)\n> + data = []\n> j += 1\n> + text += ''.join(data)\n> + del data\n>\n> if not stat.has_key('depotFile'):\n> sys.stderr.write(\"p4 print fails with: %s\\n\" % repr(stat))\n>\n> --\n> Sam.\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n>\n"},{"id":"107125","messageId":"7vzlfzwiyn.fsf@gitster.siamese.dyndns.org","threadId":"18138","inReplyTo":"20090305172332.GF25693@zoy.org","subject":"Re: [PATCH] git-p4: improve performance with large files","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-03-06T01:14:40Z","receivedAt":"2009-03-06T01:14:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\nSam Hocevar writes:\n\n> ... The ideal solution is to use a generator and refactor the commit\n> handling as a stream. I am working on that but it involves deeper\n> changes, so as I am not sure it will be accepted, I'm providing the\n> attached compromise patch first. At least it solves the appaling speed\n> issue. I tuned it so that it never uses more than 32 MiB extra memory.\n>\n> Signed-off-by: Sam Hocevar \n> ---\n\nI do not do p4, but the patch looks obviously correct. Comments?\n\n> contrib/fast-import/git-p4 | 10 +++++++++-\n> 1 files changed, 9 insertions(+), 1 deletions(-)\n>\n> diff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4\n> index 3832f60..151ae1c 100755\n> --- a/contrib/fast-import/git-p4\n> +++ b/contrib/fast-import/git-p4\n> @@ -984,11 +984,19 @@ class P4Sync(Command):\n> while j < len(filedata):\n> stat = filedata[j]\n> j += 1\n> + data = []\n> text = ''\n> while j < len(filedata) and filedata[j]['code'] in ('text', 'unicod\n> e', 'binary'):\n> - text += filedata[j]['data']\n> + data.append(filedata[j]['data'])\n> del filedata[j]['data']\n> + # p4 sends 4k chunks, make sure we don't use more than 32 MiB\n> + # of additional memory while rebuilding the file data.\n> + if len(data) > 8192:\n> + text += ''.join(data)\n> + data = []\n> j += 1\n> + text += ''.join(data)\n> + del data\n>\n> if not stat.has_key('depotFile'):\n> sys.stderr.write(\"p4 print fails with: %s\\n\" % repr(stat))\n>\n> -- \n> Sam.\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n"},{"id":"107126","messageId":"1d48f7010903051725v510f99f0h2a05b9381ff75ac1@mail.gmail.com","threadId":"18138","inReplyTo":"7vzlfzwiyn.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] git-p4: improve performance with large files","fromName":"Han-Wen Nienhuys","fromEmail":"hanwen@google.com","sentAt":"2009-03-06T01:25:48Z","receivedAt":"2009-03-06T01:25:48Z","isPatch":true,"sender":{"key":"hanwen@google.com","avatar":"https://avatars.githubusercontent.com/u/31547?v=4"},"body":"I don't understand the point of trying to save the 32 mb, if people\nare sending you blobs that are that large.\n\nThe approach to avoid sequences of appends looks sound.\n\n\nOn Thu, Mar 5, 2009 at 10:14 PM, Junio C Hamano wrote:\n\n>> ... The ideal solution is to use a generator and refactor the commit\n>> handling as a stream. I am working on that but it involves deeper\n>> changes, so as I am not sure it will be accepted, I'm providing the\n>> attached compromise patch first. At least it solves the appaling speed\n>> issue. I tuned it so that it never uses more than 32 MiB extra memory.\n\n>> +            text += ''.join(data)\n>> +            del data\n\ni'd say\n\n data = []\n\nadd a comment that you're trying to save memory. There is no reason to\nremove data from the namespace.\n\n-- \nHan-Wen Nienhuys\nGoogle Engineering Belo Horizonte\nhanwen@google.com\n"},{"id":"107168","messageId":"20090306085357.GA12880@zoy.org","threadId":"18138","inReplyTo":"1d48f7010903051725v510f99f0h2a05b9381ff75ac1@mail.gmail.com","subject":"Re: [PATCH] git-p4: improve performance with large files","fromName":"Sam Hocevar","fromEmail":"sam@zoy.org","sentAt":"2009-03-06T08:53:59Z","receivedAt":"2009-03-06T08:53:59Z","isPatch":true,"sender":{"key":"sam@zoy.org","avatar":"https://gravatar.com/avatar/1fc1e5d8c3a8d737f14572135671adfbc0e61ffba5c3bc1d1b8a6f4aac764470?d=mp&s=160"},"body":"On Thu, Mar 05, 2009, Han-Wen Nienhuys wrote:\n\n> i'd say\n> \n> data = []\n> \n> add a comment that you're trying to save memory. There is no reason to\n> remove data from the namespace.\n\n Okay. Here is an improved version.\n\nSigned-off-by: Sam Hocevar \n---\n contrib/fast-import/git-p4 | 13 ++++++++++++-\n 1 files changed, 12 insertions(+), 1 deletions(-)\n\ndiff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4\nindex 3832f60..db0ea0a 100755\n--- a/contrib/fast-import/git-p4\n+++ b/contrib/fast-import/git-p4\n@@ -984,11 +984,22 @@ class P4Sync(Command):\n while j < len(filedata):\n stat = filedata[j]\n j += 1\n+ data = []\n text = ''\n+ # Append data every 8192 chunks to 1) ensure decent performance\n+ # by not making too many string concatenations and 2) avoid\n+ # excessive memory usage by purging \"data\" often enough. p4\n+ # sends 4k chunks, so we should not use more than 32 MiB of\n+ # additional memory while rebuilding the file data.\n while j < len(filedata) and filedata[j]['code'] in ('text', 'unicod\ne', 'binary'):\n- text += filedata[j]['data']\n+ data.append(filedata[j]['data'])\n del filedata[j]['data']\n+ if len(data) > 8192:\n+ text += ''.join(data)\n+ data = []\n j += 1\n+ text += ''.join(data)\n+ data = None\n\n if not stat.has_key('depotFile'):\n sys.stderr.write(\"p4 print fails with: %s\\n\" % repr(stat))\n\n-- \nSam.\n"},{"id":"107171","messageId":"7vfxhrt2by.fsf@gitster.siamese.dyndns.org","threadId":"18138","inReplyTo":"20090306085357.GA12880@zoy.org","subject":"Re: [PATCH] git-p4: improve performance with large files","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-03-06T09:42:09Z","receivedAt":"2009-03-06T09:42:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Sam Hocevar writes:\n\n> On Thu, Mar 05, 2009, Han-Wen Nienhuys wrote:\n>\n>> i'd say\n>> \n>> data = []\n>> \n>> add a comment that you're trying to save memory. There is no reason to\n>> remove data from the namespace.\n>\n> Okay. Here is an improved version.\n>\n> Signed-off-by: Sam Hocevar \n\nSorry, but that's not a commit log message, so signing it off does not add\nmuch value to the patch.\n"},{"id":"107175","messageId":"20090306101339.GB12880@zoy.org","threadId":"18138","inReplyTo":"7vfxhrt2by.fsf@gitster.siamese.dyndns.org","subject":"[PATCH v4] git-p4: improve performance with large files","fromName":"Sam Hocevar","fromEmail":"sam@zoy.org","sentAt":"2009-03-06T10:13:39Z","receivedAt":"2009-03-06T10:13:39Z","isPatch":true,"sender":{"key":"sam@zoy.org","avatar":"https://gravatar.com/avatar/1fc1e5d8c3a8d737f14572135671adfbc0e61ffba5c3bc1d1b8a6f4aac764470?d=mp&s=160"},"body":"On Fri, Mar 06, 2009, Junio C Hamano wrote:\n\n> Sorry, but that's not a commit log message, so signing it off does not add\n> much value to the patch.\n\n I'm sorry, for some reason git format-patch is eating my commit\nmessages (other commits appear just fine). As I'm doing this from a\nWindows machine, I smell CR/LF issues in msysgit. Here is a clean\nversion:\n\n\ngit-p4: improve performance when importing huge files by reducing\nthe number of string concatenations while constraining memory usage.\n\nSigned-off-by: Sam Hocevar \n---\n contrib/fast-import/git-p4 | 13 ++++++++++++-\n 1 files changed, 12 insertions(+), 1 deletions(-)\n\ndiff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4\nindex 3832f60..db0ea0a 100755\n--- a/contrib/fast-import/git-p4\n+++ b/contrib/fast-import/git-p4\n@@ -984,11 +984,22 @@ class P4Sync(Command):\n while j < len(filedata):\n stat = filedata[j]\n j += 1\n+ data = []\n text = ''\n+ # Append data every 8192 chunks to 1) ensure decent performance\n+ # by not making too many string concatenations and 2) avoid\n+ # excessive memory usage by purging \"data\" often enough. p4\n+ # sends 4k chunks, so we should not use more than 32 MiB of\n+ # additional memory while rebuilding the file data.\n while j < len(filedata) and filedata[j]['code'] in ('text', 'unicod\ne', 'binary'):\n- text += filedata[j]['data']\n+ data.append(filedata[j]['data'])\n del filedata[j]['data']\n+ if len(data) > 8192:\n+ text += ''.join(data)\n+ data = []\n j += 1\n+ text += ''.join(data)\n+ data = None\n\n if not stat.has_key('depotFile'):\n sys.stderr.write(\"p4 print fails with: %s\\n\" % repr(stat))\n-- \nSam.\n"},{"id":"107294","messageId":"20090307122517.GA7325@zoy.org","threadId":"18138","inReplyTo":"20090306101339.GB12880@zoy.org","subject":"[PATCH v5] git-p4: improve performance when importing huge files by reducing the number of string concatenations while constraining memory usage.","fromName":"Sam Hocevar","fromEmail":"sam@zoy.org","sentAt":"2009-03-07T12:25:17Z","receivedAt":"2009-03-07T12:25:17Z","isPatch":true,"sender":{"key":"sam@zoy.org","avatar":"https://gravatar.com/avatar/1fc1e5d8c3a8d737f14572135671adfbc0e61ffba5c3bc1d1b8a6f4aac764470?d=mp&s=160"},"body":"\nSigned-off-by: Sam Hocevar \n---\n This is a properly formatted version of the previous patch.\n\n contrib/fast-import/git-p4 | 13 ++++++++++++-\n 1 files changed, 12 insertions(+), 1 deletions(-)\n\ndiff --git a/contrib/fast-import/git-p4 b/contrib/fast-import/git-p4\nindex 3832f60..db0ea0a 100755\n--- a/contrib/fast-import/git-p4\n+++ b/contrib/fast-import/git-p4\n@@ -984,11 +984,22 @@ class P4Sync(Command):\n while j < len(filedata):\n stat = filedata[j]\n j += 1\n+ data = []\n text = ''\n+ # Append data every 8192 chunks to 1) ensure decent performance\n+ # by not making too many string concatenations and 2) avoid\n+ # excessive memory usage by purging \"data\" often enough. p4\n+ # sends 4k chunks, so we should not use more than 32 MiB of\n+ # additional memory while rebuilding the file data.\n while j < len(filedata) and filedata[j]['code'] in ('text', 'unicode', 'binary'):\n- text += filedata[j]['data']\n+ data.append(filedata[j]['data'])\n del filedata[j]['data']\n+ if len(data) > 8192:\n+ text += ''.join(data)\n+ data = []\n j += 1\n+ text += ''.join(data)\n+ data = None\n \n if not stat.has_key('depotFile'):\n sys.stderr.write(\"p4 print fails with: %s\\n\" % repr(stat))\n-- \n1.6.1.3\n"}]}