Page MenuHomePhabricator

Speculatively instantiate archive members
ClosedPublic

Authored by ruiu on Jan 16 2015, 7:35 AM.

Details

Summary

LLD parses archive file index table only at first. When it finds a symbol
it is looking for is defined in a member file in an archive file, it actually
reads the member from the archive file. That's done in the core linker.

That's a single-thread process since the core linker is single threaded.
If your command line contains a few object files and a lot of archive files
(which is quite often the case), LLD hardly utilizes hardware parallelism.

This patch improves parallelism by speculatively instantiating archive
file members. At the beginning of the core linking, we first create a map
containing all symbols defined in all members, and each time we find a
new undefined symbol, we instantiate a member file containing the
symbol (if such a file exists). File instantiation is side effect free, so this
should not affect correctness.

This is a quick benchmark. Time to link self-link LLD executable:

Linux 9.78s -> 8.50s (0.86x)
Windows 6.18s -> 4.51s (0.73x)

Diff Detail

Event Timeline

ruiu updated this revision to Diff 18302.Jan 16 2015, 7:35 AM
ruiu retitled this revision from to Speculatively instantiate archive members.
ruiu updated this object.
ruiu edited the test plan for this revision. (Show Details)
ruiu added a project: lld.
ruiu added a subscriber: Unknown Object (MLST).
atanasyan added inline comments.Jan 16 2015, 8:27 AM
lib/ReaderWriter/FileArchive.cpp
102

It looks like we can remove the group from the capture list because it is not used in the lambda body.

274

Can we store promises directly and do not use unique_ptr wrapper? Though I did not test the following code, it compiled successfully. Does it have a sense?

// Instantiate the member
_promises.emplace_back();
auto &promise = _promises.back();
_preloaded[memberStart] = promise.get_future();
                                               
group.spawn([this, &promise, ci] {
  std::unique_ptr<File> result;
  if (instantiateMember(ci, result)) {
    promise.set_value(nullptr);
    return;
  }
  promise.set_value(result.release());
});

[...]

mutable std::vector<std::promise<const File *>> _promises;
ruiu added inline comments.Jan 16 2015, 8:36 AM
lib/ReaderWriter/FileArchive.cpp
102

Done.

274

I think promises created here need to be deleted when it's no longer needed. Your code wouldn't delete promises, no?

atanasyan added inline comments.Jan 16 2015, 8:46 AM
lib/ReaderWriter/FileArchive.cpp
274

They will be destroyed at the same time with the _promises container as any other types own destructor and stored in the std::vector.

ruiu updated this revision to Diff 18306.Jan 16 2015, 9:28 AM
  • Updated as per Simon's suggestion. Since object address is not guaranteed to be the same before group.spawn and inside group.spawn (because other thread may add more items to the vector, and vector contents are copied to extend), the code access the vector using index.
shankarke requested changes to this revision.Jan 16 2015, 11:14 AM
shankarke edited edge metadata.
shankarke added inline comments.
lib/Core/Resolver.cpp
285

If there is more than one archive having the same symbol name, the last file with the same symbol would be parsed. The archive library file which appears in link order should be the first one to get picked.

Weak symbols and common symbols have the same name across different archives. This doesnot appear to handle the case where the right weak symbol need to be chosen or the right common symbol be chosen.

This revision now requires changes to proceed.Jan 16 2015, 11:14 AM
shankarke accepted this revision.Jan 16 2015, 11:37 AM
shankarke edited edge metadata.

Thanks for the explanation. LGTM.

This revision is now accepted and ready to land.Jan 16 2015, 11:37 AM
ruiu added inline comments.Jan 16 2015, 2:32 PM
lib/ReaderWriter/FileArchive.cpp
274

I made a change as you suggested but eventually decided to roll it back because it didn't work on Windows. I don't fully understand why it sometimes raised an exception -- there might be a bug in std::future's move constructor? Anyways, the cost of referencing futures through unique_ptr should be negligible here.

atanasyan accepted this revision.Jan 16 2015, 2:40 PM
atanasyan edited edge metadata.

Anyway it is a nice patch.

LGTM

ruiu added inline comments.Jan 16 2015, 2:42 PM
lib/ReaderWriter/FileArchive.cpp
274

I think I understand the reason. A future returned by promise::get_future() has a reference to the promise. When a vector is extended and all elements are moved, the original promise becomes invalid (whose valid() would return false.) When that happens, future::get() fails with an exception.

My in-place comment doesn't submit for some reason, so I put it here:

lib/ReaderWriter/FileArchive.cpp:105

_promises[index].set_value(nullptr);

Here is also a concurrency issue.

_promises[index] returns a reference to the promise object stored in the vector. If before making set_value() the vector's memory is moved because of reallocation in the other thread (new element inserted), the returned reference will again be invalid as it was in the previous version of the code when capturing promise by reference.

One of the solutions is to avoid vector reallocations. So we need either to reserve some sufficient element count beforehand, or to change vector to deque, for example.

lib/ReaderWriter/FileArchive.cpp
105

Here is also a concurrency issue.

_promises[index] returns a reference to the promise object stored in the vector. If before making set_value() the vector's memory is moved because of reallocation in the other thread (new element inserted), the returned reference will again be invalid as it was in the previous version of the code when capturing promise by reference.

One of the solutions is to avoid vector reallocations. So we need either to reserve some sufficient element count beforehand, or to change vector to deque, for example.

ruiu added a comment.Jan 19 2015, 8:48 AM

Denis,

Thank you for reviewing! This code was submitted in r226336 and the final
code doesn't have the issues that you pointed out, I believe.

Rui,

Yeah, I see that you use locally constructed promise in r226336 and put it into the vector wrapped into unique_ptr. Good that you noticed that issue.

atanasyan resigned from this revision.Feb 3 2016, 12:30 AM
atanasyan removed a reviewer: atanasyan.
Eugene.Zelenko added a subscriber: Eugene.Zelenko.

Committed in r226336.