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

21–30 of 75 posts

Re: Fast Directory Listing on Linux

#21

Post by oralty »

JoshTriplett wrote: post #18
oralty wrote: post #14

Earlier quoted context omitted.

I mean, I think that was a bit of a joke. It's ironic that you rail against this dude for "code that's hard to understand" in reply to a long-form prose article about understanding the code and how it got there.. We'll probably have to agree to disagree.. but that blog post doesn't really resonate for me... especially the end where it talks about keep it to your "own language." I've never had patience for identity po…

> It's ironic that you rail against this dude for "code that's hard to understand" I'm sure that it was a joke, and that doesn't make it better. I'm not suggesting that this code was hard to understand, and I enjoyed the article. I'm calling out this particular point, and suggesting that even as a joke, mocking "frontend developers" is very much from the same territory that promotes "Real Programming" and mocks peopl…

I mean it is pretty true that most frontend developers do not have the inclination to go trodding into a C++ code base making syscalls without a wrapper. Even taken uncharitably seriously, that is all the comment was insinuating. Everything else is added by you the reader.

And anyway I'm fine with exclusively frontend devs staying out of systems stuff. Anyone that wants to read OS kernel and compiler source code has tons of choices. Most I've talked to find it dry and boring. They don't belong there... that's fine.

Re: Fast Directory Listing on Linux

#22

Post by floatboth »

elteto wrote: post #20
JoshTriplett wrote: post #12

> As an added bonus, those casts will fend off the occasional frontend developer who accidentally wanders into the codebase. https://blog.aurynn.com/2015/12/16-contempt-culture Code that intentionally celebrates its unapproachability is not a badge of honor or pride, even as a joke. It might occasionally be an unavoidable necessity, in which case it needs enough documentation that the next person who has to deal with…

That was clearly tongue-in-cheek. No need to rail against the author. Lay down the outrage pitchforks man.

Where are the outrage pitchforks? The comment was extremely calm. Why is any mild, polite criticism or disagreement perceived as "railing against the author"??

Re: Fast Directory Listing on Linux

#23

Post by [deleted] »

oralty wrote: post #21
JoshTriplett wrote: post #18

Earlier quoted context omitted.

> It's ironic that you rail against this dude for "code that's hard to understand" I'm sure that it was a joke, and that doesn't make it better. I'm not suggesting that this code was hard to understand, and I enjoyed the article. I'm calling out this particular point, and suggesting that even as a joke, mocking "frontend developers" is very much from the same territory that promotes "Real Programming" and mocks peopl…

I mean it is pretty true that most frontend developers do not have the inclination to go trodding into a C++ code base making syscalls without a wrapper. Even taken uncharitably seriously, that is all the comment was insinuating. Everything else is added by you the reader. And anyway I'm fine with exclusively frontend devs staying out of systems stuff. Anyone that wants to read OS kernel and compiler source code has…

[deleted]

Re: Fast Directory Listing on Linux

#24

Post by CoolGuySteve »

JoshTriplett wrote: post #12

> As an added bonus, those casts will fend off the occasional frontend developer who accidentally wanders into the codebase. https://blog.aurynn.com/2015/12/16-contempt-culture Code that intentionally celebrates its unapproachability is not a badge of honor or pride, even as a joke. It might occasionally be an unavoidable necessity, in which case it needs enough documentation that the next person who has to deal with…

This comment is off topic and trying to bait an argument off of a single throwaway line in the article.

Re: Fast Directory Listing on Linux

#25

Post by O_H_E »

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

Re: Fast Directory Listing on Linux

#26

Post by rasz »

romka2 wrote: post #17
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.

"." and ".." are filtered out before sorting. Sorting is O(N^2) in the common case (when there are fewer than 65 files in a directory), so it pays off to reduce the number of entries by 2 before we get there.

n log n? and arent . .. entries always at the beginning of the list? could just skip first 2 elements (or stop comparing after filtering . ..). What about scandir?

Re: Fast Directory Listing on Linux

#27

Post by jwilk »

rasz wrote: post #26
romka2 wrote: post #17

Earlier quoted context omitted.

"." and ".." are filtered out before sorting. Sorting is O(N^2) in the common case (when there are fewer than 65 files in a directory), so it pays off to reduce the number of entries by 2 before we get there.

n log n? and arent . .. entries always at the beginning of the list? could just skip first 2 elements (or stop comparing after filtering . ..). What about scandir?

> n log n?

From the article: Digging into the source code of std::sort() we can see that it uses Insertion Sort for short collections. Our 32-element vector falls under the threshold. Insertion Sort makes O(N^2) comparisons

> arent . .. entries always at the beginning of the list?

No.

Re: Fast Directory Listing on Linux

#28

Post by masklinn »

thwd wrote: post #4

But why? Why create a tool that does `git status` 10x faster?

Because you might want to display an up-to-date status permanently in a UI of some sort (e.g. an IDE or editor status bar or a shell prompt — the latter seems to be the use case here), and on big repositories it can be noticeable. Takes 150ms on the rust repository on my machine, with warm cache, that's a serious stutter when it runs on every shell prompt.

The tool's page specifically quotes Chromium which takes ~300ms to status on the author's system.

Re: Fast Directory Listing on Linux

#29

Post by ridiculous_fish »

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, except for the = region you look at the second character only. etc.

It's probably a loss for filenames which tend to be short, but for long strings this is a very easy to implement speedup. There's lots more optimizations possible with this technique, e.g. counting-sort style bucketing.

Re: Fast Directory Listing on Linux

#30

Post by tedunangst »

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.

Assuming that, branch predictor should make that check close to free. But the code still works even when that assumption is violated.
Post reply on HN