Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Elfshaker: Version control system fine-tuned for binaries

github.com

Post reply on HN
Print view View original

61–70 of 115 posts

Re: Elfshaker: Version control system fine-tuned for binaries

#61

Post by peterwaller-arm »

zeotroph wrote: post #57
peterwaller-arm wrote: post #41

Earlier quoted context omitted.

Author here. The executables shipped in manyclangs are release builds! The catch is that manyclangs stores object files pre-link. Executables are materialized by relinking after they are extracted with elfshaker. The stored object files are compiled with -ffunction-sections and -fdata-sections, which ensures that insertions/deletions to the object file only have a local effect (they don't cause relative addresses to…

Thank you for the explanation, so the pre-link storage is one of the magical ingredients, maybe mention this as well in the README? Is this the reason why manyclang (using llvms cmake based build system) can be provided easily, but it would be more difficult for gcc? Or is the object -> binary dependency automatically deduced?

> maybe mention this as well in the README?

We've tweaked the readme, I hope it's clearer.

It would be great to provide this for gcc too. The project is new and we've just started out. I know less about gcc's build system and how hard it will be to apply these techniques there. It seems as though it should be possible though and I'd love to see it happen.

To infer the object->executable dependencies we currently read the compilation database and produce a stand-alone link.sh shell script, which gets packaged into each manyclangs snapshot.

Re: Elfshaker: Version control system fine-tuned for binaries

#63

Post by the_duke »

i_like_waiting wrote: post #26

Thanks, seems like that could be good solution for storing of daily backups of DB. I didn't know I needed it but seems like I do.

Borg, bup or restic are relatively popular incremental backup tools that reduplicate with chunking.

Re: Elfshaker: Version control system fine-tuned for binaries

#64

Post by derefr »

perth wrote: post #59
wlll wrote: post #2

Related, and impressive: https://github.com/elfshaker/manyclangs > manyclangs is a project enabling you to run any commit of clang within a few seconds, without having to build it. > It provides elfshaker pack files, each containing ~2000 builds of LLVM packed into ~100MiB. Running any particular build takes about 4s.

Reminds me of how Microsoft packages the Windows installer actually. If you’ve ever unpacked Microsoft’s install.esd it’s interestingly insane how heavily it’s compressed. I assume it’s full of a lot of stuff that provides semi redundant binaries for compatibility to a lot of different systems, because the unpacked esd container goes from a few GiBs to I think around 40-50 iirc.

The emulation community also has "ROMsets" — collections of game ROM images, where the ROM images for a given game title are all grouped together into an archive. So you'd have one archive for e.g. "every release, dump, and ROMhack of Super Mario Bros 1."

These ROM-set archives — especially when using more modern compression algorithms, like LZMA/7zip — end up about 1.1x the size of a single one of the contained game ROM images, despite sometimes containing literally hundreds of variant images.

Re: Elfshaker: Version control system fine-tuned for binaries

#65

Post by Tobu »

wlll wrote: post #2

Related, and impressive: https://github.com/elfshaker/manyclangs > manyclangs is a project enabling you to run any commit of clang within a few seconds, without having to build it. > It provides elfshaker pack files, each containing ~2000 builds of LLVM packed into ~100MiB. Running any particular build takes about 4s.

The clever idea that makes manyclangs compress well is to store object files before they are linked, with each function and each variable in its own elf section so that changes are mostly local; addresses will indirect through sections and a change to one item won't cascade into moving every address.

I'm not sure the linking step they provide is deterministic/hermetic, if it is that would prove a decent way to compress the final binaries while shaving most of the compilation time. Maybe the manyclangs repo could store hashes of the linked binaries if so?

I'm not seeing any particular tricks done in elfshaker itself to enable this, the packfile system orders objects by size as a heuristic for grouping similar objects together and compresses everything (using zstd and parallel streams for, well, parallelism). Sorting by size seems to be part of the Git heuristic for delta packing: https://git-scm.com/docs/pack-heuristics

I'd like to see a comparison with Git and others listed here (same unlinked clang artifacts, compare packing and access): https://github.com/elfshaker/elfshaker/discussions/58#discus...

Re: Elfshaker: Version control system fine-tuned for binaries

#66

Post by peterwaller-arm »

mrich wrote: post #56
peterwaller-arm wrote: post #41

Earlier quoted context omitted.

Author here. The executables shipped in manyclangs are release builds! The catch is that manyclangs stores object files pre-link. Executables are materialized by relinking after they are extracted with elfshaker. The stored object files are compiled with -ffunction-sections and -fdata-sections, which ensures that insertions/deletions to the object file only have a local effect (they don't cause relative addresses to…

Thanks. I had a use case in mind where LTO is enabled. Unfortunately the LTO step is quite expensive so relinking does not seem like a viable option. If I find some time I'll give it a try though.

ThinLTO can be pretty quick if you have enough cores, it might work. Not sure how well the LTO objects compress against each other when you have small changes to them. It might work reasonably.

manyclangs is optimized to provide you with a binary quickly. The binary is not necessarily itself optimized to be fast, because it's expected that a developer might want to access any version of it for the purposes of testing whether some input manifests a bug or has a particular codegen output. In that scenario, it's likely that the developer is able to reduce the size of the input such that the speed of the compiler itself is not terribly significant in the overall runtime. Therefore, I don't see LTO for manyclangs as such a significant win. But it is still hoped that the overall end-to-end runtime is good, and the binaries are optimized, just not with LTO.

Re: Elfshaker: Version control system fine-tuned for binaries

#67

Post by veselink1 »

cyounkins wrote: post #60

Cool! I wonder how this would compare to ZFS deduplication.

An author here. elfshaker uses per-file deduplication. When building manyclangs packs, we observed that the deduplicated content is about 10 GiB in size. After compression with `elfshaker pack`, that comes down to ~100 MiB.

There is also a usability difference: elfshaker stores data in pack files, which are more easily shareable. Each of the pack files released as part of manyclangs ~100 MiB and contains enough data to materialize ~2,000 builds of clang and LLVM.

Re: Elfshaker: Version control system fine-tuned for binaries

#68

Post by derefr »

peterwaller-arm wrote: post #27
johnyzee wrote: post #21

Earlier quoted context omitted.

As far as I was able to learn (don't remember the details, sorry), git does not do well with large binary files. I believe it ends up with a lot of duplication. It is the major thing I am missing from git, currently we store assets (like big PSDs that change often) outside of version control and it is suboptimal.

Performing poorly with non-textual data happens for a a number of reasons. Binary data, when changed, often have a lot of 'non-local' changes in them. For example, a PSD file might well have a compression algorithm already applied to it. An insertion/deletion is going to result in a very different compressed representation for which there is no good way to have an efficient delta. elfshaker will suffer the same probl…

One could, in theory, write a git-clean filter (like the one used for git-lfs), that teaches git various heuristic approaches to "take apart" well-known binary container formats into trees of binary object leaf-nodes.

Then, when you committed a large binary that git could understand, what git would really be committing in its place would be a directory tree — sort of like the "resource tree" you see if you edit an MKV file, PNG file, etc., but realized as files in directories. Git would generate it, then commit it.

On checkout, this process would happen in reverse: a matching git-smudge filter could notice a metadata file in each of these generated directories, and collapse the contents of the directory together to form a binary chunk; recursively, up the tree, until you hit the toplevel, and end up with the original large binary again.

Since most of the generated leaf-nodes from this process wouldn't change on each commit, this would eliminate most of the storage overhead of having many historical versions of large files in git. (In exchange for: 1. the potentially-huge CPU overhead of doing this "taking apart" of the file on every commit; 2. the added IOPS for temporarily creating the files to commit them; and 3. the loss of any file-level compression [though git itself compresses its packfiles, so that's a wash.])

I'm almost inspired to try this out for a simple binary tree format like https://en.wikipedia.org/wiki/Interchange_File_Format. But ELF wouldn't be too hard, either! (You could even go well past the "logical tree" of ELF by splitting the text section into objects per symbol, and ensuring the object code for each symbol is stored in a PIC representation in git, even if it isn't in the binary.)

Re: Elfshaker: Version control system fine-tuned for binaries

#69

Post by mdaniel »

ChrisMarshallNY wrote: post #33
johnyzee wrote: post #21

Earlier quoted context omitted.

As far as I was able to learn (don't remember the details, sorry), git does not do well with large binary files. I believe it ends up with a lot of duplication. It is the major thing I am missing from git, currently we store assets (like big PSDs that change often) outside of version control and it is suboptimal.

> we store assets (like big PSDs that change often) outside of version control and it is suboptimal. Perforce is still used by game developers and other creatives, because it handles large binaries, quite well. In fact, I'm not sure if they still do it, but one of the game engines (I think, maybe, Unreal) used to have a free tier that also included a free Perforce install.

It was my recollection, and I confirmed it, that they've almost always had a "the first hit is free" model for small teams, and they also explicitly call out indie game studios as getting free stuff too: https://www.perforce.com/how-buy

Re: Elfshaker: Version control system fine-tuned for binaries

#70

Post by necovek »

peterwaller-arm wrote: post #23
henvic wrote: post #13

Interesting. I wonder if this can also be [ab]used to, say, deliver deltas of programs, so that you can have faster updates, but maybe it doesn't make sense. https://en.wikipedia.org/wiki/Binary_delta_compression

Author here, I don't think it would apply well to that scenario. elfshaker is good for manyclangs where we ship 2,000 revisions in one file (pack), so the cost of individual revision is amortized. If one build of llvm+clang costs you some ~400 MiB; a single elfshaker pack containing 2,000 builds has an amortized cost of around 40kiB/build. But this amazing win is only happening because you are shipping 2,000 builds a…

How fast would it be to get a delta between any two of the 2,000 builds in a single elfshaker pack?

If that's reasonably fast, perhaps an approach like that could work: server stores the entire pack, but upon user request extracts a delta between user's version and target binary.

Still, the devil is in the details of building all revisions of all software a single distribution has.

Post reply on HN