9 ms·

https://www.hackerfactor.com/blog/index.php?/archives/895-Connecting-the-iDOTs.html https://www.hackerfactor.com/blog/index.php?/archives/895-Co... > on the fi

https://www.hackerfactor.com/blog/index.php?/archives/895-Connecting-the-iDOTs.html https://www.hackerfactor.com/blog/index.php?/archives/895-Co... > on the first retina iPads, decoding PNGs was a huge portion of the total launch times for some apps, while one of the two cores sat completely idle. Could they distribute decoding PNG files to a thread pool, instead of making multithreaded PNG files? Or would this fail for single large PNG files?

Retr0id 5y ago
Decompressing zlib/DEFLATE streams, in the general case, is an inherently serial task. It cannot be meaningfully parallelised. The "trick" used by Apple, and a few other encoders, is to flush the zlib state every so often (ZLIB_FULL_FLUSH), which means that subsequent data is both byte alligned, and does not make any backreferences to before the sync. If you know where these sync points are (Apple encodes this information in their non-standard "iDOT" chunk) then you can start decompressing from that point, in an isolated thread. There are ongoing discussions as to how this metadata could be standardised: https://github.com/w3c/PNG-spec/issues/54 https://github.com/w3c/PNG-spec/issues/54
- vbphprubyjsgo 5y ago
  I think that's what restart markers are for in JPEG from the original spec. IIRC in JPEG you can have markers that are marked as "crucial for proper decode" and programs should reject the image if they don't understand them. Maybe the latter was from PNG I forget.
- lifthrasiir 5y ago
  Technically speaking you can also speculatively decode Huffman coded bitstreams because the use of canonical Huffman tree means that the end-of-block symbol is almost likely the longest code and has no 0 bits, so you can start decoding at a long string of 1 bits. Of course this doesn't solve an issue of shared LZSS window across multiple blocks.
  - xyzzy_plugh 5y ago
    This is hilarious to me, but makes complete sense. Do you know if this has ever been done anywhere?
    - lifthrasiir 5y ago
      There is indeed a hilarious backstory. Back in time one of my friends was looking for a task for the Distributed Computing course where you write a program for the Cell microprocessor, and I half-jokingly suggested this, not realizing that it won't work at all because of the shared window. The friend eventually came to realize that issue and couldn't finish the project in time, but still got a good grade solely because of the novelty of the task (!). (According to that friend virtually everyone else did the parallel JPEG stuffs.)
      - xyzzy_plugh 5y ago
        This doesn't surprise me. The Cell architecture wrought more insane hacks than good designs.
jjoonathan 5y ago
It would fail for single large splash-screen PNG files, and that's where they were looking to shave milliseconds.
- kevingadd 5y ago
  You'd also have to be kicking off PNG decodes in a way that is compatible with offloading them to a threadpool, and lots of software likely just loads images synchronously and moves on with its day.
pcwalton 5y ago
Well, one thing that does work for decoding regular old PNGs is separating the entropy decoding (in PNG, DEFLATE) from the prediction (what PNG calls filtering). You can create a pipeline where one thread is working on the entropy coding and handing off completed rows to a thread that performs the prediction decode. This doesn't get a 2x speedup because usually DEFLATE is slower than the prediction step, so it ends up bottlenecked on zlib, but it helps a good bit. (I implemented this in Rust at one point with the intention to ship in Firefox, but it never did.) Of course, this only scales to 2 CPUs. Beyond that you will need to do some sort of splitting of the input to achieve wins (since no matter how much you optimize the filtering, you're still bottlenecked on DEFLATE, which is inherently serial).
- pornel 5y ago
  I assume iOS may have a problem of the application doing: for each path { decode(path) } and the OS can't parallelize that, because it learns about a new file only after decoding the previous one.
- geocar 5y ago
  How I read nyanpasu64; I think that the point was that a web page will often have multiple png files -- often more than you have cores, so the gains of decoding a single specially-formatted png might disappear in practice. iDOT seems like overengineering to me: Why not break up the PNG and tile them in an SVG? This should be just as fast, about the same size, and you'd never have run the risk of inventing your own format and implementing it badly[1]. Users would probably be happier with all their SVGs being faster than having specially-crafted PNGs accelerated (if given the choice) [1]: https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2016-1811 https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2016-1811
  - patrec 5y ago
    Amen!
  - marcellus23 5y ago
    I’m a bit confused, are you suggesting they convert the PNGs into an SVG? How is that possible?

Retr0id 5y ago

Decompressing zlib/DEFLATE streams, in the general case, is an inherently serial task. It cannot be meaningfully parallelised. The "trick" used by Apple, and a few other encoders, is to flush the zlib state every so often (ZLIB_FULL_FLUSH), which means that subsequent data is both byte alligned, and does not make any backreferences to before the sync. If you know where these sync points are (Apple encodes this information in their non-standard "iDOT" chunk) then you can start decompressing from that point, in an isolated thread. There are ongoing discussions as to how this metadata could be standardised: https://github.com/w3c/PNG-spec/issues/54 https://github.com/w3c/PNG-spec/issues/54

vbphprubyjsgo 5y ago
I think that's what restart markers are for in JPEG from the original spec. IIRC in JPEG you can have markers that are marked as "crucial for proper decode" and programs should reject the image if they don't understand them. Maybe the latter was from PNG I forget.
lifthrasiir 5y ago
Technically speaking you can also speculatively decode Huffman coded bitstreams because the use of canonical Huffman tree means that the end-of-block symbol is almost likely the longest code and has no 0 bits, so you can start decoding at a long string of 1 bits. Of course this doesn't solve an issue of shared LZSS window across multiple blocks.
- xyzzy_plugh 5y ago
  This is hilarious to me, but makes complete sense. Do you know if this has ever been done anywhere?
  - lifthrasiir 5y ago
    There is indeed a hilarious backstory. Back in time one of my friends was looking for a task for the Distributed Computing course where you write a program for the Cell microprocessor, and I half-jokingly suggested this, not realizing that it won't work at all because of the shared window. The friend eventually came to realize that issue and couldn't finish the project in time, but still got a good grade solely because of the novelty of the task (!). (According to that friend virtually everyone else did the parallel JPEG stuffs.)
    - xyzzy_plugh 5y ago
      This doesn't surprise me. The Cell architecture wrought more insane hacks than good designs.

jjoonathan 5y ago

It would fail for single large splash-screen PNG files, and that's where they were looking to shave milliseconds.

kevingadd 5y ago
You'd also have to be kicking off PNG decodes in a way that is compatible with offloading them to a threadpool, and lots of software likely just loads images synchronously and moves on with its day.

pcwalton 5y ago

Well, one thing that does work for decoding regular old PNGs is separating the entropy decoding (in PNG, DEFLATE) from the prediction (what PNG calls filtering). You can create a pipeline where one thread is working on the entropy coding and handing off completed rows to a thread that performs the prediction decode. This doesn't get a 2x speedup because usually DEFLATE is slower than the prediction step, so it ends up bottlenecked on zlib, but it helps a good bit. (I implemented this in Rust at one point with the intention to ship in Firefox, but it never did.) Of course, this only scales to 2 CPUs. Beyond that you will need to do some sort of splitting of the input to achieve wins (since no matter how much you optimize the filtering, you're still bottlenecked on DEFLATE, which is inherently serial).

pornel 5y ago
I assume iOS may have a problem of the application doing: for each path { decode(path) } and the OS can't parallelize that, because it learns about a new file only after decoding the previous one.
geocar 5y ago
How I read nyanpasu64; I think that the point was that a web page will often have multiple png files -- often more than you have cores, so the gains of decoding a single specially-formatted png might disappear in practice. iDOT seems like overengineering to me: Why not break up the PNG and tile them in an SVG? This should be just as fast, about the same size, and you'd never have run the risk of inventing your own format and implementing it badly[1]. Users would probably be happier with all their SVGs being faster than having specially-crafted PNGs accelerated (if given the choice) [1]: https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2016-1811 https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2016-1811
- patrec 5y ago
  Amen!
- marcellus23 5y ago
  I’m a bit confused, are you suggesting they convert the PNGs into an SVG? How is that possible?