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

51–60 of 96 posts

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

#51

Post by torginus »

king_geedorah wrote: post #48
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.ht…

You have a limit of 1k simultaneous open files per process - not sure what overhead exists in the kernel that made them impose this, but I guess it exists for a reason. You might run into trouble if you open too many files at ones (either the kernel kills your process, or you run into some internal kernel bottleneck that makes the whole endeavor not so worthwhile)

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

#52

Post by marginalia_nu »

LtdJorge wrote: post #30
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…

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

It has an index at the end of the file, yeah, but once you've read that bit, you learn where the contents are located and if compression is disabled, you can e.g. memory map them.

With tar you need to scan the entire file start-to-finish before you know where the data is located, as it's literally a tape archiving format, designed for a storage medium with no random access reads.

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

#53

Post by marginalia_nu »

paulddraper wrote: post #47
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.

Do you also want the setuid bit I added?

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

#54

Post by Joker_vD »

paulddraper wrote: post #47
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.

Honestly, sometimes I just want to mark all files on a Linux system as executable and see what would even break and why. Seriously, why is there a whole bit for something that's essentially an 'read permission, but you can also directly execute it from the shell'?

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

#55

Post by cb321 »

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.

Besides `ar` as a sibiling observed, you might also be thinking of pixz - https://github.com/vasi/pixz , but really any archive format (cpio, etc.) can, in principle, just put a stake in the ground to have its last file be any kind of binary / whatever index file directory like Zip. Or it could hog a special name like .__META_INF__ instead.

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

#56

Post by hinkley »

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…

Gzip will make most line protocols efficient enough that you can do away with needing to write a cryptic one that will just end up being friction every time someone has to triage a production issue. Zstd will do even better.

The real one-two punch is make your parser faster and then spend the CPU cycles on better compression.

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

#57

Post by [deleted] »

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?

[deleted]

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

#58

Post by cb321 »

hinkley wrote: post #56
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…

Gzip will make most line protocols efficient enough that you can do away with needing to write a cryptic one that will just end up being friction every time someone has to triage a production issue. Zstd will do even better. The real one-two punch is make your parser faster and then spend the CPU cycles on better compression.

DNA researchers developed a parallel format for gzip they call "bgzip" ( https://learngenomics.dev/docs/genomic-file-formats/compress... ) that makes data seem less trapped behind a decompression perf wall. Zstd is still a bit faster (but https://forum.nim-lang.org/t/5103#32269)

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

#59

Post by smallstepforman »

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…

This is how Haiku packages are managed, from the outside its a single zstd file, internally all dependacies and files and included in read only file. Reduces IO, reduces file clutter, instant install/uninstall, zero chance for user to corrupt files or dependancy, and easy to switch between versions. The Haiku file system also supports virtual dir mapping so the stubborn Linux port thinks its talking to /usr/local/lib, but in reality its part of the zstd file in /system/packages.

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

#60

Post by 0xbadcafebee »

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…

Strangely enough, there is a tool out there that gives Zip-like functionality while preserving Tar metadata functionality, that nobody uses. It even has extra archiving functions like binary deltas. dar (Disk ARchive) http://dar.linux.free.fr/
Post reply on HN