[lld-macho] Speed up markLive() From the trace report, it's one of the most substantial pieces (only after load-input and write-output) and it seems like an easy win here. Changes: - parallelize scanning symtab, and sections. - also add additional timescope Stats for 10 runs (on Mac, 2.4 GHz 8-Core Intel Core i9 | Memory: 32 GB 2667 MHz DDR4) N Min Max Median Avg Stddev x 10 19.77 23.35 21.51 21.569 1.1866053 + 10 19.9 20.09 20 19.999 0.062795966 Difference at 95.0% confidence -1.57 +/- 0.789477 -7.27897% +/- 3.66024% (Student's t, pooled s = 0.840231) Differential Revision: https://reviews.llvm.org/D110018
- Group Reviewers
Why do we need to define our own copy constructor? Isn't the compiler doing that for us already?
Shouldn't this method also have the mutex as well?
I think we might have a race condition here. If two different symbols pointing to the same isec and off happen to enter this function, we could end up writing the same value twice to worklist. It feels like the lock should be at the enqueue scope instead of the list here.
Doing so, I believe we can also remove all the locks on the isLive and markLive methods.
because the mutex makes it non-trivially copyable(ie., the default copy ctor won't work).
yes - missed this one
No, if the lock were to be put on the whole enqueue() then the whole thing would essentially be single-threaded (because all different sections would have to wait for the same lock).
We should minimise the locked region here.
I'm a bit ambivalent about this change. The typical way that parallel mark-sweep is implemented is via a work-stealing queue. That way we have one lock per thread, instead of all threads contending on one lock. Granted this diff is already an improvement, but perhaps it would be best to implement the optimal solution right off the bat...
why this change?
I think this lock isn't necessary... multiple concurrent calls to this method will still end up setting live to true
atomics might perform better here, assuming low contention
I was hoping for a easy fix here rather than an overhaul. But yeah, I guess it doesn't make a lot of sense to leave it half-done ...
Taking this off review queue to implement a proper concurrent mark-sweep
ConcatInputSection is no longer trivially copy-able.
Done - sorry, hard to switch back and forth with different naming style
Also, that was pretty fast... I guess you've implemented something similar before?
The queue is mostly from existing code :)
The mark-and-sweep is based on code I wrote ~3 years ago ... (which is to say, there might be bugs ...)
hardware_concurrency() seems like a good initializer
hm, this seems more like a Worker or Executor to me, each of which executes a number of tasks or jobs...
if start and end denoted half-open (instead of closed) intervals, would we still need skip?
also, how do you feel about creating an array of ArrayRefs here, instead of working with raw indices? That uses a few extra ints, but given that the number of threads in the pool is small, that shouldn't be an issue.
would prefer a more descriptive name... run / execute?
I'm kind of suspicious of this. It's marking sections as live based on the liveness of other sections, which are concurrently being marked as live. Depending on the order of writes, it may incorrectly conclude that a certain live section X is not live, and therefore not mark the sections that X points to as live.
I think the "no" makes it clearer :)
work is usually a noun, not a verb... maybe this could also be run() (or have run above take a default argument)
can we have a more descriptive name, like groupSize?
i'm kind of confused here. why are we comparing start to idx -- isn't start an index into the size array of jobs, whereas idx is the index of the Task vector of size poolSize? seems like we're comparing numbers on different scales...
same thing for idx and size
|38 ↗||(On Diff #379919)|
the rest of the codebase doesn't use the _ suffix; I think we can just use capacity here and have the getter be getCapacity()
|2 ↗||(On Diff #379919)|
Good point! (kind of surprised not a lot of tests were failing ...)
"idx" is the index of the Task vector, yes but it correlates to where its work items are:
So the division of labour is like this:
Task : start=0, end = start + d -1 = d -1 Task : start=d, end = d + d - 1 Task: start = d + d, end = d + d + d -1 .... Task[n]: start = n * d, end = start + d -1.
Race conditions often don't show up on small inputs :) I would recommend running dead_strip on a large program before and after this change, and checking that the outputs are identical.
I think the easiest way to fix this is to create a mapping of sections to their live support sections (basically reversing the pointer), and then have addSect visit the live support sections.
right but... what does start < idx mean here, and when do we expect it to be true? shouldn't it never be true, since n >= n * d for all nonnegative n and d?
Ah- I misunderstood what you were confusing about.
d could be zero, which is non-negative :)
ie., when we have fewer tasks than the number of workers, then you dont need to use all of the workers, when that happens, you just need the first [0, x) workers, and give each of them 1 task.
Similarly, end >= size is true when start== d == 0 (because its type is size_t , hence the -1 will ensure it).
(but I guess you're right that this is written in a much more convoluted way than it should be ... will fix)