emacs-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Speed improvements to ido.el


From: Daniel Skarda
Subject: Re: Speed improvements to ido.el
Date: Fri, 30 Nov 2012 14:42:22 +0100

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]