Kraken: 3x faster decompression than zlib | Hacker News Reader

Kraken: 3x faster decompression than zlib

radgametools.com

147 pointsdahjelle68 comments

Another interesting compression project is "Zstandard"

Open source, high performance, decent compression and a "dictionary mode" that's especially fun when it comes to compressing a lot of small data.

http://www.zstd.net

Previous discussion over at https://news.ycombinator.com/item?id=8941955

Here's a nice graph from the zstd site, showing the trade off between compression and speed for several different algorithms:

https://raw.githubusercontent.com/Cyan4973/zstd/master/image...

Also lzturbo is very interesting, closed source but you one can download exec: https://sites.google.com/site/powturbo/ https://github.com/powturbo/TurboBench

There's too many projects named Kraken:

* http://krakenjs.com/ - Javascript framework

* https://www.kraken.com/ - BTC exchange

* https://kraken.io/ - Image Optimizer

https://ccb.jhu.edu/software/kraken/ <- taxonomic ID assignment for metagenomic sequence samples

Hahaha...that's ironic.

Agreed.

Another: GitKraken - https://www.gitkraken.com

love gitkracken

There are too many projects of any name (most never see the light of day), but somehow all these Krakens get released.

Well, what is dead may never die… is what the Krakens say…

I guess someone was ordered to release the Kraken(s), and as Eddie Izzard famously observed[1], nobody ever issued an order to retrieve the Kraken.

To the grumpy crowd: Sorry in adance for the reddit-like comment. I feel a bit light-spirited today :)

[1] https://www.youtube.com/watch?v=Cyq4zT0h0yk

Since this was a Kraken benchmark, I first thought it was some thing benchmarked in the Kraken benchmark.

http://krakenbenchmark.mozilla.org/

I should've known better...

I guess it's yet another optimised LZ variant, and it's no surprise that LZ-based/inspired algorithms are fast, because their main loop is very simple and does not involve the intense bit manipulation of Huffman/Arithmetic algorithms. That's how very carefully optimised LZ can end up being faster than memcpy() in some cases:

http://www.oldskool.org/pc/lz4_8088

Few benchmarks from @rygorous:

https://gist.github.com/rygorous/67c78fde615e078117ea1870472... (on PC)

https://gist.github.com/rygorous/9563760e24463a37984c117b572... (on PS4)

So slower than LZ4? I wonder how Kraken compression rate compares to LZ4.

Better, if you read the article.

How is it compared to Zstandard https://github.com/Cyan4973/zstd ?

Especially with level 22 with --ultra, I found the compression to be good and decompression very fast. Can't wait for 1.0 for format freeze (currently decompressor contains code for previous versions, but that's a hack).

Unfortunately not open source.

Feel free to downvote me but some people need to eat.

Game development doesn't really match well with the consultancy model of most commercial Open Source companies.

Also the RAD guys are awesome, they've been putting out solid tools for years.

All valid points, but think of all the open source projects, even browsers, that could be improved with this compression method if it wasn't proprietary.

Perhaps it's time to attempt to "free" such software via a cooperative effort, e.g. by talking to RAD about a one-time payment for an open source release and organizing that as a Kickstarter project.

That's the rub though, you're talking about a one-time payment.

That isn't a sustainable way to keep a company running. The amount of work that RAD puts into stuff like this, BINK, and their other tools if you wanted to do a OTP you'd be looking at something in the neighborhood of 50-60M.

Everyone uses their stuff in games since it's that good. You'd have to replace licensing costs not only for each game but each platform those games ship on.

I wonder whether it would be viable GPLd with a proprietary licences available for a fee. I suppose that might still be costly and would be incompatible with the licences used by some FOSS projects.

I can't find the post now, but one of the RAD developers behind this codec (it's their 3rd ANS based codec I believe) has said that they would likely be willing to open source their ANS family for a one-time payment of iirc around $5 million. No need for the entire RAD stack.

Oops, his ballpark was $50 million. I obviously have no idea how much things cost.

Still, I think many of the key ideas behind Kraken are out there and not patented. Zstd and lzfse already use ANS variants, for instance. But they're targeting different speed/compression tradeoffs, and aren't implemented as well as Kraken.

Google VP10 and WebP are also planned to be ANS-based: https://chromium.googlesource.com/webm/libvpx/+/fb9186d68d49... https://chromium-review.googlesource.com/#/c/338781/

Think about how browsers could be improved if people were willing to pay $5 for them.

Perhaps it's time to attempt to "pay" for such software via cooperative effort, eg. by the publisher setting a price for it, and then people paying $5.

Why people will pay $5 for coffee they could make at home for 'free' but not for software is beyond me.

A lot of the time people don't understand how expensive software is to develop.

It's a tangible thing. People STILL have issues paying for something that isn't physically in their hands.

Nah, I don't think it's that -- people spend crazy amounts of $ for non-tangible assets in F2P games.

I don't think you're talking about the same subset of people here.

what, people who use browsers and play games? there's got to be a pretty big overlap :) (though it's true that a large fraction of the people that play f2p games don't pay at all.)

i know for me personally, one reason i've been reluctant to pay for software is just that they paying-for-software experience has been so terrible -- you have to clumsily reenter your payment information, you get emailed, sometimes slowly, a registration code, which you inevitably lose and breaks your software when you have to reinstall on a new computer, etc.

I have no idea what it is, I catch myself doing it too. I ask myself why am I not just paying for this instead of building it / doing with out?

Whenever I think rationally I almost always opt to buy software vs make it myself.

For browsers, there is enough financial incentive for vendors:

* Google builds a browser to control the market and make sure ads and their own websites are working well

* Apple builds a browser to make sure web browsing on their devices is working well, uses little power and is not adversely affected by the competition

* Mozilla is swimming in money obviously after all the previous Google payments

So, money is not the issue with browsers - except that we could probably have a browser with built-in privacy (no tracking) and reliable ad blocking if users paid for it instead of large commercial entities. But that's very hypothetical (Google would buy that probably).

And this world needs better algorithms. It depends on what you put first: yourself or others.

Seems like a false choice. Plenty of people make a living doing things that help the world.

I didn't suggest just 2 options. It is a range of choices you get, starting from "you", ending with "others", pick any point.

And sure, you're right "Plenty of people make a living doing things that help the world.", but why this "Kraken" is not Open Source then?

Disclaimer: it is a discussion, I don't try to blame RAD Game Tools for not releasing the source of Kraken. Just curios of what others think.

Putting yourself first isn't a bad thing, especially where bread and butter is involved. Might I suggest dual licensing with a provision for free-to-use in non-commercial projects? Something similar to QT.

Qt is also free to use in commercial projects. I believe fftw had the sort of dual license you have in mind.

Where did you get the idea that putting yourself first is a bad thing in my comment? I didn't mean that. What I was trying to say that you can pick any of this. At the end of the day you're the one who did the job, so it is up to you to decide what to do with it.

You seem to see this as zero sum, meaning that the algorithm writer can only win if "the world" somehow loses. Why is the algorithm writer morally bound to give up his time and effort to the world without compensation? Or why should he consider his own needs and desires somehow lesser that anyone else's? Can not the world benefit from the work of a clever developer while the developer can benefit by earning payment for his efforts?

If the world really needs better algorithms: it can pay for them. That's called a trade, something where both parties win... and if they don't, one party or the other walks away. What this discards is the immoral idea that you can only be good by becoming some sacrificial animal that discards his own needs in favor of others.

Oh... and by the way... you can sometimes advance your own interests by NOT charging them for your work; a lot of open source actually does work this way in practice (even if self-benefit is not the motivating factor for many). Trades are not always monetary.

Where did you see all this in my 2 sentence comment?

I never said it is bad to put yourself first. You're free to do whatever you want with your work, because this work is yours. If anyone against they can make an alternative. There's no sum and the choice is huge starting from "you" and ending with "others", pick any point of this range.

If I misread the intent of your comment then I apologize. But context does matter and in context, your statements carried a fair amount of meaning with little explanation. I don't want to suggest that you said that someone should be forced to release their code; but your short statement seemed to stake a moral claim. A claim I don't see as valid. If I'm wrong, I'd be interested to know what you actually meant.

What I tried to say is that there's other side of some "people need to eat". But it is up to the author or authors to choose which side to choose (or any point in between). And there's nothing wrong with any choice.

That would be great to have this algorithm open sourced.

And it is sad to see how this went from "Unfortunately not open source" to "people need to eat". Also, please note that this company is $1.37M in sales (http://www.hoovers.com/company-information/company-search.ht...). So it is not about "eat" only.

Sales != Profit

Even considering lower gamedev salaries that's not a ton of revenue for one of the top middleware companies in an industry. Given east-side salaries I don't know if you could support more than 8-10 people on that revenue.

I think I still disagree with your ultimate position. But I do thank you for taking the time to respond. I'm upvoting you because, agree or not, you engaged in an honest discussion.

My only regret is that I have but one upvote to give. You really nailed that on the head.

As a computer programmer and an open source software enthusiast, believe me when I say that I would love to contribute every line of code I write to open source. Not because of any moral imperative, but simply because I'd love for my work to be widely distributed and used. Unfortunately, it's incredibly difficult for a company of one to pull that off (but not impossible -- see Mike Pall, for example, though I have no idea how much money he actually makes (made?) via LuaJIT). If I could work on nothing but my open source software without needing to sacrifice my (already rather modest, really) quality of life, I would tender my letter of resignation in the morning. People don't even want to pay for software when it's not available for free: I have a very hard time imagining that they'd be willing to pay for software that is free.

I just don't see any way I can make it work, at least not right now. Maybe once I've got more of a financial safety net set up, I'll give it a shot or two, but for now I'm content to develop proprietary software for The Man™ in exchange for a monetary salary. I do try to squeeze in bits of open source development wherever/whenever I can, and that'll have to be good enough.

Does good will feed my family? Will my landlord let me pay the rent in GitHub stars?

Or in the words of The Oatmeal: http://theoatmeal.com/comics/exposure

Good luck feeding your family with the sales of a proprietary compression algorithm.

This company did exactly that for a long time http://www.radgametools.com/bnkmain.htm

$1.37M in sales(http://www.hoovers.com/company-information/company-search.ht...). They sure can feed their families.

And, yes, you're right: good does not feed your family.

https://s-media-cache-ak0.pinimg.com/736x/19/d3/b0/19d3b0b76...

It may not directly feed your family, but it can certainly improve the world you live in and that includes your own private habitat. Small improvements might not be worth giving away because the effect on your life will be negligible, but bigger ones should be (at least once you've obtained financial independence through them, there's no longer a good excuse not to).

I get what you mean, but it is still a downside for the format.

"contact us" pricing is fine and all, but it means it's irrelevant to me most of the time. Their software could be the coolest; but the chances of them taking an individual seriously are probably low.

> some people need to eat.

That'll need to be addressed some day: jobs are being automated away (yesterday typists, today cashiers, tomorrow drivers…), and those people need to eat too. Then there's artificial scarcity. Unlike food, software can be copied at negligible costs. Proprietary software puts arbitrary (and harmful) restrictions to that copying so that its developer can eat.

When we get our act together and finally have a form of guaranteed income, we won't need copyright or patents any more, because there won't be any starving artist or author or developer.

Proprietary software is harmful and needs to die. The need for proprietary software is harmful and needs to die. I long for the day they will.

There's nothing artificial about the scarcity of people like cbloom and ryg, competent enough to produce something like Kraken.

"getting your act together" sounds scary to someone who grew up in Communist Eastern Europe; I surely hope you don't get your act together.

I was talking about the marginal cost of software. Of course the first copy is expensive. Of course talent is scarce. Of course time is scarce. Still, once it's done, copying it cost near nothing. If you raise that marginal cost above this natural "near zero", that creates an incentive to reinvent the wheel. Your actually scarce resource, talent, is being wasted on duplicated effort.

Proprietary software causes duplicated efforts. Not an ideal use of our resources, don't you think?

---

> "getting your act together" sounds scary to someone who grew up in Communist Eastern Europe

Come on, that was a small group of people seizing power to the detriment of most everyone else. You sound like it's the only alternative to our corporate capitalism. Seriously?

RAD own the IP completely so they can dual-license GPL and Commercial.

No non-Free commercial product or game would touch the GPL version so license revenues would continue.

RAD-tech could then be used in Free software too, gaining publicity, adoption and developer mind-share.

If innovation comes downstream in the Free version then RAD could license that from the coders for their commercial product. The good will from their initial gift of Freeing their tech may make upstream patch re-licensing on good terms.

The social benefits of dual licensing should be encouraged by a GPL tax-relief akin to charitable write-downs.

Is this 3x faster than zlib at decompressing on zlib-compressed data, or 3x faster on samples compressed with its own format versus the same samples compressed with zlib?

It is custom compression algorithm. It has its own format.

Does anyone know how Apple's lzfse [0] compares to some of these other compression algos?

>Beginning with iOS 9 and OSX 10.11 El Capitan, we provide Apple’s proprietary compression algorithm, LZFSE. LZFSE is a new algorithm, matching the compression ratio of ZLIB level 5, but with much higher energy efficiency and speed (between 2x and 3x) for both encode and decode operations.

I'm interested because of the low energy characteristics...

[0] : https://developer.apple.com/library/tvos/documentation/Perfo...

What about LZHAM; I thought that was the top "slow compress, good ratio, fast decompress" contender for games and such?

This article has some comparisons between Oodle's LZNA and LZHAM (at least as of a year ago): http://cbloomrants.blogspot.com/2015/05/05-09-15-oodle-lzna....

It is no secret that vanilla zlib is slow. Would have been interesting if they compared with https://github.com/Dead2/zlib-ng

Is the speed difference algorithmic, implementation optimization or a mix of both?

They say it's a mix of both.

Looking at the figures, it seems to have roughly the same performance as Zstandard in high compression mode.

But what is it's Weissman score?

I was just watching Silicon Valley yesterday and this is exactly what I was thinking when I read the title. 6.0+?

Reply on news.ycombinator.com