3

I've often found myself with the need to develop tools that process large files over a network and perform an operation to every element in that file. An element may be an individual line or an object that is parsed out based on its structure (XML, JSON, binary format). A key feature of these tools is what I often call "user feedback", and it tends to manifest itself as a progress bar that is updated periodically. I've found the only way to do this is to use the "line by line" approach:

for file in file_set:
    with open(file, 'r') as f:
        for element in f:
            do_thing_to(element)
        # after 'time' update progress

This seems idiomatic and straight forward. But I've often wondered if reading the entire file first into some structure and then using an apply or a map to that structure would result in faster performance. However, doing so I lose the ability to keep track of "progress" and inform the user on the granular level I've chosen. Instead it must become more broad in classification of progress.

This obviously is system dependent and requires benchmarking, but which tends to be the typical approach to such a problem?

An immediate concern I have for the "reading entirely first" method is a memory constraint, but that's all I can really think of. Speed and memory efficiency are the main concerns, per usual. If they both benchmark at the same rate, I'd default to the lower memory profile method.

pstatix
  • 1,017
  • 10
  • 16
  • It depends entirely on the size of the file, and you acknowledge this in your question. You would likely load a 1KB file into memory but stream a 200GB file. – Dan Wilson Jul 20 '20 at 20:02
  • 1
    Does this answer your question? [Is micro-optimisation important when coding?](https://softwareengineering.stackexchange.com/questions/99445/is-micro-optimisation-important-when-coding) – gnat Jul 20 '20 at 20:12
  • @DanWilson Absolutely. Now suppose that the 200GB has only 3GB of data in it that are needed, parsed from each line and stored in an array (say a NumPy array) where the size in bytes are controlled. Is it better to parse the entire file, store in a structure and then process? In my mind, no. Why? Because all that time going over each line to parse and store could've parsed and computed. Is that a normal thought? – pstatix Jul 20 '20 at 20:17
  • @gnat Interesting question for sure, although I don't think I'm on the scale of microseconds. The problem is fairly straight forward: process each file sequentially or read them all into a structure (manageable in memory) and process in parallel. I'm immediately dissuaded from the latter as I lose the ability to report progress, but benchmarks could yield decent gains (unsure currently). Memory is the scarce resource in this scenario, so such an implementation would need to consider that whereas the former would not. – pstatix Jul 20 '20 at 21:49
  • @gnat Ultimately, the facts come down to the time spent doing the computation for each line, moving on to the next one, and repeating per file rather than a very fast read and mapping the computation across the structure. Is the overhead of processing in parallel going to yield performance gains at the expense of progress reporting, or will it be just as fast as sequential processing? This I must do experimentation to resolve, though I thought I'd query the community for "best practices" if any. – pstatix Jul 20 '20 at 21:50

5 Answers5

4

You can always measure, but you might be surprised at the results, especially for sequential access. People don't think about optimizations done at lower levels of abstraction. For example, your operating system is caching files to memory:

$ free -h
              total        used        free      shared  buff/cache   available
Mem:           31Gi       4.9Gi        22Gi       445Mi       4.2Gi        25Gi
Swap:         1.0Gi          0B       1.0Gi

Here on my system, I currently have 4.2G of file cache. Your language's standard library also does buffering. Some, like Java's BufferedReader, are more explicit than others. Even your disk drive has its own buffering. These things have all been optimized by some very smart people.

In other words, your application is not going out to physically read from the disk every time you read another line. If you try to optimize by doing your own buffering, you might end up throwing the filesystem cache out to make room in RAM. You might end up writing another application's memory to a swap file in order to make room in RAM. You might choose buffer strategies that can't take advantage of faster levels of CPU cache. You don't want to undo optimizations other people have made on your behalf.

Karl Bielefeldt
  • 146,727
  • 38
  • 279
  • 479
2

This is often a tradeoff between

  • memory usage, and

  • ease of implementation

As you already noted by yourself, reading a file entirely first has the drawbacks of requiring more memory and making it more complicated to report progress.

However, reading a structured file entirely first may be necessary (or at least simpler) when further processing cannot be easily implemented sequentially. For example, let us say you have to process a complex XML file, and the processing requires several xslt queries into the data where the result of a previous query may influence the next query. For such a situation, reading the XML into an DOM document structure first may be way more simple than trying to build some sequential processing.

So here is how I usually deal with it this way: ask yourself

  • is the expected maximum file size "small enough" to be handled in entirety?

  • does reading the file entirely make further processing simpler?

If the answer to both questions is "yes", then I would prefer reading the file completely into a suitable data structure. Otherwise, I would prefer a sequential (i.e. "line-by-line") approach.

Let me add I had to deal sometimes with situations where reading the entire file was not feasible, but the requirements did not fit well to a sequential approach, either. These cases may require a mixed approach, for example one where a first step sequential processing step is used to filter the required data down to a smaller subset, or transform it into a different representation so afterwards the non-sequential processing can take place.

Doc Brown
  • 199,015
  • 33
  • 367
  • 565
1

For 90% of problems most people would encounter, reading the file in its entirety and then completely parsing them is faster, simpler, and easier. This should be your default choice when working with smaller data.

You should only use incremental parsing/stream processing when your program may be used in a context where it need to process a very large input, where slurping the entire file may cause unacceptable memory usage, or if processing takes such a significant amount time that you really need to report partial progress.

Lie Ryan
  • 12,291
  • 1
  • 30
  • 41
  • For 90% of problems most people would encounter, reading the file in its entirety and then completely parsing them is simpler, and easier and **equally fast** (but not faster). – Doc Brown Jul 24 '20 at 06:20
  • @DocBrown: if you're using native compiled language, you're correct, there shouldn't be any difference, but if your code is in a VM-based language, e.g. CPython, parsing in one shot means the parsing loop is going to be fully in native code (assuming the underlying parser is optimised using compiled language) but when using an incremental parser, it needs to go back and forth between native and VM code, which usually comes with a higher overhead than building everything in one shot for small to medium sized data (though with small data, the difference is likely negligible anyway). – Lie Ryan Jul 24 '20 at 12:43
  • Then I would recommend to write "for 90% of problems most people would encounter, reading the file in its entirety and then completely parsing them is simpler, and easier any performance differences (if any) are not relevant". – Doc Brown Jul 24 '20 at 13:14
1

For many formats you have no choice but parsing the complete file. For example, with JSON adding a single zero byte to the end of a perfectly fine JSON file makes it invalid. And parsing the complete structure is likely easier than having a function that processes line by line.

That said, you avoid problems with very large files by passing largish blocks (say 64K at a time) to the parser. If you think that the whole file contents won’t be used, you can just parse the file without creating all the data structures.

gnasher729
  • 42,090
  • 4
  • 59
  • 119
  • Using the JSON example, an equivalent to my problem would be specifying the file to a JSONReader object that has internal methods that know how to iterate each object inside the format (i.e. `for obj in JSONReader(fp).iter(): ... `). The corollary would be to read the entire file first, then iterate over the objects (i.e. `for obj in JSONReader(fp).objects(): ...`). Here, `iter()` yields lazy results while `objects()` gathers all the objects first, before iterating, thus storing in memory. – pstatix Jul 21 '20 at 18:38
  • So when I say "line by line" I really mean "each formatted element/block in a file". Thus the problem is, process each formatted chunk (if methods allow it) as the file is read sequentially; or store the entire file as formatted objects and then process in bulk. – pstatix Jul 21 '20 at 18:55
1

There are a number of factors here but we can definitely lay out some principles around these kinds of situations. Let's start with the basic framework. Consider the following visualization:

time it takes to load    |----------|
time it takes to process |----------|

The length of the line represents time. The units involved matter in practice but not at the conceptual level.

Now here's a what it looks like when you load the data and then process it:

loading    |----------|
process               |----------|

We can simply add the time it takes to load to the time it takes to process. Now consider if we don't wait for loading to finish before we process it. It might look something like this:

loading    |----------|
process     |----------|

Now I've made an assumption here that the loading process can happen in parallel with processing. While this isn't guaranteed, it's absolutely doable with non-blocking IO. Even with regular IO, this is often still roughly how things happen.

Now if either the loading or processing is insignificant, this won't have a major impact either way. But when both take long enough to matter, stream processing can make a serious dent in the total time. Another case where this can make a big is when you chain processes steps such as in a 'pipes and filters' design. e.g. you could have this:

|----------|
           |----------|
                      |----------|
                                 |----------|
                                            |----------|

Or this:

|----------|
 |----------|
  |----------|
   |----------|
    |----------|

This is simplifying some things, of course but at a high level it's absolutely true. So with regard to your situation, the most costly step is likely the download of the file. You don't seem to be considering that but if you wanted to stream, it would really be against the data as you pull it down. But if your processing is relatively quick, there's not much advantage and it could present some complexities.

Another factor to consider if you are really to eek out every last drop of performance: it takes time to allocate memory. Let's say you need to allocate 1KiB of memory per line and there are 1024 lines. That's 1 MiB of memory if you pre-load and 1KiB (roughly) process at a line level. It takes a lot longer to allocate a megabyte of memory than a kilobyte and then you need to reclaim which also takes time.

Ultimately, at a high-level, if you are processing data sequentially, it's going to take more time and resources to pre-load the data. When you are loading small files from disk or SSD, it's not going to matter and you might get a little speed boost by pre-loading because of how your hardware manages IO. But for any significant amount of data, pre-loading is less efficient.

It's important to note that there are other considerations such as how it can be more complex to handle errors in a streaming solution. If you need all the data for a calculation or need to access the same values repeatedly, streaming can become impractical or impossible.

JimmyJames
  • 24,682
  • 2
  • 50
  • 92
  • Given my situation, processing each *element* is an independent action and there are no dependencies. Using your overlap example (3rd graphic), is that equivalent to `opening a file, getting an element, processing it, getting next element, repeat` or splitting that between two processes: one reading and pushing to another that processes? – pstatix Jul 21 '20 at 19:42
  • That would be a single process. As the application is doing computation on a record, the next can be loaded into memory. A related situation I've seen is processing a result set from a DB. You'll often see all the results be loaded into memory and then processed one-by-one. That approach unnecessarily delays the beginning of the processing until every record has been retrieved by, the database, serialized, deserialized, and loaded into memory. It also tends to limit scalability. – JimmyJames Jul 21 '20 at 20:04
  • So unfortunately with CPython, performing a computation while simultaneously loading the next element into memory is not permitted because of the GIL. However, your scenario is exactly what I am talking about, loading an entire file into memory before processing; the act of loading the entire file into memory (especially a formatted one) meant that each element had to be iterated beforehand, so why waste time not processing as you go? – pstatix Jul 21 '20 at 20:13
  • @datta: in a VM based language like CPython, incremental parsing files is almost always going to be slower than just parsing everything everything at once. This is because when parsing the whole file the inner loop to construct all objects is running in C speed, while incremental parser will have to go in and out of the VM code. In native speed language like C, these are usually not an issue though. GIL isn't usually going to be the main issue here. – Lie Ryan Jul 22 '20 at 00:52
  • @datta "So unfortunately with CPython, performing a computation while simultaneously loading the next element into memory is not permitted because of the GIL." Not so: [asyncio](https://docs.python.org/3/library/asyncio.html). I've used [aiohttp](https://docs.aiohttp.org/en/stable/) and [aiofile](https://pypi.org/project/aiofile/) to good result. – JimmyJames Jul 22 '20 at 01:48
  • @JimmyJames Never heard of `aiofile`, will have to give it a look. – pstatix Jul 22 '20 at 12:00
  • I should also mention that you don't necessarily need Async IO to get benefit from doing processing inline with IO. Much of what happens with IO is happening outside the thread of execution of the Python app. When doing IO with a remote resource, it's lot of work is happening on other machines entirely. At the very least it allows you to start producing results nearly immediately which can make a huge difference if there is downstream processing in an other application. – JimmyJames Jul 22 '20 at 13:45
  • @JimmyJames I'm unsure how I would begin processing a line while loading the next one in CPython without using multiple processes since the GIL prevents that (unless using `asyncio`). In order to execute the next bytecode in the program, the processing needs to complete before reading next line with native Python. – pstatix Jul 22 '20 at 14:55
  • Along the lines of Karl's answer, you are assuming that GIL blocks the file IO on the OS. When you are interacting with the file system, there's a lot happening that isn't part of your application such IO buffering from disk to memory. These kinds of OS functions exist outside the Python execution space and are not blocked by the GIL. – JimmyJames Jul 22 '20 at 15:10