Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Re: Help performing "random" access on very very large file

by ctilmes (Priest)
on Jul 16, 2007 at 16:26 UTC ( #626874=note: print w/ replies, xml ) Need Help??


in reply to Help performing "random" access on very very large file

Displaying/buffering huge text files describes some methods for indexing text files for more fast/efficient jumping to a specific line.


Comment on Re: Help performing "random" access on very very large file
Re^2: Help performing "random" access on very very large file
by downer (Monk) on Jul 16, 2007 at 17:44 UTC
    they seem to have some good advice for indexing, I could probably just index every ~50 lines instead of every line, then, loading that block in memory.

      One very effective optimisation for reducing the size of the index, is to store just lengths rather than full absolute offsets for most of the lines.

      Say for example, that you know that all the lines in your 500GB file are less than 255 characters long, and for calculation purposes, average 100 characters. Then if you build a full, absolute index using the pack 'd' template (required for anything over 4GB), then your index itself is going to be 500GB / 100 * 8 ~= 40 GB!

      However, if you store the absolute index of every (say) 1000th line, and 999 x 1-byte lengths for the intervening lines, the index size becomes: 500 GB / (100*1000) * 1007 ~= 5GB.

      Each record within your index is then a fixed 1007 bytes, and the process of locating any individual line becomes:

      1. my( $recNo, $offset ) = ( int( $lineNo / 1000 ), ( $lineNo % 1000 ) - 1 );
      2. seek INDEX, $recno *1007, 0;
      3. read INDEX, $idxBuf, 1007;
      4. my $absOffset = unpack 'd', $idxBuf;
      5. my( $addOffset, $length ) = unpack "x[d] %32C$offset C", $idxBuf;
      6. seek BIGFILE, $absOffset + $addOffset, 0;
      7. read BIGFILE, $line, $length;

      By using the 'checksum' unpack template (%n-bits) to perform the summing of the intermediate lengths, the calculation of the composite offset is really very fast. This puts any line of your huge file just two reads away.

      Note: There is nothing special about the number 1000 I've used in this example except that it is convenient for calculations. As we are calculating a 32-bit offset (%32C), and representing length with 8-bit unsigned chars, the theoretical maximum, absolute offset spacing is 2**32 / 2**8 == 2**24 == 16 MB.

      A quick test suggests that it takes Perl ~ 60 milliseconds to calculate the sum of 16 MB chars. That's far less time than having to read even 1 extra data record.

      However, there is little extra saving to be had by further decreasing the frequency of the absolute offsets.

      • Using an absolute offset every 1000 lines gives an index size of: 5.035 GB

        The checksum time for 999 bytes: 112 microseconds.

      • Using an absolute offset every 64k lines gives an index size of: 5.00053405761719 GB

        The checksum time for 64k bytes: 320 microseconds.

      • Using an absolute offset every 16MB lines gives an index size of: 5.00000208616257 GB

        The checksum time for 16MB bytes: 60 milliseconds.

      So, you see there is little extra index space saving by decreasing the frequency of absolute offsets, but there is a considerable calculation penalty in doing so. You also have to factor in the extra time taken to read the larger index records from the index file.


      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://626874]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (8)
As of 2014-12-27 06:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (176 votes), past polls