Bad performance when many notes are listed

[yuuki0xff]

The notes list refreshing process takes long time when many notes are listed. In particular, very slow-down in windows environment.

TODO: measures performance.

[yuuki0xff]

I added simple benchmark codes for note sorters. The results show that AlphaNumSorter is 20+ times slower than other sorters. AlphaNumSorter may cause performance problems when nvpy manages many notes. Other sorters seems to have enough performance.

The biggest impact on performance is the update process of the tk.Text in NotesList. I'll try to benchmark it later.

$ make benchmark
PYTHONPATH=.:$PYTHONPATH python3 -m nose --with-timer -q -s benchmarks/*.py
[success] 91.64% benchmarks.sorters.BenchmarkSorters.test_alphanum_10k_10times: 1.3473s
[success] 3.89% benchmarks.sorters.BenchmarkSorters.test_alpha_10k_10times: 0.0571s
[success] 2.01% benchmarks.sorters.BenchmarkSorters.test_date_10k_10times: 0.0295s
[success] 1.76% benchmarks.sorters.BenchmarkSorters.test_pinnged_10k_10times: 0.0259s
[success] 0.70% benchmarks.sorters.BenchmarkSorters.test_nop_10k_10times: 0.0103s
----------------------------------------------------------------------
Ran 5 tests in 1.471s

OK

[yuuki0xff]

Benchmark Result

• The refresh_notes_list_view task is O(n). When the first time synchronization, O(n^2) because it will be called n times.
• The refresh_notes_list_view task is 1.6x slower on Windows 11 than on Debian sid and Ubuntu 22.04.1.
• AlphaNumSorter has poor performance compared to other sorters, but it's not a critical problem.

Windows 11 21H2 Python 3.11.1 @ QEMU on EPYC 7452

PS C:\Users\User\Desktop\nvpy-dev> python benchmarks/sorters.py
sorter/notes_10k/NopSorter                   1.34 ms/loop
sorter/notes_10k/PinnedSorter                3.14 ms/loop
sorter/notes_10k/AlphaSorter                 7.83 ms/loop
sorter/notes_10k/AlphaNumSorter             85.27 ms/loop
sorter/notes_10k/DateSorter                  3.71 ms/loop
PS C:\Users\User\Desktop\nvpy-dev> python benchmarks/notes_list.py
refresh_notes_list_view/10_notes           826.00 us/loop
refresh_notes_list_view/100_notes            9.10 ms/loop
refresh_notes_list_view/1000_notes          85.98 ms/loop
refresh_notes_list_view/10000_notes        790.12 ms/loop

Debian sid Python 3.10.8 @ Core i5-4460

% pipenv run make benchmark
PYTHONPATH=.:$PYTHONPATH python3 benchmarks/sorters.py
sorter/notes_10k/NopSorter                 850.00 us/loop
sorter/notes_10k/PinnedSorter                2.68 ms/loop
sorter/notes_10k/AlphaSorter                 5.71 ms/loop
sorter/notes_10k/AlphaNumSorter             66.36 ms/loop
sorter/notes_10k/DateSorter                  2.80 ms/loop
PYTHONPATH=.:$PYTHONPATH python3 benchmarks/notes_list.py
refresh_notes_list_view/10_notes           498.00 us/loop
refresh_notes_list_view/100_notes            5.08 ms/loop
refresh_notes_list_view/1000_notes          52.06 ms/loop
refresh_notes_list_view/10000_notes        513.01 ms/loop

Ubuntu 22.04.1 Python 3.10.6 @ QEMU on EPYC 7452

ubuntu@ubuntu:~/work/nvpy-dev$ make benchmark 
PYTHONPATH=.:$PYTHONPATH python3 benchmarks/sorters.py
sorter/notes_10k/NopSorter                   1.10 ms/loop
sorter/notes_10k/PinnedSorter                3.04 ms/loop
sorter/notes_10k/AlphaSorter                 6.83 ms/loop
sorter/notes_10k/AlphaNumSorter             86.95 ms/loop
sorter/notes_10k/DateSorter                  2.87 ms/loop
PYTHONPATH=.:$PYTHONPATH python3 benchmarks/notes_list.py
refresh_notes_list_view/10_notes           557.00 us/loop
refresh_notes_list_view/100_notes            6.28 ms/loop
refresh_notes_list_view/1000_notes          66.58 ms/loop
refresh_notes_list_view/10000_notes        648.70 ms/loop

Ubuntu 18.04.6 Python 3.6.9 @ QEMU on EPYC 7452

ubuntu@ubuntu:~/work/nvpy-dev$ make benchmark
PYTHONPATH=.:$PYTHONPATH python3 benchmarks/sorters.py
sorter/notes_10k/NopSorter                   1.20 ms/loop
sorter/notes_10k/PinnedSorter                4.43 ms/loop
sorter/notes_10k/AlphaSorter                 9.08 ms/loop
sorter/notes_10k/AlphaNumSorter            139.46 ms/loop
sorter/notes_10k/DateSorter                  4.50 ms/loop
PYTHONPATH=.:$PYTHONPATH python3 benchmarks/notes_list.py
refresh_notes_list_view/10_notes           458.00 us/loop
refresh_notes_list_view/100_notes            5.25 ms/loop
refresh_notes_list_view/1000_notes          51.56 ms/loop
refresh_notes_list_view/10000_notes        565.56 ms/loop

Ideas to improve performance

• Omit rendering hidden areas.
• Omit rendering hidden areas, and refresh hidden areas during idle time.
• Limit the refresh operation frequency.
• Implement delta update logic.