From: Christian Couder Date: Sun, 10 May 2009 04:44:14 GMT Subject: Re: [PATCH 07/10] bisect: automatically sort sha1_array if needed when looking it up Message-ID: <200905100644.14786.chriscool@tuxfamily.org> In-Reply-To: Le samedi 9 mai 2009, Jakub Narebski a écrit : > Christian Couder writes: > > This makes sha1_array easier to use, so later patches will be simpler. > > Hmmm... sort on lookup array. I wonder if it would be worth > librarizing, and if there is any smart optimization for that (like > e.g. heap for fast access to smallest value and fast insertion, using > insertion sort for almost sorted array, etc.). > > BTW. does it become unsorted anywhere? No, it doesn't. We first read all the "refs/bisect/good-*" and "refs/bisect/skip-*" and put them in some "struct sha1_array". Then later we may lookup sha1 there from 2 different functions: "check_merge_bases" first and then "filter_skipped". This patch optimizes by not sorting before we lookup, so if we don't lookup anything, we pay no sorting price. Best regards, Christian.