<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Nov 23, 2016 at 4:53 PM, Sean Silva <span dir="ltr"><<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span class="gmail-">On Wed, Nov 23, 2016 at 6:31 AM, Rafael Espíndola <span dir="ltr"><<a href="mailto:rafael.espindola@gmail.com" target="_blank">rafael.espindola@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Interesting. Might be worth giving a try again to the idea of creating<br>
the file in anonymous memory and using a write to output it.<br></blockquote><div><br></div></span><div>I'm not sure that will help. Even the kernel can't escape some of these costs; in modern 64-bit operating systems when you do a syscall you don't actually change the mappings (TLB flush would be expensive), so the cost of populating the page tables in order to read the pages is still there (and hence the serialization point remains).</div></div></div></div></blockquote><div><br></div><div>I looked a bit more closely at this. In current linux, the actual faulting doesn't seem like it will have contention unless it needs to do memory allocation for the page table structures (but even then, linux's memory allocation is hopefully pretty optimized and scalable). The serialization point is when the kernel VM data structures need to be updated (NOT the hardware page tables which are usually populated lazily), which generally will only happen inside the mmap call.</div><div><br></div><div>This should mean that the primary serialization points in the kernel will be:</div><div>1. during the mmap call on any file</div><div>2. depending on where the kernel maps each input file, during the first accesses to a file to allocate page table structures (but that should be pretty scalable)</div><div>3. allocating the output files (this should be pretty scalable too since it is just memory allocation)</div><div><br></div><div>A simple test on my machine at home (i7-6700HQ CPU @ 2.60GHz) shows about 90ms to fill a 1GB buffer when it is freshly allocated (i.e., while the buffer is unfaulted and the kernel has to fault the memory during the memset) and about 45ms subsequent times (when the buffer is already faulted). Linux is using transparent huge pages though so that is with 2M pages. Turning off transparent hugepages so that 4k pages are used, the initial memset time goes up to about 280ms and subsequent times are still about 45ms. So with 4k pages, the slowdown is more than 6x for the initial faulting. Adding threads helps a bit, but cannot hide the fundamental work that the kernel has to do to allocate the memory.</div><div><br></div><div>4kpages-1thread-unfaulted 280ms</div><div>4kpages-2thread-unfaulted 160ms</div><div>4kpages-3thread-unfaulted 110ms</div><div>4kpages-4thread-unfaulted 100ms</div><div><br></div><div>2Mpages-1thread-unfaulted 90ms</div><div>2Mpages-2thread-unfaulted 60ms</div><div>2Mpages-3thread-unfaulted 65ms</div><div>2Mpages-4thread-unfaulted 70ms</div><div><br></div><div>4kpages-1thread-faulted 45ms</div><div>2Mpages-1thread-faulted 45ms</div><div><br></div><div>(note: these are pretty rough numbers; they are just to get a feel for the scaling)</div><div><br></div><div>Also, adding threads for this test case *after the pages are faulted in* only helps a little bit since it is mostly bottlenecked on DRAM bandwidth (it is just a simple memset test though, so that is expected).</div><div><br></div><div>This was on Linux. The OS overhead will probably be larger (potentially much larger) for Mac and Windows.</div><div><br></div><div>-- Sean Silva</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div> One alternative is to use multiple processes instead of multiple threads which would remove serialization point by definition (it also seems like it might be less invasive of a change, at least for the copying+relocating step).</div><div><br></div><div>One experiment might be to add a hack to pre-fault all the files that are used, so that you can isolate that cost from the rest of the link. That will give you an upper bound on the speedup that there is to get from optimizing this.</div><div>Pre-faulting the allocations removes the serialization bottleneck on the kernel VA, since after the page tables are fully populated, they become a read-only data structure and each core's hardware TLB walker can read it independently.<br></div><div><br></div><div>For example, you could change elf::link to optionally take a map from file paths to buffers, which will override the native filesystem. Then in main() (before calling elf::link) you can map and pre-fault all the input files (which can be found from a trace of a previous run or whatever). By timing the subsequent call to elf::link you can get the desired measurement.</div><div><br></div><div>The ability to pass in a map of buffers would allow other experiments that would be interesting. For example, the experiment above could be repeated with all the input buffers copied into a handful of 1GB pages. This would allow entirely eliminating the hardware TLB walking overhead for input buffers.</div><span class="gmail-HOEnZb"><font color="#888888"><div><br></div><div>-- Sean Silva</div></font></span><div><div class="gmail-h5"><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
Cheers,<br>
Rafael<br>
<br>
On 23 November 2016 at 02:41, Sean Silva via llvm-dev<br>
<div class="gmail-m_2245536423846730805gmail-HOEnZb"><div class="gmail-m_2245536423846730805gmail-h5"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>
><br>
><br>
> On Wed, Nov 16, 2016 at 12:44 PM, Rui Ueyama via llvm-dev<br>
> <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>
>><br>
>> LLD supports multi-threading, and it seems to be working well as you can<br>
>> see in a recent result. In short, LLD runs 30% faster with --threads option<br>
>> and more than 50% faster if you are using --build-id (your mileage may vary<br>
>> depending on your computer). However, I don't think most users even don't<br>
>> know about that because --threads is not a default option.<br>
>><br>
>> I'm thinking to enable --threads by default. We now have real users, and<br>
>> they'll be happy about the performance boost.<br>
>><br>
>> Any concerns?<br>
>><br>
>> I can't think of problems with that, but I want to write a few notes about<br>
>> that:<br>
>><br>
>>  - We still need to focus on single-thread performance rather than<br>
>> multi-threaded one because it is hard to make a slow program faster just by<br>
>> using more threads.<br>
>><br>
>>  - We shouldn't do "too clever" things with threads. Currently, we are<br>
>> using multi-threads only at two places where they are highly parallelizable<br>
>> by nature (namely, copying and applying relocations for each input section,<br>
>> and computing build-id hash). We are using parallel_for_each, and that is<br>
>> very simple and easy to understand. I believe this was a right design<br>
>> choice, and I don't think we want to have something like workqueues/tasks in<br>
>> GNU gold, for example.<br>
><br>
><br>
> Sorry for the late response.<br>
><br>
> Copying and applying relocations is actually are not as parallelizable as<br>
> you would imagine in current LLD. The reason is that there is an implicit<br>
> serialization when mutating the kernel's VA map (which happens any time<br>
> there is a minor page fault, i.e. the first time you touch a page of an<br>
> mmap'd input). Since threads share the same VA, there is an implicit<br>
> serialization across them. Separate processes are needed to avoid this<br>
> overhead (note that the separate processes would still have the same output<br>
> file mapped; so (at least with fixed partitioning) there is no need for<br>
> complex IPC).<br>
><br>
> For `ld.lld -O0` on Mac host, I measured <1GB/s copying speed, even though<br>
> the machine I was running on had like 50 GB/s DRAM bandwidth; so the VA<br>
> overhead is on the order of a 50x slowdown for this copying operation in<br>
> this extreme case, so Amdahl's law indicates that there will be practically<br>
> no speedup for this copy operation by adding multiple threads. I've also<br>
> DTrace'd this to see massive contention on the VA lock. LInux will be better<br>
> but no matter how good, it is still a serialization point and Amdahl's law<br>
> will limit your speedup significantly.<br>
><br>
> -- Sean Silva<br>
><br>
>><br>
>><br>
>>  - Run benchmarks with --no-threads if you are not focusing on<br>
>> multi-thread performance.<br>
>><br>
>><br>
>> ______________________________<wbr>_________________<br>
>> LLVM Developers mailing list<br>
>> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
>> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
>><br>
><br>
><br>
> ______________________________<wbr>_________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
><br>
</div></div></blockquote></div></div></div><br></div></div>
</blockquote></div><br></div></div>