From: Dmitry Gutov <dgutov@yandex.ru>
To: Daniel Skarda <dan.skarda@gmail.com>
Cc: monnier@iro.umontreal.ca, emacs-devel@gnu.org
Subject: Re: Speed improvements to ido.el
Date: Sat, 01 Dec 2012 04:40:05 +0400 [thread overview]
Message-ID: <50B951E5.9050109@yandex.ru> (raw)
In-Reply-To: <CAAfMPgD0eqPBgFi-D+VAfARmbo-Vms6g-Ux2S-ej8m6L8mns3A@mail.gmail.com>
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
> >
> >
prev parent reply other threads:[~2012-12-01 0:40 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
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 [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=50B951E5.9050109@yandex.ru \
--to=dgutov@yandex.ru \
--cc=dan.skarda@gmail.com \
--cc=emacs-devel@gnu.org \
--cc=monnier@iro.umontreal.ca \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.