count pages in pdf without opening c# : Extract page from pdf document application software tool html windows web page online antocuni-thesis4-part304

Chapter 5
Tracing JITs in a nutshell
5.1 What is a tracing JIT compiler?
Therearetwogeneralwellknownrulestoconsiderwhentacklingtheproblemofcompiler
optimization:
 TheParetoprinciple[Wik10b],or80-20rule:the20%oftheprogramwillaccount
forthe80%oftheruntime. Inotherwords,whenexecutingaprogrammostofthe
timewillbespentinfewregions,calledhot-spots.
 TheFastPathprinciple[HH93]:itisusuallypossibletosplitexpensiveoperations
intoafast path andaslowpath: theformer r handlesthemostcommoncases and,
therefore,isexpectedtobeexecutedformosttimeandhastobehighlyoptimized,
whereasthelatterdealswiththeremainingcasesandisnotrequiredtobeparticularly
ecient.
Tracing JIT compilers are e designed to exploit t these rules to o produce better and d more
ecientcode.Inparticular,theyarebuiltonthefollowingbasicassumptions:
 programsspendmostoftheirruntimeinloops
 severaliterationsofthesamelooparelikelytotakesimilarcodepaths
The basicapproach ofatracingJITis togeneratemachine codeonly for thehotcode
paths of most frequently executedloops andtointerpretthe rest of theprogram. The
codeforthosecommonloopshoweverishighlyoptimized,includingaggressiveinliningof
thefastpaths.
32
Extract page from pdf document - application software tool:C# PDF Page Extract Library: copy, paste, cut PDF pages in C#.net, ASP.NET, MVC, Ajax, WinForms, WPF
Easy to Use C# Code to Extract PDF Pages, Copy Pages from One PDF File and Paste into Others
www.rasteredge.com
Extract page from pdf document - application software tool:VB.NET PDF Page Extract Library: copy, paste, cut PDF pages in vb.net, ASP.NET, MVC, Ajax, WinForms, WPF
Detailed VB.NET Guide for Extracting Pages from Microsoft PDF Doc
www.rasteredge.com
TracingoptimizationswereinitiallyexploredbytheDynamoproject[BDB00]todynam-
ically optimizemachinecodeatruntime. Itstechniqueswerethensuccessfullyexploited
toimplement aJITcompilerfor aJava VM[GPF06,GF06]. Subsequently y thesetrac-
ingJITs were discovered tobe a relatively simple way to implement JITcompilers for
dynamiclanguages[CBY
+
07]. ThetechniqueisnowbeingusedbybothMozilla’sTrace-
Monkey JavaScriptVM[GES
+
09]andhasbeentriedforAdobe’s TamarinActionScript
VM[CSR
+
09].
ThischaptergivesanoverviewofhowatypicaltracingJITcompilerworks:itisnotmeant
tobeanexhaustivesurveyonallthevariousstrategyadoptedbyknownimplementations,
but itisusefulto introducesome key concepts that areneededto understandthenext
chapter,whichexplainshowthePyPyJITcompilerworks.
5.2 Phases of execution
Typically,atracingvirtualmachinegoesthroughvariousphaseswhenexecutingaprogram:
Interpretation Whentheprogramstarts,everythingisinterpreted.Theinterpreterbe-
haveslikeastandardone,exceptfortheadditionofsomelightweightcodetoprole
theexecution,andinparticulartoestablishwhichloopsarerunmostfrequently.To
detect loops,itassociatesacountertoeachbackwardjump,whichis incremented
every timethejumpistaken. Whenthe e counterhits acertainthreshold,theVM
entersthetracing phase.
Tracing Duringthisphase,theinterpreterrecordsahistoryofalltheoperationsitexe-
cutes. Ittracesuntilithasrecordedtheexecutionofoneiterationofthehotloop
1
.
Todecide whenthis is the case,thetraceisrepeatedlycheckedas towhether the
interpreterisat aposition intheprogram whereit hadbeenearlier. Thehistory
recordedbythetraceriscalledatrace: itisalistofoperations,togetherwiththeir
actualoperandsandresults.ThetraceispassedtotheJITcompiler.
Compilation ThejoboftheJITcompileristoturnatraceintoecientmachinecode.
Thegeneratedmachinecodeisimmediatelyexecutable,andcanbeusedinthenext
iterationoftheloop.
Running In n this phase, thecode generated by y the JITcompiler is executed. Remind
thatatracerepresentaloop,thusthecoderunsrepeatedlyuntilsomeexitcondition
1
Incasethetracebecomestoolonganditslengthexceedsacertainthreshold,tracingisabortedand
thecontrolreturnstotheinterpreter. Thiscanoccure.g.intheunluckycaseinwhichtheiterationofthe
loopthatisbeingtracedisthelast,andthusthebackwardjumpisnevertaken.
33
application software tool:C# PDF Image Extract Library: Select, copy, paste PDF images in C#
C# users are able to extract image from PDF document page and get image information for indexing and accessing. C# Project: DLLs for PDF Image Extraction.
www.rasteredge.com
application software tool:VB.NET PDF Image Extract Library: Select, copy, paste PDF images
VB.NET PDF - Extract Image from PDF Document in VB.NET. Support PDF Image Extraction from a Page, a Region on a Page, and PDF Document in VB.NET Project.
www.rasteredge.com
istriggered. Whentheloopexits,theVMeithergoesback k intotheinterpretation
modeortransfersthecontroltoanotheralreadycompiledpieceofcode.
Being sequential, thetrace representsonly oneofthe many possible paths throughthe
code. Toensurecorrectness,thetracecontainsaguard d ateverypossiblepointwherethe
pathcouldhavefollowedanotherbranch,forexampleatconditionsandindirectorvirtual
calls. Whengeneratingthe e machine code,every guard is turnedinto aquick check to
guaranteethat the pathweareexecutingis stillvalid. Ifaguardfails,weimmediately
quitthemachinecodeandcontinuetheexecutionbyfallingbacktointerpretation.
Dependingonthetracingtechnique,every guardmighthaveanassociatedguardfailure
counter,similartotheloopcounterseenabove. Thefailurecounterisincrementedevery
timethe guardfails,untilithitsacertainthresholdandtheguardbecomeshot. Then,
weassumethattheparticularcodepathwhichstartsfromtheguardfailureis executed
oftenenoughtobeworthcompiling,andstarttracingagainfromthere. SeeSection5.6
formoredetails.
Figure5.1summarizethetransitionsbetweenthevariousphasesofatracingVM.
Interpretation
Tracing
Compilation
Running
hotloopdetected
enteringcompiledloop
coldguardfailed
guardfailure!hot
hotguardfailed
Figure 5.1: : VariousphasesofatracingVM
5.3 A deeper look at traces
Intheprevioussectionwehaveseenthatatracecontainsahistoryofalltheoperations
executed,plussomeexitconditionsthatarecalledguards. But,whichkindofoperations
34
application software tool:C# PDF Text Extract Library: extract text content from PDF file in
from PDF page. // Open a document. PDFDocument doc = new PDFDocument(inputFilePath); PDFTextMgr textMgr = PDFTextHandler.ExportPDFTextManager(doc); // Extract
www.rasteredge.com
application software tool:C# PDF Page Insert Library: insert pages into PDF file in C#.net
Support to create new page to PDF document in both web server-side application and Windows Forms. DLLs for Inserting Page to PDF Document.
www.rasteredge.com
aretraced?Andwhatisaguard,exactly?Givingapreciseanswerisdicult,asitdepends
onthedetailsoftheimplementation: however,wecanabstractsomepropertiesthatare
alwaysvalid.
To understand which kind of operations are e traced, we need d to recallthat tracing g is
performedby aninterpreter: everytimetheinterpreterexecutesthenext t instruction,it
alsoaddanentrytothetrace.Thus,wecanthinkofitasanunrolledversionoftheoriginal
code,wheretheoperationsrecordedinthehistorycorrespondtotheopcodesencodedin
thebytecode.
Moreover,foreachoperationwealsorecordits operands,as wellasitsresult. Foreach
of them, we record both the origin (e.g. if it is the result of a previous operation)
and its actualvalue (e.g., 42). Thus, , a typical l operation in the trace e could look like
c[42] = = add(a[30], b[12])
,wherea,bandcarevariables,whosevalueatthemoment
ofexecutionisindicatedinsidethesquarebrackets.
Tracesaremeanttobelinear,i.e.asequentiallistofalltheoperationsthatwereactually
executed,nomatterwheretheycomefrom. Thus,unconditionaljumpsarenotrecorded:
instead, we simply continue e the execution and record the subsequent operations. The
sameprincipleappliestodirectcalls,i.e.allcallsinwhichthetargetfunctionisstatically
known: thetracerdoesnot t recordthecallitself,buttheoperationsexecutedinsidethe
calledfunction:thisway,weautomaticallygettheeectofinlining.
Aslongasweonlyencounterunconditionaljumps,thereisonlyonepossiblecodepathto
betaken,sowearesurethatallthesubsequentiterationsoftheloopwillfollowthesame
one. Obviously,this s isnolongervalidassoonasweexecuteaconditional jump,i.e. a
jumpwhosetargetdestinationdependsontheruntimevalueofsomecondition. Toensure
acorrectbehaviour eachtimea conditionaljumpis encountered,a guard ischeckedto
ensurethattheconditionisstillvalid,andthusthatthecodepathwhichisbeingexecuted
isthecorrectone.
Thesametechniqueisusedtofollowcallswhosetargetisnotstaticallyknown.Inpartic-
ular,forcallsthroughafunctionpointer,whichwecallindirectcalls,theactualvalue of
thepointerisguarded,whileforvirtualmethodcallstheguardisontheexactclassofthe
receiverobject.
5.4 Example of tracing
Inthissection,weexamineaconcreteexampleoftracingtoseehowitworksandhowthe
resultingtracemightlooklike.
Figures 5.2 and 5.3showthe source code andthe corresponding bytecode for a simple
35
application software tool:VB.NET PDF Text Extract Library: extract text content from PDF
able to extract target text content from source PDF document and save extracted text to other file formats through VB.NET programming. This page will supply
www.rasteredge.com
application software tool:VB.NET PDF Page Delete Library: remove PDF pages in vb.net, ASP.
VB.NET PDF - How to Delete PDF Document Page in VB.NET. Please follow the sections below to learn more. DLLs for Deleting Page from PDF Document in VB.NET Class.
www.rasteredge.com
interface Operation {
int DoSomething(int x);
}
class IncrOrDecr implements Operation {
public int DoSomething(int x) {
if (x < 0)
return x-1;
else
return x+1;
}
}
class tracing {
public static void main(String argv[]) {
int N = 100;
int i = 0;
Operation op = new IncrOrDecr();
while (i < N) {
i = op.DoSomething(i);
}
System.out.println(i);
}
}
Figure5.2: Sourcecodeofthetracingexample
programsthatcontainsafrequentlyexecutedloop,avirtualmethodcallandaconditional
branchinginstruction. We e chose to use Java for these examples because it is a widely
knownprogramminglanguageandbecausealotofresearchontracingJITcompilershas
beendonefortheJVM.Moreover,byusingJavaweemphasizethatthischapterdescribes
thegeneraltechniquesabouttracingJITcompilersandnottheirsimplementationinPyPy,
whichisthesubjectofChapter6.
Forthepurposesofthisexample,wesetthehotloop threshold to3. Thus,thetracing
phasebeginsatthefourthiterationoftheloop,atline19intheJavacodeand46inthe
bytecode.
Figure 5.4 shows the recordedtrace: toease e thereading,it shows the individualJVM
instructionswhichareactuallyrecordedsidebysidewiththecorrespondingJavasource
code.Wecanseethatmostinstructionsarerecordedastheyareexecuted:however,fewof
themarenotrecordedatall,orhavebeenreplacedwithsomethingdierent.Inparticular:
 Conditionaljumpsarereplacedbyguardsthatchecktheexpectedconditionistrue.
Itisinterestingtonotethatconditionaljumpsthatareexpectednottobetakenare
36
application software tool:VB.NET PDF Page Insert Library: insert pages into PDF file in vb.
Easy to Use VB.NET APIs to Add a New Blank Page to PDF Document in VB.NET Program. DLLs for Adding Page into PDF Document in VB.NET Class.
www.rasteredge.com
application software tool:C# PDF Page Delete Library: remove PDF pages in C#.net, ASP.NET
C#.NET PDF Library - Delete PDF Document Page in C#.NET. Able to remove a single page from PDF document. Ability to remove a range of pages from PDF file.
www.rasteredge.com
class IncrOrDecr r {
...
public DoSomething(I)I
ILOAD 1
IFGE LABEL_0
ILOAD 1
ICONST_1
ISUB
IRETURN
LABEL_0
ILOAD 1
ICONST_1
IADD
IRETURN
}
class tracing {
...
public static main([Ljava/lang/String;)V
...
LABEL_0
ILOAD 2
ILOAD 1
IF_ICMPGE LABEL_1
ALOAD 3
ILOAD 2
INVOKEINTERFACE Operation.DoSomething (I)I
ISTORE 2
GOTO LABEL_0
LABEL_1
...
}
Figure5.3: Bytecodeofthetracingexample
37
Method
Javacode
Trace
Value
Main
while (i < N) f
ILOAD 2
3
ILOAD 1
100
IF
ICMPGE LABEL
1
false
GUARD
ICMPLT
i = op.DoSomething(i);
ALOAD 3
IncrOrDecrobj
ILOAD 2
3
INVOKEINTERFACE ...
GUARD
CLASS(IncrOrDecr)
DoSomething
if (x < 0)
ILOAD 1
3
IFGE LABEL
0
true
GUARD
GE
return x+1;
ILOAD 1
3
ICONST 1
1
IADD
4
IRETURN
Main
i = op.DoSomething(i);
ISTORE 2
4
g
GOTO LABEL
0
INSTR:Instructionexecutedbutnotrecorded
INSTR:Instructionaddedtothetracebutnotexecuted
Figure5.4: TraceproducedbythecodeinFigure5.2
replacedbyaguardthatcheckstheopposite condition: intheexample,
IF_ICMPGE
(\jumpifgreatorequal")isreplacedby
GUARD_ICMPLT
(\checklessthan")
 unconditionaljumps(
IRETURN
and
GOTO
intheexample)arejustremovedfromthe
trace
 virtualmethodcallsarereplacedbyaguardthatcheckstheexactclassofthereceiver,
andthecontentofthe methodisjustappendedtothetrace. Intheexample,the
INVOKEINTERFACE
to
DoSomething
isturnedintoa
GUARD_CLASS(IncrOrDecr)
,then
thebodyof
IncrOrDecr.DoSomething
isrecordedintothetrace
5.5 Generalization of the trace and code generation
Oncethetracehasbeencompleted,wecannallycompileit.Thegoalofthecompilation
phaseistogenerateecientmachinecodethatcanbeusedtoexecutethenextiterations
oftheloopthatwehavejusttraced.Rememberthatatracerepresentsasingle,concrete
iterationofthe loop,thus before actuallyemittingthemachinecode,we generalize the
traceinordertomakeitrepresentingawiderrangeofthenextiterations.
38
Asusuallyhappensinmostsituations,thereisatensionbetweenabstractionandeciency:
 ifwegeneralizetoomuch,wemightendupwithsub-optimalmachinecode
 ifwedon’tgeneralizeenough,wemightendupwithcodebloats,asthecodegenerated
istoospecializedandcannotbereusedforsomeormostofthesubsequentiterations
oftheloop
Sometimes,ndingtherightgeneralizationiseasy. Considerforexamplethetraceabove
inFigure 5.4: most t of the operandsofthe instructions areconcrete integers (e.g.,1,3,
4),thuswecangeneralizethemtovariablesoftype
int
andbesurethatthegenerated
codeisoptimalforallthenextiterations. However,sometimesthejobismorecomplex,
especiallyifwehavecomplexinheritancetrees: forexample,ifsomeconcretevalueseen
inthetraceisaninstanceof,say,class
A
,wemightwanttogeneratecodethataccepts
only
A
instances,orwemightwanttogeneratecodethatismorereusableandacceptsalso
instancesofsomesuperclassof
A
.
Theconcretestrategytosolvethisproblemvarybetweeneachimplementationofatracing
JIT.InSection6.5.1wewillseehowPyPydealswithit.
5.6 Linear traces vs. trace trees
So far,we have only seenexamples of linear traces,but there aresituations where the
generatedcodeisnotsucientlyecient. Forthenextexample,weconsidertheloopin
Figure5.5anditsbytecodeinFigure5.6,andassumethatthehotloopthreshold isagain
setto3.
Thetracingphasebeginswheni==3,andproducesthetraceshowninFigure5.7. As
wecansee,theconcreteiterationoftheloopfollowsthepaththroughthe
else
clauseof
the
if
,guardedbythe
GUARD_NE
condition.
However,itisclearthatwhilerunningtheguardwillsucceedonlyfortheodditerations
oftheloop: whenitfails,theVMswitchesbacktotheinterpretationphase(following
thecoldguardfailed arrowinFigure5.1),untiltheendoftheloop.Then,whenitistime
toreentertheloop,itreusesthealreadycompiledmachinecode,switchingagaintothe
runningphase(enteringcompiledloop)
Suchabehaviourisfarlessthanoptimal,becauseweneedtointerprethalfoftheiterations
throughtheloop,andmoreovertheswitchbetweenthetwophasesproducessomeoverhead.
Thishappensbecauseoneoftheoriginalassumptions,theFastPathPrinciple(seeSection
5.1)hasbeenviolated:inthiscase,thereisnotjustonefastpath,buttwothatareequally
important.
39
public static void trace_trees() {
int a = 0;
int i = 0;
int N = 100;
while(i < N) {
if (i%2 == 0)
a++;
else
a
*
=2;
i++;
}
}
Figure5.5: Tracingtreeexample
public static c void trace_trees() {
...
LABEL_0
ILOAD 1
ILOAD 2
IF_ICMPGE LABEL_1
ILOAD 1
ICONST_2
IREM
IFNE LABEL_2
IINC 0 1
GOTO LABEL_3
LABEL_2
ILOAD 0
ICONST_2
IMUL
ISTORE 0
LABEL_3
IINC 1 1
GOTO LABEL_0
LABEL_1
RETURN
}
Figure5.6: Bytecodefortrace
trees
Method
Javacode
Trace
Value
trace
trees
while (i < N) f
ILOAD 1
3
ILOAD 2
100
IF
ICMPGE LABEL
1
false
GUARD
ICMPLT
if (i%2 == 0)
ILOAD 1
3
ICONST
2
2
IREM
1
IFNE LABEL
2
true
GUARD
NE
a
*
=2;
ILOAD 0
3
ICONST
2
2
IMUL
6
ISTORE 0
6
i++;
IINC 1 1 1
4
g
GOTO LABEL
0
Figure5.7: TraceproducedbythecodeinFigure5.5
40
Todealwith such cases inanecientway, weneedto modify y thedatastructure that
containsthetraces,inordertosupportnotonlylineartraces,butalsotreesoftraces: if
weobservethataguardfailsoftenenough,itbecomeshotandwestarttracingagainfrom
there(thearrowguardfailure!hot inFigure5.1):then,wecompilethetraceandteach
theexistingmachinecodetocallthenewonewhenthatparticularguardfailsinthefuture
(i.e.,tofollowthehotguardfailed arrow).
Thisway,afteranintialphaseofwarm-up,allthehotpathsendsupbeingcompiled,and
thustheloopcanbeexecutedentirelyinmachinecode. Moreover,thistechniqueallows
the VMto automatically adapt itself tothebehaviour of the program,in case it varies
duringtheexecution,becauseifacoldpathstarts tobe executedvery often,it willbe
soonorlaterturnedintoahotpathandoptimizedaswell.
However,implementingthistechniqueinavirtualmachineliketheCLIandtheJVMis
noteasyatall,asitdoesnotoerdirectsupporttomodifythebehaviourofexistingcode.
AswewillseeinSection7.5,thisproblemthatwehadtofaceduringthedevelopmentof
theCLIbackendisoneofthemostchallenging.
41
Documents you may be interested
Documents you may be interested