Multiline Regex

[BiBi-Abc]

I'm curious, how does the multiline regex mode work?

When I use the -U mode to match new lines, I thought that ripgrep has read entire file.
That was stated here.
When I used this:

rg.exe -U "Sherlock\nA" en.txt

on http://opus.nlpl.eu/download.php?f=OpenSubtitles/v2018/mono/OpenSubtitles.raw.en.gz,
which is a 13GB file, it just used a standard 8MB of memory.
How does ripgrep incrementally do a multiline search on a 13GB file and only use 8MB of memory?

[BurntSushi]

ripgrep does read the entire file, so I think I would have to scrutinize how you are measuring that it's only using 8MB of memory. On my Linux system, my time command is configured to tell me peak memory usage. Here are a few different variations of your command:

$ time rg -U "Sherlock\nA" OpenSubtitles2018.raw.en
37584157:You go for it, Sherlock
37584158:Arthur?
145584942:You go for it, Sherlock
145584943:Arthur?
145585729:You go for it, Sherlock
145585730:Arthur?

real    3.118
user    2.657
sys     0.456
maxmem  12508 MB
faults  0

$ time rg -U "Sherlock\nA" OpenSubtitles2018.raw.en --no-mmap
37584157:You go for it, Sherlock
37584158:Arthur?
145584942:You go for it, Sherlock
145584943:Arthur?
145585729:You go for it, Sherlock
145585730:Arthur?

real    9.839
user    3.251
sys     6.564
maxmem  12512 MB
faults  0

$ time rg -U "Sherlock A" OpenSubtitles2018.raw.en --no-mmap

real    3.917
user    2.302
sys     1.609
maxmem  6 MB
faults  0

The first command is yours exactly while the second command is the same, but explicitly disables the use of memory maps. I suspect that's what is confounding you here. Namely, instead of reading the entire file on to the heap, ripgrep will try to memory map the file first. In cases where you're searching a huge file, and especially in cases where ripgrep has to have the entire file in a single contiguous memory region, memory mapping can be substantially faster. On Linux, when I memory map a file like this, it's included in the "RSS" or "resident set size" of the process, and so correctly reports the maximum memory usage of that process. Note though that it is not necessarily the case that memory mapping a large file will use an amount of memory equivalent to the size of the file. It is really up to the operating system to manage it.

That means, it's possible that the way you're measuring memory usage isn't quite correct. But it might also be possible that Windows really isn't loading more than 8MB of the file into memory at a time. Whatever the case, this is transparent to ripgrep. Sadly, I'm not a Windows user or expert, so I'm not sure which is the case here and wouldn't know how to discover it without research.

The last command above tweaks the pattern slightly to remove the \n. Even though multi-line mode is enabled, ripgrep detects that it isn't a multi-line search and uses a small amount of heap memory (when not using memory maps).

[BiBi-Abc]

Ah hah, you are correct. I redid the test with original settings, and even though Ripgrep process memory was not increasing via task manager, the total system memory usage was. Also, disabling memory mapping made Ripgreps memory usage jump up.
I just wonder how

ugrep.exe -U "Sherlock\nA" en.txt

doesn't increase memory usage at all, for the entire system and such.

[BurntSushi]

It is a very difficult question to answer in full correct detail. Or at least, would take time that I don't have. I note that there is no theoretical reason why ripgrep requires all of the file to be loaded in memory. Rather, it is a limitation of the regex engine it uses. And indeed, most regex engines have this limitation because fixing it is complex and full of trade offs.

On top of that, I don't know what ugrep is doing here. I've tried reading its code in the past, but failed to come away with important insights in a reasonable amount of time. So I'd need to dedicate more time to understanding its implementation. It could, for example, impose a limit on the size of a match, which would simplify aspects of the implementation but is unlikely to be something you'll observe with a pattern that matches something so short. However, this experiment---that matches the entire 13GB file---suggests that ugrep has no match limit:

[andrew@frink 2018]$ time rg -U '(?s)^.*$' OpenSubtitles2018.raw.en -c
1

real    50.124
user    49.573
sys     0.503
maxmem  12510 MB
faults  0
[andrew@frink 2018]$ time ugrep -U '(?s)^.*$' OpenSubtitles2018.raw.en -c
1

real    1:49.66
user    1:43.77
sys     5.799
maxmem  12512 MB
faults  0

So my guess is that its regex engine is able to correctly deal with streaming input. (Although notice how much slower it is than ripgrep.) Which makes sense, since I believe it was designed primarily for the lexing use case, which tends to want to work in streaming contexts.

[BiBi-Abc]

Thank you for taking so much time to write all this up!
I'm going to experiment with a simple multiline regex on a large file on a small test program, just out of curiosity for the speed.