Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fast Directory Listing on Linux

github.com

Post reply on HN
Print view View original

51–60 of 75 posts

Re: Fast Directory Listing on Linux

#51

Post by mistrial9 »

saagarjha wrote: post #47
mistrial9 wrote: post #40

Earlier quoted context omitted.

dont you want the compiler to do this for you, with ARCH flags? a bit of foresight and a little checking seems like enough.. excessive ASM is a mistake these days CXXFLAGS -march=sandybridge -mtune=sandybridge

The point is that the compiler does not have enough information to do this automatically.

.. meant to say, after rewriting code to avoid (this,that) extra actions, then let the compiler make the optimized code.. not saying "just re-run the old code with CFLAGS thus" ..

Re: Fast Directory Listing on Linux

#52

Post by univerio »

romka2 wrote: post #39
avar wrote: post #34

Earlier quoted context omitted.

Your documentation indicates that you've tried with core.untrackedCache, but have you tried core.fsmonitor with the watchman hook? Obviously your "gitstatus" is still generally useful, but if your main itch you're trying to scratch is to have a faster "status" in a particular repo then you should be able to get that down to a few milliseconds with "git status", if you're willing to have watchman sit in the background…

> [...] have you tried core.fsmonitor with the watchman hook? I read the docs but it seems like it's not something I can enable on users' machines. Or maybe there is a way to take advantage of it even if it's not enabled? I really haven't looked much into it. To clarify, my main motivation isn't to make my own prompt latency low (I don't even work on large git projects) but to make Powerlevel10k as good a product as…

You could use it if available, and fall back to existing behavior if not. (Not sure if it would be faster, but probably worth experimenting with.)

Re: Fast Directory Listing on Linux

#53

Post by ezoe »

> returning vector is an unaffordable convenience.

Not anymore since C++11.

Reusing vector storage is good, but you can still use move on parameter and not the reference.

Although, in this case, reference is probably easier to write.

Re: Fast Directory Listing on Linux

#54

Post by lathiat »

aasasd wrote: post #50

In my experience, another important component of fast directory listings is a cron job that does “ls -R” every half hour. Because you can't control the eagerness of fs metadata caches even if your fileserver has plenty of free mem.

You can actually tune some VFS parameters to make it less likely to evict the VFS caches (vfs_cache_pressure), however, it's not well documented which settings work the best other than to set it to '1' for 'mostly don't' which mostly works well only if you have way more RAM than you need and will tend to go quite badly if that is not the case. I think the only way to determine that well would be to benchmark it for your specific use case. But it may help you over a recurring "ls -R"

Re: Fast Directory Listing on Linux

#56

Post by adrianratnapala »

ridiculous_fish wrote: post #29

A lovely way to sort strings, especially strings that may have long shared prefixes, is a 3-way partition quicksort. This allows you to avoid walking the same prefix over and over the way that memcmp does. Pick your pivot element and partition the strings into based on the first character only. Note this differs from classic quicksort in that we're maintaining three regions, not two. Now recurse for all three regions…

> There's lots more optimizations possible with this technique, e.g. counting-sort style bucketing.

:) I was going to say that since you are half re-inventing bucket-sort anyway, why not go the whole hog.

Is the code three-part quicksort simpler and easier to understand than a bucket sort?

Re: Fast Directory Listing on Linux

#57

Post by milemi »

ezoe wrote: post #53

> returning vector is an unaffordable convenience. Not anymore since C++11. Reusing vector storage is good, but you can still use move on parameter and not the reference. Although, in this case, reference is probably easier to write.

I think he was concerned about the cost of allocating separate strings that go into the vector.

Re: Fast Directory Listing on Linux

#58

Post by chubot »

ridiculous_fish wrote: post #29

A lovely way to sort strings, especially strings that may have long shared prefixes, is a 3-way partition quicksort. This allows you to avoid walking the same prefix over and over the way that memcmp does. Pick your pivot element and partition the strings into based on the first character only. Note this differs from classic quicksort in that we're maintaining three regions, not two. Now recurse for all three regions…

That's a nice idea. Do you know of any programs that use this?

I know that CPython treats hash tables with string keys as a special case, for performance. I wonder if it might also make sense to treat sorting lists of strings as a special case (or maybe it already does, I will check ...).

Hm yeah it looks like Python's timsort is meant to minimize the number of comparison operations (see Objects/listsort.txt). But it doesn't try to make the comparisons themselves cheaper. That would break the interface to some extent, i.e. it doesn't really fit within the model.

Interesting to think about though!

Re: Fast Directory Listing on Linux

#59

Post by flukus »

ridiculous_fish wrote: post #29

A lovely way to sort strings, especially strings that may have long shared prefixes, is a 3-way partition quicksort. This allows you to avoid walking the same prefix over and over the way that memcmp does. Pick your pivot element and partition the strings into based on the first character only. Note this differs from classic quicksort in that we're maintaining three regions, not two. Now recurse for all three regions…

Would reversing the strings or writing a custom comparer to compare in reverse be simpler and get to the more significant bits quicker? You could maybe even do the file extension comparison at a later point.

Re: Fast Directory Listing on Linux

#60

Post by jplayer01 »

O_H_E wrote: post #25
rasz wrote: post #13

Every directory has entries "." and "..", which we aren't interested in. We filter them out with a helper function Dots(). bool Dots(const char* s) { return s[0] == '.' && (!s[1] || (s[1] == '.' && !s[2])); } why would you iterate over every single file entry? both . .. entries will land at one end of sorted list anyway.

You forgot to quote/code block, and to add a second newline

I hope nobody ever uses code blocks. They're unreadable on mobile.
Post reply on HN