3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What separates one block from another? Spaces? $\endgroup$ – Mr.Wizard Feb 10 '15 at 18:34
  • 1
    $\begingroup$ No, it's all contiguous bytes, the only way to separate the blocks is to read the length prefix bytes to know how long each block is. $\endgroup$ – R. Kazeno Feb 10 '15 at 18:36
  • $\begingroup$ @Mr.Wizard You don't need separators - the lengths instruct you when one block ends and the next starts. $\endgroup$ – Leonid Shifrin Feb 10 '15 at 18:37
  • $\begingroup$ @Leonid I can see how that could be but it didn't seem clear from the question. Now it is. :-) $\endgroup$ – Mr.Wizard Feb 10 '15 at 18:39
  • $\begingroup$ Are your block lengths really arbitrary? For typical real files the block lengths are multiples of some power of two - you may gain efficiency if you can make some assumption. Also what is your actual final goal? Lists of bytes as integers? From the title I thought you might be splitting the file into multiple files. $\endgroup$ – george2079 Feb 10 '15 at 20:03
3
$\begingroup$

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 *)
$\endgroup$
  • $\begingroup$ This solution is a 200x speed improvement over my original (naive) implementation. Many thanks! $\endgroup$ – R. Kazeno Feb 10 '15 at 21:32
  • $\begingroup$ @R.Kazeno Good to know. Was glad to help. Thanks for the accept. $\endgroup$ – Leonid Shifrin Feb 10 '15 at 21:55
  • $\begingroup$ I was wise not to answer this question when I saw your apparent interest in it. +1 $\endgroup$ – Mr.Wizard Feb 10 '15 at 21:59
  • $\begingroup$ @Mr.Wizard Thanks :) But I am sure you would do it at least just as well, and besides, it uses your code as an ingredient. $\endgroup$ – Leonid Shifrin Feb 10 '15 at 22:24
2
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ I thought of not answering because the OP asks for "most efficient". However, when I saw that a naive implementation worked x1.6 slower than a solution which is 200x faster than the OP's, I thought it might be useful anyway. $\endgroup$ – Rojo Feb 11 '15 at 6:01
  • $\begingroup$ Is fun@s /. res_ :> (Close[s]; res) simply stylistic preference or is there a functional benefit over # & [fun@s, Close[s]] or {fun@s, Close[s]}[[1]]? $\endgroup$ – Mr.Wizard Feb 11 '15 at 7:38
  • $\begingroup$ No functional benefit, and not really a stylistic preference either. It is what came to mind first. I am not sure which I prefer. I think your last offer is my favourite $\endgroup$ – Rojo Feb 11 '15 at 7:45
  • $\begingroup$ I've been meaning to learn Haskell for the last three years but I never get started. I think rm -rf already dabbled in it (if not more); I should ask how that went. $\endgroup$ – Mr.Wizard Feb 11 '15 at 8:00
  • 1
    $\begingroup$ @Mr.Wizard So far I am finding Haskell really interesting. My guess is you would like it, very terse. You don't even need brackets to call a function ;) $\endgroup$ – Rojo Feb 11 '15 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.