One Small, Arbitrary Change and It's a Whole New World

http://prog21.dadgum.com/147.html

by prajjwal • 14 years ago

47 11 14 years ago

prog21.dadgum.com

greggman2• 14 years ago

Only tangentially related but the ZIP file format is designed with floppy disks in mind. A ZIP file puts its table of contents at the end of the file. The point of this design was that if you had a slow floppy and wanted to add some files to zip file you could read the old table of contents, append some new files and write a new table of contents. Therefore you didn't have to re-write the entire file. Of course you might have some wasted space because you've got 2 tables of contents and might even have some older versions of files earlier in the zip file. That was a trade off though. Re-writing an entire floppy (or 10) was prohibitively slow.

Unfortunately that makes zip files whole unsuited to streaming because according to the official standard you MUST read the table of contents at the end of the file to know which parts of the file correspond to the correct contents. Steaming the file and looking for headers is an invalid way to parse a zip file.

A large number of engineers are unaware of this fact and sadly keep choosing zip for standards that would be better off with a format that can be streamed. (tar/gz can be streamed). Examples: Chrome's extension format. The W3Cs Widget format. I'm sure there are several others.

rarrrrrr2• 14 years ago

Indeed. This is one of my favorite idioms for untarring a remote file locally:

  ssh remote_host cat archive.tar.gz | pv | tar zx

Unless the contents are very large, that's almost always faster than rsyncing the remote directory locally, because both ends just stream. No coordinated start and stop for each little file.

There is one big advantage of the zip file format: you can extract a single member without having to read the whole archive. It's usually just two seeks: seek to end, read TOC; seek to position, read member.

rogerbinns• 14 years ago

This is also the reason the self extractors are so easy. A zip file doesn't care what is at the beginning of the file so you can prepend anything you want.

Note that streaming is pointless for the examples you give. You definitely want the content signed and integrity checked, and you can't do that until the whole thing is downloaded. If you did decide to start extracting before you have the whole thing then you'd need to ensure no race conditions or avenues of attack from malicious payloads.

On a related tale, back when I worked on WAN optimizers I looked at Windows Explorer showing the contents of a zip file (folder view). Writing SMB/CIFS requests by hand it was possible to do so using 5 requests (which means 5 round trips). Explorer in Windows XP used 1,500 requests and Explorer in Vista used 3,000!

saurik2• 14 years ago

(edit: I just noticed that rarrrrrr made the same argument in his comment, which I totally believe I did not have locally before leaving my response. Regardless, I went into more depth and provided a few related issues, so I don't feel my comment is sufficiently repetitive to delete.)

While tar.gz can be streamed, if you happen to have the entire zip file already and want to extract a single item from it, you are screwed: you actually must scan through the entire file; this is both because gzip is not random access and because tar files have no index at all, they just concatenate files.

This reason is actually insidious, because it also means that zip files are much more efficient containers if you need to be able to "browse into them", such as with a GUI. This means that they tend to be much better supported ("better" assuming .tar.gz files are supported at all) by graphical file managers.

In comparison, the fact that you can't stream download and decompress the tar.gz on the fly is actually largely irrelevant: you aren't going to be using the Chrome extension until you've downloaded the entire package anyway; and for some file formats (Java jar files, for example) you don't intend to decompress the entire contents anyway.

Ironically, the reason tar files are designed this way, is actually due to yet another ancient piece of storage technology: the tape drive. The name "tar" stands for "tape archive", and is a modified version of the file format used for "ar" that is better suited to tape drives, which were much slower than floppies if you needed to rewrite earlier content (if rewriting was possible at all, which I don't think it was on all tapes).

greggman2• 14 years ago

Streaming is not unimportant for the examples I gave. Both are 1 step away from being replacements for flash apps. They are basically a webpage with all assets bundled together making them easy to distribute. Except, because a non-streamable format was chosen they can't make the leap to full flash replacements.

Even as an extensions or widget, the fact that I can't stream them means I have to wait for them to download entirely before they can be used. I can certainly imagine a Chrome app (game) > 500meg that would be awesome if I could start interacting with as soon as 1-20 meg had been downloaded. That use case though was made harder because a non streamable format was chosen. Instead the app has to download some small boot loader and the manually stream the rest of its assets. With a little more foresight that could have been solved directly by the format chosen.

As for tar/gz not being random access. There's nothing preventing implementations from caching locations as the file is downloaded or inserting a file as part of the tar that lists the locations.

rarrrrrr2• 14 years ago

Casual disk writes like the ones mentioned in the article rarely effect overall performance, because the operating system doesn't actually do them right now. They're buffered by the OS and happen behind the scenes whenever the disk is free. If you profile a complex program that uses much disk IO, rarely will you find that write calls are hot.

Rather, it's usually reads (and consequently seeks) that matter.

The exception to this is when you're wanting to fsync or fdatasync on every write.

Similarly, the situation of writing an entire new file when you only need to append a few lines to the end may sometimes be desirable, depending on how often that file is read. If it's a fairly short file that's read more frequently than written, it's often better to just write out the whole new file without fragmentation, rather that appending to the end.

gwern• 14 years ago

> They're buffered by the OS and happen behind the scenes whenever the disk is free.

I don't think you're cooperating with the thought experiment here. Yes, buffering will help a lot, but buffering doesn't conjure up capacity that doesn't exist. If you need to write a megabyte and your throughput is just 5kb/sec, then buffering isn't going to make a whole lot of difference: you'll need to use up a full 2000 seconds of throughput at some point. If your written logs and files over a day average out to be more than 5kb/sec, you're still in for a world of pain no matter how nicely your buffering smooths out the load.

Evbn• 14 years ago

You have to consider relative scale. If you have 5mb of log data, and you have 1000mb of app data that triggered that log data, the logging isn't your problem.

nkurz• 14 years ago

Rarrrrrr may not be cooperative, but I think he's right.

Sure, if you actually need to write a giant file, beyond a certain point buffering isn't going to help you. But two of the three examples in the text are rapidly rewriting short history files and avoiding intermediate files that will immediately be deleted. In both of these cases, the VM system of a modern operating system completely solves the problem.

The third example is logging, which feels more like a question of defaults. He's probably right, and a lot of logged messages are never used, but this is a matter of configuring syslog rather than changing the way we think about disk IO. Removing the ability to turn on debug messages doesn't feel like a good optimization.

The overall thought exercise is good, but I think it's misguided. I think the real frontier is optimizing access to RAM: RAM is the new disk. Assume every TLB miss costs a second: how would you lay out your data differently? If (as is approximately the case) access to main memory is 100x as expensive as fetching from L1, do you really want to be using a linked list?

Or one that I'd love to have a good solution to: given the flexibility of the mapping between virtual memory and physical memory, why is there no good way to insert a 4K page at the head or in the middle of a multi-megabyte (virtually) contiguous array?

http://stackoverflow.com/questions/11621606/faster-way-to-mo...

gumdad• 14 years ago

In the article he asks why does less need a history file. Who says it does? It's an option. It can be disabled turned off. The question of why it's on by default is another matter.

Manpage extract:

LESSHISTFILE

Name of the history file used to remember search commands and shell commands between invocations of less. If set to "-" or "/dev/null", a history file is not used. The default is "$HOME/.lesshst" on Unix systems, "$HOME/_lesshst" on DOS and Windows systems, or "$HOME/lesshst.ini" or "$INIT/lesshst.ini" on OS/2 systems.

Then the author complains about applications that write too much to disk. He has my sympathies.

Has he ever heard of a ramdisk? mfs? tmpfs?

This is the easy solution to the problem of braindead applications writing needlessly to disk.

The simple rule is: If you don't want disk writes then don't use the disk. Mount your directories in RAM. Is this perfect solution with zero overhead? No. Is the cost very small? Is is exponentially faster than using the HDD? Try it and answer these questions for yourself.

There are also the countless bloggers who write about installing an OS to a USB stick or SD card. They usually mention the issue of disk writes and how this impacts flash memory, but they almost always proceed to instruct their readers to "untar" several thousand files in the course of an install anyway. This is not very helpful.

Did it ever occur to them that they could make an image of a filesystem and transfer that to the media - requiring only a single write? Can you mount root read-only and other dirs like /var and /etc read-write? Yes, of course.

How do tech support people in corporations deploy countless Windows installations? They use imaging. It is not rocket science.

One commenter says you can't extract a single member from a tarball without reading the entire file. What version of tar is he using?

Manpage extract:

-q, --fast-read

Select the first archive member that matches each pattern operand. No more than one archive member is matched for each pattern. When members of type directory are matched, the file hierarchy rooted at that directory is also matched.

This means the entire archive is not read, unless the member to be extracted is at the very end. Similar to sed /pattern/q or grep -m1 pattern.

Anyway pax is better than tar.

Another commenter claims you cannot "stream download and decompress" tar.gz files "on-the-fly". What exactly does that mean?

What if you do this: (BSD/OSX only; Linux ftp is not the same)

ftp -o"|gzip -dc" http://host.tld/file.tar.gz

Or this

{ echo GET /file.tar.gz HTTP/1.0 ;echo ;} |nc -vv http://host.tld 80 | gzip -dc

Then try the same with a .zip file and using unzip -c instead of gzip -d -c

One Small, Arbitrary Change and It's a Whole New World

Related Stories