Replace linear lookup with a hash to speedup.

michaeleisel / zld

A faster version of Apple's linker

MIT License

1.19k stars 50 forks source link

Replace linear lookup with a hash to speedup. #102

Closed CrazyFanFan closed 2 years ago

CrazyFanFan commented 2 years ago

Update
- tbb tp 2020.3
- dyld to 940
- llvm to 13.0.1
- remove cfe
- Update implementation of libunwind::DwarfInstructions<A, B>::parseCFIs and Parser<A>::scanSymbolTableForAddress

CrazyFanFan commented 2 years ago

@michaeleisel Thanks for your review, please review again.

michaeleisel commented 2 years ago

i'm curious: what % of iterations are we avoiding with _symbolsMap, once the .find change is in? how big of a bottleneck were these functions? are you able to test that an app binary is identical without these changes (except the library updates) vs. with? if so, what app is it? (it's hard for me to find open-source apps that are large and complicated enough to do a great job of testing zld's many corners, so i'm always on the lookout for people that can test with larger ones)

CrazyFanFan commented 2 years ago

This is a hybrid project that uses multiple technology stacks, including Rust Swift Objective-C C/C++ Flutter..., It so big that it has 2,600k of symbols when generate dSYM file and this will take about 30 minutes. So that i have to create PR to llvm to speedup this prosess just like code you just reviewed.

For data, using my modified ZLD, at best, incremental compilation of word links saves two-thirds of the time.

My English is not very good. The above is translated by machine.

CrazyFanFan commented 2 years ago

Two-thirds went from about 180 seconds to 60 seconds.

MacBook Pro (16-inch, 2019) CPU: 2.6 GHz 六核Intel Core i7 Memory: 64 GB 2667 MHz DDR4

CrazyFanFan commented 2 years ago

六核 ==> six-core

michaeleisel commented 2 years ago

if this produces the same application for you, byte-for-byte, with this change, then it looks good to me

CrazyFanFan commented 2 years ago

In the past two months, this patch has been running well in our project. Do you mean to compare the hash or structure of the product?

michaeleisel commented 2 years ago

you mentioned that large project with 2,600+ files. could you check that the largest binary in that project, when built with zld using this pr, is identical to that binary when built with the master version of zld? cmp MyBinary_with_master MyBinary_with_pr

CrazyFanFan commented 2 years ago

Not 2,600 files, but 2,670,000 symbols, and I will complete the tests you mentioned later in the next few days.

CrazyFanFan commented 2 years ago

After a huge number of tests, when the input parameters are the same:

The product of multiple links is the same when using ld.
The product of multiple links were different at the position of line 1, char 138.
The same effect comes up when using zld with my patchs.

michaeleisel commented 2 years ago

Thanks for doing this!