[PATCH] md: Enhancements and clean to linear RAID

[PATCH] md: Enhancements and clean to linear RAID

[SandeepKsinha]

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.
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.

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.

The patches will follow this mail.


-- 
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@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] md: Enhancements and clean to linear RAID

[NeilBrown]

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?

> 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.


>
> 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;

NeilBrown

Re: [PATCH] md: Enhancements and clean to linear RAID

[SandeepKsinha]

Thanks Neil,


On Tue, May 19, 2009 at 12:55 PM, NeilBrown <neilb@suse.de> 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@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] md: Enhancements and clean to linear RAID

[SandeepKsinha]

Hi Neil,

I have made all the required changes and have tested the changes.
It works fine.

Thanks for enlightening me, the changes really optimized the code further.

The patches will be followed by this mail.

On Tue, May 19, 2009 at 1:01 PM, SandeepKsinha <sandeepksinha@gmail.com> wrote:
> Thanks Neil,
>
>
> On Tue, May 19, 2009 at 12:55 PM, NeilBrown <neilb@suse.de> 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.”
>



-- 
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@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] md: Enhancements and clean to linear RAID

[Neil Brown]

On Tuesday May 19, sandeepksinha@gmail.com wrote:
> Hi Neil,
> 
> I have made all the required changes and have tested the changes.
> It works fine.
> 
> Thanks for enlightening me, the changes really optimized the code further.
> 
> The patches will be followed by this mail.

Thanks.
I have applied them all (with very minor cleanups) and pushed them to
my for-next tree.
They can be viewed here:
    http://neil.brown.name/git?p=md;a=shortlog;h=refs/heads/for-next

I have taken the liberty of rewriting the introductory comments on the
patches a little.  I hope you don't mind.

One important part of the patches that was missing was a
"signed-off-by" line.
Please read section 12 of Documentation/SubmittingPatches
and then if you agree that the you an certify the Developer's
Certificate of Origin on these patches, please write explicitly that I
should add your Signed-off-by line to these patches.

I have no doubt that the patches are suitably original, but the
process requires that you explicitly tell me so.

Thanks,
NeilBrown

Re: [PATCH] md: Enhancements and clean to linear RAID

[SandeepKsinha]

Hi Neil,

On Tue, May 19, 2009 at 5:08 PM, Neil Brown <neilb@suse.de> wrote:
> On Tuesday May 19, sandeepksinha@gmail.com wrote:
>> Hi Neil,
>>
>> I have made all the required changes and have tested the changes.
>> It works fine.
>>
>> Thanks for enlightening me, the changes really optimized the code further.
>>
>> The patches will be followed by this mail.
>
> Thanks.
> I have applied them all (with very minor cleanups) and pushed them to
> my for-next tree.
> They can be viewed here:
>    http://neil.brown.name/git?p=md;a=shortlog;h=refs/heads/for-next
>
> I have taken the liberty of rewriting the introductory comments on the
> patches a little.  I hope you don't mind.
>

Sure. You always have the liberty to do so.

> One important part of the patches that was missing was a
> "signed-off-by" line.
> Please read section 12 of Documentation/SubmittingPatches
> and then if you agree that the you an certify the Developer's
> Certificate of Origin on these patches, please write explicitly that I
> should add your Signed-off-by line to these patches.
>

Yes, So, I kindly request you to add
"Signed-off-by: Sandeep K Sinha <sandeepksinha@gmail.com>"
against each of the patches.

Thanks a lot.

> I have no doubt that the patches are suitably original, but the
> process requires that you explicitly tell me so.
>
> 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@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] md: Enhancements and clean to linear RAID

[Sujit Karataparambil]

Neil,

Is there any git tree where the test cases can be added.
These seem to be huge changes with regard to the dev
interface.

Hopefully the test cases can be added in specific cases.

Thanks,
Sujit

On Tue, May 19, 2009 at 5:26 PM, SandeepKsinha <sandeepksinha@gmail.com> wrote:
> Hi Neil,
>
> On Tue, May 19, 2009 at 5:08 PM, Neil Brown <neilb@suse.de> wrote:
>> On Tuesday May 19, sandeepksinha@gmail.com wrote:
>>> Hi Neil,
>>>
>>> I have made all the required changes and have tested the changes.
>>> It works fine.
>>>
>>> Thanks for enlightening me, the changes really optimized the code further.
>>>
>>> The patches will be followed by this mail.
>>
>> Thanks.
>> I have applied them all (with very minor cleanups) and pushed them to
>> my for-next tree.
>> They can be viewed here:
>>    http://neil.brown.name/git?p=md;a=shortlog;h=refs/heads/for-next
>>
>> I have taken the liberty of rewriting the introductory comments on the
>> patches a little.  I hope you don't mind.
>>
>
> Sure. You always have the liberty to do so.
>
>> One important part of the patches that was missing was a
>> "signed-off-by" line.
>> Please read section 12 of Documentation/SubmittingPatches
>> and then if you agree that the you an certify the Developer's
>> Certificate of Origin on these patches, please write explicitly that I
>> should add your Signed-off-by line to these patches.
>>
>
> Yes, So, I kindly request you to add
> "Signed-off-by: Sandeep K Sinha <sandeepksinha@gmail.com>"
> against each of the patches.
>
> Thanks a lot.
>
>> I have no doubt that the patches are suitably original, but the
>> process requires that you explicitly tell me so.
>>
>> 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@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>



-- 
-- Sujit K M
--
To unsubscribe from this list: send the line "unsubscribe linux-raid" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] md: Enhancements and clean to linear RAID

[SandeepKsinha]

Hi Neil,

> I have applied them all (with very minor cleanups) and pushed them to
> my for-next tree.


Can you help me pull out this git tree?
How can I do this ?

-- 
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@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] md: Enhancements and clean to linear RAID

[NeilBrown]

On Thu, May 21, 2009 1:15 pm, SandeepKsinha wrote:
> Hi Neil,
>
>> I have applied them all (with very minor cleanups) and pushed them to
>> my for-next tree.
>
>
> Can you help me pull out this git tree?
> How can I do this ?

Clone a recent linux kernel tree from somewhere, e.g.
  git clone git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6

then fetch my tree into that

  cd linux-2.6
  git fetch git://neil.brown.name/md

then look at the branches

  git branch -a

and choose one to checkout

But don't try to clone directly from neil.brown.name.  My link
isn't fast enough for that.

NeilBrown