my emacs is completely fucked
Post
Replies:
15
the docs just called me out for my use of the term "path" right as i said that above!!!! bc the stuff emacs works on is largely concrete files as opposed to search paths (and in fact i totally agree with their distinction here)
this distinction is actually like the most interesting part of my directory traversal work: using file descriptors and inodes to confidently read and write and have a clear concept of progress and completion, instead of path strings which are fundamentally racy and cannot be deduplicated
@hipsterelectron so wait what is different in practice when you do that
@kirakira great question! there's a short answer and a long answer. the long answer is likely still beyond my ability to do it justice but it's kinda why i've been so focused on filesystems for so long.
so essentially the filesystem is where fucking everything happens all at once. the NASDAQ trading floor. people biking to work. kids walking to school in their outfits. it's new york, baby! it all happens here!
@kirakira it's been really fascinating to learn with build tools how that differs from the challenges of network and web browser engineering like servo. the biggest distinction there is that most async models are wildly inappropriate for local file i/o. there are larger discussions to have about why, but the close technical distinction here is that networking and servers are largely optimizing:
(1) interactions with many other entities they don't control
(2) with incredibly nondeterministic latency for every request
(1) interactions with many other entities they don't control
(2) with incredibly nondeterministic latency for every request
@kirakira so that's the reason why async works really well because it lets you timeshare your cycles when these unpredictable latencies finally occur. but the filesystem is different. you have some degree of control over it (but not much). but importantly, instead of web/http standards for things like caching artifacts (as i'm taking advantage of with pip), you generally have to handle a massive variety of complexity that has grown directly from all the different ideas people had about UNIX from bell labs. it's the C ABI baby!!!
but most importantly, you're often writing code that runs on your users' laptops and touches their files. that's a different degree of closeness and responsibility that you have to bear on top of figuring out all these situations that don't have protocols to provide easy answers.
@kirakira so the reason i started investigating this in the first place was because i thought it would be relatively plug and play. we used the rust
ignore crate in pants for almost two years before we amicably parted ways because pants needed more control over that traversal. this was supposed to be something i could contribute to @ethersync which like pants has to concern itself not just with a single filesystem crawl but also correctly maintaining state over time. this mutable state is where things get really dicey.
@kirakira so then i almost immediately found a deadlock in ripgrep https://github.com/BurntSushi/ripgrep/pull/3010 because it turns out recursive directory traversal is almost uniquely difficult to map to standard parallelism models.
the literally fractal complexity that results from every directory potentially having an entirely new set of entries is genuinely just very difficult to solve.
contrast to a problem space that can be solved: https://github.com/zip-rs/zip2/pull/236. zip files tell you up front what contents they have and you can plan and schedule your work around this. this ability to schedule "offline" is what the filesystem gives you, and it's something i haven't been able to translate to the async executor model vs one with explicit threading.
@kirakira in particular, the reason ripgrep had this occur (andrew gallant is great and i admire him a lot to be clear) is because when you traverse a directory recursively, you legitimately might want to return early, either from a subbranch (e.g. if it doesn't match your regex patterns, like the
ignore crate) or from the entire process. differentiating that from erroneous behavior is extremely difficult and i spent probably several days thinking about that PR before trying to solve it on my own.
@kirakira the reason i focused on (1) file descriptors and (2) inodes is because they (at least fds) represent some of the very few rigid contracts you can actually request from the filesystem (something @zwol has been pondering recently). i believe for example when working on the parallel zip implementation (which required expanding the rust libc wrapper) that POSIX does not guarantee the behavior of parallel write operations on the same file handle, but it does guarantee that parallel reads with
pread() will succeed.so while path strings are a really tempting way to reduce the problem to an abstraction, they can be and often are a complete lie. just yesterday i started getting errors in my shell because i'd unlinked the directory i was in, and even though i added the directory back later (so my shell was still displaying a valid path), the filesystem does not take IOUs like that >=[
@kirakira i think inodes are potentially a little overrated but i'm not sure about that yet and would need to talk to an expert more thoroughly. but one basic thing the
ignore crate (and ripgrep more generally) does that is clearly pessimal is not differentiating symlinks from other types of paths, so they traverse the same output twice. i suspect ripgrep keeps track of more persistent identifiers like inodes when it actually reads the files, but i think it's the wrong abstraction that leads to more than just deadlocking if you're relying on it for correctness like pants
@kirakira the specific thing i investigated to solve the deadlock from this recursive problem was (1) deduplicating posix paths (hence the path library which is production quality) (2) codifying directory streams as a resource you're blocking on--instead of kinda glossing that over with the work-stealing approach of ripgrep/
ignore.so this should still be plausible on windows too, but POSIX literally just standardized last year the posix_getdents() libc function call https://pubs.opengroup.org/onlinepubs/9799919799/functions/posix_getdents.html. and this is really fucking sick for a variety of reasons but mostly it codifies what everyone already agreed on and that is POSIX's job
@kirakira so there is a nontrivial direct performance improvement from this by simply doing like a million fewer syscalls for large directories: you provide a buffer and the os just keeps writing those entries until it runs out of space. i know in linux it literally implements the old
readdir() interface (one at a time) in terms ofgetdents() now. so it's not doing anything tricky and it's well aligned with the hardware.but the really "rusty" thing i was able to get from this was that instead of mixing all your directory workers together like ripgrep's thread pool (andrew gallant didn't actually write the deadlocking code there), you can explicitly assign workers to own specific memory regions which they employ for their own tasks (directory handles, file handles, and symlink handling). and i used Pin<...> a good amount which is a very confusing but very thoughtful interface that is also what rust uses for async primitives to ensure safety across threads etc
@kirakira i don't have good benchmarks yet and i don't actually like the API yet but this is the VFS interface with tons of intersecting traits that attempts to codify the relationships between filesystem entities https://codeberg.org/cosmicexplorer/deep-link/src/branch/main/d-major/src/vfs.rs
this is the path library that actually supports a robust binary representation and that the stdlib should have had in the first place https://codeberg.org/cosmicexplorer/deep-link/src/branch/main/d-major/pathing/src/lib.rs did you know std::path::Path objects with different string values will compare as equal? i think that's thoroughly unacceptable along with the way (as with this problem in general) you can't parse the Path into a representation that maintains the kind of performance or safety guarantees you want. you just have to keep asking it questions which is a lot of extra busywork at best.
@kirakira i don't think literally anyone else cares about this but i found this particular method API (along with the sneaky equality comparison) to be particularly indicative of path handling not aligning with how the rust language works https://doc.rust-lang.org/std/path/struct.Path.html#method.exists i don't think there is a single other method in the rust stdlib that doesn't return an
io::Result<...> to wrap an underlying syscall to the OS. i agree that the logic makes sense (and python's wonderful pathlib has this exact same Path.exists() method), but in fact the filesystem is partially an API and protocol problem that i think we can solve.and i consider the Path::exists() in the rust stdlib to be an abdication of what rust can help us all to solve collectively, so i'm very hopeful i can file an actual RFC later this year (still need help with windows though)
