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
>
>