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 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 wrote: >> >> Daniel Skarda 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 > >