From: Daniel Skarda <dan.skarda@gmail.com>
To: Dmitry Gutov <dgutov@yandex.ru>
Cc: monnier@iro.umontreal.ca, emacs-devel@gnu.org
Subject: Re: Speed improvements to ido.el
Date: Fri, 30 Nov 2012 14:42:22 +0100 [thread overview]
Message-ID: <CAAfMPgD0eqPBgFi-D+VAfARmbo-Vms6g-Ux2S-ej8m6L8mns3A@mail.gmail.com> (raw)
In-Reply-To: <CAAfMPgCMaxDh4jdAUjeODCkEGmUFZBZcXnCFF+jScqSLZHh2iw@mail.gmail.com>
[-- 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 --]
next prev parent reply other threads:[~2012-11-30 13:42 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 [this message]
2012-12-01 0:40 ` Dmitry Gutov
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
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAAfMPgD0eqPBgFi-D+VAfARmbo-Vms6g-Ux2S-ej8m6L8mns3A@mail.gmail.com \
--to=dan.skarda@gmail.com \
--cc=dgutov@yandex.ru \
--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 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).