3 ms·

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 t

by 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.
    - zxzax 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. So would a simple search in that folder? I don't see what is special about type-ahead here. I'm not talking about recursive search, that can already be disabled in Nautilus if you don't want it. I think this another reason is why it's bad that people get so outraged about this, a lot of the anger is directed at recursive search when really the solution there is to just fix or disable recursive search. Bringing back type-ahead is not the only way to deal with the problem. Another option would be to speed up recursive search so that it uses your suggestion first to do a fast search and quickly display results from the current folder before recursing, that would be the best of both worlds. >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. That could also be solved with an intentional search option to search by prefix, maybe with a button and bound to a certain key that makes it obvious and not confusing what's happening. I'm not saying it's bad to search by prefix.
dleslie 5y ago
Win95 and Win98 had super fast file managers. Hell, the whole 9x era of Windows would run laps around all these "modern" desktops.
- zxzax 5y ago
  I'd love to see the source code to the Win95 and Win98 file managers, maybe we can copy some of the performance tricks.
  - jstimpfle 5y ago
    The "trick" is to just run a loop over a list stored in RAM.
    - zxzax 5y ago
      That seems to be over simplifying, every database is "just running a loop over a list stored in RAM." The challenge is in how you build that list, and then with a GUI the challenge becomes how to display it. Win95 had to run in very memory constrained environments compared to today so I'd imagine there is some special considerations there.
      - jstimpfle 5y ago
        I don't find there is a lot that could make sense to do. I believe computers running Win95 had like 16-128MB of RAM, it wouldn't be too wasteful for a file manager to store, say, 32-64K worth of cached file entries uncompressed in RAM. That could allow for maybe 1024 file entries (depending on the attributes that should be cached for each entry - more if we're really just storing a list of zero-terminated strings and maybe directory bits), which would already cover almost all realistic use cases at the time. So it's literally a loop over that in-RAM cache in most cases. It seems like e.g. FAT32 allowed for theoretically 64K entries per directory, but I find it unlikely that most programs would bother to optimize for that. One could just punt and allocate more memory dynamically in those cases until there is a Out-of-memory situation. Or one could page in the directory entries chunk by chunk (so, maybe 64 chunks max) on each update which would considerably slow down some operations of the program (such as scrolling, sorting, type-ahead, when any of those cross a chunk boundary), but still be acceptable as a rare occurrence. Or, if one specifically wanted to optimize for something like scrolling or type ahead, which are simple "linear movements", one could just keep this linear list (sorted according to user preferences / filters) in a cache file on disk. Streaming that in chunk-by-chunk is very fast as well, since you only need one disk access to get at the next chunk. I figure that would be way overkill for most practical requirements, but it still wouldn't be a lot of work to implement.

by zxzax 5y ago

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.
  - zxzax 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. So would a simple search in that folder? I don't see what is special about type-ahead here. I'm not talking about recursive search, that can already be disabled in Nautilus if you don't want it. I think this another reason is why it's bad that people get so outraged about this, a lot of the anger is directed at recursive search when really the solution there is to just fix or disable recursive search. Bringing back type-ahead is not the only way to deal with the problem. Another option would be to speed up recursive search so that it uses your suggestion first to do a fast search and quickly display results from the current folder before recursing, that would be the best of both worlds. >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. That could also be solved with an intentional search option to search by prefix, maybe with a button and bound to a certain key that makes it obvious and not confusing what's happening. I'm not saying it's bad to search by prefix.

dleslie 5y ago

Win95 and Win98 had super fast file managers. Hell, the whole 9x era of Windows would run laps around all these "modern" desktops.

zxzax 5y ago
I'd love to see the source code to the Win95 and Win98 file managers, maybe we can copy some of the performance tricks.
- jstimpfle 5y ago
  The "trick" is to just run a loop over a list stored in RAM.
  - zxzax 5y ago
    That seems to be over simplifying, every database is "just running a loop over a list stored in RAM." The challenge is in how you build that list, and then with a GUI the challenge becomes how to display it. Win95 had to run in very memory constrained environments compared to today so I'd imagine there is some special considerations there.
    - jstimpfle 5y ago
      I don't find there is a lot that could make sense to do. I believe computers running Win95 had like 16-128MB of RAM, it wouldn't be too wasteful for a file manager to store, say, 32-64K worth of cached file entries uncompressed in RAM. That could allow for maybe 1024 file entries (depending on the attributes that should be cached for each entry - more if we're really just storing a list of zero-terminated strings and maybe directory bits), which would already cover almost all realistic use cases at the time. So it's literally a loop over that in-RAM cache in most cases. It seems like e.g. FAT32 allowed for theoretically 64K entries per directory, but I find it unlikely that most programs would bother to optimize for that. One could just punt and allocate more memory dynamically in those cases until there is a Out-of-memory situation. Or one could page in the directory entries chunk by chunk (so, maybe 64 chunks max) on each update which would considerably slow down some operations of the program (such as scrolling, sorting, type-ahead, when any of those cross a chunk boundary), but still be acceptable as a rare occurrence. Or, if one specifically wanted to optimize for something like scrolling or type ahead, which are simple "linear movements", one could just keep this linear list (sorted according to user preferences / filters) in a cache file on disk. Streaming that in chunk-by-chunk is very fast as well, since you only need one disk access to get at the next chunk. I figure that would be way overkill for most practical requirements, but it still wouldn't be a lot of work to implement.