{"thread":{"id":"18719","subject":"[PATCH 0/4] start refactoring binary search function","startedAt":"2009-04-04T20:59:20Z","lastAt":"2009-04-05T09:45:07Z","messageCount":2,"participants":["Christian Couder","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"110344","messageId":"20090404225920.6a10fe78.chriscool@tuxfamily.org","threadId":"18719","inReplyTo":null,"subject":"[PATCH 0/4] start refactoring binary search function","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-04-04T20:59:20Z","receivedAt":"2009-04-04T20:59:20Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"There are many binary search functions in the code base and I have been\nasked to refactor them in these message:\n\nhttp://thread.gmane.org/gmane.comp.version-control.git/105363/focus=105436\nhttp://thread.gmane.org/gmane.comp.version-control.git/114735/focus=115391\n\nso here is a start\n\nThe following patch applies on top of pu where they can be squashed into other\npatches:\n\n  sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1\n  patch-ids: use the new generic \"sha1_pos\" function to lookup sha1\n  bisect: use the new generic \"sha1_pos\" function to lookup sha1\n  replace_object: use the new generic \"sha1_pos\" function to lookup\n    sha1\n\n bisect.c         |   23 +++++-------\n patch-ids.c      |   93 +++-----------------------------------------------\n replace_object.c |   24 +++++--------\n sha1-lookup.c    |  101 ++++++++++++++++++++++++++++++++++++++++++++++++++++++\n sha1-lookup.h    |    7 ++++\n 5 files changed, 131 insertions(+), 117 deletions(-)\n"},{"id":"110392","messageId":"7veiw7wi1o.fsf@gitster.siamese.dyndns.org","threadId":"18719","inReplyTo":"20090404225920.6a10fe78.chriscool@tuxfamily.org","subject":"Re: [PATCH 0/4] start refactoring binary search function","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-04-05T09:45:07Z","receivedAt":"2009-04-05T09:45:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder <chriscool@tuxfamily.org> writes:\n\n> There are many binary search functions in the code base and I have been\n> asked to refactor them in these message:\n>\n> http://thread.gmane.org/gmane.comp.version-control.git/105363/focus=105436\n> http://thread.gmane.org/gmane.comp.version-control.git/114735/focus=115391\n>\n> so here is a start\n>\n> The following patch applies on top of pu where they can be squashed into other\n> patches:\n>\n>   sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1\n>   patch-ids: use the new generic \"sha1_pos\" function to lookup sha1\n>   bisect: use the new generic \"sha1_pos\" function to lookup sha1\n>   replace_object: use the new generic \"sha1_pos\" function to lookup\n>     sha1\n\nI think the refactoring itself does make sense.  Less duplicated code has\nbetter chance to be improved further if there is demonstrated need, and\nI like the series for that \"clean-up\" value alone.\n\nIn the last two patches, however, you advertised the use of this new API\nfor gaining better performance (in exchange for simpler copy-pasted\nimplementation), but changing a simple (base + index * sizeof(struct that\ncontains the sha-1 field)) into a call to a function whose address is\npassed _may_ have larger negative impact to the performance, than what is\ngained by the better initial midpoint selection the new code uses.\n\nIf the extra indirect call turns to degrade the performance too much, we\ncould always reimplement it as a macro, I think, but let's not go there\nbefore somebody runs benchmarks and demonstrates that it is a problem.\n\nI've restructured your existing two branches to take advantage of the\nfirst two patches.\n\nThanks.\n"}]}