Golang implementation of Bentley/McIlroy compression
github.com
github.com
Original paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11....
RFC: http://tools.ietf.org/html/rfc3284
John Graham-Cumming's amusing blog post applying the algorithm to everyone's favorite Rick Astley song: http://blog.jgc.org/2012/06/compression-of-lyrics-of-never-g...
One thing I've been using Github for is keeping an archive of all the talks I've given and related code and data: https://github.com/cloudflare/jgc-talks
https://github.com/cloudflare/bm/blob/master/src/bm/bm.go#L4...
-- comment block should start with Dictionary.
https://github.com/cloudflare/bm/blob/master/src/bm/bm.go#L5...
-- comment should precede the declaration.
https://github.com/cloudflare/bm/blob/master/src/bm/bm.go#L6... and others
-- spurious newlines
https://github.com/cloudflare/bm/blob/master/src/bm/bm.go#L7...
-- needless named return parameters
https://github.com/cloudflare/bm/blob/master/src/bm/bm.go#L1...
https://github.com/cloudflare/bm/blob/master/src/bm/bm.go#L1...
https://github.com/cloudflare/bm/blob/master/src/bm/bm.go#L2...
(many others)
-- prefer early return or continue over if/else
https://github.com/cloudflare/bm/blob/master/src/bm/bm.go#L1...
-- more boilerplate due to the needless decision to use named return params
It's far more convenient looking at the function deceleration and knowing what comes and goes instead of hunting for return statements.
There are times they can be redundant (Sum(ints) does not need its return value named), or make the code less clear, or they indicate that you're trying to work around having overcomplicated methods by documenting them--I'm not saying always use them. But I don't try to avoid them.
Brad Fitzpatrick doesn't use it for Camlistore, instead he also does a Makefile-like system: https://github.com/bradfitz/camlistore
The sooner they deprecate the use of "go get", the better.
Is this the approach you recommend? I’ve never built a large go project, so I’m eager to learn what the best practices are.
Also, GP is conflating the issues of (1) fetching dependencies, (2) building a project, (3) installing the project. Makefiles aren't inherently evidence against "go get"; there is no reason that "go get" couldn't call "make" instead of "go build" (which it does).
The main reason that (almost) no pure Go projects have Makefiles anymore[0] is because they're frankly not needed. The standard Go build tools[1] are more than sufficient.
Don't take my word for it, though. Hop on #go-nuts on freenode and ask the guys there (many of whom are core contributors) what they think of Makefiles. They'll tell you the same thing that they told me over a year ago when I tried to advocate the use of Makefiles in pure Go projects.
[0] For what it's worth, before Go 1.0 came out, projects had Makefiles. The fact that Makefiles were a part of the standard build process and later removed should be a hint as to what the idiomatic Go approach is considered to be.
[1] "go get" isn't exactly a build tool in this sense; it's a convenience wrapper for cloning using git/hg/etc., followed by "go build" and "go install"
Go get conflates those issues. It fetches dependencies, builds the project, and installs it.
You don't need Makefiles, you're right. You need a script that sets GOPATH and calls "go build".
The most important thing is to not depend on the whims of somebody else's repository. In the best case, they'll push an update and break your code for a while. In the worst case, they'll delete their repo; then you get to find your local copy, push it to github, and change all your source files to point to that.
Heaven help you if other people want to fork your project. Say I wrote "github.com/jff/bigproject", which depends on my package "github.com/jff/mypackage". Now, if Joe wants to fork the package and make a tweak, he also has to fork the main project and change all of its imports to point to github.com/joe/mypackage so he can compile and test it. Of course he can't very well push that, he'll have to revert the import changes again assuming I accept his pull request for mypackage. I've dealt with this in real practice when we had 3 people working on a project which imported 3 other packages. We were forever dealing with build failures and changed import paths and of course could hardly do a pull from one fork to another. It was hell.
Better to distribute the entire workspace, with src/ containing all the packages you need and nothing else.
No. :|
(As pointed out elsewhere, there are style issues, but the lack of installability prevents me from even playing around with it).
EDIT: Just submitted a pull request - here's what I'm talking about: https://github.com/ChimeraCoder/bm
But go get will hapilly try to use it...
First, confession that my code style, interface, etc. are fairly awful (panics, mixing Reader/Writer with passing []bytes around, and there's even a line commented 'why?'). Can't justify it; I just never properly cleaned up the first thing I got working. I also suspect you've got some performance wins over my code--you probably saved overhead by not calling encoding/binary for varints, for example, and your 'radix' constant (257) almost certianly makes the hashing faster (the multiply even optimizes to an 'lea' instr, I think). Also, (de)serializing the dicts is handy and probably crucial for your use case.
Here are some things we're doing different--just to document them, not claiming that anything is a win:
The rolling hash: We're using similar multiply-add-modulus hashes. I'm relying on uint32 wraparound for the modulus (Go spec says you can rely on wraparound), and I'm doing another multiply when I subtract values out of the hash instead of using a 'save' array.
Blocks vs hash bits: I'm stealing a trick from rzip, where instead of saving hashes of non-overlapping blocks, I save hashes whenever a certain number of bits of the hash are zero. I don't know what works better, empirically.
Min. match length: I used 24 after trying out various values. Too low and you find short matches when you could get longer ones, too high and you miss matches. The right value is probably data-dependent anyway.
The hash table: I'm using a 128k-entry array that's directly indexed by some bits of the rolling hash. Because I'm hashing a lot of documents and only using each hashtable once, I worked out a scheme to reuse the array for multiple diff tasks without garbaging or zeroing it: I made the values in the array indices into all the bytes this MatchState has ever hashed, not into the current document. After fetching an offset out of the hash table, I check if it's before the start of the latest doc (if h < base) and ignore it if so, and otherwise subtract 'base' from it to convert it into an offset into the current doc. Costs something during hashing and matching, but clearing the table was ultimately costing me more.
The encoding: I'm encoding each copy/literal as a protobufs-style signed varint. Positive numbers give a number of literal bytes to copy into the output, negative numbers give a number of bytes to be copied from the reference text, zero means end of diff. Copy lengths are followed by another signed varint that gives the location in the reference doc where the copy should start, relative to a "cursor" position. Having that "cursor" allows a copy that starts right after the end of the last copy to have a slightly shorter encoding. Short encoding of matches isn't that critical anyway, compared with doing well at finding matches, so that part I sort of overdid.
Things I was intrigued by but haven't actually tried:
- rzip separates the 'instructions' ('insert X literal bytes', 'copy Y bytes from position Z in the original') from the text data. For rzip, that seems to improve the secondary compressor (bzip)'s compression ratio. I'm curious if it helps.
- I think the Git packfile format makes the literal instruction always a single byte, but the max. literal len is 127. I wonder if that saves output bytes on net.
- Lots of other packers look at multiple match candidates for the longest match. It would probably make smaller diffs, but not at all sure that the complexity and CPU-time costs would be worth it.
- I could probably eke out a small CPU-time win by matching from "the ends" of the input first, since often one can find longish matches there without hashing.
- I wonder if there's any win in checking whether a match can be extended backwards to completely cover a preceding match. It seems complicated, and probably not a huge win.
Thanks a lot for open sourcing this. When I get time, may try dropping bm into the program I was playing with. (And both my code and my words above are probably a little fried, forgive--the words are rushed, and the code was nights-and-weekends stuff and my first Go project ever.)