From: Ken Bloom <kbloom@...>
Date: 2008-04-30T09:40:05+09:00
Subject: Re: Transpose a large file(>2GB)

On Wed, 30 Apr 2008 01:26:45 +0200, Lionel Bouton wrote:

> Ken Bloom wrote:
> 
>> Now let's start writing. We write a block at the beginning of line 0,
>> then we seek to the beginning of line 1 and write another block. Since
>> Linux allows sparse files it doesn't write anything in the blocks
>> between these two blocks.
> 
> Yes
> 
>> They'll get filled in later when we write more blocks there. The two
>> blocks we just wrote are now next to each other on disk.
> 
> Not necessarily. Filesystems might protect themselves against these
> access patterns to avoid fragmentation (ext2/3 already prevent several
> processes accessing the disk at the same time writing to the same
> cylinder groups to avoid fragmentation), in fact if I understand the
> source code of ext2 correctly this is one of the things indirect block
> allocation prevent partially (ie: non-contiguous parts are allocated in
> different parts of the disk and the fs tries to put a part next to a
> contiguous one).
> I guess you'd probably end with a matrix split in large continuous
> blocks in various parts of one or perhaps more cylinder groups on disk.

In that case, none of the rest of what I said is relevant anymore.
Without reading into the guts of your filesystem, all you can do is guess 
and benchmark.

>> Does this sound about right? In practice it may not be worth optimizing
>> seek time, since that's very much the realm of the operating system.
>> 
>> 
> Unfortunately when you deal with data that can't fit in cache, you
> pretty much defeat any mechanism that the OS uses to optimize disk
> access so you can't rely on it.

There's still an I/O scheduler. My suggestion now might actually be to 
use your algorithm, making sure to read in several lines in a single read
(2) call, so that the OS's I/O scheduler could figure out the best way to 
get the data. I'm not entirely sure about writes. Does the write system 
call queue up the writes for the I/O scheduler and let the user process 
keep going, or does it stop the process until the write completes (for 
some definition of completes)?

My point was that you can't rely on the data having any particular 
organization with respect to seek times.

> Now what would be real fun is the OP telling that he uses a SSD with
> access times in the order of 0.1ms for storing these matrices :-) Then
> I'd eat my hat and advise to go with the easiest algorithm to code :-)

Yep. More unstated assumptions about the best way to do things.
I hope he finds a solution that's good enough.

--Ken

-- 
Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/