Improving Find in Files performance

Vitalii Dovgan

Hi Notepad++ team!

I’ve created a pull request that improves the Find in Files performance by re-using the existing approach with several optimizations, and thus making it 2…3 times faster.

https://github.com/notepad-plus-plus/notepad-plus-plus/pull/18376

I haven’t invented anything new, just optimized what was already there.
I realize the code review may create an impression that several parts have been completely re-written, but that’s no true.
In fact, the existing code has been refactored by extracting parts of several functions into separate helpers, so these moved blocks of code together with new helpers create an impression of a lot of changes. But if you follow the code logic, or just manually copy-paste the separate helpers into the places where these helpers are called, you’d realize the code flow remains the same.
Please feel free to review and test.
I’m writing here because I’m afraid the longer this pull request remains open, the higher are chances of merge conflicts to appear in the affected files.

PeterJones

@Vitalii-Dovgan ,

Even though you just “moved” stuff, it’s a lot of lines of code changed, from the diff perspective, and Don manually reviews all of that. So it’s not an easy one to review.

And since you didn’t attach the PR to any open Issue (though I’m sure there must be more than one asking for improved FiF performance), it’s probably a low priority in his mind (and I’m surprised he didn’t reject it out of hand. It might be because it came from you that it wasn’t rejected).

I recommend searching out one or more Issues to attach it to.

But yes, I do hope it’s able to be merged before there is a conflict.

guy038

Hello, @vitalii-dovgan and All,

I gave a try to your Windows Release-x64 version of N++ v6.9.8 from https://github.com/notepad-plus-plus/notepad-plus-plus/pull/18376

Here is the chosen protocol for testing :

I tested an USB key, named D: which contains 26,388 occurrences of the string Fi, with that exact case, in regex mode, within 619 files out of a totality of 1,120 files. Note that I’ve revisited this same test because I’ve already used it to test the MultiReplace plugin by @thomas-knoefel and the Search++ plugin by @coises.

Note that all the results were identical whatever the program or plugin used for the Find in Files test !

Before running any test :

I closed my portable v8.9.8 version, lying in a the D:\898_x64 folder
I un-plug my USB key
I restart my windows 11 laptop
I re-plug my USB key
I reopen Notepad++ v8.9.8 for all the tests but your version
Once each test finished, I re-run immediately a second test

Remark : the first time I ran this test, with N++ v8.9.8, BEFORE using the above protocol, so with N++ simply opened from many hours, I got a time of 2 minutes to execute the Find in Files search

After following the protocol, I got these results :

    •----------------•---------------•--------------•
    |  N++ Vitalii   |  FIRST test   |    1m 30s    |
    |                |  SECOND test  |        2,9s  |
    •----------------•---------------•--------------•
    |  Notepad++     |  FIRST test   |    1m 32s    |
    |                |  SECOND test  |        4.6s  |
    •----------------•---------------•--------------•
    |  MultiReplace  |  FIRST test   |    1m 30s    |
    |                |  SECOND test  |        3s    |
    •----------------•---------------•--------------•
    |  Search++      |  FIRST test   |    2m 16s    |
    |                |  SECOND test  |        1s    |
    •----------------•---------------•--------------•

What did I observe :

If I consider the initial search, during 2m, The Vitalii version seems significantly faster than native N++.
However, after using my protocol, the difference became negligible regarding the first test, but significant regarding the second text.
Globally, the MultiReplace plugin give similar results than the N++ versions.
As for the Search++ plugin, although using a multi-thread approch, the first text takes some more time but the speed of the second test is truly surprising !

At this point, I decided to run a big test, scanning every file of my SSD drive of 512 Gb ! So, I tried again to find occurrences of the Fi string, with exact case and regex mode

Using the same protocol as above, here are the results :

•----------------•-------------------------------------------------------•----------------•-----------------------------------------------------------------------------------------------------------------•
|    Program     |                        Results                        |     Total      |                                                  Errors                                                         |
•----------------•-------------------------------------------------------•----------------•-----------------------------------------------------------------------------------------------------------------•
|  N++ Vitalii   |  10,076,894 hits in 89,907 files of 305,950 searched  |     40 m 42 s  |                                                                                                                 |
•----------------•-------------------------------------------------------•----------------•-----------------------------------------------------------------------------------------------------------------•
|  Native N++    |  10,076,963 hits in 89,910 files of 315,953 searched  |  1h  0 m 21 s  |                                                                                                                 |
•----------------•-------------------------------------------------------•----------------•-----------------------------------------------------------------------------------------------------------------•
|  Search++      |   9,730,269 matches in 90,434 documents               |     18 m       |  585 errors found : mostly,  permission to read NOT granted !                                                   |
•----------------•-------------------------------------------------------•----------------•-------------------------------------------------------------------------------------------- --------------------•
|  MultiReplace  |  ERROR after 2,6s and about 102,000 files             |      n/a       |  Error scanning directory: recursive_directory_iterator::operator++: The system cannot find the path specified  |
•----------------•-------------------------------------------------------•----------------------------------------------------------------------------------------------------------------------------------•

What did I observe :

The Vitalii Dovgan version is clearly faster than native N++
Due to multi-thread processing, the Search++ plugin is the winner
The MultiReplace plugin quickly triggers an error while scanning the C: drive
Unfortunately, I must add, that, for four tests above, the resulting Results panel, after the search phase, was rather unusable and did not displayed correctly as really too large !

II tried one last round of tests, searching every pdf file within my SSD drive of 512 Gb, with the same parameters than above.

Using the same protocol as above, here are the results :

•----------------•--------------------------------------------•------------•------------•----------------------------•
|    Program     |                 Results                    |  Scan ...  |   Total    |           Errors           |
•----------------•--------------------------------------------•------------•------------•----------------------------•
|  N++ Vitalii   |  74,854 hits in 130 files of 130 searched  |  5 m 20 s  |  5 m 24 s  |                            |
•----------------•--------------------------------------------•------------•------------•----------------------------•
|  Native N++    |  74,854 hits in 130 files of 130 searched  |  5 m 29 s  |  5 m 32 s  |                            |
•----------------•--------------------------------------------•------------•------------•----------------------------•
|  Search++      |  74,854 matches in 130 documents           |  3 m 58 s  |  4 m       |                            |
•----------------•--------------------------------------------•------------•------------•----------------------------•
|  MultiReplace  |  ERROR after 3,6s and about 116,000 files  |     3,6 s  |    n/a     |  Error IDENTICAL to above  |
•----------------•--------------------------------------------•------------•-----------------------------------------•

What did I observe :

The Vitalii Dovgan version is slightly faster than native N++
Again, due to multi-thread processing, the Search++ plugin is the winner
The MultiReplace plugin quickly triggers an error while scanning the C: drive
Luckily,this time, the resulting Results panel, after the search phase, are all correctly displayed
Note that the scan column represents the scanning phase, at beginning of the search, which is labelled :
- Discovering file candidates.., within N++
- Scanning directory; found ... files, within Search++
- Discovering files (...), within MultiReplace

General conclusion :

If the total number of scanned files is SMALL, any program will do. Paradoxically, the multithreaded process seems to take longer
Globally, the Vitalii version seems faster than the native N++ one
When a great amount of files is scanned, the Search++ plugin should be preferred

Surely, some people should try and test your version, in order to confirm my own impression !

Best Regards,

guy038

Coises

@guy038 said:

Unfortunately, I must add, that, for four tests above, the resulting Results panel, after the search phase, was rather unusable and did not displayed correctly as really too large !

In what sense did it not display correctly? Did it fail to load at all? Was the information corrupt, or some data missing? Was the behavior roughly the same for Notepad++/Vitalii-Notepad++ and for Search++?

II tried one last round of tests, searching every pdf file within my SSD drive of 512 Gb, with the same parameters than above.

Using the same protocol as above, here are the results :

•----------------•--------------------------------------------•------------•------------•----------------------------•
|    Program     |                 Results                    |  Scan ...  |   Total    |           Errors           |
•----------------•--------------------------------------------•------------•------------•----------------------------•
|  N++ Vitalii   |  74,854 hits in 130 files of 130 searched  |  5 m 20 s  |  5 m 24 s  |                            |
•----------------•--------------------------------------------•------------•------------•----------------------------•
|  Native N++    |  74,854 hits in 130 files of 130 searched  |  5 m 29 s  |  5 m 32 s  |                            |
•----------------•--------------------------------------------•------------•------------•----------------------------•
|  Search++      |  74,854 matches in 130 documents           |  3 m 58 s  |  4 m       |                            |
•----------------•--------------------------------------------•------------•------------•----------------------------•
|  MultiReplace  |  ERROR after 3,6s and about 116,000 files  |     3,6 s  |    n/a     |  Error IDENTICAL to above  |
•----------------•--------------------------------------------•------------•-----------------------------------------•

What did I observe :

The Vitalii Dovgan version is slightly faster than native N++
Again, due to multi-thread processing, the Search++ plugin is the winner

What I find curious is that most of the difference is in the scanning phase. The directory scan in Search++ is not multi-threaded, though it does run in a background thread. So I don’t know what it’s doing that’s faster than Notepad++ native. I did code it from scratch, not even looking at Notepad++ code, so it might not use the same APIs.

If the total number of scanned files is SMALL, any program will do. Paradoxically, the multithreaded process seems to take longer

I’m fairly sure that the difference isn’t the number of files scanned, it’s the device. There is something about the way I process files that does not work well with your USB drive. I tried to reproduce this with devices I have over the several weeks I spent trying to optimize the multi-threading, but I was never able to find anything that behaved the same way as yours.

I’m sure there are other devices out there that will show the same behavior. I just don’t know how to diagnose and fix the problem when I can’t reproduce it.

Thomas Knoefel

@Coises said:

Again, due to multi-thread processing, the Search++ plugin is the winner

I insist! MultiReplace is the fastest, done in just seconds! Just ignore the bug ;-) I’ll have a fix ready soon…

Vitalii Dovgan

I gave a try to your Windows Release-x64 version of N++ v6.9.8 from https://github.com/notepad-plus-plus/notepad-plus-plus/pull/18376

That’s interesting!
Were you searching or replacing?
The replacing performance should be very close since almost the same code is executed.
The searching (find only) performance is expected to be 2-3 times faster.

Vitalii Dovgan

Here are my average results:

Search "text" (122307 hits in 2161 files of 4385 searched)

standard Notepad++  -  00:15.37
modified Notepad++  -  00:08.15

Search "cache" (19176 hits in 787 files of 12821 searched)

standard Notepad++  -  01:00.02
modified Notepad++  -  00:33.54

Search "cache" (45120 hits in 2316 files of 18920 searched)

standard Notepad++  -  02:53.74
modified Notepad++  -  02:12.04

The modified Notepad++ demonstrates better performance on text files rather than binary files.
That’s why my very last search, which included many binary files, is not 2 times faster.

To see the full power of the modified Notepad++, apply file masks that will exclude most of binary files.

Vitalii Dovgan

Here are results for the same folder for mostly text files :

Search "cache" (17205 hits in 343 files of 11839 searched)

standard Notepad++  -  00:44.52
modified Notepad++  -  00:22.15