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

61–70 of 96 posts

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

#61

Post by spwa4 »

0xbadcafebee wrote: post #60
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/

You mean ZIP?

Zip has 2 tricks: First, compression is per-file, allowing extraction of single files without decompressing anything else.

Second, the "directory" is at the end, not the beginning, and ends in the offset of the beginning of the directory. Meaning 2 disk seeks (matters even on SSDs) and you can show the user all files.

Then, you know exactly what bytes are what file and everything's fast. Second, you can easily take off the directory from the zip file, allowing new files to be added without modifying the rest of the file, which can be extended to allow for arbitrary modification of the contents, although you may need to "defragment" the file.

And I believe, encryption is also per-file. Meaning to decrypt a file you need both the password and the directory entry, which means that if you delete a file, and rewrite just the directory, the data is unrecoverable without requiring a total rewrite of the bytes.

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

#62

Post by __turbobrew__ »

stabbles wrote: post #5
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…

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

Just make sure you mount the squashfs with —direct-io or else you will be double caching (caching the sqfs pages, and caching the uncompressed files within the sqfs). I have no idea why this isn’t the default. Found this out the hard way.

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

#63

Post by dinosaurdynasty »

torginus wrote: post #51
king_geedorah wrote: post #48

Earlier quoted context omitted.

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)

That's mainly for historical reasons (select syscall can only handle fdshttps://0pointer.net/blog/file-descriptor-limits.html

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

#64

Post by sheepscreek »

Always knew this anecdotally - through experience - told myself it’s the file system block size that’s the culprit. Put together with SSD random seek times, it makes sense on the surface. I never thought of syscalls being so expensive. But they might just be symptom and not the bottleneck itself (after all it’s just a function call to the server). My initial thought was DMA. You see, CPUs usually have direct access to only one PCI/e in most consumer hardware. The other PCI/e and mvme.2 slots share the same bandwidth and take turns. When someone wants access, they do a dance with the CPU and other parts of the computer using INT or (or interrupt) instructions that make the CPU pause so I/O can take over for a bit. The switching back and forth is costly too and adds up quickly.

That said, it wouldn’t explain why a MacBook (which should have the SSD already on the fastest/dedicated pathway) be this slow unless something else in the OS was the bottleneck?

I think we’re just scratching the surface here and there is more to this story that is waiting to be discovered. But yeah, to get the job done, package it in fewer files for the OS, preload into RAM or use mmap, then profit.

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

#65

Post by ori_b »

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?

It's not the syscalls. There were only 300,000 syscalls made. Entering and exiting the kernel takes 150 cycles on my (rather beefy) Ryzen machine, or about 50ns per call.

Even assume it takes 1us per mode switch, which would be insane, you'd be looking at 0.3s out of the 17s for syscall overhead.

It's not obvious to me where the overhead is, but random seeks are still expensive, even on SSDs.

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

#67

Post by hwspeed »

Classic case of optimizing the wrong thing. I've hit similar issues with ML training pipelines where GPU utilization looks terrible because data loading is the bottleneck. The profiler tells you the GPU kernel is fast, but doesn't show you it's sitting idle 80% of the time waiting for the next batch. Amdahl's law is brutal when you've got a serial component in your pipeline.

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

#68

Post by torginus »

I started programming on DOS - I remember how amazing was that you basically almost talked to hardware directly, there was very little restriction on what you could do, and the OS (which imo was much more akin to a set of libraries) provided very little abstraction for you.

Then I moved to Windows, and Linux. Each had its own idiosyncrasies, like how everything is a file on Linux, and you're supposed to write programs by chaining existing executables together, or on the desktop, both Win32 and X11 started out with their own versions of UI elements, so XWindow or Win32 would know about where a 'button' was, and the OS was responsible for event handling and drawing stuff.

Eventually both Windows and Linux programs moved to a model where the OS just gave you the window as a drawing surface, and you were supposed to fill it.

Similarly, all other OS supplied abstractions slowly fell out of use beyond the bare minimum.

Considering this, I wonder if it's time to design a new, much lower level abstraction, for file systems in this case, this would be a way to mmap an entire directory into the process space, where each file would be a struct, whicha had a list of pointers for the pages on the disk, and each directory would be a list of such entries, again stored in some data structure you could access, synchronizing reads/writes would be orechestrated by the kernel somehow (I'm thinking locking/unlocking pages being written to).

So that way there'd be no difference between traversing an in-memory data structure and reading the disk.

I know this approach isnt super compatible with the async/await style of I/O, however I'm not 100% convinced that's the correct approach either (disk paging is a fundamental feature of all OSes, yet is absolutely inexpressible in programming terms)

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

#69

Post by thaumasiotes »

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 effectively reduces the I/O, while unlike TAR, allowing direct random to the files without "extracting" them or seeking through the entire file

How do you access a particular file without seeking through the entire file? You can't know where anything is without first seeking through the whole file.

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

#70

Post by charcircuit »

thaumasiotes wrote: post #69
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 effectively reduces the I/O, while unlike TAR, allowing direct random to the files without "extracting" them or seeking through the entire file How do you access a particular file without seeking through the entire file? You can't know where anything is without first seeking through the whole file.

You look at the end of the file which tells you where the central directory is. The directory tells you where individual files are.
Post reply on HN