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

71–80 of 96 posts

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

#71

Post by charcircuit »

zahlman wrote: post #46
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?)

Specifically the benefit is for the native libraries within the file as you can map the library directly to memory instead of having to make a decompressed copy and then mapping that copy to memory.

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

#72

Post by 1718627440 »

zahlman wrote: post #49
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…

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

I was talking about using zipfile as a generic file format, instead of open and close.

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

#73

Post by ncruces »

ori_b wrote: post #65
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.

Didn't test, but my guess is it's not “syscalls” but “open,” “stat,” etc; “read” would be fine. And something like “openat” might mitigate it.

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

#74

Post by nikanj »

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.

At the end of the ZIP file, there's a central directory of all files contained in that archive. Read the last block, seek to the block containing the file you want to access, done

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

#75

Post by zahlman »

1718627440 wrote: post #72
zahlman wrote: post #49

Earlier quoted context omitted.

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

I was talking about using zipfile as a generic file format, instead of open and close.

I'm afraid I don't understand specifically what you're referring to. Maybe you could show some code citations of popular projects doing it?

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

#76

Post by zahlman »

charcircuit wrote: post #71
zahlman wrote: post #46

Earlier quoted context omitted.

> 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?)

Specifically the benefit is for the native libraries within the file as you can map the library directly to memory instead of having to make a decompressed copy and then mapping that copy to memory.

Yes, that's clear. I'm just not aware of people actually doing that, or having done it back in the era when Java was more dominant.

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

#77

Post by hedora »

spwa4 wrote: post #61
0xbadcafebee wrote: post #60

Earlier quoted context omitted.

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…

I think Zip's main trick is that it's been preloaded on everything forever.

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

#78

Post by charcircuit »

zahlman wrote: post #76
charcircuit wrote: post #71

Earlier quoted context omitted.

Specifically the benefit is for the native libraries within the file as you can map the library directly to memory instead of having to make a decompressed copy and then mapping that copy to memory.

Yes, that's clear. I'm just not aware of people actually doing that, or having done it back in the era when Java was more dominant.

The bigger issue is that glibc doesn't support loading libraries from zip archives where bionic's linker ddoes. So on platforms where glibc is used you wouldn't see it being done.

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

#79

Post by paulddraper »

Joker_vD wrote: post #54
paulddraper wrote: post #47

Earlier quoted context omitted.

> 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'?

It’s a security thing, in conjunction with sudoers, I think.

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

#80

Post by 1vuio0pswjnm7 »

"TAR vs ZIP: Sequential vs Random Access"

https://199.233.217.201/pub/pkgsrc/distfiles/dictd-1.13.3.ta...

Wikipedia:

"In order to efficiently store dictionary data, dictzip, an extension to the gzip compression format (also the name of the utility), can be used to compress a .dict file. Dictzip compresses file in chunks and stores the chunk index in the gzip file header, thus allowing random access to the data."

Post reply on HN