<div dir="ltr">BTW, the JamCRC is used in writing Windows COFF object files, PGO instrumentation, and PDB Debug Info reading / writing, so any work we do to make it faster will benefit many parts of the toolchain.</div><br><div class="gmail_quote"><div dir="ltr">On Wed, Apr 12, 2017 at 12:42 PM Zachary Turner <<a href="mailto:zturner@google.com">zturner@google.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">It would be nice if we could simply update LLVM's implementation to be faster. Having multiple implementations of the same thing seems undesirable, especially if one (fast) implementation is always superior to some other reason. i.e. there's no reason anyone would ever want to use a slow implementation if a fast one is available.<div><br></div><div>Can we change the JamCRC implementation in LLVM to use 4-byte slicing and parallelize it ourselves? This way there's no dependency on zlib, so even people who have non-zlib enabled builds of LLDB get the benefits of the fast algorithm.</div></div><br><div class="gmail_quote"><div dir="ltr">On Wed, Apr 12, 2017 at 12:36 PM Scott Smith <<a href="mailto:scott.smith@purestorage.com" target="_blank">scott.smith@purestorage.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>I didn't realize that existed; I just checked and it looks like there's JamCRC which uses the same polynomial. I don't know what "Jam" means in this context, unless it identifies the polynomial some how? The code is also byte-at-a-time.<br><br></div>Would you prefer I use JamCRC support code instead, and then change JamCRC to optionally use zlib if it's available?<br></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Apr 12, 2017 at 12:23 PM, Zachary Turner <span dir="ltr"><<a href="mailto:zturner@google.com" target="_blank">zturner@google.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Zlib is definitely optional and we cannot make it required.<br><br>Did you check to see if llvm has a crc32 function somewhere in Support?<br><div class="gmail_quote"><div><div class="m_8792906402178877529m_-6095628003756269983h5"><div dir="ltr">On Wed, Apr 12, 2017 at 12:15 PM Scott Smith via lldb-dev <<a href="mailto:lldb-dev@lists.llvm.org" target="_blank">lldb-dev@lists.llvm.org</a>> wrote:<br></div></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="m_8792906402178877529m_-6095628003756269983h5"><div dir="ltr"><div><div><div><div><div><div><div><div><div><div>The algorithm included in ObjectFileELF.cpp performs a byte at a time computation, which causes long pipeline stalls in modern processors. Unfortunately, the polynomial used is not the same one used by the SSE 4.2 instruction set, but there are two ways to make it faster:<br><br></div>1. Work on multiple bytes at a time, using multiple lookup tables. (see <a href="http://create.stephan-brumme.com/crc32/#slicing-by-8-overview" target="_blank">http://create.stephan-brumme.com/crc32/#slicing-by-8-overview</a>)<br></div>2. Compute crcs over separate regions in parallel, then combine the results. (see <a href="http://stackoverflow.com/questions/23122312/crc-calculation-of-a-mostly-static-data-stream" target="_blank">http://stackoverflow.com/questions/23122312/crc-calculation-of-a-mostly-static-data-stream</a>)<br><br></div>As it happens, zlib provides functions for both:<br></div>1. The zlib crc32 function uses the same polynomial as ObjectFileELF.cpp, and uses slicing-by-4 along with loop unrolling.<br></div>2. The zlib library provides crc32_combine.<br><br></div>I decided to just call out to the zlib library, since I see my version of lldb already links with zlib; however, the llvm CMakeLists.txt declares it optional.<br><br></div>I'm including my patch that assumes zlib is always linked in. Let me know if you prefer:<br></div>1. I make the change conditional on having zlib (i.e. fall back to the old code if zlib is not present)<br></div>2. I copy all the code from zlib and put it in ObjectFileELF.cpp. However, I'm going to guess that requires updating some documentation to include zlib's copyright notice.<br><br></div>This brings startup time on my machine / my binary from 50 seconds down to 32.<br>(time ~/llvm/build/bin/lldb -b -o 'b main' -o 'run' MY_PROGRAM)<br><br></div></div></div>
_______________________________________________<br>
lldb-dev mailing list<br>
<a href="mailto:lldb-dev@lists.llvm.org" target="_blank">lldb-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-dev</a><br>
</blockquote></div>
</blockquote></div><br></div>
</blockquote></div></blockquote></div>