flx -- flex with better sorting

flx -- flex with better sorting

[Le Wang]

[-- Attachment #1: Type: text/plain, Size: 414 bytes --]

Hi all,

I've put up my implementation of Sublime Text 2's fuzzy matching -- i.e.
ido's flex with superior sorting. https://github.com/lewang/flx

I've made a screencast (5 min) of rationale and workflow.
http://www.youtube.com/watch?v=_swuJ1RuMgk

I have signed assignment papers, and would be willing to contribute it to
Emacs.  So please check it out and point out any inefficiencies in my
algorithms.


-- 
Le

[-- Attachment #2: Type: text/html, Size: 685 bytes --]

Re: flx -- flex with better sorting

[Óscar Fuentes]

Le Wang <l26wang@gmail.com> writes:

> I've put up my implementation of Sublime Text 2's fuzzy matching -- i.e.
> ido's flex with superior sorting. https://github.com/lewang/flx
>
> I've made a screencast (5 min) of rationale and workflow.
> http://www.youtube.com/watch?v=_swuJ1RuMgk
>
> I have signed assignment papers, and would be willing to contribute it to
> Emacs.  So please check it out and point out any inefficiencies in my
> algorithms.

From trying it for a few minutes with ido:

1. I like it. Looks much better that ido's flex matching.

2. Working with 10500 candidate files, there is a noticeable pause the
   first time ido-complete is invoked. I'm using a reasonably fast
   machine and the pause is not annoying, but that perception may change
   when using less capable machines.

3. With the same set of candidates, RES memory jumps from 35 MB to 70 MB
   on first use (on a 64 bit GNU/Linux machine). This is a more serious
   concern.

4. Sometimes it fails to work as advertised. For instance, if I type
   `ltx' this file is shown first on the list of matches:

lib/Target/NVPTX/NVPTXLowerAggrCopies.h

but I would expect

lib/Target/X86/* (* meaning any file under that subdirectory).

Furthermore, when inputting `ltx8', matching letters on candidates are
highlighted like this:

lib/Target/X86/X86TargetTransformInfo.cpp
^   ^          ^^

It ignores the first occurrence of `X8'.

5. Another quirk is that it rejects capital letters. For instance, if I
   type `lT' it shows no matches, but in fact there are lots of files
   like this:

lib/Target/...

Actually, typing just `T' fails to find any candidate, but there are
lots files with a capital T on its name.

Re: flx -- flex with better sorting

[Le Wang]

[-- Attachment #1: Type: text/plain, Size: 2231 bytes --]

On Thu, May 2, 2013 at 12:04 AM, Óscar Fuentes <ofv@wanadoo.es> wrote:

> From trying it for a few minutes with ido:
>
> 1. I like it. Looks much better that ido's flex matching.
>

Thanks.

2. Working with 10500 candidate files, there is a noticeable pause the
>    first time ido-complete is invoked. I'm using a reasonably fast
>    machine and the pause is not annoying, but that perception may change
>    when using less capable machines.
>

Yep, it's adding these candidates to the cached hash.


> 3. With the same set of candidates, RES memory jumps from 35 MB to 70 MB
>    on first use (on a 64 bit GNU/Linux machine). This is a more serious
>    concern.
>

Yep.  I mentioned this in my first thread that the algorithm trades memory
usage for speed.  I'm not sure how to optimize this part.


> 4. Sometimes it fails to work as advertised. For instance, if I type
>    `ltx' this file is shown first on the list of matches:
>
> lib/Target/NVPTX/NVPTXLowerAggrCopies.h
>
> but I would expect
>
> lib/Target/X86/* (* meaning any file under that subdirectory).
>

1. The algorithm favors basepaths heavily.
2. I ended up considering all capitals to be beginning of word.

This means ltx is matching as expected.  As you supply more letters, better
results should float to the top.

I made a helm demo that shows scoring of each match.  If you're curious,
just replace the hardcoded list of files with your own list and run it
through helm.  (btw, helm integration still doesn't work)

Furthermore, when inputting `ltx8', matching letters on candidates are
> highlighted like this:
>
> lib/Target/X86/X86TargetTransformInfo.cpp
> ^   ^          ^^
>
> It ignores the first occurrence of `X8'.
>

The letters that made the best score is highlighted.  See: favoring
basename.


> 5. Another quirk is that it rejects capital letters. For instance, if I
>    type `lT' it shows no matches, but in fact there are lots of files
>    like this:
>
> lib/Target/...
>
> Actually, typing just `T' fails to find any candidate, but there are
> lots files with a capital T on its name.
>

I hadn't considered people might do this.  :-)  Will fix soon.


-- 
Le

[-- Attachment #2: Type: text/html, Size: 3972 bytes --]

Re: flx -- flex with better sorting

[Óscar Fuentes]

Le Wang <l26wang@gmail.com> writes:

>> 4. Sometimes it fails to work as advertised. For instance, if I type
>>    `ltx' this file is shown first on the list of matches:
>>
>> lib/Target/NVPTX/NVPTXLowerAggrCopies.h
>>
>> but I would expect
>>
>> lib/Target/X86/* (* meaning any file under that subdirectory).
>>
>
> 1. The algorithm favors basepaths heavily.
> 2. I ended up considering all capitals to be beginning of word.
>
> This means ltx is matching as expected.  As you supply more letters, better
> results should float to the top.

Okay. Knowing this makes for a much more effective usage.

>> 5. Another quirk is that it rejects capital letters. For instance, if I
>>    type `lT' it shows no matches, but in fact there are lots of files
>>    like this:
>>
>> lib/Target/...
>>
>> Actually, typing just `T' fails to find any candidate, but there are
>> lots files with a capital T on its name.
>>
>
> I hadn't considered people might do this.  :-)  Will fix soon.

Ideally, when using capital letters those candidates that matched case
would get higher points.

More quirks:

C-s, C-r etc stops working on ido after enabling flx.

One Emacs instance started to quickly use memory and had to kill it when
noticed that the system was furiously paging. That Emacs instance was
doing nothing, just showing a prompt of 3 candidates for kill-buffer.

With ido, C-x k (kill-buffer) usually offers the current buffer as the
first candidate. After activating flx, that's not necessarily so.

While navigating directory trees with find-file, at certain point no
candidates where listed as soon as any string was entered. With no
input, all candidates were shown. I was unable to replicate the problem.

Re: flx -- flex with better sorting

[Le Wang]

[-- Attachment #1: Type: text/plain, Size: 2453 bytes --]

On Thu, May 2, 2013 at 1:04 AM, Óscar Fuentes <ofv@wanadoo.es> wrote:

> Le Wang <l26wang@gmail.com> writes:
>
> >> 4. Sometimes it fails to work as advertised. For instance, if I type
> >>    `ltx' this file is shown first on the list of matches:
> >>
> >> lib/Target/NVPTX/NVPTXLowerAggrCopies.h
> >>
> >> but I would expect
> >>
> >> lib/Target/X86/* (* meaning any file under that subdirectory).
> >>
> >
> > 1. The algorithm favors basepaths heavily.
> > 2. I ended up considering all capitals to be beginning of word.
> >
> > This means ltx is matching as expected.  As you supply more letters,
> better
> > results should float to the top.
>
> Okay. Knowing this makes for a much more effective usage.
>
> >> 5. Another quirk is that it rejects capital letters. For instance, if I
> >>    type `lT' it shows no matches, but in fact there are lots of files
> >>    like this:
> >>
> >> lib/Target/...
> >>
> >> Actually, typing just `T' fails to find any candidate, but there are
> >> lots files with a capital T on its name.
> >>
> >
> > I hadn't considered people might do this.  :-)  Will fix soon.
>
> Ideally, when using capital letters those candidates that matched case
> would get higher points.
>

I fixed this bug.  Capital letters are considered word beginnings so they
are always preferred.

More quirks:
>
> C-s, C-r etc stops working on ido after enabling flx.
>

I opened a bug on github to track this.

>
> One Emacs instance started to quickly use memory and had to kill it when
> noticed that the system was furiously paging. That Emacs instance was
> doing nothing, just showing a prompt of 3 candidates for kill-buffer.
>

It'd be good to get repro steps for this.

With ido, C-x k (kill-buffer) usually offers the current buffer as the
> first candidate. After activating flx, that's not necessarily so.
>

The completion list should change until you hit the first letter.  After
that flx takes over sorting.  Is this what you're seeing?


> While navigating directory trees with find-file, at certain point no
> candidates where listed as soon as any string was entered. With no
> input, all candidates were shown. I was unable to replicate the problem.
>

I opened a bug on github to track this.  But I don't actually use ido, so
it may take some time to get around to this.  Follow up in the bug if you
have more repro details.

Thanks.

-- 
Le

[-- Attachment #2: Type: text/html, Size: 4107 bytes --]

Re: flx -- flex with better sorting

[Óscar Fuentes]

Le Wang <l26wang@gmail.com> writes:

> I fixed this bug.  Capital letters are considered word beginnings so they
> are always preferred.

Thanks.

>> One Emacs instance started to quickly use memory and had to kill it when
>> noticed that the system was furiously paging. That Emacs instance was
>> doing nothing, just showing a prompt of 3 candidates for kill-buffer.
>>
>
> It'd be good to get repro steps for this.

I'm trying, but no luck so far.

>> With ido, C-x k (kill-buffer) usually offers the current buffer as the
>> first candidate. After activating flx, that's not necessarily so.
>>
>
> The completion list should change until you hit the first letter.  After
> that flx takes over sorting.  Is this what you're seeing?

Yes, if I start with emacs -Q, but no with my setup. I'll bisect my
.emacs later and let you know.

>> While navigating directory trees with find-file, at certain point no
>> candidates where listed as soon as any string was entered. With no
>> input, all candidates were shown. I was unable to replicate the problem.
>>
>
> I opened a bug on github to track this.  But I don't actually use ido, so
> it may take some time to get around to this.  Follow up in the bug if you
> have more repro details.

Ok.

While finding a file on a directory that has one named
Makefile.configure.in, if I type `ci' no matches are shown. Is this the
expected behavior?