Most efficient way of splitting a file into length-prefixed blocks

Question

Let's say I have a really big file (>100MB) that consists of length-prefixed blocks, i.e. the first byte of each byte block indicates the length of the rest of the block. This is a simplified example of such a file (each non-space character is one byte, X just designates some random byte value):

7 X X X X X X X 5 X X X X X 4 X X X X 7 X X X X X X X

What would be the most efficient way to read the file and generate a list of all the block contents? In this case the result would need to be:

{{X,X,X,X,X,X,X},{X,X,X,X,X},{X,X,X,X},{X,X,X,X,X,X,X}}

If the answer involves using some function such as BinaryReadList, would it be better to read the whole file first and then split the resulting list, or to read the file block by block?

Answer 1

General

Here is my suggestion: if you have enough RAM (which may well be the case, given that your files are not in GB range), it will likely be faster to load the file into memory at once, and then split into groups of bytes.

Note however, that since at the moment there isn't a top-level byte array representation in Mathematica which would be easy to work with, we have to essentially use integers to store bytes, which would require 8 times more space for 64-bit integers. This would mean that RAM usage would be roughly 8 x the size of the file on disk, if it is all loaded into RAM.

Preparation

Here one way how is how this can be done. We will first prepare a test example:

bytes = Flatten[{#, RandomInteger[{60, 90}, #]} & /@ {7, 5, 4}]

(* {7, 87, 73, 90, 72, 74, 88, 75, 5, 87, 68, 89, 88, 90, 4, 70, 78, 77, 75} *)

Now save this to a temporary file:

file = $TemporaryPrefix <> "test1";
Close@OpenWrite[file, BinaryFormat -> True];
BinaryWrite[file, bytes];
Close[file];

Now test that we have it done right:

BinaryReadList[file]

(* {7, 87, 73, 90, 72, 74, 88, 75, 5, 87, 68, 89, 88, 90, 4, 70, 78, 77, 75} *)

Implementation

The first ingredient will be a function that would compute the lengths, given the bytes:

chunklengths = 
  Compile[{{bt, _Integer, 1}},
    Module[{chunkLengths = Internal`Bag[], ctr = 1, len = Length[bt]},
      While[ctr <  len,
        Internal`StuffBag[chunkLengths, bt[[ctr]]];
        ctr += bt[[ctr]] + 1;
      ];
      IntegerPart@Internal`BagPart[chunkLengths, All]
    ]
  ];

I have used Compile, because this is the type of problem where standard functional techniques are rather hard to apply efficiently, since every time the size of the next chunk only becomes known when we reach a given one. The Internal`Bag data structure was used to efficiently accumulate lengths of chunks as we sweep through the list. Otherwise, the code is quite straightforward.

For example:

chunklengths[bytes]

(* {7, 5, 4} *)

What remains now is to split the bytes according to lengths, keeping in mind that we don't need the length-giving bytes, and that the lengths would be larger than what chunklengths gives, by 1, to account for precisely those bytes (which we should then drop). We will use Mr. Wizard's dynP function:

dynP[l_, p_] := MapThread[l[[# ;; #2]] &, {{0} ~Join~ Most@# + 1, #} & @ Accumulate @ p]

and then the final one to actually do the splitting:

ClearAll[loadAndSplit];
loadAndSplit[file_] := 
  With[{bytes = BinaryReadList[file]},
    With[{lengths = chunklengths[bytes] + 1},
      dynP[bytes, lengths][[All, 2 ;;]] /; Total[lengths] == Length[bytes]
    ]
  ];

We can test:

loadAndSplit[file]

(* {{87, 73, 90, 72, 74, 88, 75}, {87, 68, 89, 88, 90}, {70, 78, 77, 75}} *)

Benchmarks

Here, we will construct a larger file first:

largeFile = $TemporaryPrefix <> "testLrg";
Close@OpenWrite[largeFile, BinaryFormat -> True];
lbytes = 
   Developer`ToPackedArray @ 
     Flatten[{#, RandomInteger[{60, 90}, #]} & /@ RandomInteger[{100, 200}, {100000}]];
ByteCount[lbytes]
BinaryWrite[largeFile, lbytes];
Close[largeFile];
FileByteCount[largeFile]


(*

   120826096

   15103244

*)

which is, the file size is about 15Mb. Now, we test:

(lsplit = loadAndSplit[largeFile]); // AbsoluteTiming

(* {0.461512, Null} *)

So, it takes about half a second to load 15Mb and split the bytes, on my machine, which doesn't look too bad.

Now, we can test that it gives the correct result:

Flatten[{Length[#], #} & /@ lsplit] == lbytes

(* True *)

Answer 2

This times about 65% higher than Leonid's on my machine. But maybe a more naive answer might be useful to some.

Module[{rBytes},
(* Returns the next numbers or $Failed *)    

read[str_InputStream] := rBytes[str, BinaryRead@str];
  rBytes[str_, n_Integer] := BinaryReadList[str, "Byte", n];
  rBytes[_, EndOfFile] := $Failed;
]

(* Some usability defs *)

  (* Returns n of them or as many as it can *)
read[str_InputStream, n: _Integer?Positive | Infinity | All] := 
   NestWhileList[read[str] &, read[str], # =!= $Failed &, 1, n /. All->Infinity] /.
        {l___, $Failed} :> {l};

  (* Takes a file name, returns all *)      
read[file_String] := blockIStream[
  OpenRead[file, BinaryFormat -> True], 
  read[#, All] &
  ];

blockIStream[s_InputStream, fun_] := fun@s /. res_ :> (Close[s]; res)