Thanks Neil,
On Tue, May 19, 2009 at 12:55 PM, NeilBrown <neilb@xxxxxxx> wrote:
> On Tue, May 19, 2009 4:23 pm, SandeepKsinha wrote:
>> Hi Neil,
>>
>> I have made the desired changes and have tested the changes as well.
>> As expected the performance gain with number of devices ( > 20 ) is
>> quite visible.
>
> How did you measure the performance gain and what were your
> results?
>
I created arrays with 20 devices and performed random I/O it.
The results with linear search were slower as compared to binary.
>> The code also looks simpler as compared to what it earlier was.
>>
>> I have created the following patches for the changes:
>>
>> PATCH [01/03] md: Removal of num_sectors from dev_info in linear raid
>>
>> This patch removes the num_sectors from dev_info and makes use of the
>> rdev->sectors for
>> all further usage.
>
> Could I as you to redo this one a little differently?
> I want to keep the linear search very tight, and you have just added
> a pointer de-reference to it.
>
> If you could replace start_sector by end_sector, we wouldn't need that
> de-reference or the addition.
>
>
I would make the required changes.
>>
>> PATCH[02/03] md: Getting rid of sector_div and hash table in linear raid
>>
>> Removal of all the code pertaining hast table and other related data
>> structures.
>> This also makes the code really really simple.
>> The searching being made linear for the time being to test the patch.
>>
>> PATCH[03/03] md: Replacing linear with a binary search
>>
>> This patch replaces the linear search in which_dev with binary search.
>
> Two things wrong with you binary search.
> 1/ the while() condition is "hi >= lo". That will always be true, so it
> would be better to make that explicit. i.e. "while(1)".
> However the while loop of a binary search should be
> while (hi > lo)
>
> 2/ You have 3 comparisons against 'sector' inside the loop. There should
> only be one. We are aiming for speed remember :-)
>
> while (hi > lo) {
> mid = (hi + lo + 1) / 2;
> dev = conf->disks + mid;
>
> if (sector >= dev->start_sector)
> lo = mid;
> else
> hi = mid - 1;
> }
> return dev;
>
> With that formulation, you don't even need to replace
> sector_start by sector_end.. However doing so would make other
> code simpler, so please do proceed with replacing sector_start by
> sector_end.
> Then the binary search (with a fix because dev can be uninitialised),
> becomes:
>
> while (hi > lo) {
> mid = (hi + lo) / 2;
>
> if (sector < conf->disks[mid].end_sector)
> hi = mid;
> else
> lo = mid + 1;
> }
> return conf->disks + lo;
>
I will make this change too.
Thanks.
> NeilBrown
>
>
>
>
--
Regards,
Sandeep.
“To learn is to change. Education is a process that changes the learner.”
--
To unsubscribe from this list: send the line "unsubscribe linux-raid" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
