From: Pratik Shinde <pratikshinde320@gmail.com>
To: Gao Xiang <gaoxiang25@huawei.com>
Cc: miaoxie@huawei.com, linux-erofs@lists.ozlabs.org
Subject: Re: [RFCv2] erofs-utils:code for detecting and tracking holes in uncompressed sparse files.
Date: Tue, 24 Dec 2019 16:15:47 +0530 [thread overview]
Message-ID: <CAGu0czTzBiT_n-13tXohNp22gbJrsdNXdY7kYDvv=WDdn2hZwA@mail.gmail.com> (raw)
In-Reply-To: <20191224100511.GB164058@architecture4>
[-- Attachment #1: Type: text/plain, Size: 1702 bytes --]
Hi Gao,
No no. What I am saying is - in the current code (excluding all my changes)
the block lookup will happens in constant time. with only hole list it
won't be O(1) time but rather we have to traverse the holes list. (say in
binary search way).
what I don't understand is - what is the purpose of tracking data extents.
hope you get it.
--Pratik.
On Tue, Dec 24, 2019, 3:35 PM Gao Xiang <gaoxiang25@huawei.com> wrote:
> Hi Pratik,
>
> On Tue, Dec 24, 2019 at 03:05:53PM +0530, Pratik Shinde wrote:
> > Hello Gao,
> >
> > Thanks for the review.
> > If I understand correctly , you wish to keep track of every extent
> assigned
> > to the file.
> > in case of file without any holes in it, there will single extent
> > representing the entire file.
> >
> > Also, the current block no. lookup happens in constant time. (since we
> only
> > record the start blk no.)
> > If we use extent record for finding given block no. it can't be done in
> > constant time correct ? (maybe in LogN)
>
>
> Could I ask a question?
> In short, how can we use the proposal approach to read random blocks
> in constant time O(1)?
>
> e.g.
> if you have two holes 2...4 7...10 in a file with 12 blocks.
>
> if we want to random access block 11, only block number 1,5,6,11 were
> saved one by one (maybe p1,p2,p3,p4).
>
> How can we get the physical address (p4) of block 11 directly without
> scanning the previous holes?
>
> Thanks,
> Gao Xiang
>
>
> >
> > I think I don't fully understand reason for recording extents assigned
> to a
> > file.Since the current design
> > is already time and space optimized & there are no deletions happening.
> > Is it for some future requirement ?
> >
> > --Pratik.
>
>
[-- Attachment #2: Type: text/html, Size: 2364 bytes --]
next prev parent reply other threads:[~2019-12-24 10:46 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-12-23 17:29 [RFCv2] erofs-utils:code for detecting and tracking holes in uncompressed sparse files Pratik Shinde
2019-12-24 3:48 ` Gao Xiang
2019-12-24 9:35 ` Pratik Shinde
2019-12-24 10:05 ` Gao Xiang
2019-12-24 10:45 ` Pratik Shinde [this message]
2019-12-24 11:15 ` Gao Xiang
2019-12-26 5:42 ` Pratik Shinde
2019-12-26 6:00 ` Gao Xiang
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAGu0czTzBiT_n-13tXohNp22gbJrsdNXdY7kYDvv=WDdn2hZwA@mail.gmail.com' \
--to=pratikshinde320@gmail.com \
--cc=gaoxiang25@huawei.com \
--cc=linux-erofs@lists.ozlabs.org \
--cc=miaoxie@huawei.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).