[lldb-dev] Improve performance of crc32 calculation

[Scott Smith via lldb-dev]

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:

1. Work on multiple bytes at a time, using multiple lookup tables. (see
http://create.stephan-brumme.com/crc32/#slicing-by-8-overview)
2. Compute crcs over separate regions in parallel, then combine the
results.  (see
http://stackoverflow.com/questions/23122312/crc-calculation-of-a-mostly-static-data-stream
)

As it happens, zlib provides functions for both:
1. The zlib crc32 function uses the same polynomial as ObjectFileELF.cpp,
and uses slicing-by-4 along with loop unrolling.
2. The zlib library provides crc32_combine.

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.

I'm including my patch that assumes zlib is always linked in.  Let me know
if you prefer:
1. I make the change conditional on having zlib (i.e. fall back to the old
code if zlib is not present)
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.

This brings startup time on my machine / my binary from 50 seconds down to
32.
(time ~/llvm/build/bin/lldb -b -o 'b main' -o 'run' MY_PROGRAM)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/lldb-dev/attachments/20170412/83d75329/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: zlib_crc.patch
Type: text/x-patch
Size: 6316 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/lldb-dev/attachments/20170412/83d75329/attachment.bin>