5 ms·

Making CRC calculations in Mojo 18x faster than Python and 3x slower than Python

58 points by fnands 2y ago

molenzwiebel 2y ago
For those that thought the process of speeding up CRC was interesting, I strongly recommend reading [1]. It describes a step by step process on how a naive CRC implementation might be improved, until finally arriving at an implementation in assembly with a staggering throughput of 62 processed bits (almost 8 bytes) per CPU cycle. Yes, you read that right. [1]: https://github.com/komrad36/CRC https://github.com/komrad36/CRC
- fnands 2y ago
  Yup, it's a fantastic read. I based most of my post off it (I clearly mention so) and it's worth it to read at least the first part of it before reading my post.
bsaul 2y ago
How is mojo doing ? Has it made its way as a niche language in some places ?
- khimaros 2y ago
  and is it still closed source?
  - fnands 2y ago
    Yup, language is still closed, stdlib is open.
- fnands 2y ago
  It's coming along. I don't think anyone is using it for anything serious yet, but it is starting to feel like a real language. My guess is that it will start being used as a library language (i.e. have libraries written in Mojo being called from Python) before it really gets going as its own thing.
jorams 2y ago
For what it's worth, it appears the paper "Everything we know about CRC but afraid to forget" was originally published as part of the release of crcutil on Google Code[1]. This is a hg repository with one commit that includes the paper, the source of the paper, and an implementation. [1]: https://code.google.com/archive/p/crcutil/ https://code.google.com/archive/p/crcutil/
- fnands 2y ago
  Thanks! I'll add it to the post.
adsharma 2y ago
https://github.com/py2many/py2many/pull/653 https://github.com/py2many/py2many/pull/653 Transpiling the python version in the blog to mojo gives me a 4x speedup. Had to hand edit a couple of things: - List to bytearray conversion is not working yet - Can't iterate over SIMD. So a "for x in list" loop has to be rewritten as a range based loop. With a bit more work, the manual edits won't be necessary.
- adsharma 2y ago
  Generated code: https://gist.github.com/adsharma/22ec18664ce4a59750b78fddc5801045 https://gist.github.com/adsharma/22ec18664ce4a59750b78fddc58... Edited code: https://gist.github.com/adsharma/72516d8333a25fd8e350472568d944de https://gist.github.com/adsharma/72516d8333a25fd8e350472568d...
- fnands 2y ago
  Oh! Cool project! You mean 4x speedup over Python?
  - adsharma 2y ago
    Yes. Details in the pull request linked above
chrislattner 2y ago
Great post @fnands!
- fnands 2y ago
  Thanks Chris! It has been about a year since I started playing around with Mojo and it's impressive how far it (and the community) has come!
onethumb 2y ago
FYI, I forked and improved [1] a Rust implementation that supports both table- and SIMD-accelerated CRC-64/NVME [2] calculations. The SIMD-accelerated (x86/x86_64 and aarch64) version delivers 10X over the table (16-bytes at a time) implementation. The original implementation [3] did the same thing but for CRC-64/XZ [4]. [1]: https://github.com/awesomized/crc64fast-nvme https://github.com/awesomized/crc64fast-nvme [2]: https://reveng.sourceforge.io/crc-catalogue/all.htm#crc.cat.crc-64-nvme https://reveng.sourceforge.io/crc-catalogue/all.htm#crc.cat.... [3]: https://github.com/tikv/crc64fast https://github.com/tikv/crc64fast [4]: https://reveng.sourceforge.io/crc-catalogue/all.htm#crc.cat.crc-64-xz https://reveng.sourceforge.io/crc-catalogue/all.htm#crc.cat....
- Genbox 2y ago
  How does it compare to the built-in CRC32 instruction? [1] [1] https://www.intel.com/content/www/us/en/docs/ipp/developer-guide-reference/2021-12/crc32-crc32c.html https://www.intel.com/content/www/us/en/docs/ipp/developer-g...
  - onethumb 2y ago
    This is computing CRC-64, not CRC-32, so there's not really a comparison. But perhaps most importantly, ours works with a variety of polynomials (there are a lot! [1])... we're just using the NVME one, but it's trivially adaptable to most (all?) of them. (The Intel instruction you link to only works with two - CRC32 and CRC32C) Finally, it's based on Intel's paper [2], so they also believe it's extremely fast. :) [1]: https://reveng.sourceforge.io/crc-catalogue/all.htm https://reveng.sourceforge.io/crc-catalogue/all.htm [2]: https://web.archive.org/web/20131224125630/https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf https://web.archive.org/web/20131224125630/https://www.intel...

58 points by fnands 2y ago

For those that thought the process of speeding up CRC was interesting, I strongly recommend reading [1]. It describes a step by step process on how a naive CRC implementation might be improved, until finally arriving at an implementation in assembly with a staggering throughput of 62 processed bits (almost 8 bytes) per CPU cycle. Yes, you read that right. [1]: https://github.com/komrad36/CRC https://github.com/komrad36/CRC

fnands 2y ago
Yup, it's a fantastic read. I based most of my post off it (I clearly mention so) and it's worth it to read at least the first part of it before reading my post.

bsaul 2y ago

How is mojo doing ? Has it made its way as a niche language in some places ?

khimaros 2y ago
and is it still closed source?
- fnands 2y ago
  Yup, language is still closed, stdlib is open.
fnands 2y ago
It's coming along. I don't think anyone is using it for anything serious yet, but it is starting to feel like a real language. My guess is that it will start being used as a library language (i.e. have libraries written in Mojo being called from Python) before it really gets going as its own thing.

jorams 2y ago

For what it's worth, it appears the paper "Everything we know about CRC but afraid to forget" was originally published as part of the release of crcutil on Google Code[1]. This is a hg repository with one commit that includes the paper, the source of the paper, and an implementation. [1]: https://code.google.com/archive/p/crcutil/ https://code.google.com/archive/p/crcutil/

fnands 2y ago
Thanks! I'll add it to the post.

adsharma 2y ago

https://github.com/py2many/py2many/pull/653 https://github.com/py2many/py2many/pull/653 Transpiling the python version in the blog to mojo gives me a 4x speedup. Had to hand edit a couple of things: - List to bytearray conversion is not working yet - Can't iterate over SIMD. So a "for x in list" loop has to be rewritten as a range based loop. With a bit more work, the manual edits won't be necessary.

adsharma 2y ago
Generated code: https://gist.github.com/adsharma/22ec18664ce4a59750b78fddc5801045 https://gist.github.com/adsharma/22ec18664ce4a59750b78fddc58... Edited code: https://gist.github.com/adsharma/72516d8333a25fd8e350472568d944de https://gist.github.com/adsharma/72516d8333a25fd8e350472568d...
fnands 2y ago
Oh! Cool project! You mean 4x speedup over Python?
- adsharma 2y ago
  Yes. Details in the pull request linked above

chrislattner 2y ago

Great post @fnands!

fnands 2y ago
Thanks Chris! It has been about a year since I started playing around with Mojo and it's impressive how far it (and the community) has come!

onethumb 2y ago

FYI, I forked and improved [1] a Rust implementation that supports both table- and SIMD-accelerated CRC-64/NVME [2] calculations. The SIMD-accelerated (x86/x86_64 and aarch64) version delivers 10X over the table (16-bytes at a time) implementation. The original implementation [3] did the same thing but for CRC-64/XZ [4]. [1]: https://github.com/awesomized/crc64fast-nvme https://github.com/awesomized/crc64fast-nvme [2]: https://reveng.sourceforge.io/crc-catalogue/all.htm#crc.cat.crc-64-nvme https://reveng.sourceforge.io/crc-catalogue/all.htm#crc.cat.... [3]: https://github.com/tikv/crc64fast https://github.com/tikv/crc64fast [4]: https://reveng.sourceforge.io/crc-catalogue/all.htm#crc.cat.crc-64-xz https://reveng.sourceforge.io/crc-catalogue/all.htm#crc.cat....

Genbox 2y ago
How does it compare to the built-in CRC32 instruction? [1] [1] https://www.intel.com/content/www/us/en/docs/ipp/developer-guide-reference/2021-12/crc32-crc32c.html https://www.intel.com/content/www/us/en/docs/ipp/developer-g...
- onethumb 2y ago
  This is computing CRC-64, not CRC-32, so there's not really a comparison. But perhaps most importantly, ours works with a variety of polynomials (there are a lot! [1])... we're just using the NVME one, but it's trivially adaptable to most (all?) of them. (The Intel instruction you link to only works with two - CRC32 and CRC32C) Finally, it's based on Intel's paper [2], so they also believe it's extremely fast. :) [1]: https://reveng.sourceforge.io/crc-catalogue/all.htm https://reveng.sourceforge.io/crc-catalogue/all.htm [2]: https://web.archive.org/web/20131224125630/https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf https://web.archive.org/web/20131224125630/https://www.intel...