{"thread":{"id":"22642","subject":"[PATCH 0/5] Speed up string search routines","startedAt":"2010-02-13T14:20:14Z","lastAt":"2010-02-14T20:16:05Z","messageCount":4,"participants":["Fredrik Kuivinen","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"134430","messageId":"20100213142014.GA9543@fredrik-laptop","threadId":"22642","inReplyTo":null,"subject":"[PATCH 0/5] Speed up string search routines","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2010-02-13T14:20:14Z","receivedAt":"2010-02-13T14:20:14Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"This series speeds up git grep and pickaxe by using the string search\nroutines from GNU grep.\n\n---\n\nFredrik Kuivinen (5):\n      Use kwset in grep\n      Use kwset in pickaxe\n      Adapt the kwset code to Git\n      Add string search routines from GNU grep\n      Add obstack.[ch] from EGLIBC 2.10\n\n\n Makefile           |    2 \n diffcore-pickaxe.c |   34 ++\n grep.c             |   61 +++-\n grep.h             |    2 \n kwset.c            |  775 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n kwset.h            |   62 ++++\n obstack.c          |  441 ++++++++++++++++++++++++++++++\n obstack.h          |  509 ++++++++++++++++++++++++++++++++++\n 8 files changed, 1855 insertions(+), 31 deletions(-)\n create mode 100644 kwset.c\n create mode 100644 kwset.h\n create mode 100644 obstack.c\n create mode 100644 obstack.h\n"},{"id":"134454","messageId":"7vk4uhklxm.fsf@alter.siamese.dyndns.org","threadId":"22642","inReplyTo":"20100213142014.GA9543@fredrik-laptop","subject":"Re: [PATCH 0/5] Speed up string search routines","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-02-13T18:52:37Z","receivedAt":"2010-02-13T18:52:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen <frekui@gmail.com> writes:\n\n> This series speeds up git grep and pickaxe by using the string search\n> routines from GNU grep.\n\nThanks.\n\nIt needs to be a bit more friendly to readers of \"git log\" and\nReleaseNotes by hinting why use of kwset is beneficial (e.g. \"use kwset\ninstead of memmem to find fixed string more efficiently\") in the commit\ntitles.\n\nThe preference of using GPLv2 version was already mentioned by a few\npeople.\n\nShouldn't obstack.[ch] be in compat/ so that people on platforms where\nthey are natively available do not have to compile our own copies?\n\nIt is somewhat curious that you gave numbers for only negative case in\npickaxe test and numbers for only positive case in grep test.  Does this\nconversion have some interesting performance charasteristics such as\npenalizing positive-match case to speed up negative-match case or vice\nversa (the earlier \"grep lookahead\" work had that effect, even though the\ndownside was really small)?\n"},{"id":"134557","messageId":"4c8ef71002140847i19b64b21ocfa71658a49d97b5@mail.gmail.com","threadId":"22642","inReplyTo":"7vk4uhklxm.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 0/5] Speed up string search routines","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2010-02-14T16:47:05Z","receivedAt":"2010-02-14T16:47:05Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Sat, Feb 13, 2010 at 19:52, Junio C Hamano <gitster@pobox.com> wrote:\n> Fredrik Kuivinen <frekui@gmail.com> writes:\n>\n> It needs to be a bit more friendly to readers of \"git log\" and\n> ReleaseNotes by hinting why use of kwset is beneficial (e.g. \"use kwset\n> instead of memmem to find fixed string more efficiently\") in the commit\n> titles.\n\nWill fix in the next iteration.\n\n> Shouldn't obstack.[ch] be in compat/ so that people on platforms where\n> they are natively available do not have to compile our own copies?\n\nThere is code in obstack.c to check if we are using gnu libc or not.\nIf gnu libc is used, then ELIDE_CODE is defined and no code from\nobstack.c is compiled.\n\n> It is somewhat curious that you gave numbers for only negative case in\n> pickaxe test and numbers for only positive case in grep test.  Does this\n> conversion have some interesting performance charasteristics such as\n> penalizing positive-match case to speed up negative-match case or vice\n> versa (the earlier \"grep lookahead\" work had that effect, even though the\n> downside was really small)?\n\nI did some more benchmarking. In the extreme case when we are looking\nfor ' ' (i.e., a single space) with pickaxe the new code is actually\nslightly slower than the old one.\n\nbefore:\n\n$ time git log -S' ' > /dev/null\n\nreal\t0m32.908s\nuser\t0m32.258s\nsys\t0m0.652s\n\nafter:\n\n$ time ./git-log -S' ' > /dev/null\n\nreal\t0m34.072s\nuser\t0m33.418s\nsys\t0m0.656s\n\nHowever, with longer strings the new code wins (the new code wins when\nwe are searching for two spaces).\n\ngrep gets a significant performance increase for all strings I have\ntried, it doesn't matter if there are no matches or a lot of matches.\n\nThanks for the comments.\n\n- Fredrik\n"},{"id":"134568","messageId":"7v3a13fu9m.fsf@alter.siamese.dyndns.org","threadId":"22642","inReplyTo":"4c8ef71002140847i19b64b21ocfa71658a49d97b5@mail.gmail.com","subject":"Re: [PATCH 0/5] Speed up string search routines","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-02-14T20:16:05Z","receivedAt":"2010-02-14T20:16:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen <frekui@gmail.com> writes:\n\n> There is code in obstack.c to check if we are using gnu libc or not.\n> If gnu libc is used, then ELIDE_CODE is defined and no code from\n> obstack.c is compiled.\n\nThanks; that explains why there is no need to change Makefile to customize\nwhere obstack is taken from.\n\nBut I am not a big fan of keeping borrowed code mixed together in the same\ndirectory with our own code.  For something as large as xdiff, giving it\nits own directory made sense, but for only two files, I thought compat/\nwould be a good place, hence my suggesiton.  kwset would probably want to\ngo together with them somewhere.\n"}]}