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

I built a 2x faster lexer, then discovered I/O was the real bottleneck

modulovalue.com

Post reply on HN
Print view View original

41–50 of 96 posts

Re: I built a 2x faster lexer, then discovered I/O was the real bottleneck

#41

Post by nh2 »

1718627440 wrote: post #8
marginalia_nu wrote: post #2

Zip with no compression is a nice contender for a container format that shouldn't be slept on. It effectively reduces the I/O, while unlike TAR, allowing direct random to the files without "extracting" them or seeking through the entire file, this is possible even via mmap, over HTTP range queries, etc. You can still get the compression benefits by serving files with Content-Encoding: gzip or whatever. Though it has…

Isn't this what is already common in the Python community? > I don't want to unpack an archive and have to scrutinize it for files with o+rxst permissions, or have their creation date be anything other than when I unpacked them. I'm the opposite, when I pack and unpack something, I want the files to be identical including attributes. Why should I throw away all the timestamps, just because the file were temporarily i…

There is some confusion here.

ZIP retains timestamps. This makes sense because timestamps are a global concept. Consider them a attribute dependent on only the file in ZIP, similar to the file's name.

Owners and permissions are dependent also on the computer the files are stored on. User "john" might have a different user ID on another computer, or not exist there at all, or be a different John. So there isn't one obvious way to handle this, while there is with timestamps. Archiving tools will have to pick a particular way of handling it, so you need to pick the tool that implements the specific way you want.

Re: I built a 2x faster lexer, then discovered I/O was the real bottleneck

#42

Post by stabbles »

direwolf20 wrote: post #37
stabbles wrote: post #20

Earlier quoted context omitted.

What comes closest is scandir [1], which gives you an iterator of direntries, and can be used to avoid lstat syscalls for each file. Otherwise you can open a dir and pass its fd to openat together with a relative path to a file, to reduce the kernel overhead of resolving absolute paths for each file. [1] https://man7.org/linux/man-pages/man3/scandir.3.html

This is a (3) man page which means it's not a syscall. Have you checked it doesn't call lstat on each file?

Fair, https://www.man7.org/linux/man-pages/man2/getdents64.2.html is a better link. You'd have to call lstat when d_type is DT_UNKNOWN

Re: I built a 2x faster lexer, then discovered I/O was the real bottleneck

#43

Post by st_goliath »

01HNNWZ0MV43FF wrote: post #39
marginalia_nu wrote: post #2

Zip with no compression is a nice contender for a container format that shouldn't be slept on. It effectively reduces the I/O, while unlike TAR, allowing direct random to the files without "extracting" them or seeking through the entire file, this is possible even via mmap, over HTTP range queries, etc. You can still get the compression benefits by serving files with Content-Encoding: gzip or whatever. Though it has…

I thought Tar had an extension to add an index, but I can't find it in the Wikipedia article. Maybe I dreamt it.

You might be thinking of ar, the classic Unix ARchive that is used for static libraries?

The format used by `ar` is a quite simple, somewhat like tar, with files glued together, a short header in between and no index.

Early Unix eventually introduced a program called `ranlib` that generates and appends and index for libraries (also containing extracted symbols) to speed up linking. The index is simply embedded as a file with a special name.

The GNU version of `ar` as well as some later Unix descendants support doing that directly instead.

Re: I built a 2x faster lexer, then discovered I/O was the real bottleneck

#44

Post by ralferoo »

rcxdude wrote: post #32
password4321 wrote: post #19

Earlier quoted context omitted.

> Why should I throw away all the timestamps, just because the file were temporarily in an archive? In case anyone is unaware, you don't have to throw away all the timestamps when using "zip with no compression". The metadata for each zipped file includes one timestamp (originally rounded to even number of seconds in local time). I am a big last modified timestamp fan and am often discouraged that scp, git, and even…

git updates timestamps in part by necessity of compatibility with build systems. If it applied the timestamp of when the file was last modified on checkout then most build systems would break if you checked out an older commit.

git blame is more useful than the file timestamp in any case.

Re: I built a 2x faster lexer, then discovered I/O was the real bottleneck

#45

Post by pwg »

nh2 wrote: post #41
1718627440 wrote: post #8

Earlier quoted context omitted.

Isn't this what is already common in the Python community? > I don't want to unpack an archive and have to scrutinize it for files with o+rxst permissions, or have their creation date be anything other than when I unpacked them. I'm the opposite, when I pack and unpack something, I want the files to be identical including attributes. Why should I throw away all the timestamps, just because the file were temporarily i…

There is some confusion here. ZIP retains timestamps. This makes sense because timestamps are a global concept. Consider them a attribute dependent on only the file in ZIP, similar to the file's name. Owners and permissions are dependent also on the computer the files are stored on. User "john" might have a different user ID on another computer, or not exist there at all, or be a different John. So there isn't one ob…

> ZIP retains timestamps.

It does, but unless the 'zip' archive creator being used makes use of the extensions for high resolution timestamps, the basic ZIP format retains only old MSDOS style timestamps (rounded to the closed two seconds). So one may lose some precision in ones timestamps when passing files through a zip archive.

Re: I built a 2x faster lexer, then discovered I/O was the real bottleneck

#46

Post by zahlman »

marginalia_nu wrote: post #2

Zip with no compression is a nice contender for a container format that shouldn't be slept on. It effectively reduces the I/O, while unlike TAR, allowing direct random to the files without "extracting" them or seeking through the entire file, this is possible even via mmap, over HTTP range queries, etc. You can still get the compression benefits by serving files with Content-Encoding: gzip or whatever. Though it has…

> It's pretty widely used, though often dressed up as something else. JAR files or APK files or whatever.

JAR files generally do/did use compression, though. I imagine you could forgo it, but I didn't see it being done. (But maybe that was specific to the J2ME world where it was more necessary?)

Re: I built a 2x faster lexer, then discovered I/O was the real bottleneck

#47

Post by paulddraper »

marginalia_nu wrote: post #2

Zip with no compression is a nice contender for a container format that shouldn't be slept on. It effectively reduces the I/O, while unlike TAR, allowing direct random to the files without "extracting" them or seeking through the entire file, this is possible even via mmap, over HTTP range queries, etc. You can still get the compression benefits by serving files with Content-Encoding: gzip or whatever. Though it has…

> I wouldn't expect this to be something that transfers between machines

Maybe non-UNIX machines I suppose.

But I 100% need executable files to be executable.

Re: I built a 2x faster lexer, then discovered I/O was the real bottleneck

#48

Post by king_geedorah »

solatic wrote: post #11

Headline is wrong. I/O wasn't the bottleneck, syscalls were the bottleneck. Stupid question: why can't we get a syscall to load an entire directory into an array of file descriptors (minus an array of paths to ignore), instead of calling open() on every individual file in that directory? Seems like the simplest solution, no?

io_uring supports submitting openat requests, which sounds like what you want. Open the dirfd, extract all the names via readdir and then submit openat SQEs all at once. Admittedly I have not used the io uring api myself so I can't speak to edge cases in doing so, but it's "on the happy path" as it were.

https://man7.org/linux/man-pages/man3/io_uring_prep_open.3.h...

https://man7.org/linux/man-pages/man2/readdir.2.html

Note that the prep open man page is a (3) page. You could of course construct the SQEs yourself.

Re: I built a 2x faster lexer, then discovered I/O was the real bottleneck

#49

Post by zahlman »

1718627440 wrote: post #8
marginalia_nu wrote: post #2

Zip with no compression is a nice contender for a container format that shouldn't be slept on. It effectively reduces the I/O, while unlike TAR, allowing direct random to the files without "extracting" them or seeking through the entire file, this is possible even via mmap, over HTTP range queries, etc. You can still get the compression benefits by serving files with Content-Encoding: gzip or whatever. Though it has…

Isn't this what is already common in the Python community? > I don't want to unpack an archive and have to scrutinize it for files with o+rxst permissions, or have their creation date be anything other than when I unpacked them. I'm the opposite, when I pack and unpack something, I want the files to be identical including attributes. Why should I throw away all the timestamps, just because the file were temporarily i…

> Isn't this what is already common in the Python community?

I'm not aware of standards language mandating it, but build tools generally do compress wheels and sdists.

If you're thinking of zipapps, those are not actually common.

Re: I built a 2x faster lexer, then discovered I/O was the real bottleneck

#50

Post by paulddraper »

solatic wrote: post #11

Headline is wrong. I/O wasn't the bottleneck, syscalls were the bottleneck. Stupid question: why can't we get a syscall to load an entire directory into an array of file descriptors (minus an array of paths to ignore), instead of calling open() on every individual file in that directory? Seems like the simplest solution, no?

io_uring can open multiple files.
Post reply on HN