[Ocfs2-tools-devel] [PATCH 2/2] looped chain - Break loop in fsck

[tristan]

Goldwyn Rodrigues wrote:
> Hi Tristan,
>
> On Fri, Mar 5, 2010 at 6:58 PM, tristan ye <tristan.ye at oracle.com> wrote:
>   
>> Goldwyn Rodrigues wrote:
>>     
>>> Hi Tristan,
>>>
>>> On Fri, Mar 5, 2010 at 9:56 AM, Goldwyn Rodrigues <rgoldwyn at gmail.com>
>>> wrote:
>>>
>>>       
>>>> Hi Tristan,
>>>>
>>>>
>>>> On Fri, Mar 5, 2010 at 8:44 AM, tristan ye <tristan.ye at oracle.com> wrote:
>>>>
>>>>
>>>>         
>>> <snip>
>>>
>>>
>>>       
>>>>> Let me know if you have some other suggestions on it.
>>>>>
>>>>>           
>>> On second thoughts, in an un-cached environment, your algorithm would
>>> have more number of disk reads as compared to my algorithm. So, a
>>> cached environment might be better, but will consume more memory. I am
>>> not sure how you would want to handle this efficiently.
>>>
>>>       
>> Yes, your time complexity of disk reads is O(N), while mine is O(2N), it we
>> disgard the cache.
>>     
>
> Correction, it will be N(for slow) + 2N (for fast) = 3N
>   
Oh,
You may misunderstand my words, here 'N' I meant is the length of loop, 
not walking steps, so the slow and fast have the same disk i/o reads.

Anyway, as joel said, they were the same when N is close to infinite,

>   
>> So the problem is 'Your extra collection/comparions' VS 'My extra disk
>> reads', the best way I guess is to compare their efficiency  in a real world
>> after we drop all buffer and caches. by doing:
>>
>> 1. echo 3>/proc/sys/vm/drop_caches
>>
>> 2. time fsck...
>>
>>
>> The winner will be consuming less time.
>>     
>
> Theoretically, this will depend on the size of the loop. Not tried it,
> so cannot say practically.
>   

Yes, we may make the testing volume big to see the difference:), also 
make the blocksize and clustersize as small as possible.

>
>   
>> Joel, sunil,
>>
>> How do you think about that issue?
>>
>>
>>     
>>> Even, in my algorithm, it can be improvised by collecting the block
>>> numbers in the check_chain loop itself, but lets face it... how often
>>> do you get a loop in the chain to do this? We don't want to have
>>> multiple collections/comparisons for all chains checked.
>>>
>>>       
>
>
>
>