3 ms·

If you don't preload the folder contents and index it then type-ahead will also be arbitrarily slow there too. I don't know of any Linux filesystem that stores

by zxzax 5y ago

If you don't preload the folder contents and index it then type-ahead will also be arbitrarily slow there too. I don't know of any Linux filesystem that stores the files sorted and indexed on disk. >And how does that support your argument that re-instroducing Type Ahead would de-prioritize search for them? The idea I got from reading the GNOME HIG is that if users accidentally type into the window, the behavior should be consistent and predictable with what the user was really trying to do (search). Doing a strange and inconsistent matching behavior that is not available through any other means and is essentially hidden functionality is only going to cause confusion.

jstimpfle 5y ago
But why would you rely on the filesystem to implement Type-Ahead? The File Manager just goes through that little list of files that it has already cached because it is displaying them anyway. And it just goes through the list linearly, starting from the currently highlighted item, stopping at the first match. It's a miniscule operation. -- Speaking practically, have you ever experienced any file manager that has type-ahead (like most do) and the type ahead was not blazingly fast? > The idea I got from reading the GNOME HIG is that if users accidentally type into the window, the behavior should be consistent and predictable with what the user was really trying to do (search). Doing a strange and inconsistent matching behavior that is not available through any other means and is essentially hidden functionality is only going to cause confusion. If you're refusing to see that they achieved just the opposite and broke a totally sane implementation that was super predictable for any user that actually cared about their workflow, you can't be helped.
- zxzax 5y ago
  Until global file indexing became a thing built into operating systems, every file manager was slow to open and sort directories with a lot of files. At least that was my experience. An index is still needed to do type-ahead, at minimum you'd need to build a prefix tree. You can't just load the list of files and be done; linear search will cause the same arbitrary slowness. Imagine typing an 'a' when on disk the all the 'a' files happen to be stored at the end of the directory. You would have to rescan the whole list every time you type another letter. >you can't be helped This is not the way to have a constructive conversation, please stop. I gave an example of how it's confusing and not predictable for some, let's discuss ways we can make it more predictable.
  - jstimpfle 5y ago
    See, you just iterate the list or array where you store the list items that you're pushing to the screen anyway. There is nothing at all that you need to add in terms of data structure. No index whatsoever. > linear search will cause the same arbitrary slowness. Let's see. My Thinkpad x220, which was built almost 10 years ago, can easily scan through 10 Gigabytes of memory per second. If we assume that visiting each list item causes a cache miss though (which is pessimistic), then (assuming a cache miss costs 100 nanoseconds) maybe we can visit roughly 10 million directory entries with the worst possible, dumb, serial implementation. Let's say we want to ensure a reasonable target of not wasting more than 1 millisecond for the search, we can still Type-Ahead through directories containing 10000 entries with incredible performance (1ms latency). However, if the directory contents are stored only in a slightly reasonable structure (say, the developer spent the slightest thought at it, like caching the entries in a list of array chunks or so), then, I don't know, it might be closer to 100K entries per 1ms or even approach 1 million entries per 1ms with a little optimization. It's not a problem at all, it's less than a piece of cake.
    - zxzax 5y ago
      If you're set on linear search then you would see the same performance for a simple search box too, I don't see how type-ahead changes it. For big folders you will still need an index, imagine now you sorted the list by reverse alphabetical, typing an 'a' is still going to be slow when you're at the top.
      - jstimpfle 5y ago
        Again, the point is that type-ahead is an operation on the directory entries that are cached in the file manager's memory. It does not touch the file system at all. That's why it is so fast in practice, it's instantaneous (as far as screen refreshs go) on every file manager I've ever used. Recursive search however, does have to touch the filesystem, and does have to touch it massively for directories that contain thousands of subdirectories. That's what a "search" is, the user expects the search results to be fresh from the file system, not just scraped from a cache internal to the File Manager. That's why recursive search is so disturbingly slow, to the point where it routinely takes seconds, or could even minutes depending on the setup (spinning drive + bad filesystem + large directory tree...). And that is why Nautilus is basically unusable for me and a lot of other people. By the way, there are other semantical problems with search vs Type-Ahead. For example, I cannot type a prefix in the current directory to see whether there is a file with that prefix in the current directory. Nautilus' recursive search will just pull up a completely unrelated and unexpected file from somewhere in this tree. That means, that if I mistype, I don't get any reasonable feedback from Nautilus, but instead get a warm "thank you" and a huge diskload. It's about as depressing as browsing some websites that bombard you with ads and never show the contents you searched for.

by zxzax 5y ago

jstimpfle 5y ago

But why would you rely on the filesystem to implement Type-Ahead? The File Manager just goes through that little list of files that it has already cached because it is displaying them anyway. And it just goes through the list linearly, starting from the currently highlighted item, stopping at the first match. It's a miniscule operation. -- Speaking practically, have you ever experienced any file manager that has type-ahead (like most do) and the type ahead was not blazingly fast? > The idea I got from reading the GNOME HIG is that if users accidentally type into the window, the behavior should be consistent and predictable with what the user was really trying to do (search). Doing a strange and inconsistent matching behavior that is not available through any other means and is essentially hidden functionality is only going to cause confusion. If you're refusing to see that they achieved just the opposite and broke a totally sane implementation that was super predictable for any user that actually cared about their workflow, you can't be helped.

zxzax 5y ago
Until global file indexing became a thing built into operating systems, every file manager was slow to open and sort directories with a lot of files. At least that was my experience. An index is still needed to do type-ahead, at minimum you'd need to build a prefix tree. You can't just load the list of files and be done; linear search will cause the same arbitrary slowness. Imagine typing an 'a' when on disk the all the 'a' files happen to be stored at the end of the directory. You would have to rescan the whole list every time you type another letter. >you can't be helped This is not the way to have a constructive conversation, please stop. I gave an example of how it's confusing and not predictable for some, let's discuss ways we can make it more predictable.
- jstimpfle 5y ago
  See, you just iterate the list or array where you store the list items that you're pushing to the screen anyway. There is nothing at all that you need to add in terms of data structure. No index whatsoever. > linear search will cause the same arbitrary slowness. Let's see. My Thinkpad x220, which was built almost 10 years ago, can easily scan through 10 Gigabytes of memory per second. If we assume that visiting each list item causes a cache miss though (which is pessimistic), then (assuming a cache miss costs 100 nanoseconds) maybe we can visit roughly 10 million directory entries with the worst possible, dumb, serial implementation. Let's say we want to ensure a reasonable target of not wasting more than 1 millisecond for the search, we can still Type-Ahead through directories containing 10000 entries with incredible performance (1ms latency). However, if the directory contents are stored only in a slightly reasonable structure (say, the developer spent the slightest thought at it, like caching the entries in a list of array chunks or so), then, I don't know, it might be closer to 100K entries per 1ms or even approach 1 million entries per 1ms with a little optimization. It's not a problem at all, it's less than a piece of cake.
  - zxzax 5y ago
    If you're set on linear search then you would see the same performance for a simple search box too, I don't see how type-ahead changes it. For big folders you will still need an index, imagine now you sorted the list by reverse alphabetical, typing an 'a' is still going to be slow when you're at the top.
    - jstimpfle 5y ago
      Again, the point is that type-ahead is an operation on the directory entries that are cached in the file manager's memory. It does not touch the file system at all. That's why it is so fast in practice, it's instantaneous (as far as screen refreshs go) on every file manager I've ever used. Recursive search however, does have to touch the filesystem, and does have to touch it massively for directories that contain thousands of subdirectories. That's what a "search" is, the user expects the search results to be fresh from the file system, not just scraped from a cache internal to the File Manager. That's why recursive search is so disturbingly slow, to the point where it routinely takes seconds, or could even minutes depending on the setup (spinning drive + bad filesystem + large directory tree...). And that is why Nautilus is basically unusable for me and a lot of other people. By the way, there are other semantical problems with search vs Type-Ahead. For example, I cannot type a prefix in the current directory to see whether there is a file with that prefix in the current directory. Nautilus' recursive search will just pull up a completely unrelated and unexpected file from somewhere in this tree. That means, that if I mistype, I don't get any reasonable feedback from Nautilus, but instead get a warm "thank you" and a huge diskload. It's about as depressing as browsing some websites that bombard you with ads and never show the contents you searched for.