3 ms·

Basically an Apple-specific reimplementation of Zstd: https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd

by awalton 10y ago

DiabloD3 10y ago
So, worse than LZ4 for what Apple seems to be using it for. Why didn't they just use LZ4? Confusing company, they are.
- shmerl 10y ago
  They are very much into NIH, seemingly out of paranoid fear of patent attacks (though not sure how it can protect them).
  - dchest 10y ago
    This is a baseless speculation. First of all, Apple provides LZ4 in libcompression. Secondly, LZFSE uses Lempel–Ziv algorithm and ANS coder invented by Jarek Duda (https://arxiv.org/abs/1311.2540 https://arxiv.org/abs/1311.2540): https://developer.apple.com/library/ios/documentation/Performance/Reference/Compression/index.html https://developer.apple.com/library/ios/documentation/Perfor...
    - nicky0 10y ago
      Can I just say I really appreciate your contributions on this thread. Answering crass company-bashing with well-referenced and informative replies.
      - dchest 10y ago
        Thank you :)
    - twitch_checksum 10y ago
      Well, many people nowadays pretend that, as if they read Jarek's paper, understood it and came out with a genuine implementation of their own. But Jarek's ANS paper was first out in 2007, and almost no one paid attention to it, because it was plain inscrutable. Many years later, it took an individual to create FSE (https://github.com/Cyan4973/FiniteStateEntropy https://github.com/Cyan4973/FiniteStateEntropy), to prove that it could be transformed into something actually useful and competitive. Since then, the paper has been updated a few times, borrowing a few points from FSE in order to become more readable. But it's still very hard to read. In contrast, FSE code can be copy/pasted. And all of a sudden, lot of versions have popped out over Internet. By pure chance, they all look like derivatives of FSE or Fabian Giesen's rANS, but they pay tribute to Jarek's ANS paper, because quite clearly it is the source of their work, and prior existence of an actual open source implementation which works and looks pretty damn close to theirs was purely accidental. This is not paying tribute where it's due.
      - dchest 10y ago
        Thanks for the insight!
      - tmd83 10y ago
        Very well said. Its a stark contrast to how Yann Collet acknowledges others inspiration and collaboration (http://fastcompression.blogspot.fr/2013/12/finite-state-entropy-new-breed-of.html http://fastcompression.blogspot.fr/2013/12/finite-state-entr...)
- mhw 10y ago
  From the infoq article https://www.infoq.com/news/2016/07/apple-lzfse-lossless-opensource https://www.infoq.com/news/2016/07/apple-lzfse-lossless-open... that contains much more detail and is linked to by the original submitted link. "Admittedly, LZFSE does not aim to be the best or fastest algorithm out there. In fact, Apple states that LZ4 is faster than LZFSE while LZMA provides a higher compression ratio, albeit at the cost of being an order of magnitude slower than other options available in Apple SDKs. LZFSE is Apple’s suggested option when compression and speed are more or less equally important and you want reduce energy consumption." https://developer.apple.com/library/ios/documentation/Performance/Reference/Compression/index.html https://developer.apple.com/library/ios/documentation/Perfor... has a section titled "Choice of Compression Algorithm"
- dchest 10y ago
  It's not worse than LZ4. LZ4 is just an LZ-based compression (find common strings, reference them), while LZFSE does both LZ compression and entropy coding (like ZIP's deflate). It's comparable to zstd, which uses LZ and finite state entropy coder. They achieve better compression at lower (than just LZ-based compressor) speed. You can say they replace zlib, achieving much higher performance at pretty much the same compression ratio. Apple's libcompression also provides LZ4 if you need it: https://developer.apple.com/library/ios/documentation/Performance/Reference/Compression/index.html https://developer.apple.com/library/ios/documentation/Perfor...
tmd83 10y ago
Thats kind of what I thought when it came out. Zstd is closest to it both in terms of characteristic and concept. It would be nice to have a head to head comparison between the two. Zstd & LZ4 being the work of single developer is amazing though.

Basically an Apple-specific reimplementation of Zstd: https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd

by awalton 10y ago

Basically an Apple-specific reimplementation of Zstd: https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd

DiabloD3 10y ago

So, worse than LZ4 for what Apple seems to be using it for. Why didn't they just use LZ4? Confusing company, they are.

shmerl 10y ago
They are very much into NIH, seemingly out of paranoid fear of patent attacks (though not sure how it can protect them).
- dchest 10y ago
  This is a baseless speculation. First of all, Apple provides LZ4 in libcompression. Secondly, LZFSE uses Lempel–Ziv algorithm and ANS coder invented by Jarek Duda (https://arxiv.org/abs/1311.2540 https://arxiv.org/abs/1311.2540): https://developer.apple.com/library/ios/documentation/Performance/Reference/Compression/index.html https://developer.apple.com/library/ios/documentation/Perfor...
  - nicky0 10y ago
    Can I just say I really appreciate your contributions on this thread. Answering crass company-bashing with well-referenced and informative replies.
    - dchest 10y ago
      Thank you :)
  - twitch_checksum 10y ago
    Well, many people nowadays pretend that, as if they read Jarek's paper, understood it and came out with a genuine implementation of their own. But Jarek's ANS paper was first out in 2007, and almost no one paid attention to it, because it was plain inscrutable. Many years later, it took an individual to create FSE (https://github.com/Cyan4973/FiniteStateEntropy https://github.com/Cyan4973/FiniteStateEntropy), to prove that it could be transformed into something actually useful and competitive. Since then, the paper has been updated a few times, borrowing a few points from FSE in order to become more readable. But it's still very hard to read. In contrast, FSE code can be copy/pasted. And all of a sudden, lot of versions have popped out over Internet. By pure chance, they all look like derivatives of FSE or Fabian Giesen's rANS, but they pay tribute to Jarek's ANS paper, because quite clearly it is the source of their work, and prior existence of an actual open source implementation which works and looks pretty damn close to theirs was purely accidental. This is not paying tribute where it's due.
    - dchest 10y ago
      Thanks for the insight!
    - tmd83 10y ago
      Very well said. Its a stark contrast to how Yann Collet acknowledges others inspiration and collaboration (http://fastcompression.blogspot.fr/2013/12/finite-state-entropy-new-breed-of.html http://fastcompression.blogspot.fr/2013/12/finite-state-entr...)
mhw 10y ago
From the infoq article https://www.infoq.com/news/2016/07/apple-lzfse-lossless-opensource https://www.infoq.com/news/2016/07/apple-lzfse-lossless-open... that contains much more detail and is linked to by the original submitted link. "Admittedly, LZFSE does not aim to be the best or fastest algorithm out there. In fact, Apple states that LZ4 is faster than LZFSE while LZMA provides a higher compression ratio, albeit at the cost of being an order of magnitude slower than other options available in Apple SDKs. LZFSE is Apple’s suggested option when compression and speed are more or less equally important and you want reduce energy consumption." https://developer.apple.com/library/ios/documentation/Performance/Reference/Compression/index.html https://developer.apple.com/library/ios/documentation/Perfor... has a section titled "Choice of Compression Algorithm"
dchest 10y ago
It's not worse than LZ4. LZ4 is just an LZ-based compression (find common strings, reference them), while LZFSE does both LZ compression and entropy coding (like ZIP's deflate). It's comparable to zstd, which uses LZ and finite state entropy coder. They achieve better compression at lower (than just LZ-based compressor) speed. You can say they replace zlib, achieving much higher performance at pretty much the same compression ratio. Apple's libcompression also provides LZ4 if you need it: https://developer.apple.com/library/ios/documentation/Performance/Reference/Compression/index.html https://developer.apple.com/library/ios/documentation/Perfor...

tmd83 10y ago

Thats kind of what I thought when it came out. Zstd is closest to it both in terms of characteristic and concept. It would be nice to have a head to head comparison between the two. Zstd & LZ4 being the work of single developer is amazing though.