<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.hoenzb
{mso-style-name:hoenzb;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Thanks for the analysis, Kevin! This is a great jumping off point for moving forward.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Unfortunately, I’m not sure the PM/addPassesToEmitMC issue is as straightforward as it seems. It does sound like there may be some duplicated effort that could
be done just once, but I think it might involve some restructuring at the TargetMachine level.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">addPassesToEmitMC actually does a couple of things. It does, as the name implies, add code generation passes to the PassManager. However, it also sets up
the MCObjectStreamer, which is necessarily module-specific and gets added to the PassManager. So it seems to me that optimizing this would at least require separating the pass creation from the object streaming creation. Whether that’s worth doing depends
heavily on where the time is being spent inside addPassesToEmitMC and whether or not it can be better optimized as it currently is structured.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">The topic of optimizing PM.run() came up at the BoF. That’s a broader issue than just MCJIT, so I imagine if you raise awareness of the problem there will
be a lot of interest in fixing it. Maybe send some profiling numbers to the llvmdev list with a general subject line like “PassManager::run() has a lot of overhead.”<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">There is definitely some low hanging fruit. In RuntimeDyldImpl::resolveRelocations() and SectionMemoryManager::applyMemoryGroupPermissions().<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">In the case of RuntimeDyldImpl::resolveRelocations(), the vast majority of the Sections being iterated over won’t actually have any pending relocations because
we remove relocations from the lists as we apply them. If we just kept a separate list of sections which contain pending relocations and removed sections from that list as appropriate it should fix that time sink.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">In the case of SectionMemoryManager::applyMemoryGroupPermissions(), we would only be hitting each section in the worst case scenario where each module is immediately
compiled after it is defined. Otherwise, the memory manager combines sections into common memory groups whenever possible (though the implementation may need some work). However, that still leaves a glaring issue that this function is doing redundant work.
Namely, it is reapplying permissions to memory groups that in most cases already have the permissions it is setting. Again, it should be trivial manage separate data structures to track which memory groups need permissions applied and which do not.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">With regard to SectionMemoryManager, however, I feel I should mention that it is only intended as a reference implementation to get people up and running, and
it is my expectation that many clients will want to implement their own memory manager to fine tune performance in accordance with their particular workload characteristics. Even so, there’s no reason we shouldn’t fix obvious problems in the reference implementation.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">BTW, another bit of low hanging fruit would be to turn off the module verifier. The parameter to disable it (in the call to addPassesToEmitMC) is hard-coded
to ‘false’ in MCJIT right now.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Now, having said all this, I need to tell you that based on my current priorities I don’t have time to take on any of this. However, I’d be more than happy
to review patches if someone else has time to do the work.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">-Andy<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Yaron Keren [mailto:yaron.keren@gmail.com]
<br>
<b>Sent:</b> Tuesday, November 19, 2013 3:54 AM<br>
<b>To:</b> Kevin Modzelewski; Kaylor, Andrew<br>
<b>Cc:</b> <llvmdev@cs.uiuc.edu><br>
<b>Subject:</b> Re: [LLVMdev] Some MCJIT benchmark numbers<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">The pass manager is re-created in emitObject on every call.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Andy, is that needed or can we create the PM in MCJIT constructor and keep it around?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Yaron<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">2013/11/19 Kevin Modzelewski <<a href="mailto:kmod@dropbox.com" target="_blank">kmod@dropbox.com</a>><o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<p class="MsoNormal">So I finally took the plunge and switched to MCJIT (wasn't too bad, as long as you remember to call InitializeNativeTargetDisassembler if you want disassembly...), and I got the functionality to a point I was happy with so I wanted to test
perf of the system. I created a simple benchmark and I'd thought I'd share the results, both because I know I personally had no idea what the results would be, and because it seems like there's some low-hanging fruit to improve performance.<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">My JIT is currently structured as creating a new module per function it wants to jit; I had experimented with using an approach where I had an "incubator module" where all IR starts, and then on-demand extract it to "compilation modules"
when I want to send it to MCJIT, but my experience was that this wasn't very helpful. (My goal was to enable cross-function optimizations such as inlining, but there's no easy way [and might not even make sense] to run module-level optimizations on a single
function.)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">The benchmark I set up is a simple REPL loop, where the input is a pre-parsed no-op statement. I put this in a loop and measured the amount of time it took, and tested it at 1k iterations and 10k iterations. This includes my IR-generation,
but my expectation is that that should be negligible compared to the MCJIT time (confirmed through profiling). The absolute numbers are from a Release build with asserts turned off (this made a big difference), and the percentages are from a Release+Profiling
build.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">For 1k iterations, the test took about 640ms on my desktop machine, ie 0.64ms per module. Looking at the profiling results, it looks like about 47% of the time is spent in PassManagerImpl::run, and another 47% is spent in addPassesToEmitMC,
which feels like it could be avoided by doing that just once. Of the time spent in PassManagerImpl::run, about 35% is spent in PassManager overhead such as initializeAnalysisImpl() / removeNotPreservedAnalysis() / removeDeadPasses().<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">For 10k iterations, the test took about 12.6s, or 1.26ms per module, so there's definitely some slowdown happening. Looking at the profiling output, it looks like the main difference is the appearance of MCJIT::finalizeLoadedModules(),
which ultimately calls RuntimeDyldImpl::resolveRelocations() and SectionMemoryManager::applyMemoryGroupPermissions(), both of which iterate over all memory sections leading to quadratic overhead. I'm not sure how easy it would be, but it seems like there
could be single-module variants of these apis that could cut down on the overhead, since it looks like MCJIT knows what modules need to be finalized but doesn't pass this information to the dyld / memory manager.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">My overall takeaway from these numbers is pretty good: they're good enough for where my JIT is right now, and it seems like there's some relatively-straightforward work that can be done to make them better. I'm curious what other people
think.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#888888"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#888888">Kevin<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">
http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><o:p></o:p></p>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</body>
</html>