On Tue, 29 Apr 2008 18:13:23 +0200, Lionel Bouton wrote:

> Ken Bloom wrote:
>> On Sun, 27 Apr 2008 05:32:52 -0500, Ams Lo wrote:
>> 
>>> Hi -
>>>
>>> What is the fast and ruby way to transpose a large file(>2GB)??
>>>
>>> I can't read the whole file into memory due to the file sizes..
>> 
>> I assume all of the lines in the file are the same length, and the line
>> length is a multiple of the disk block size.
> 
>  From the rest of the algorithm, you assume that the OP wants to
> transpose in place, and indeed your algorithm is probably one of the
> best in this case (and is more or less Pascal Bourguignon's algorithm
> tuned for disk access). I'm not sure this is what the OP wants (wasn't
> specified). He seemed memory constrained but didn't report any disk
> space constraint, so he may benefit from an algorithm writing another
> file.
> 
> In short I wonder if it's the best in the general case.
> 
> For a data point a 20000 * 20000 64 bit integer matrix is >2GB but only
> 160kb-wide, splitting it in narrower chunks will take a huge toll on the
> reading/writing speed compared to the huge sequential reads (or writes
> depending on the choices I left open) I proposed. The slow writes (or
> reads) due to numerous seeks would even be faster than in your algorithm
> as you advise a block size access which is only 512bytes, with 2G of RAM
> you can write/read in ~ 2 * 10^9 / 20000 * 8 = 12500 bytes (12288 bytes
> is the nearest multiple of 512), so it should be around 24 times faster
> (assuming inverse proportion of bandwidth vs number of seeks).

The block size I used was just for illustration. I chose the blocksize 
and line size that I did so that my diagrams wouldn't be overwhelmingly 
tall. I also made no assumption about the data size. You should use your 
disk's block size -- the size that is fetched anyway when you do a read
(). I don't know of a portable way to get this number. On my ext3 
filesystem, I can get it by running dumpe2fs, and it's 4KB.

Beyond the block size, you have no guarantee of contiguous blocks in the 
file being contiguous on disk anyway, though ext2 and ext3 are pretty 
good at avoiding fragmentation.

Your algorithm poses other interesting questions about seeks, reads and 
writes. Let's assume that whenever we allocate a new block it's 
contiguous with the last one we wrote in the file. Let's read in the 
original file contiguously, and write noncontiguously.

We need to read in enough lines to fill all of the blocks we are 
outputting. With a 512k block size and 64-bit integers, that's 4 lines. 
Not too bad memory-wise, but keep this in mind because if we read in less 
lines, we'll be writing to the same disk block multiple times.

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. 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. 
Keep going, and you'll find that both your reads and writes are 
contiguous. On the other hand, if you try to transpose back, the file 
that you just finished writing is the pathological worst case for seek 
time.

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.

--Ken

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