* Speed improvements to ido.el @ 2012-11-20 18:25 Daniel Skarda 2012-11-21 3:20 ` Leo 2012-11-21 3:37 ` Dmitry Gutov 0 siblings, 2 replies; 6+ messages in thread From: Daniel Skarda @ 2012-11-20 18:25 UTC (permalink / raw) To: emacs-devel [-- Attachment #1: Type: text/plain, Size: 1121 bytes --] Hello, I like to use ido mode for everything, including very large lists (like M-x or info). Unfortunately ido is not suitable for such lists. On my old notebook, performance is not amazing, so I took the challenge and spend some time with profiler. I improved the performance in several steps: - inlined several functions - disabled ido-case-fold for some completions (eg commands) - prunning collections based on character bitmaps - caching character bitmaps during completion or for same completions - caching intermediate completion lists when adding new characters You can view my changes on github: - https://github.com/orfelyus/ido-speed-hack - https://github.com/orfelyus/ido-mode-el - (and optionally) https://github.com/orfelyus/ido-better-flex ido-speed-hack includes large changes (bitmaps) while ido-mode-el includes minor changes to ido.el The changes made huge speed improvements on my notebook and ido does not feel sluggish even with very large lists. Could you please test my improvements? I would appreciate any feedback. Dan ps: I am not subscribed to the mailing list, please keep me in Cc [-- Attachment #2: Type: text/html, Size: 1628 bytes --] ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Speed improvements to ido.el 2012-11-20 18:25 Speed improvements to ido.el Daniel Skarda @ 2012-11-21 3:20 ` Leo 2012-11-21 3:37 ` Dmitry Gutov 1 sibling, 0 replies; 6+ messages in thread From: Leo @ 2012-11-21 3:20 UTC (permalink / raw) To: emacs-devel On 2012-11-21 02:25 +0800, Daniel Skarda wrote: > I like to use ido mode for everything, including very large lists > (like M-x or info). Unfortunately ido is not suitable for such lists. > On my old notebook, performance is not amazing, so I took the > challenge and spend some time with profiler. We have just improved the speed for ido in both trunk and emacs 24.3. Please use it as your baseline for benchmarking. Thanks. BTW, I get reasonable performance for a 40K lists. Leo ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Speed improvements to ido.el 2012-11-20 18:25 Speed improvements to ido.el Daniel Skarda 2012-11-21 3:20 ` Leo @ 2012-11-21 3:37 ` Dmitry Gutov 2012-11-22 9:36 ` Daniel Skarda 1 sibling, 1 reply; 6+ messages in thread From: Dmitry Gutov @ 2012-11-21 3:37 UTC (permalink / raw) To: Daniel Skarda; +Cc: emacs-devel Daniel Skarda <dan.skarda@gmail.com> writes: Hey Daniel, Like Leo said, please provide some numbers. A comparison to the current trunk would be best, since it contains an additional optimization compared to the emacs-24 branch. Here my test setup from the relevant discussion: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=12796#47 --Dmitry > I like to use ido mode for everything, including very large lists (like M-x or > info). Unfortunately ido is not suitable for such lists. On my old notebook, > performance is not amazing, so I took the challenge and spend some time with > profiler. > > I improved the performance in several steps: > > - inlined several functions > - disabled ido-case-fold for some completions (eg commands) > - prunning collections based on character bitmaps > - caching character bitmaps during completion or for same completions > - caching intermediate completion lists when adding new characters > > You can view my changes on github: > > - https://github.com/orfelyus/ido-speed-hack > - https://github.com/orfelyus/ido-mode-el > > - (and optionally) https://github.com/orfelyus/ido-better-flex > > ido-speed-hack includes large changes (bitmaps) while ido-mode-el includes minor > changes to ido.el > > The changes made huge speed improvements on my notebook and ido does not feel > sluggish even with very large lists. > > Could you please test my improvements? I would appreciate any feedback. > Dan > > ps: I am not subscribed to the mailing list, please keep me in Cc ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Speed improvements to ido.el 2012-11-21 3:37 ` Dmitry Gutov @ 2012-11-22 9:36 ` Daniel Skarda 2012-11-30 13:42 ` Daniel Skarda 0 siblings, 1 reply; 6+ messages in thread From: Daniel Skarda @ 2012-11-22 9:36 UTC (permalink / raw) To: Dmitry Gutov; +Cc: emacs-devel [-- Attachment #1: Type: text/plain, Size: 1964 bytes --] Hi Dmitry, thanks for the suggestions. I will prepare some benchmarks using new Emacs and send the results. I already did some statistics with elp during development, but I suspect that the numbers are not precise. I am curious which improvements will be the fastest :) Regards, Dan On Wed, Nov 21, 2012 at 4:37 AM, Dmitry Gutov <dgutov@yandex.ru> wrote: > Daniel Skarda <dan.skarda@gmail.com> writes: > > Hey Daniel, > > Like Leo said, please provide some numbers. > > A comparison to the current trunk would be best, since it contains an > additional optimization compared to the emacs-24 branch. > > Here my test setup from the relevant discussion: > http://debbugs.gnu.org/cgi/bugreport.cgi?bug=12796#47 > > --Dmitry > > > I like to use ido mode for everything, including very large lists (like > M-x or > > info). Unfortunately ido is not suitable for such lists. On my old > notebook, > > performance is not amazing, so I took the challenge and spend some time > with > > profiler. > > > > I improved the performance in several steps: > > > > - inlined several functions > > - disabled ido-case-fold for some completions (eg commands) > > - prunning collections based on character bitmaps > > - caching character bitmaps during completion or for same completions > > - caching intermediate completion lists when adding new characters > > > > You can view my changes on github: > > > > - https://github.com/orfelyus/ido-speed-hack > > - https://github.com/orfelyus/ido-mode-el > > > > - (and optionally) https://github.com/orfelyus/ido-better-flex > > > > ido-speed-hack includes large changes (bitmaps) while ido-mode-el > includes minor > > changes to ido.el > > > > The changes made huge speed improvements on my notebook and ido does not > feel > > sluggish even with very large lists. > > > > Could you please test my improvements? I would appreciate any feedback. > > Dan > > > > ps: I am not subscribed to the mailing list, please keep me in Cc > [-- Attachment #2: Type: text/html, Size: 2992 bytes --] ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Speed improvements to ido.el 2012-11-22 9:36 ` Daniel Skarda @ 2012-11-30 13:42 ` Daniel Skarda 2012-12-01 0:40 ` Dmitry Gutov 0 siblings, 1 reply; 6+ messages in thread From: Daniel Skarda @ 2012-11-30 13:42 UTC (permalink / raw) To: Dmitry Gutov; +Cc: monnier, emacs-devel [-- Attachment #1: Type: text/plain, Size: 16860 bytes --] Hi, I prepared detailed benchmark. Results: - standard Emacs 24.3 indeed provides significant speed improvement over 23.3 in ido flexible matching - original ido-better-flex performance is terrible - speed-hack introduces two improvements: ido-mode patches and (shared) bitmaps - ido-mode patches improve ido E24 performance - bitmap optimization provides significant improvement for better-flex but slows down E24 a little bit - shared bitmaps significantly improve performance of all methods My setup: - debian x64 testing on Lenovo R400 (Intel Core2 Duo) - debian testnig emacs 23.3 & emacs-snapshot 20121115 from http://emacs.naquadah.org/ - to avoid cpu frequency scaling, I call cpufreq-set -r -g userspace -d 800MHz -u 800MHz - I use benchmark-run to meassure time and garbage collection Tests I simulate interactive ido mode by calls to ido-set-matches. I emulate typing by setting ido-text. I start with one character and append one character for each iteration (eg. 'a', 'ab', 'abc' etc...) I use 4 different tests: - "abcdefghijklmnopqrstuvwxyz" - this test favours my patches, because they reuse results from last matching. - "-etaimn" - most common characters in English (and Emacs commands). The number of completions will not be reduced too much in this test. - "bcfile" - "real-world" example. Shortcut for byte-compile-file - "fndgd" - second "real-world" example. Shortcut for find-grep-dired Ido uses obarray to complete all 4 examples. To have same conditions, I saved the completion list to file (39580 symbols). All tests start with fresh Emacs and with the same list to complete. Variants I tested following variants: - ido-mode - ido mode file version - cmn - ido-set-common-completion is part of the test - flx - ido-enable-flex-matching on and off - cas - ido-case-fold on and off - rgx - ido-enable-regexp on and off - better - ido-better-flex off, original and patched version - cache - use of bimaps cache (only for ido-speed-hack) ido-mode variants: - 23.3 - file from 23.3 distribution - 24.3 - file from debian emacs-snapshot package (as of 20121122) - patched - 24.3 + patches (function inlining and avoid gc) - bitmaps - using ido-speed-hack bitmaps and result caching - shared - bitmaps are cached between executions. Results - Emacs 23.3 | ido-mode | cmn | flx | cas | rgx | better | "a..z" | #GC | GC | -etaimn | #GC | GC | bcfile | #GC | GC | fndgd | #GC | GC | |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+------+--------+---------+-----+--------+---------+-----+--------| | 23.3 | - | - | - | - | - | 25.373 | 87 | 7.715 | 7.98 | 26 | 2.32 | 5.582 | 20 | 1.766 | 5.728 | 20 | 1.794 | | 23.3 | t | - | - | - | - | 27.980 | 106 | 9.466 | 11.526 | 50 | 4.649 | 6.727 | 29 | 2.559 | 7.089 | 30 | 2.659 | | 23.3 | - | t | - | - | - | 371.272 | 87 | 7.703 | 112.883 | 26 | 2.333 | 38.856 | 20 | 1.787 | 41.674 | 20 | 1.792 | | 23.3 | - | t | t | - | - | 592.653 | 87 | 7.714 | 181.204 | 26 | 2.343 | 60.389 | 20 | 1.793 | 64.969 | 20 | 1.799 | | 23.3 | - | - | - | t | - | 24.662 | 87 | 7.708 | 7.480 | 26 | 2.330 | 5.371 | 20 | 1.768 | 5.450 | 20 | 1.770 | | 23.3 | - | - | - | - | orig | 463.980 | 1289 | 117.554 | 204.444 | 615 | 58.911 | 129.562 | 340 | 30.715 | 137.558 | 370 | 33.878 | | 23.3 | - | - | t | - | orig | 885.647 | 2440 | 222.092 | 342.790 | 1035 | 98.879 | 239.584 | 629 | 57.987 | 256.425 | 695 | 64.553 | |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+------+--------+---------+-----+--------+---------+-----+--------| | 24.3 | - | - | - | - | - | 25.465 | 87 | 7.700 | 8.019 | 26 | 2.343 | 5.613 | 20 | 1.767 | 5.707 | 20 | 1.775 | | 24.3 | t | - | - | - | - | 28.182 | 106 | 9.493 | 11.572 | 50 | 4.664 | 6.777 | 29 | 2.561 | 7.127 | 30 | 2.660 | | 24.3 | - | t | - | - | - | 47.964 | 87 | 7.725 | 13.261 | 26 | 2.329 | 7.575 | 20 | 1.768 | 7.804 | 20 | 1.773 | | 24.3 | - | t | t | - | - | 67.351 | 87 | 7.738 | 18.109 | 26 | 2.335 | 10.264 | 20 | 1.787 | 10.592 | 20 | 1.775 | | 24.3 | - | - | - | t | - | 24.791 | 87 | 7.714 | 7.513 | 26 | 2.318 | 5.382 | 20 | 1.771 | 5.487 | 20 | 1.771 | | 24.3 | - | - | - | - | orig | 459.364 | 1299 | 116.504 | 203.055 | 620 | 58.518 | 129.042 | 344 | 31.143 | 136.720 | 373 | 34.116 | | 24.3 | - | - | t | - | orig | 875.099 | 2440 | 219.660 | 338.753 | 1040 | 97.563 | 236.528 | 639 | 57.794 | 252.875 | 699 | 63.647 | |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+------+--------+---------+-----+--------+---------+-----+--------| | patched | - | - | - | - | - | 13.209 | 2 | 0.184 | 4.697 | 3 | 0.277 | 2.838 | 1 | 0.090 | 2.950 | 1 | 0.087 | | patched | t | - | - | - | - | 14.984 | 15 | 1.401 | 7.057 | 20 | 1.912 | 3.518 | 6 | 0.551 | 3.895 | 8 | 0.731 | | patched | - | t | - | - | - | 32.246 | 3 | 0.267 | 9.443 | 4 | 0.365 | 4.335 | 1 | 0.088 | 4.578 | 1 | 0.089 | | patched | - | t | t | - | - | 51.477 | 3 | 0.265 | 14.232 | 4 | 0.363 | 7.024 | 1 | 0.088 | 7.385 | 1 | 0.090 | | patched | - | - | - | t | - | 12.853 | 2 | 0.177 | 4.267 | 3 | 0.271 | 2.676 | 1 | 0.088 | 2.774 | 1 | 0.089 | | patched | - | - | - | - | patch | 430.462 | 1176 | 107.325 | 185.306 | 554 | 53.674 | 107.259 | 278 | 24.945 | 115.460 | 310 | 27.954 | | patched | - | - | t | - | patch | 835.141 | 2295 | 205.013 | 319.621 | 967 | 92.213 | 201.717 | 538 | 48.043 | 218.950 | 599 | 53.997 | |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+------+--------+---------+-----+--------+---------+-----+--------| | bitmaps | - | - | - | - | - | 12.109 | 10 | 1.067 | 15.753 | 20 | 2.197 | 11.172 | 10 | 1.061 | 11.633 | 10 | 1.066 | | bitmaps | t | - | - | - | - | 13.824 | 20 | 2.233 | 17.727 | 30 | 3.426 | 11.432 | 10 | 1.075 | 12.087 | 11 | 1.193 | | bitmaps | - | t | - | - | - | 12.379 | 10 | 1.066 | 17.347 | 20 | 2.204 | 11.273 | 10 | 1.068 | 11.760 | 10 | 1.076 | | bitmaps | - | t | t | - | - | 12.849 | 10 | 1.068 | 19.326 | 20 | 2.190 | 11.507 | 10 | 1.061 | 12.160 | 10 | 1.069 | | bitmaps | - | - | - | t | - | 13.561 | 10 | 1.157 | 5.120 | 10 | 1.157 | 3.610 | 10 | 1.051 | 3.803 | 10 | 1.151 | | bitmaps | - | - | - | - | patch | 25.564 | 40 | 4.500 | 87.040 | 180 | 21.534 | 19.759 | 30 | 3.351 | 26.850 | 41 | 4.705 | | bitmaps | - | - | t | - | patch | 39.640 | 70 | 7.918 | 139.870 | 290 | 35.046 | 27.684 | 41 | 4.575 | 42.250 | 71 | 8.024 | |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+------+--------+---------+-----+--------+---------+-----+--------| | shared | - | - | - | - | - | 3.617 | 4 | 0.452 | 6.836 | 10 | 1.167 | 2.470 | 2 | 0.215 | 3.044 | 3 | 0.329 | | shared | t | - | - | - | - | 5.338 | 14 | 1.609 | 9.127 | 23 | 2.674 | 3.162 | 6 | 0.678 | 3.916 | 8 | 0.897 | | shared | - | t | - | - | - | 3.986 | 5 | 0.548 | 8.549 | 11 | 1.247 | 2.545 | 2 | 0.218 | 3.173 | 3 | 0.331 | | shared | - | t | t | - | - | 4.482 | 5 | 0.549 | 10.544 | 11 | 1.247 | 2.805 | 2 | 0.222 | 3.590 | 3 | 0.326 | | shared | - | - | - | t | - | 12.662 | 2 | 0.219 | 4.134 | 2 | 0.214 | 2.645 | 1 | 0.107 | 2.732 | 1 | 0.108 | | shared | - | - | - | - | patch | 17.136 | 34 | 3.869 | 78.877 | 172 | 20.579 | 11.027 | 21 | 2.377 | 18.757 | 38 | 4.313 | | shared | - | - | t | - | patch | 30.922 | 61 | 6.953 | 131.599 | 282 | 33.907 | 19.531 | 37 | 4.165 | 34.522 | 70 | 7.966 | |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+------+--------+---------+-----+--------+---------+-----+--------| Results - Emacs 24.3.50 | ido-mode | cmn | flx | cas | rgx | better | "a..z" | #GC | GC | -etaimn | #GC | GC | bcfile | #GC | GC | fndgd | #GC | GC | |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+-----+--------+---------+-----+--------+---------+-----+--------| | 23.3 | - | - | - | - | - | 23.422 | 86 | 7.802 | 7.265 | 25 | 2.281 | 5.170 | 20 | 1.808 | 5.265 | 20 | 1.812 | | 23.3 | t | - | - | - | - | 26.067 | 106 | 9.670 | 10.791 | 50 | 4.728 | 6.035 | 26 | 2.360 | 6.609 | 30 | 2.718 | | 23.3 | - | t | - | - | - | 370.813 | 86 | 7.795 | 112.986 | 25 | 2.288 | 38.377 | 20 | 1.807 | 41.195 | 20 | 1.790 | | 23.3 | - | t | t | - | - | 595.396 | 86 | 7.771 | 182.541 | 25 | 2.296 | 60.243 | 20 | 1.814 | 64.945 | 20 | 1.787 | | 23.3 | - | - | - | t | - | 23.010 | 86 | 7.704 | 6.915 | 25 | 2.254 | 5.025 | 20 | 1.792 | 5.101 | 20 | 1.792 | | 23.3 | - | - | - | - | orig | 354.581 | 1224 | 113.705 | 164.447 | 570 | 59.209 | 98.402 | 320 | 30.417 | 105.588 | 350 | 33.808 | | 23.3 | - | - | t | - | orig | 642.533 | 2310 | 213.541 | 261.947 | 969 | 98.604 | 174.093 | 600 | 57.592 | 186.379 | 659 | 62.799 | |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+-----+--------+---------+-----+--------+---------+-----+--------| | 24.3 | - | - | - | - | - | 22.806 | 86 | 7.797 | 7.128 | 25 | 2.298 | 5.010 | 20 | 1.798 | 5.112 | 20 | 1.799 | | 24.3 | t | - | - | - | - | 25.488 | 106 | 9.651 | 10.632 | 50 | 4.708 | 5.899 | 26 | 2.366 | 6.471 | 30 | 2.712 | | 24.3 | - | t | - | - | - | 43.514 | 86 | 7.729 | 12.157 | 25 | 2.323 | 6.780 | 20 | 1.796 | 6.987 | 20 | 1.798 | | 24.3 | - | t | t | - | - | 62.310 | 86 | 7.761 | 16.737 | 25 | 2.322 | 9.357 | 20 | 1.797 | 9.681 | 20 | 1.804 | | 24.3 | - | - | - | t | - | 22.500 | 86 | 7.737 | 6.772 | 25 | 2.259 | 4.892 | 20 | 1.796 | 4.962 | 20 | 1.793 | | 24.3 | - | - | - | - | orig | 356.023 | 1227 | 115.312 | 162.438 | 571 | 57.330 | 97.526 | 320 | 29.748 | 104.051 | 350 | 32.425 | | 24.3 | - | - | t | - | orig | 642.029 | 2320 | 213.897 | 257.828 | 969 | 95.111 | 172.289 | 600 | 56.291 | 183.545 | 659 | 60.493 | |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+-----+--------+---------+-----+--------+---------+-----+--------| | patched | - | - | - | - | - | 11.587 | 2 | 0.185 | 4.167 | 3 | 0.280 | 2.520 | 1 | 0.093 | 2.585 | 1 | 0.093 | | patched | t | - | - | - | - | 13.263 | 14 | 1.327 | 6.388 | 19 | 1.813 | 3.143 | 6 | 0.544 | 3.503 | 8 | 0.738 | | patched | - | t | - | - | - | 29.458 | 3 | 0.277 | 8.620 | 3 | 0.279 | 3.868 | 1 | 0.090 | 4.075 | 1 | 0.093 | | patched | - | t | t | - | - | 48.135 | 3 | 0.275 | 13.259 | 3 | 0.279 | 6.437 | 1 | 0.090 | 6.769 | 1 | 0.092 | | patched | - | - | - | t | - | 11.307 | 2 | 0.185 | 3.847 | 3 | 0.277 | 2.362 | 1 | 0.091 | 2.427 | 1 | 0.090 | | patched | - | - | - | - | patch | 326.320 | 1095 | 102.650 | 147.375 | 515 | 53.024 | 80.696 | 263 | 24.657 | 87.440 | 292 | 27.547 | | patched | - | - | t | - | patch | 607.426 | 2136 | 196.133 | 243.672 | 898 | 90.915 | 145.362 | 507 | 46.650 | 159.114 | 564 | 52.703 | |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+-----+--------+---------+-----+--------+---------+-----+--------| | bitmaps | - | - | - | - | - | 9.825 | 10 | 1.061 | 13.090 | 20 | 2.180 | 9.068 | 10 | 1.052 | 9.442 | 10 | 1.054 | | bitmaps | t | - | - | - | - | 11.604 | 20 | 2.320 | 14.934 | 30 | 3.381 | 9.270 | 10 | 1.055 | 9.839 | 11 | 1.174 | | bitmaps | - | t | - | - | - | 10.084 | 10 | 1.052 | 14.586 | 20 | 2.160 | 9.149 | 10 | 1.062 | 9.569 | 10 | 1.061 | | bitmaps | - | t | t | - | - | 10.562 | 10 | 1.054 | 16.538 | 20 | 2.167 | 9.391 | 10 | 1.073 | 9.961 | 10 | 1.068 | | bitmaps | - | - | - | t | - | 12.150 | 10 | 1.043 | 4.632 | 10 | 1.043 | 3.324 | 10 | 1.037 | 3.407 | 10 | 1.0378 | | bitmaps | - | - | - | - | patch | 20.721 | 40 | 4.482 | 69.525 | 170 | 20.207 | 16.163 | 30 | 3.407 | 21.572 | 40 | 4.514 | | bitmaps | - | - | t | - | patch | 29.711 | 61 | 6.860 | 106.825 | 280 | 33.311 | 21.392 | 40 | 4.450 | 32.450 | 70 | 7.902 | |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+-----+--------+---------+-----+--------+---------+-----+--------| | shared | - | - | - | - | - | 3.012 | 4 | 0.452 | 5.836 | 10 | 1.154 | 2.029 | 2 | 0.219 | 2.531 | 3 | 0.332 | | shared | t | - | - | - | - | 4.589 | 13 | 1.511 | 7.910 | 22 | 2.546 | 2.693 | 6 | 0.671 | 3.380 | 8 | 0.901 | | shared | - | t | - | - | - | 3.407 | 5 | 0.565 | 7.387 | 10 | 1.159 | 2.115 | 2 | 0.219 | 2.655 | 3 | 0.332 | | shared | - | t | t | - | - | 3.873 | 5 | 0.564 | 9.322 | 10 | 1.161 | 2.339 | 2 | 0.218 | 3.032 | 3 | 0.329 | | shared | - | - | - | t | - | 11.290 | 2 | 0.220 | 3.759 | 2 | 0.222 | 2.259 | 0 | 0.000 | 2.448 | 1 | 0.105 | | shared | - | - | - | - | patch | 13.653 | 33 | 3.784 | 62.698 | 163 | 19.750 | 8.690 | 20 | 2.262 | 14.945 | 37 | 4.231 | | shared | - | - | t | - | patch | 23.090 | 58 | 6.624 | 99.838 | 268 | 32.725 | 14.645 | 36 | 4.064 | 25.692 | 66 | 7.531 | |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+-----+--------+---------+-----+--------+---------+-----+--------| On Thu, Nov 22, 2012 at 10:36 AM, Daniel Skarda <dan.skarda@gmail.com> wrote: > > Hi Dmitry, > > thanks for the suggestions. I will prepare some benchmarks using new Emacs and send the results. > I already did some statistics with elp during development, but I suspect that the numbers are not precise. > > I am curious which improvements will be the fastest :) > > Regards, > Dan > > > On Wed, Nov 21, 2012 at 4:37 AM, Dmitry Gutov <dgutov@yandex.ru> wrote: >> >> Daniel Skarda <dan.skarda@gmail.com> writes: >> >> Hey Daniel, >> >> Like Leo said, please provide some numbers. >> >> A comparison to the current trunk would be best, since it contains an >> additional optimization compared to the emacs-24 branch. >> >> Here my test setup from the relevant discussion: >> http://debbugs.gnu.org/cgi/bugreport.cgi?bug=12796#47 >> >> --Dmitry >> >> > I like to use ido mode for everything, including very large lists (like M-x or >> > info). Unfortunately ido is not suitable for such lists. On my old notebook, >> > performance is not amazing, so I took the challenge and spend some time with >> > profiler. >> > >> > I improved the performance in several steps: >> > >> > - inlined several functions >> > - disabled ido-case-fold for some completions (eg commands) >> > - prunning collections based on character bitmaps >> > - caching character bitmaps during completion or for same completions >> > - caching intermediate completion lists when adding new characters >> > >> > You can view my changes on github: >> > >> > - https://github.com/orfelyus/ido-speed-hack >> > - https://github.com/orfelyus/ido-mode-el >> > >> > - (and optionally) https://github.com/orfelyus/ido-better-flex >> > >> > ido-speed-hack includes large changes (bitmaps) while ido-mode-el includes minor >> > changes to ido.el >> > >> > The changes made huge speed improvements on my notebook and ido does not feel >> > sluggish even with very large lists. >> > >> > Could you please test my improvements? I would appreciate any feedback. >> > Dan >> > >> > ps: I am not subscribed to the mailing list, please keep me in Cc > > [-- Attachment #2: Type: text/html, Size: 18879 bytes --] ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Speed improvements to ido.el 2012-11-30 13:42 ` Daniel Skarda @ 2012-12-01 0:40 ` Dmitry Gutov 0 siblings, 0 replies; 6+ messages in thread From: Dmitry Gutov @ 2012-12-01 0:40 UTC (permalink / raw) To: Daniel Skarda; +Cc: monnier, emacs-devel On 30.11.2012 17:42, Daniel Skarda wrote: > I prepared detailed benchmark. Results: > > - standard Emacs 24.3 indeed provides significant speed improvement over > 23.3 in ido flexible matching > - original ido-better-flex performance is terrible > - speed-hack introduces two improvements: ido-mode patches and (shared) > bitmaps > > - ido-mode patches improve ido E24 performance > - bitmap optimization provides significant improvement for better-flex > but slows down E24 a little bit > - shared bitmaps significantly improve performance of all methods So, the "patches" consistently provide about twice better performance. That's good, I guess. Can you actually see this improvement while using ido with your data (i.e. trunk ido is not fast enough), or is your main goal at this point to improve better-flex performance? Do smex, describe-function, etc still work slow enough for you to warrant "shared bitmaps"? I think now you're supposed to provide the patch(es) against the trunk ido. Just to make sure, you haven used any code from ido-hacks, right? IIRC it uses some similar optimizations. > My setup: > > - debian x64 testing on Lenovo R400 (Intel Core2 Duo) > - debian testnig emacs 23.3 & emacs-snapshot 20121115 from > http://emacs.naquadah.org/ > - to avoid cpu frequency scaling, I call > cpufreq-set -r -g userspace -d 800MHz -u 800MHz > - I use benchmark-run to meassure time and garbage collection > > Tests > > I simulate interactive ido mode by calls to ido-set-matches. I emulate > typing by > setting ido-text. I start with one character and append one character > for each > iteration (eg. 'a', 'ab', 'abc' etc...) > > I use 4 different tests: > > - "abcdefghijklmnopqrstuvwxyz" - this test favours my patches, because > they reuse > results from last matching. > > - "-etaimn" - most common characters in English (and Emacs commands). > The number > of completions will not be reduced too much in this test. > > - "bcfile" - "real-world" example. Shortcut for byte-compile-file > > - "fndgd" - second "real-world" example. Shortcut for find-grep-dired > > Ido uses obarray to complete all 4 examples. To have same conditions, > I saved the completion list to file (39580 symbols). All tests > start with fresh Emacs and with the same list to complete. > > Variants > > I tested following variants: > > - ido-mode - ido mode file version > - cmn - ido-set-common-completion is part of the test > - flx - ido-enable-flex-matching on and off > - cas - ido-case-fold on and off > - rgx - ido-enable-regexp on and off > > - better - ido-better-flex off, original and patched version > - cache - use of bimaps cache (only for ido-speed-hack) > > ido-mode variants: > > - 23.3 - file from 23.3 distribution > - 24.3 - file from debian emacs-snapshot package (as of 20121122) > - patched - 24.3 + patches (function inlining and avoid gc) > - bitmaps - using ido-speed-hack bitmaps and result caching > - shared - bitmaps are cached between executions. > > > Results - Emacs 23.3 > > > | ido-mode | cmn | flx | cas | rgx | better | "a..z" | #GC | GC | > -etaimn | #GC | GC | bcfile | #GC | GC | fndgd | #GC | GC | > |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+------+--------+---------+-----+--------+---------+-----+--------| > | 23.3 | - | - | - | - | - | 25.373 | 87 | 7.715 | > 7.98 | 26 | 2.32 | 5.582 | 20 | 1.766 | 5.728 | 20 | 1.794 | > | 23.3 | t | - | - | - | - | 27.980 | 106 | 9.466 | > 11.526 | 50 | 4.649 | 6.727 | 29 | 2.559 | 7.089 | 30 | 2.659 | > | 23.3 | - | t | - | - | - | 371.272 | 87 | 7.703 | > 112.883 | 26 | 2.333 | 38.856 | 20 | 1.787 | 41.674 | 20 | 1.792 | > | 23.3 | - | t | t | - | - | 592.653 | 87 | 7.714 | > 181.204 | 26 | 2.343 | 60.389 | 20 | 1.793 | 64.969 | 20 | 1.799 | > | 23.3 | - | - | - | t | - | 24.662 | 87 | 7.708 | > 7.480 | 26 | 2.330 | 5.371 | 20 | 1.768 | 5.450 | 20 | 1.770 | > | 23.3 | - | - | - | - | orig | 463.980 | 1289 | 117.554 | > 204.444 | 615 | 58.911 | 129.562 | 340 | 30.715 | 137.558 | 370 | 33.878 | > | 23.3 | - | - | t | - | orig | 885.647 | 2440 | 222.092 | > 342.790 | 1035 | 98.879 | 239.584 | 629 | 57.987 | 256.425 | 695 | 64.553 | > |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+------+--------+---------+-----+--------+---------+-----+--------| > | 24.3 | - | - | - | - | - | 25.465 | 87 | 7.700 | > 8.019 | 26 | 2.343 | 5.613 | 20 | 1.767 | 5.707 | 20 | 1.775 | > | 24.3 | t | - | - | - | - | 28.182 | 106 | 9.493 | > 11.572 | 50 | 4.664 | 6.777 | 29 | 2.561 | 7.127 | 30 | 2.660 | > | 24.3 | - | t | - | - | - | 47.964 | 87 | 7.725 | > 13.261 | 26 | 2.329 | 7.575 | 20 | 1.768 | 7.804 | 20 | 1.773 | > | 24.3 | - | t | t | - | - | 67.351 | 87 | 7.738 | > 18.109 | 26 | 2.335 | 10.264 | 20 | 1.787 | 10.592 | 20 | 1.775 | > | 24.3 | - | - | - | t | - | 24.791 | 87 | 7.714 | > 7.513 | 26 | 2.318 | 5.382 | 20 | 1.771 | 5.487 | 20 | 1.771 | > | 24.3 | - | - | - | - | orig | 459.364 | 1299 | 116.504 | > 203.055 | 620 | 58.518 | 129.042 | 344 | 31.143 | 136.720 | 373 | 34.116 | > | 24.3 | - | - | t | - | orig | 875.099 | 2440 | 219.660 | > 338.753 | 1040 | 97.563 | 236.528 | 639 | 57.794 | 252.875 | 699 | 63.647 | > |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+------+--------+---------+-----+--------+---------+-----+--------| > | patched | - | - | - | - | - | 13.209 | 2 | 0.184 | > 4.697 | 3 | 0.277 | 2.838 | 1 | 0.090 | 2.950 | 1 | 0.087 | > | patched | t | - | - | - | - | 14.984 | 15 | 1.401 | > 7.057 | 20 | 1.912 | 3.518 | 6 | 0.551 | 3.895 | 8 | 0.731 | > | patched | - | t | - | - | - | 32.246 | 3 | 0.267 | > 9.443 | 4 | 0.365 | 4.335 | 1 | 0.088 | 4.578 | 1 | 0.089 | > | patched | - | t | t | - | - | 51.477 | 3 | 0.265 | > 14.232 | 4 | 0.363 | 7.024 | 1 | 0.088 | 7.385 | 1 | 0.090 | > | patched | - | - | - | t | - | 12.853 | 2 | 0.177 | > 4.267 | 3 | 0.271 | 2.676 | 1 | 0.088 | 2.774 | 1 | 0.089 | > | patched | - | - | - | - | patch | 430.462 | 1176 | 107.325 | > 185.306 | 554 | 53.674 | 107.259 | 278 | 24.945 | 115.460 | 310 | 27.954 | > | patched | - | - | t | - | patch | 835.141 | 2295 | 205.013 | > 319.621 | 967 | 92.213 | 201.717 | 538 | 48.043 | 218.950 | 599 | 53.997 | > |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+------+--------+---------+-----+--------+---------+-----+--------| > | bitmaps | - | - | - | - | - | 12.109 | 10 | 1.067 | > 15.753 | 20 | 2.197 | 11.172 | 10 | 1.061 | 11.633 | 10 | 1.066 | > | bitmaps | t | - | - | - | - | 13.824 | 20 | 2.233 | > 17.727 | 30 | 3.426 | 11.432 | 10 | 1.075 | 12.087 | 11 | 1.193 | > | bitmaps | - | t | - | - | - | 12.379 | 10 | 1.066 | > 17.347 | 20 | 2.204 | 11.273 | 10 | 1.068 | 11.760 | 10 | 1.076 | > | bitmaps | - | t | t | - | - | 12.849 | 10 | 1.068 | > 19.326 | 20 | 2.190 | 11.507 | 10 | 1.061 | 12.160 | 10 | 1.069 | > | bitmaps | - | - | - | t | - | 13.561 | 10 | 1.157 | > 5.120 | 10 | 1.157 | 3.610 | 10 | 1.051 | 3.803 | 10 | 1.151 | > | bitmaps | - | - | - | - | patch | 25.564 | 40 | 4.500 | > 87.040 | 180 | 21.534 | 19.759 | 30 | 3.351 | 26.850 | 41 | 4.705 | > | bitmaps | - | - | t | - | patch | 39.640 | 70 | 7.918 | > 139.870 | 290 | 35.046 | 27.684 | 41 | 4.575 | 42.250 | 71 | 8.024 | > |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+------+--------+---------+-----+--------+---------+-----+--------| > | shared | - | - | - | - | - | 3.617 | 4 | 0.452 | > 6.836 | 10 | 1.167 | 2.470 | 2 | 0.215 | 3.044 | 3 | 0.329 | > | shared | t | - | - | - | - | 5.338 | 14 | 1.609 | > 9.127 | 23 | 2.674 | 3.162 | 6 | 0.678 | 3.916 | 8 | 0.897 | > | shared | - | t | - | - | - | 3.986 | 5 | 0.548 | > 8.549 | 11 | 1.247 | 2.545 | 2 | 0.218 | 3.173 | 3 | 0.331 | > | shared | - | t | t | - | - | 4.482 | 5 | 0.549 | > 10.544 | 11 | 1.247 | 2.805 | 2 | 0.222 | 3.590 | 3 | 0.326 | > | shared | - | - | - | t | - | 12.662 | 2 | 0.219 | > 4.134 | 2 | 0.214 | 2.645 | 1 | 0.107 | 2.732 | 1 | 0.108 | > | shared | - | - | - | - | patch | 17.136 | 34 | 3.869 | > 78.877 | 172 | 20.579 | 11.027 | 21 | 2.377 | 18.757 | 38 | 4.313 | > | shared | - | - | t | - | patch | 30.922 | 61 | 6.953 | > 131.599 | 282 | 33.907 | 19.531 | 37 | 4.165 | 34.522 | 70 | 7.966 | > |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+------+--------+---------+-----+--------+---------+-----+--------| > > Results - Emacs 24.3.50 > > | ido-mode | cmn | flx | cas | rgx | better | "a..z" | #GC | GC | > -etaimn | #GC | GC | bcfile | #GC | GC | fndgd | #GC | GC | > |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+-----+--------+---------+-----+--------+---------+-----+--------| > | 23.3 | - | - | - | - | - | 23.422 | 86 | 7.802 | > 7.265 | 25 | 2.281 | 5.170 | 20 | 1.808 | 5.265 | 20 | 1.812 | > | 23.3 | t | - | - | - | - | 26.067 | 106 | 9.670 | > 10.791 | 50 | 4.728 | 6.035 | 26 | 2.360 | 6.609 | 30 | 2.718 | > | 23.3 | - | t | - | - | - | 370.813 | 86 | 7.795 | > 112.986 | 25 | 2.288 | 38.377 | 20 | 1.807 | 41.195 | 20 | 1.790 | > | 23.3 | - | t | t | - | - | 595.396 | 86 | 7.771 | > 182.541 | 25 | 2.296 | 60.243 | 20 | 1.814 | 64.945 | 20 | 1.787 | > | 23.3 | - | - | - | t | - | 23.010 | 86 | 7.704 | > 6.915 | 25 | 2.254 | 5.025 | 20 | 1.792 | 5.101 | 20 | 1.792 | > | 23.3 | - | - | - | - | orig | 354.581 | 1224 | 113.705 | > 164.447 | 570 | 59.209 | 98.402 | 320 | 30.417 | 105.588 | 350 | 33.808 | > | 23.3 | - | - | t | - | orig | 642.533 | 2310 | 213.541 | > 261.947 | 969 | 98.604 | 174.093 | 600 | 57.592 | 186.379 | 659 | 62.799 | > |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+-----+--------+---------+-----+--------+---------+-----+--------| > | 24.3 | - | - | - | - | - | 22.806 | 86 | 7.797 | > 7.128 | 25 | 2.298 | 5.010 | 20 | 1.798 | 5.112 | 20 | 1.799 | > | 24.3 | t | - | - | - | - | 25.488 | 106 | 9.651 | > 10.632 | 50 | 4.708 | 5.899 | 26 | 2.366 | 6.471 | 30 | 2.712 | > | 24.3 | - | t | - | - | - | 43.514 | 86 | 7.729 | > 12.157 | 25 | 2.323 | 6.780 | 20 | 1.796 | 6.987 | 20 | 1.798 | > | 24.3 | - | t | t | - | - | 62.310 | 86 | 7.761 | > 16.737 | 25 | 2.322 | 9.357 | 20 | 1.797 | 9.681 | 20 | 1.804 | > | 24.3 | - | - | - | t | - | 22.500 | 86 | 7.737 | > 6.772 | 25 | 2.259 | 4.892 | 20 | 1.796 | 4.962 | 20 | 1.793 | > | 24.3 | - | - | - | - | orig | 356.023 | 1227 | 115.312 | > 162.438 | 571 | 57.330 | 97.526 | 320 | 29.748 | 104.051 | 350 | 32.425 | > | 24.3 | - | - | t | - | orig | 642.029 | 2320 | 213.897 | > 257.828 | 969 | 95.111 | 172.289 | 600 | 56.291 | 183.545 | 659 | 60.493 | > |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+-----+--------+---------+-----+--------+---------+-----+--------| > | patched | - | - | - | - | - | 11.587 | 2 | 0.185 | > 4.167 | 3 | 0.280 | 2.520 | 1 | 0.093 | 2.585 | 1 | 0.093 | > | patched | t | - | - | - | - | 13.263 | 14 | 1.327 | > 6.388 | 19 | 1.813 | 3.143 | 6 | 0.544 | 3.503 | 8 | 0.738 | > | patched | - | t | - | - | - | 29.458 | 3 | 0.277 | > 8.620 | 3 | 0.279 | 3.868 | 1 | 0.090 | 4.075 | 1 | 0.093 | > | patched | - | t | t | - | - | 48.135 | 3 | 0.275 | > 13.259 | 3 | 0.279 | 6.437 | 1 | 0.090 | 6.769 | 1 | 0.092 | > | patched | - | - | - | t | - | 11.307 | 2 | 0.185 | > 3.847 | 3 | 0.277 | 2.362 | 1 | 0.091 | 2.427 | 1 | 0.090 | > | patched | - | - | - | - | patch | 326.320 | 1095 | 102.650 | > 147.375 | 515 | 53.024 | 80.696 | 263 | 24.657 | 87.440 | 292 | 27.547 | > | patched | - | - | t | - | patch | 607.426 | 2136 | 196.133 | > 243.672 | 898 | 90.915 | 145.362 | 507 | 46.650 | 159.114 | 564 | 52.703 | > |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+-----+--------+---------+-----+--------+---------+-----+--------| > | bitmaps | - | - | - | - | - | 9.825 | 10 | 1.061 | > 13.090 | 20 | 2.180 | 9.068 | 10 | 1.052 | 9.442 | 10 | 1.054 | > | bitmaps | t | - | - | - | - | 11.604 | 20 | 2.320 | > 14.934 | 30 | 3.381 | 9.270 | 10 | 1.055 | 9.839 | 11 | 1.174 | > | bitmaps | - | t | - | - | - | 10.084 | 10 | 1.052 | > 14.586 | 20 | 2.160 | 9.149 | 10 | 1.062 | 9.569 | 10 | 1.061 | > | bitmaps | - | t | t | - | - | 10.562 | 10 | 1.054 | > 16.538 | 20 | 2.167 | 9.391 | 10 | 1.073 | 9.961 | 10 | 1.068 | > | bitmaps | - | - | - | t | - | 12.150 | 10 | 1.043 | > 4.632 | 10 | 1.043 | 3.324 | 10 | 1.037 | 3.407 | 10 | 1.0378 | > | bitmaps | - | - | - | - | patch | 20.721 | 40 | 4.482 | > 69.525 | 170 | 20.207 | 16.163 | 30 | 3.407 | 21.572 | 40 | 4.514 | > | bitmaps | - | - | t | - | patch | 29.711 | 61 | 6.860 | > 106.825 | 280 | 33.311 | 21.392 | 40 | 4.450 | 32.450 | 70 | 7.902 | > |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+-----+--------+---------+-----+--------+---------+-----+--------| > | shared | - | - | - | - | - | 3.012 | 4 | 0.452 | > 5.836 | 10 | 1.154 | 2.029 | 2 | 0.219 | 2.531 | 3 | 0.332 | > | shared | t | - | - | - | - | 4.589 | 13 | 1.511 | > 7.910 | 22 | 2.546 | 2.693 | 6 | 0.671 | 3.380 | 8 | 0.901 | > | shared | - | t | - | - | - | 3.407 | 5 | 0.565 | > 7.387 | 10 | 1.159 | 2.115 | 2 | 0.219 | 2.655 | 3 | 0.332 | > | shared | - | t | t | - | - | 3.873 | 5 | 0.564 | > 9.322 | 10 | 1.161 | 2.339 | 2 | 0.218 | 3.032 | 3 | 0.329 | > | shared | - | - | - | t | - | 11.290 | 2 | 0.220 | > 3.759 | 2 | 0.222 | 2.259 | 0 | 0.000 | 2.448 | 1 | 0.105 | > | shared | - | - | - | - | patch | 13.653 | 33 | 3.784 | > 62.698 | 163 | 19.750 | 8.690 | 20 | 2.262 | 14.945 | 37 | 4.231 | > | shared | - | - | t | - | patch | 23.090 | 58 | 6.624 | > 99.838 | 268 | 32.725 | 14.645 | 36 | 4.064 | 25.692 | 66 | 7.531 | > |----------+-----+-----+-----+-----+--------+---------+------+---------+---------+-----+--------+---------+-----+--------+---------+-----+--------| > > On Thu, Nov 22, 2012 at 10:36 AM, Daniel Skarda <dan.skarda@gmail.com > <mailto:dan.skarda@gmail.com>> wrote: > > > > Hi Dmitry, > > > > thanks for the suggestions. I will prepare some benchmarks using new > Emacs and send the results. > > I already did some statistics with elp during development, but I > suspect that the numbers are not precise. > > > > I am curious which improvements will be the fastest :) > > > > Regards, > > Dan > > > > > > On Wed, Nov 21, 2012 at 4:37 AM, Dmitry Gutov <dgutov@yandex.ru > <mailto:dgutov@yandex.ru>> wrote: > >> > >> Daniel Skarda <dan.skarda@gmail.com <mailto:dan.skarda@gmail.com>> > writes: > >> > >> Hey Daniel, > >> > >> Like Leo said, please provide some numbers. > >> > >> A comparison to the current trunk would be best, since it contains an > >> additional optimization compared to the emacs-24 branch. > >> > >> Here my test setup from the relevant discussion: > >> http://debbugs.gnu.org/cgi/bugreport.cgi?bug=12796#47 > >> > >> --Dmitry > >> > >> > I like to use ido mode for everything, including very large lists > (like M-x or > >> > info). Unfortunately ido is not suitable for such lists. On my old > notebook, > >> > performance is not amazing, so I took the challenge and spend some > time with > >> > profiler. > >> > > >> > I improved the performance in several steps: > >> > > >> > - inlined several functions > >> > - disabled ido-case-fold for some completions (eg commands) > >> > - prunning collections based on character bitmaps > >> > - caching character bitmaps during completion or for same completions > >> > - caching intermediate completion lists when adding new characters > >> > > >> > You can view my changes on github: > >> > > >> > - https://github.com/orfelyus/ido-speed-hack > >> > - https://github.com/orfelyus/ido-mode-el > >> > > >> > - (and optionally) https://github.com/orfelyus/ido-better-flex > >> > > >> > ido-speed-hack includes large changes (bitmaps) while ido-mode-el > includes minor > >> > changes to ido.el > >> > > >> > The changes made huge speed improvements on my notebook and ido > does not feel > >> > sluggish even with very large lists. > >> > > >> > Could you please test my improvements? I would appreciate any > feedback. > >> > Dan > >> > > >> > ps: I am not subscribed to the mailing list, please keep me in Cc > > > > ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2012-12-01 0:40 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2012-11-20 18:25 Speed improvements to ido.el Daniel Skarda 2012-11-21 3:20 ` Leo 2012-11-21 3:37 ` Dmitry Gutov 2012-11-22 9:36 ` Daniel Skarda 2012-11-30 13:42 ` Daniel Skarda 2012-12-01 0:40 ` Dmitry Gutov
Code repositories for project(s) associated with this public inbox https://git.savannah.gnu.org/cgit/emacs.git This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).