I need to scan very large JSONL files efficiently and am considering a parallel grep-style approach over line-delimited text.

Would love to hear how you would design it.

  • Jayjader@jlai.lu
    0·
    12 days ago

    1. chunk_size := file_size / cpu_cores. Compile regex.

    2. spawn cpu_cores workers:
      2.a. worker #n starts at n * chunk_size bytes. If n > 0, skip bytes until newline encountered.
      2.b worker starts feeding bytes from file/chunk into regex. When match is found, write to output (stdout or file, whichever has better performance). When newline encountered, restart regex state automata.
      2.c after having read chunk_size bytes, continue until encountering a newline to ensure the whole file is covered by the parallel search.

    Optionally, keep track of byte number and attach them to the found matches when outputting, to facilitate eventually de-duplicating and/or navigating to said match in the file.

    To avoid problems, have each worker output to a separate file, and only combine these output files when the workers are all finished.

    As others have said, it’s going to be hard to get more speedup than this, and you will ultimately be limited by your storage’s read speed and throughput if the whole file cannot fit into memory.

  • vfscanf()@discuss.tchncs.de
    0·
    13 days ago

    The question is, what will be your limiting factor: CPU or disk I/O? Parallel processing doesn’t do much good if the workers have to wait on the disk to deliver more data. I’d start with an async architecture, where the program can do its processing while it is waiting on more data.

    • pelya@lemmy.world
      0·
      13 days ago

      One additinal trick is to compress your files before writing them to disk, using some kind of fast lightweight compression like parallel gzip (pigz command) or lzop. When parsing them, you will have smaller disk reads but higher CPU usage, which will give speed advantage if you have server-class CPU with lots of cache.

  • Bazell@lemmy.zip
    0·
    13 days ago

    Splitting file in equal parts and analyzing in threads each part is basically the only efficient option to utilize modern CPU architectures efficiently for your task that I can think about. Since I doubt that the data stored in your files can be quickly processed by the GPU(I assume that you have text data).

    • bleistift2@sopuli.xyzEnglish
      0·
      13 days ago

      Can a file really be split efficiently? And is reading from multiple files on the same disk really faster than scanning a single file from top to bottom?

      • Bazell@lemmy.zip
        0·
        13 days ago

        If the task to just read the data quickly without processing it(doing calculations, sorting, transformation, etc.), then yes, reading line by line is the fastest way. But the OP mentioned some processing operations on data, which may require additional time and computing power, thus it will be efficient to firstly load file into ram splitting it into chunks, give each thread a chunk to process and then combine results.

        In fact, my first comment suggested that you can read file line by line and once enough lines were read in RAM, thread 1 can start processing them while thread 0 still reads new lines from hard drive. Once another chunk is ready, thread 2 can start processing it and so on.

        In conclusion, it all depends on what exactly you need to do with data. Simply transferring it from HDD to RAM must be done by reading line by line. But processing of data can be split among cores of CPU to maximize the speed of computations.

        • anton@lemmy.blahaj.zone
          0·
          10 days ago

          Don’t have a thread doing line by line file reads, just to have it in memory. There is a piece of software optimized for tasks like this, the OS.
          Just mmap your file and start processing.

      • entwine@programming.dev
        0·
        13 days ago

        You don’t actually need to “split” anything, you just read from different offsets per thread. Mmap might be the most efficient way to do this (or at least the easiest)

        Whether or not that’s going to run into hardware bottlenecks is a separate issue from designing a parallel algorithm. Idk what OP is trying to accomplish, but if their hardware is known (eg this is an internal tool meant to run in a data center), they’ll need to read up on their hardware and virtualization architecture to squeeze the most IO performance.

        But if parsing is actually the bottleneck, there’s a lot you can do to optimize it in software. Simdjson would be a good place to start.

  • bizdelnick@lemmy.ml
    0·
    13 days ago

    Bad idea. First, file is read sequentially, and you can’t parallelize this. Second, grep is a bad solution for structured files. Better use jq or something similar.

      • bizdelnick@lemmy.ml
        0·
        13 days ago

        Sorry, I missed that L, and I’ve never heard about JSONL before (although worked with JSON logs that are effectively JSONL). So, well, you may use grep, however it can be inefficient (depends on regex engine and how good you are in regexes). It is also easy to make a mistake if you are not very proficient in regexes. So I’d prefer using JSON parser (jq or another, maybe lower level if performance matters) over grep anyway.