Live data from Hacker News

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

modulovalue.com

31–40 of 96 posts

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

#31
post #5

Earlier quoted context omitted.

> Zip with no compression is a nice contender for a container format that shouldn't be slept on SquashFS with zstd compression is used by various container runtimes, and is popular in HPC where filesystems often have high latency. It can be mounted natively or with FUSE, and the decompression overhead is not really felt.

Wouldn't you still have a lot of syscalls?

You then use io_uring

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

#32

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…

> 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.

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

#33
I still use a 10x faster lexer, RE2C over flex, because it does so much more at compile-time. And on top of that has a bunch of optimization options for better compilers, like computed goto's.

Of course syscalls suck, slurping the whole file at once always wins, and in this case all files at once.

Kernels suck in general. You don't really need one for high perf and low space.

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

#34

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…

Doesn’t ZIP have all the metadata at the end of the file, requiring some seeking still?

Yes, but it's an O(1) random access seek rather than O(n) scanning seek

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

#35
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?

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

in what way does scandir avoid stat syscalls?

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

#36
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?

You can probably do it with io_uring, as a generic syscall batching mechanism.

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

#37
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?

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?

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

#38
post #9

Same thing applies to other system aspects: compressing the kernel loads it faster on RAM even if it still has to execute the un compressing operation. Why? Load from disk to RAM is a larger bottleneck than CPU uncompressing. Same is applied to algorithms, always find the largest bottleneck in your dependent executions and apply changes there as the rest of the pipeline waits for it. Often picking the right algorithm…

Networks too. Compressing the response with gzip is usually faster than sending it uncompressed through the network. This wasn't always the case.

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

#39

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.

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

#40
post #35

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

in what way does scandir avoid stat syscalls?

Because you get an iterator over `struct dirent`, which includes `d_type` for popular filesystems.

Notice that this avoids `lstat` calls; for symlinks you may still need to do a stat call if you want to stat the target.

Post reply on HN