CN101630268B - Synchronous optimization method and synchronous optimization equipment - Google Patents

Abstract

The invention provides a synchronization optimization method and equipment. The method includes the following steps: performing static program analysis on the compiled method, determining a synchronization method call point in the compiled method that does not need to perform a synchronization operation on a synchronization object according to the analysis result, and marking the synchronization method call point; The marked synchronous method call point compiles and generates a local code that allows no synchronization operation to be performed on the synchronization object of the synchronous method for the called synchronous method; executes the local code according to the marked synchronous method call point. The method and device for synchronous optimization proposed by the present invention have high flexibility and good scalability.

Description

Method and device for synchronous optimization

technical field

The present invention relates to computer technology, and more particularly to synchronization optimization technology.

Background technique

Java is a programming language that supports multi-threaded programming at the language level. It provides synchronization methods and synchronization statements based on the monitor mechanism for synchronization between threads. Each object in Java has a corresponding monitor. Threads can lock/unlock an object through synchronous method calls and synchronous statements. Only one thread can hold the lock on a certain monitor at a time. Others try to monitor this Threads that lock the monitor will be blocked until they acquire the lock on the monitor.

In order to ensure multi-thread safety, many classes in the Java standard library must be designed to be thread-safe, that is, synchronization operations need to be added when accessing shared data, such as java.util.Vector class, java.util.Hashtable class, etc., application Programs can simply and safely use the functions provided by these libraries in a multi-threaded environment. In addition to calling various thread-safe classes and methods in the Java standard library, programmers can also use synchronization methods and synchronization statements to achieve mutual exclusive access to shared data by multiple threads to ensure the correctness of the program. Although the synchronization mechanism in Java can easily ensure the safety of multi-threading, it also brings a very large overhead to the operation of multi-threaded programs. According to research, synchronization overhead usually accounts for 5%-10% of the total execution time; in a test of Marmot (a Java optimizing compiler), 5 medium-sized single-threaded programs spent 26%-60% on synchronization. %time. Therefore, it is very important to carry out synchronization optimization.

Synchronization optimization aims to reduce the overhead of synchronization operations and improve the overall performance of the program. In order to reduce the overhead of synchronization operations, some methods directly improve the implementation of synchronization primitives, such as thin lock technology and lock reservation technology. There are also some methods that use static program analysis techniques to automatically analyze and eliminate unnecessary synchronization operations, such as lock cancellation (lock elimination) technology and lock coarsening (lock coarsening, lock coalescence) technology. Lock cancellation technology uses escape analysis (escape analysis) technology to determine thread-local (thread-local) objects, and then cancels the synchronization operations on these objects. The lock coarsening technology merges some multiple synchronization operations that act on the same synchronization object. After the merger, the range of the code area to be synchronized will increase, which will cause a decrease in program concurrency in a multi-threaded environment, especially in When the number of threads is very large, the impact on concurrency will be more obvious.

Therefore, a synchronization optimization scheme with good flexibility and scalability and little impact on concurrency is needed at present.

Contents of the invention

In order to solve one of the above-mentioned problems, the present invention proposes a synchronization optimization method, which includes the following steps: performing static program analysis on the compiled method, and determining a synchronization method in the compiled method that does not need to perform a synchronization operation on the synchronization object according to the analysis result call point, and mark the synchronization method call point; according to the marked synchronization method call point, compile and generate a local code that allows not to perform a synchronization operation on the synchronization object of the synchronization method; according to the The marked synchronous method call site executes the native code.

According to an embodiment of the present invention, the step of performing static program analysis on the compiled method to determine a synchronization method call point that does not need to perform a synchronization operation on a synchronization object includes: merging adjacent synchronization areas and/or functions on the same synchronization object Or a nested synchronization area, determining a synchronization method call point included in the merged synchronization area as the redundant synchronization method call point.

According to an embodiment of the present invention, the step of performing static program analysis on the compiled method to determine the call point of the synchronization method that does not need to perform a synchronization operation on the synchronization object includes: determining the call point of the object according to whether the object is shared among multiple threads Whether the synchronous method call point is a synchronous method call point that does not need to perform a synchronous operation on the synchronization object.

According to an embodiment of the present invention, according to whether the object is shared between multiple threads, the step of determining whether the synchronization method call point for the object is a synchronization method call point that does not need to perform a synchronization operation on the synchronization object includes: if the object is only in the If the object is accessed in the thread that created the object, the synchronization method call point acting on the object is determined as the synchronization method call point that does not need to perform a synchronization operation on the synchronization object.

According to an embodiment of the present invention, the step of compiling and generating a local code for the synchronization method according to the marked synchronization method call point that allows not to perform a synchronization operation on the synchronization object of the synchronization method includes: according to the marked synchronization method call point is Compilation of the synchronized method generates a normal version of the synchronized method and an unsynchronized version of the synchronized method, wherein the unsynchronized version of the synchronized method includes local code.

According to an embodiment of the present invention, the step of compiling and generating a local code that allows no synchronization operation on the synchronization object of the synchronization method for the synchronization method called by the marked synchronization method call point includes: according to the synchronization method of the mark The call point compiles and generates a branch version of the synchronization method for the synchronization method, and inserts an instruction for setting marking information before the marked synchronization method call point. Wherein the branch version of the synchronization method is obtained through the following steps: inserting an instruction for obtaining tag information and an instruction for clearing the tag at the entry of the synchronization method; inserting a branch instruction before the synchronization operation acting on the synchronization object of the synchronization method , the branch instruction judges the obtained flag information, if the flag information is true, jump to after the synchronization operation, and if the flag information is false, execute the synchronization operation.

According to an embodiment of the present invention, the step of executing the local code includes: when executing a synchronous method call point, if the synchronous method call point is a marked synchronous method call point, calling the asynchronous version of the local code, If the synchronous method call point is an unmarked synchronous method call point, then call the normal version of the native code.

According to an embodiment of the present invention, the step of executing the native code includes: calling the local code of the branch version according to the flag information set before the synchronous method call point when execution reaches the synchronous method call point.

According to an embodiment of the present invention, when one of the following situations occurs in the static program analysis of the compiled method, the step of determining the synchronization method call point as a synchronization method call point that does not need to perform a synchronization operation on the synchronization object is not performed: acting on the same synchronization Between adjacent synchronization method call points and synchronization operations on the object include synchronization operations acting on other objects; between adjacent synchronization method call points and synchronization operations acting on the same synchronization object include access variable volatile Operation of data; the call point of the adjacent synchronization method acting on the same synchronization object and the synchronization operation contain static unresolvable access or method call; the call of the adjacent synchronization method acting on the same synchronization object There is a loop between the point and the synchronization operation; between the adjacent synchronization method call point and the synchronization operation acting on the same synchronization object, there are operations with inconsistent locking times, and the control flow graph CFG to which the operations with inconsistent locking times belong Each predecessor node of a node is locked a different number of times.

The invention also proposes a synchronous optimization device, which includes an analysis module, a compilation module and an execution module. Wherein, the analysis module is used to perform static program analysis on the compiled method, determine the synchronization method call points in the compiled method that do not need to perform synchronization operations on the synchronization object according to the analysis results, and mark the synchronization method call points ; The compiling module is used to compile and generate a local code that allows not to perform a synchronization operation on the synchronization object of the synchronization method according to the synchronization method call point of the mark for the synchronization method called by it; A synchronous method call site executes the native code.

The method and device for synchronous optimization proposed by the present invention have high flexibility and good scalability.

Description of drawings

The above and/or additional aspects and advantages of the present invention will become apparent and easy to understand from the following description of the embodiments in conjunction with the accompanying drawings, wherein:

Fig. 1 is a flow chart of a synchronization optimization method according to an embodiment of the present invention;

Fig. 2 is a schematic diagram of a code version of a synchronization method according to an embodiment of the present invention;

Fig. 3 is a schematic diagram of a dual-version algorithm according to an embodiment of the present invention;

Fig. 4 is a schematic diagram of a branch version algorithm according to an embodiment of the present invention;

FIG. 5 is a schematic diagram of a synchronization optimization device according to an embodiment of the present invention;

Fig. 6 is a schematic diagram of throughput comparison when method inlining is not used according to an embodiment of the present invention;

Fig. 7 is a schematic diagram of throughput comparison after inlining using methods according to an embodiment of the present invention.

Detailed ways

Embodiments of the invention are described in detail below, examples of which are illustrated in the accompanying drawings. The embodiments described below by referring to the figures are exemplary only for explaining the present invention and should not be construed as limiting the present invention.

While the synchronization optimization improves the synchronization overhead of the application program, it also consumes a large program analysis overhead. In order to balance the cost and benefit of synchronous optimization between processes, the present invention optimizes the calling point of the synchronous method, because: 1) in the actual code, the synchronous overhead spent by the synchronous method call accounts for a large proportion in the total synchronous overhead; 2) The analysis of the calling point of the synchronization method is relatively simple.

As an embodiment of the present invention, the synchronization object of a static synchronization method (i.e. class synchronization method) refers to the Class object corresponding to the class to which the method belongs; the synchronization object of a non-static synchronization method (i.e. instance synchronization method) refers to The this object of this method; the synchronization object of a synchronization statement refers to the object explicitly specified in the parentheses in the synchronization statement, that is, the O in the synchronization statement synchronized(O){...}.

At the bytecode level, the language-level synchronization statement is transformed into a sequence of instructions starting with the monitorenter (lock, that is, obtaining the monitor on the synchronization object) instruction and ending with the monitorexit (unlocking, that is, releasing the corresponding monitor) instruction. At the bytecode level, the synchronization method is set with the synchronization flag ACC_SYNCRONIZED in its constant pool entry. The method call instruction will check this flag. When calling a method with this flag (that is, when calling the synchronization method), the current thread will Get the monitor, and then call to execute the method body itself, regardless of whether the method call ends normally or abnormally, the monitor must be released. For ease of description, in the present invention, lock(O) and unlock(O) are collectively used to represent locking and unlocking of the object O, respectively.

As an embodiment of the present invention, a synchronization area acting on the object O refers to a code area formed by a sequence of continuously executed instructions from locking the object to unlocking the object.

The present invention proposes a synchronization method optimization framework for optimizing the synchronization method and its calling point. The basic idea is to analyze the calling point of the synchronization method that does not need to synchronize the synchronization object, and change it into a calling of the non-synchronized version of the synchronization method. , or a branched version that sets the tag information and calls the synchronous method. The framework consists of three stages: program analysis, compilation and execution. These three stages are briefly described below.

FIG. 1 is a flowchart of a synchronization optimization method 100 according to an embodiment of the present invention. As shown, the method 100 includes the following steps:

S101: Perform static program analysis on the compiled method, determine a synchronization method call point in the compiled method that does not need to perform a synchronization operation on a synchronization object according to the analysis result, and mark the synchronization method call point. This step is also called the program analysis phase.

As an embodiment of the present invention, when the compiler compiles a method in the Java program, static program analysis is performed on the compiled method, and according to the analysis result, it is determined which synchronization method call points in the compiled method are on its synchronization object The synchronous operations of are redundant and mark the sites of these synchronous method calls.

As an embodiment of the present invention, at this stage, different program analysis techniques can be used to analyze the compiled method to determine which synchronous method call points need to be marked. These analysis techniques can be based on lock coarsening technology or escape Analytical techniques, or other techniques.

As an embodiment of the present invention, the program analysis stage may adopt program analysis based on lock coarsening.

As an embodiment of the present invention, the main idea of synchronization optimization based on lock coarsening is: if thread T acquires the same lock while acquiring the lock but not releasing the lock, then the second lock acquisition operation is unnecessary; If thread T acquires and releases the same lock multiple times in a row, then these lock acquisition and lock release operations can be combined into a pair to reduce the number of lock operations.

As an embodiment of the present invention, the main method for analyzing and identifying synchronization method call points that do not need to be synchronized based on lock coarsening technology includes: merging adjacent synchronization regions or nested synchronization regions that act on the same synchronization object to reduce the cost of synchronization operations quantity. If you treat a synchronized method call as a special kind of synchronization area and merge it with an adjacent synchronization area or the synchronization area that contains it, then the synchronization method call site contained in the merged synchronization area is synchronized at its synchronization area. Synchronous operations on objects are redundant, allowing these call sites to be marked.

As an embodiment of the present invention, the program analysis stage may adopt program analysis based on escape analysis.

As an embodiment of the present invention, the main idea of synchronization optimization based on escape analysis is: if no other thread T' accesses O during the synchronization operation of a certain thread T on the object O, then the thread T's access to O can be deleted. Synchronous operation. In Java applications, some seemingly single-threaded programs often use the helper threads in the JDK. These programs are actually multi-threaded, but the helper threads do not share data with the single thread of the application; based on escape analysis, it will be identified Create some thread-local objects, which are only accessed by the thread that created them, and access to these objects does not need to be synchronized.

As an embodiment of the present invention, it is determined whether to delete the synchronization operation acting on the object according to whether the object is shared among multiple threads. If an object O is accessed only in the thread that created it (that is, O has not escaped from the thread), then all synchronization operations on O (including synchronization operations on O involved in O's synchronization method calls) are redundant , so that any invocation site of O's synchronous method can be marked.

It should be noted that the purpose of the program analysis phase is to analyze and identify the synchronization method call points that do not need to be synchronized. In addition to the program analysis technology and escape analysis technology based on lock coarsening, other technologies can also be used. This technique can be used by the program analysis phase of the synchronization method optimization framework described in the present invention as long as the technique can identify synchronous method call points that do not require synchronization.

S102: Compile and generate local code for the synchronization method according to the marked synchronization method call point, which allows no synchronization operation to be performed on the synchronization object of the synchronization method. This step is also called the compilation phase.

As an embodiment of the present invention, as required, a dual version strategy or a branch version strategy can be used to compile and generate different versions of local codes for the synchronization method.

As an embodiment of the present invention, the dual-version strategy may include: compiling and generating two versions of native code for a synchronous method, one is the normal version of the method, and the other is the asynchronous version of the method. As an embodiment of the present invention, the common version of a synchronization method refers to the local code generated by compiling the code of the method in a conventional manner. An unsynchronized version of a synchronized method is the native code generated by ignoring all synchronization operations on the method's synchronized object when the method's code is compiled.

As an embodiment of the present invention, the branch version strategy may include: compiling and generating a branch version of local code for a synchronization method, and inserting an instruction for setting marking information before the marked synchronization method call point. As an embodiment of the present invention, the branch version of a synchronous method refers to adding the following processing when compiling the code corresponding to the method: (a) inserting an instruction for obtaining tag information and an instruction for clearing the tag at the method entry; (b) For each synchronization operation acting on the synchronization object of the method, insert a branch instruction before it, the branch instruction judges the obtained flag information, if it is true, jump to after the synchronization operation, otherwise, Execute the sync operation.

FIG. 2 is a schematic diagram of different code versions of a synchronization method according to an embodiment of the present invention. Taking the instance synchronization method setSharedField() in Figure 2(a) as an example, Figure 2(b), (c) and (d) give the pseudocodes of its normal version, asynchronous version and branch version respectively. In (b) diagram, the this object needs to be locked and unlocked before and after executing the code in the method body; in (c) diagram, the code in the method body is directly executed; in (d) diagram, first obtain The mark information when the current method is called is marked, then clear the mark, and then add branch instructions to each lock and unlock operation on this object to ensure that these operations are executed when marked is false.

The dual version strategy and the branch version strategy have their own advantages and disadvantages. The dual-version strategy generates and saves two versions of local code for a synchronization method, while the branch version strategy only needs to generate and save one version of the local code for a synchronization method, so the double-version strategy requires additional space overhead and requires a virtual machine kernel Supports management of multi-version native code. On the other hand, the double-version strategy does not add a branch operation to determine whether the current invocation of the method is marked in each version of the local code generated by a synchronous method, while the branch version strategy adds additional such branch operations, so The branch version will affect the runtime performance of the program to a certain extent.

The dual-version strategy is suitable for situations where the number of marked synchronization methods is small but the calling frequency is high, and the branch version strategy is suitable for those situations where the number of marked synchronization methods is large and the calling frequency is low. When optimizing the synchronization method, you can decide whether to use the double version strategy or the branch version strategy according to the characteristics of the application, or design a heuristic algorithm to let the compiler automatically select the most appropriate strategy.

S103: Execute the local code according to the marked synchronous method call point, this step is called the execution phase. This phase is responsible for executing native code, and it varies slightly depending on whether the compilation phase adopts a double-version strategy or a branch-version strategy.

As an embodiment of the present invention, if the compiling stage adopts a dual-version strategy, when the invocation point of a synchronous method is executed, if the invocation point is marked in the program analysis stage, the local code of its asynchronous version is called, Otherwise, call its normal version of the native code.

As an embodiment of the present invention, if the compilation stage adopts a branch version strategy, when the call point of a synchronous method is executed, it is determined whether to set the mark information according to whether the call point has been marked in the program analysis stage, and then call its branch version of the native code.

The synchronization method optimization method described above includes three stages of program analysis, compilation and execution, and different strategies can be adopted in the first two stages. The following introduces several application examples of the synchronization method optimization framework, namely, the dual-version synchronization method optimization algorithm based on lock coarsening (referred to as the dual-version coarsening algorithm), and the branch version synchronization method optimization algorithm based on lock coarsening (referred to as the branch version coarsening algorithm). Algorithm), the double-version synchronization method optimization algorithm based on escape analysis (referred to as the dual-version escape algorithm), and the branch version synchronization method optimization algorithm based on escape analysis (referred to as the branch version escape algorithm), etc.

The double-version coarsening algorithm refers to the synchronization method optimization algorithm formed by using the lock coarsening analysis technology in the program analysis stage of the synchronization method optimization framework and the dual-version strategy in the compilation stage; the branch version coarsening algorithm refers to the program in the synchronization method optimization framework Synchronous method optimization algorithm formed by using lock coarse analysis technology in the analysis stage and branch version strategy in the compilation stage; double-version escape algorithm refers to the use of escape analysis technology in the program analysis stage of the synchronization method optimization framework and the dual-version strategy in the compilation stage. The synchronization method optimization algorithm; the branch version escape algorithm refers to the synchronization method optimization algorithm formed by using the escape analysis technology in the program analysis stage of the synchronization method optimization framework and the branch version strategy in the compilation stage.

As an embodiment of the present invention, the dual-version coarsening algorithm includes the following two parts:

1) Use the just-in-time compiler (JIT) of the Java virtual machine to analyze and transform the CFG (control flow graph) of each compiled method, and perform the following operations:

(a) Find adjacent synchronization method call points and synchronization operations that act on the same synchronization object and can be merged, merge them and mark the synchronization method call points in the merged area.

(b) In the synchronization statement block acting on a certain synchronization object, find the synchronous operations and synchronization method call points that can be combined on the synchronization object, delete these synchronization operations and mark these synchronization method call points.

2) Modify the component responsible for coordinating the compilation and execution of the Java method in the Java virtual machine, that is, the compilation pipeline and the virtual machine kernel VMCore. When executing a synchronous method call point, if the call point is not marked, check whether the normal version of the native code of the synchronous method exists, if it exists, execute it, otherwise start the JIT compilation pipeline to compile and generate the normal version for it Native code, and then execute it; if the call point is marked, check whether the asynchronous version of the native code of the synchronous method exists, if it exists, execute it, otherwise start JIT compilation to generate an asynchronous version of the native code, and then execute it .

As an embodiment of the present invention, if one of the following conditions exists between the adjacent synchronization method call site and the synchronization operation acting on the same synchronization object, the above optimization process cannot be performed:

Condition 1: Contains synchronous operations acting on other objects.

Condition 2: Operations involving access to volatile data.

Condition 3: Contains a static unresolvable access or method call.

Condition 4: contains loops.

Condition 5: A certain operation corresponds to a node in the CFG whose predecessor nodes are locked for different times.

Among them, conditions 1 to 3 are to prevent deadlocks that may occur in codes that acquire different locks in different orders after merging synchronization areas; conditions 3 to 4 are to prevent synchronization area merging from generating a large synchronization area and reduce the number of multi-threaded programs. The degree of concurrency; condition 5 is a complex situation, the probability of this situation is almost 0, so the algorithm does not deal with this situation.

As an embodiment of the present invention, the branch version coarsening algorithm utilizes the just-in-time compiler of the Java virtual machine to carry out program analysis and transformation to the CFG of each compiled method, and performs the following operations:

(a) Find adjacent synchronization method call points and synchronization operations that act on the same synchronization object and can be merged, merge them and insert a mark instruction before these synchronization method call points (this instruction sets the mark information to real).

(b) In the synchronization statement block acting on a synchronization object, find the synchronous operations and synchronization method call points that can be combined on the synchronization object, delete these synchronization operations, and insert a line before these synchronization method call points Flag command (this command sets flag information to true).

(c) If the currently compiled method is a marked synchronous method, generate a branched version of the native code for its transformation.

Like the double-version coarsening algorithm, if one of the conditions 1-5 exists between the adjacent synchronization method call site and the synchronization operation acting on the same synchronization object, the above optimization process cannot be performed.

As an embodiment of the present invention, the double-version escape algorithm and the branch version escape algorithm adopt escape analysis technology in the program analysis stage of the synchronization method optimization framework. If accessed by this thread, all synchronization method call points acting on the synchronization object O can be marked.

As an embodiment of the present invention, for the double-version escape algorithm, similar to the double-version coarsening algorithm, it is also necessary to modify the compilation pipeline and the virtual machine kernel VMCore. When executing a synchronous method call point, if the call point is not marked, check whether the normal version of the native code of the synchronous method exists, if it exists, execute it, otherwise start the JIT compilation pipeline to compile and generate the normal version of the native code , and then execute it; if the call point is marked, check whether the native code of the asynchronous version of the synchronous method exists, if it exists, execute it, otherwise start JIT compilation to generate the native code of the asynchronous version, and then execute it.

As an embodiment of the present invention, for the branch version escape algorithm, it is also necessary to insert a marking instruction mark() before each marked synchronization method call point, and compile each marked synchronization method into a branch version local code.

It should be noted that the optimization framework of the synchronization method proposed by the present invention is very flexible, and different strategies can be adopted in the first two stages, and different strategies can be combined into different optimization algorithms in each stage. Different combinations can be used according to different application requirements.

Besides high flexibility, another advantage of this framework is good scalability. In addition to lock coarsening and escape analysis, other strategies can be used in the program analysis phase of the framework. As long as the strategy can identify the synchronization method call point that does not need to be synchronized, it can be used as the first step in the synchronization method optimization framework. stage. Whenever a new strategy is added in the program analysis stage of the synchronization method optimization framework, this strategy can be combined with the two strategies in the compilation stage to generate a new optimization algorithm.

As an embodiment of the present invention, can be on the open source Java SE platform Apache Harmony, realize double-version coarsening algorithm and branch version coarsening algorithm with C++, introduce the realization of these two algorithms with examples respectively below.

The dual-version coarsening algorithm refers to the algorithm that adopts the lock coarsening technology in the program analysis phase of the synchronization method optimization framework, and adopts the dual-version strategy in the compilation phase. The algorithm includes two parts:

1) Use Harmony's just-in-time compiler to analyze and transform the CFG of each compiled method. The algorithm of this process is described as follows:

Input: CFG of the method currently being compiled

Output: Transformed CFG

Process: including two stages of program analysis and code transformation, the basic framework is as follows:

doubleOptimization(){

programAnalyse();//program analysis

transform();//code transformation

}

FIG. 3 is a schematic diagram of a dual-version algorithm according to an embodiment of the present invention. The O.syncCall() instruction is a call to the native code of the normal version of the synchronous method, and the O.Call() instruction is a call to the native code of the asynchronous version. Take the pseudo-CFG shown in Figure 3 (that is, the nodes in the figure may not necessarily be strict basic block nodes) as an example to briefly describe it.

programAnalyse(): Use JIT to perform program analysis on the intermediate representation of the currently compiled method, and find the adjacent synchronization method call points acting on the same synchronization object, such as O.syncCall1() and O.syncCall2() in Figure 3 And O.syncCall3 (), and synchronous operations, such as lock (O) and unlock (O) in Figure 3.

transform(): Perform code transformation on the intermediate representation of the currently compiled method according to the found synchronous method call points and synchronous operations. The specific process is as follows:

(a) Find the first of these adjacent synchronous method call sites and synchronous operations, such as O.syncCall1() in Figure 3, insert the lock (O) instruction before it; find these adjacent synchronous method calls The last one in the point and synchronization operation, such as O.syncCall3() in Figure 3, inserts the unlock(O) instruction after it.

(b) mark these synchronization method call points found in programAnalyse(), such as O.syncCall1(), O.syncCall2() and O.syncCall3() in Figure 3; delete these synchronizations found in programAnalyse() Operation, such as lock (O) and unlock (O) in Figure 3.

(c) For a basic block that is not in the synchronization area before the transcoding but is included in the synchronous area after the transcoding, such as basic block D in Figure 3, if after the transcoding, there is a The control flow edge from the basic block to the basic block, such as the control flow edge from the basic block C to the basic block D in Figure 3, then you need to insert a lock (O) instruction on this edge; The control flow edge from the basic block to the basic block not in the synchronization area, such as the control flow edge from basic block D to basic block E in Figure 3, needs to insert an unlock (O) instruction on this edge.

(d) Modify the compilation pipeline and the virtual machine kernel VMCore. When a synchronous method call point is executed, if the call point is not marked, then execute its normal version of the local code, and then execute it; if the call point is marked, as shown in O.syncCall1(), O in Figure 3 .syncCall2() and O.syncCall3() execute the local codes of their asynchronous versions, such as O.Call1(), O.Call2() and O.Call3() in Figure 3.

As an embodiment of the present invention, the branch version coarsening algorithm refers to the algorithm that adopts the lock coarsening technology in the program analysis stage of the synchronization method optimization framework, and adopts the branch version strategy in the compilation stage, and its algorithm is described as follows:

Input: CFG of the method currently being compiled

Output: Transformed CFG

Process: Including three stages of program analysis, code transformation and branch transformation, the basic framework is as follows:

branchOptimization(){

programAnalyse();//program analysis

transform();//code transformation

branch();//branch transformation

}

FIG. 4 is a schematic diagram of a branch version algorithm according to an embodiment of the present invention. The O.syncCall() instruction is a call to the native code of the normal version of the synchronization method, and the O.brCall() instruction is a call to the branch version native code. The pseudo CFG shown in Fig. 4 is taken as an example for a brief description below.

programAnalyse(): Use JIT to perform program analysis on the intermediate representation of the currently compiled method, and find the adjacent synchronization method call points acting on the same synchronization object, such as O.syncCall1() and O.syncCall2() in Figure 4 And O.syncCall3 (), and synchronous operations, such as lock (O) and unlock (O) in Figure 4.

transform(): Perform code transformation on the intermediate representation of the currently compiled method according to the found synchronous method call points and synchronous operations. The specific process is as follows:

(a) Find the first of these adjacent synchronous method call points and synchronous operations, such as O.syncCall1() in Figure 4, insert the lock (O) instruction before it; find these adjacent synchronous method calls The last one in the point and synchronization operation, such as O.syncCall3() in Figure 4, inserts the unlock(O) instruction after it.

(b) Insert a mark instruction mark() before the synchronous method call points found in programAnalyse(), such as O.syncCall1(), O.syncCall2() and O.syncCall3() in Figure 4, and delete them in programAnalyse These synchronous operations found in () are lock(O) and unlock(O) in Figure 4.

(c) For a basic block that is not in the synchronization area before the transcoding but is included in the synchronous area after the transcoding, such as basic block D in Figure 4, if after transcoding, there is a block that is never in the synchronous area The control flow edge from the basic block to the basic block, such as the control flow edge from basic block C to basic block D in Figure 4, needs to insert a lock (O) instruction on this edge. The control flow edge from the block to the basic block not in the synchronization area, such as the control flow edge from basic block D to basic block E in Figure 4, needs to insert an unlock (O) instruction on this edge.

branch(): If the currently compiled method is a synchronous method, transform it into a branch version. The specific process is as follows:

(a) Insert an instruction for obtaining mark information and an instruction for clearing the mark at the entry of the method, such as the marked=getMark() and clearMark() instructions in the entry block in Figure 4 .

(b) For the synchronization operation acting on the synchronization object of this method, such as lock (O1) and unlock (O1) in Figure 4, a branch instruction is inserted before it, and the branch instruction judges whether the obtained mark information marked is True, if true, jump to after the synchronous operation, otherwise, execute the synchronous operation.

It should be noted that, as an embodiment of the present invention, whether it is a double-version coarsening algorithm or a branch version coarsening algorithm, if the above-mentioned One of conditions 1 to 5 cannot be optimized. The basic blocks A, B and D in Fig. 3 and Fig. 4 cannot be optimized if any one of the above conditions 1-5 is satisfied.

FIG. 5 is a schematic diagram of a synchronization optimization device according to an embodiment of the present invention. As shown in the figure, the synchronization optimization device includes an analysis module, a compilation module and an execution module. in,

The analysis module is used for static program analysis of the compiled method, and according to the analysis result, it is determined that there is a synchronous method call point that does not need to be synchronized on the synchronization object in the compiled method, and the call point of the synchronous method is marked.

The compiling module is used for compiling and generating a local code for synchronous method compilation according to the marked synchronous method call point, allowing no synchronous operation to be performed on the synchronous object of the synchronous method.

The execution module is used to execute the local code according to the marked synchronous method call point.

The synchronization method optimization method and equipment proposed by the present invention mainly have the following three advantages:

First, the synchronization method optimization method and equipment of the present invention are highly flexible, and can freely combine different strategies at each stage to generate different optimization algorithms according to different requirements.

Second, the synchronization method optimization method and device of the present invention have good scalability, as long as a program analysis method can identify synchronization method call points that do not need to be synchronized, it can be applied to the first synchronization method optimization framework stage.

Third, the optimization algorithm designed on the basis of the synchronization method optimization method and equipment of the present invention is a synchronization optimization algorithm between processes, which can not only delete a large number of synchronization operations that cannot be deleted by the synchronization algorithm in the process, but also use the synchronization optimization algorithm in the process. The cost of the algorithm is close to the optimization effect of the inter-procedural algorithm, which alleviates the contradiction between the cost and the optimization effect.

The inventor realized the dual-version coarsening algorithm and the branch-version coarsening algorithm based on the synchronization method optimization framework on the open source Java SE platform Apache Harmony, and the framework can be similarly applied to other Java virtual machines. The inventor used SPECjbb2005 as a test program to test the realization of the synchronization method optimization algorithm.

Table 1 shows the number of various synchronization operations in SPECjbb2005, where static and dynamic represent the number of various synchronization operations counted by compile-time analysis and run-time analysis respectively, and before inline and after inline represent respectively The number of various synchronization operations in SPECjbb2005 before and after method inlining is performed. Static compile-time analysis only analyzes each method in the application program once. It cannot accurately reflect the number of various synchronization operations performed by the program during actual runtime, but it can reflect how many opportunities exist for static optimization in SPECjbb2005; and The information collected and counted by dynamic runtime analysis (dynamic columns) can accurately reflect the number of various synchronization operations performed by the program during actual runtime, thereby accurately reflecting the impact of the synchronization optimization algorithm on the performance of the entire program. Locks in the table indicates the number of all monitorenters, Unlocks indicates the number of all monitorexits, inserted Locks indicates the number of monitorenters inserted when lock coarsening technology is used, insertedUnlocks indicates the number of monitor exits inserted when lock coarsening technology is used, and removed Locks indicates optimization The number of monitorenters deleted by the algorithm, removed Unlocks indicates the number of monitorexits deleted by the optimization algorithm, Sync-Methods is the number of all synchronization methods, and optSync-Methods is the synchronization method of local codes with non-synchronized versions in the dual-version strategy quantity. For static information, sync method Callsites indicates the number of all synchronization method call sites, and opt sync methods Callsites indicates the number of all marked synchronization method call sites in the synchronization method optimization algorithm, that is, the number of optimized synchronization method call sites quantity. For dynamic information, sync method Callsites indicates the total number of times the synchronization method is executed, and opt syncmethods Callsites indicates the total number of times all optimized synchronization method call sites are executed.

Table 1 Statistics of various synchronous operations in SPECjbb2005

It can be seen from Table 1 that only the synchronization operations on the synchronization object in the marked synchronization method can be deleted before inlining, and the synchronization method optimization algorithm can delete 61 locking operations in the 61 synchronization methods, otherwise it cannot Remove any locking operations. After inlining, because a large number of synchronization methods are inlined into the caller's method to become a synchronization statement block, there are a lot of opportunities to delete the locking operation in the caller's method. As can be seen from the data in the table, After inlining, 431 locking operations can be removed, including 29 locking operations in 29 synchronized methods.

From the static information in Table 1, it can be seen that the number of optimized synchronization method call points is quite large no matter before or after inlining, indicating that there are a large number of synchronization method optimization opportunities before and after inlining. From the dynamic information in Table 1, it can be seen that the optimized synchronization method is actually executed quite a lot, no matter before or after inlining. Therefore, no matter whether the compiler supports inlining or not, the synchronization method optimization algorithm can achieve a better effect of optimizing the synchronization method.

It can also be seen from Table 1 that the number of synchronization operations inserted in order to ensure that the program semantics are not changed is much smaller than the number of deleted synchronization operations; the number of optimized synchronization methods is much smaller than the total number of synchronization methods There are many, and in general, the code of the synchronization method is very small. For the double-version coarsening algorithm, it means that the additional storage space overhead for saving the non-synchronized version of the local code will be very small.

Using the dual-version strategy generates two versions of native code for each synchronization method that needs to be optimized, requiring some additional storage space overhead.

Table 2 shows the storage space of the local code consumed by SPECjbb2005 in various situations, where none indicates the storage space required by all local codes when the method is not inlined and the double-version coarsening algorithm is not used during execution, and none&syncOpt indicates the execution The storage space required by all native code when not doing method inlining but using the double version coarsening algorithm. From the data shown in the table, it can be seen that the additional storage space overhead generated by the dual-version strategy is only 83324 bytes when inlining is not used, which only increases the storage space by about 5.6%. inline in the table indicates the storage space required by all native codes when method inlining is performed but does not use the dual-version coarsening algorithm, and inline&syncOpt indicates the storage space required by all local codes when method inlining is performed and the dual-version coarsening algorithm is used, as shown in the table From the data shown in , it can be seen that when the method is inlined, the additional storage space overhead generated by the double-version strategy is only 114428 bytes, which only increases the storage space by about 7.5%. It can be seen that the additional storage overhead of SPECjbb2005 caused by the dual-version strategy is not large. If for some applications, the double-version algorithm will generate very large additional storage space overhead, you can consider using the branch version strategy.

Table 2 Local code storage space consumed by SPECjbb2005 in various situations (unit: byte)

The inventor constructed different versions of Java virtual machines to test SPECjbb2005. The platform used in the experiment was Intel(R) Core(TM) 2 Quad CPU Q6600 2.40GHz, 3GB memory, and the operating system was Windows XP. Part of the test results are shown in the figure 6 and Figure 7.

FIG. 6 is a schematic diagram of a comparison of throughput (bops: business operation per second) obtained by executing SPECjbb2005 with three Java virtual machines that do not use method inlining according to an embodiment of the present invention. Among them, none indicates that no synchronization optimization is applied during execution, branch indicates that the branch version coarse synchronization optimization algorithm is applied during execution, double indicates that the double version coarse synchronization optimization algorithm is applied during execution, improvement1 and improvement2 indicate that branch is relative to none and double respectively Throughput improvement over none. Rows 1 to 3 of the data table in the figure are respectively the virtual machine using no synchronization optimization (denoted as none), the virtual machine applying the branch version coarsening algorithm (denoted as branch), and the virtual machine applying the dual version coarsening algorithm. The machine (denoted as double) executes 6 sets of test results of SPECjbb2005. The last two rows in the data table are the throughput improvement rates of branch relative to none and double relative to none. Since the procedural lock coarsening algorithm of Stoodley et al. has almost no improvement on synchronization when method inlining is not used, it is not compared with it here. It can be seen from Figure 6 that both the branch version coarsening algorithm and the dual version coarsening algorithm can improve the throughput of SPECjbb2005, and the double version coarsening algorithm improves the throughput higher than the branch version coarsening algorithm, which is Because the branch version coarsening algorithm will add branch instructions in some synchronization methods to determine whether to perform synchronization operations, these branch instructions will consume running time, thereby affecting the improvement of throughput. However, the higher performance improvement of the dual-version coarsening algorithm comes at the cost of more compile-time and storage overhead.

Fig. 7 is a schematic diagram of the throughput comparison obtained by executing SPECjbb2005 using the inline Java virtual machine of four methods according to an embodiment of the present invention, wherein inline means that no synchronization optimization is applied during execution, and inline & Stoodley means that Stoodley etc. are applied during execution inline&branch indicates that the branch version coarsening synchronization optimization algorithm is applied during execution, inline&double indicates the test result of applying the double version coarsening synchronization optimization algorithm during execution, improvement1, improvement2, and improvement3 respectively indicate that inline&Stoodley is relative to inline, and inline&branch is relative to inline , The throughput improvement rate of inline&double relative to inline. Rows 1 to 4 of the data table in the figure are respectively the virtual machine using method inlining but not applying any synchronization optimization (denoted as inline), and the virtual machine applying Stoodley’s coarsening algorithm after inlining (denoted as inline&Stoodley ), the virtual machine (denoted as inline&branch) that applies the branch version coarsening algorithm after inlining, and the virtual machine that applies the double version coarsening algorithm after inlining (denoted as inline&double) execute six groups of test results of SPECjbb2005. The last three rows in the data table are the throughput improvement rates of inline&Stoodley relative to inline, inline&branch relative to inline, and inline&double relative to inline. It can be seen that the three synchronous optimization algorithms can improve the throughput, and the improvement brought by the double-version coarsening algorithm and the branch version coarsening algorithm is higher than that brought by the algorithm of Stoodley et al. It can be seen from Table 1 that the number of executions of synchronous method calls after inlining is reduced from 612136827 to 87182262. This is because most of the synchronous method call points are replaced by the method bodies of these synchronous methods after inlining. In addition, since the number of branch instructions for judging whether a synchronous operation needs to be performed by applying the branch version coarsening algorithm after inlining is significantly reduced, the impact of branch instructions brought by the branch version coarsening algorithm on performance is also reduced. As can be seen from Figure 7, inline&branch and inline&double have similar throughput improvement rates.

It can be seen from the improvement of the throughput of the branch version coarsening algorithm and the double version coarsening algorithm in Figure 6 and Figure 7 that the improvement of the two algorithms after inlining is higher than the corresponding improvement before inlining. This is mainly because: when inlining is not performed, the new synchronization area formed by the lock coarsening algorithm will contain operations such as method calls and returns, and even compilation of uncompiled synchronization methods, which lead to new synchronization areas Longer, which seriously affects the concurrency of multi-threaded programs. After inlining, since most of the synchronous method call points are replaced by the method body of the synchronous method, the method call and return in the new synchronous area formed by the lock coarsening algorithm, as well as the compilation of the uncompiled synchronous method, etc. significantly reduced so that new sync regions are relatively short and concurrency will improve.

Although the embodiments of the present invention have been shown and described, those skilled in the art can understand that various changes, modifications and substitutions can be made to these embodiments without departing from the principle and spirit of the present invention. and modifications, the scope of the invention is defined by the appended claims and their equivalents.

Claims (10)

1. A method of synchronization optimization, comprising the steps of:

performing static program analysis on the compiled method, determining a synchronous method calling point which does not need to perform synchronous operation on a synchronous object in the compiled method according to an analysis result, and marking the synchronous method calling point;

compiling and generating a local code which allows synchronous operation not to be executed on a synchronous object of the synchronous method according to the marked synchronous method calling point;

and executing the local code according to the marked synchronous method calling point.

2. The synchronization optimization method of claim 1, wherein the step of performing static program analysis on the compiled method and determining the calling points of the synchronization method without performing synchronization operation on the synchronization object comprises:

and merging adjacent synchronous areas and/or nested synchronous areas acting on the same synchronous object, and determining a synchronous method calling point contained in the merged synchronous area as the synchronous method calling point which does not need to carry out synchronous operation on the synchronous object.

3. The synchronization optimization method of claim 1, wherein the step of performing static program analysis on the compiled method and determining the calling points of the synchronization method without performing synchronization operation on the synchronization object comprises:

and determining whether the synchronous method call point of the object is a synchronous method call point without synchronous operation on the synchronous object according to whether the object is shared among a plurality of threads.

4. The synchronization optimization method of claim 3, wherein the step of determining whether the synchronization method call point for the object is a synchronization method call point that does not require a synchronization operation for a synchronization object based on whether the object is shared among a plurality of threads comprises:

and if the object is accessed only in the thread for creating the object, determining the synchronous method call point acting on the object as the synchronous method call point without synchronous operation on the synchronous object.

5. The synchronization optimization method according to claim 1, wherein the step of generating native code allowing not to perform synchronization operations on synchronization objects of the synchronization method according to the marked synchronization method call point for the compilation of the synchronization method called by the marked synchronization method call point comprises:

compiling a normal version of the synchronization method and an unsynchronized version of the synchronization method for the synchronization method according to the marked synchronization method call points,

wherein the unsynchronized version of the synchronization method includes native code generated by ignoring synchronization operations on synchronization objects of the synchronization method.

6. The synchronization optimization method according to claim 1, wherein the step of generating native code allowing not to perform synchronization operations on synchronization objects of the synchronization method according to the marked synchronization method call point for the compilation of the synchronization method called by the marked synchronization method call point comprises:

compiling and generating a branch version of the synchronous method for the synchronous method according to the marked synchronous method calling point, inserting an instruction for setting marking information in front of the marked synchronous method calling point,

wherein a branched version of the synchronization method is obtained by: inserting an instruction for obtaining mark information and an instruction for clearing marks at an entrance of the synchronization method; inserting a branch instruction before the synchronous operation acted on a synchronous object of the synchronous method, wherein the branch instruction judges the obtained marking information, if the marking information is true, jumping to the back of the synchronous operation, and if the marking information is false, executing the synchronous operation.

7. The synchronous optimization method of claim 5, wherein the step of executing the native code comprises:

when executing the synchronous method call point, if the synchronous method call point is the marked synchronous method call point, calling the local code of the asynchronous version, and if the synchronous method call point is the unmarked synchronous method call point, calling the local code of the common version.

8. The synchronous optimization method of claim 6, wherein the step of executing the native code comprises:

and when the synchronous method calling point is executed, calling the local code of the branch version according to the marking information instruction set in front of the synchronous method calling point.

9. The synchronization optimization method according to claim 1, wherein the step of determining the synchronization method call point as not requiring a synchronization operation on the synchronization object is not performed when one of the following occurs in the static program analysis of the compiled method:

the synchronization operation acted on other objects is included between the adjacent synchronization method calling points acted on the same synchronization object and the synchronization operation;

the operation of accessing variable data is included between the adjacent synchronous method calling points acting on the same synchronous object and the synchronous operation;

the adjacent synchronous method call points acting on the same synchronous object and the synchronous operation contain static unresolvable access or method call;

the adjacent synchronous method call points acting on the same synchronous object and the synchronous operation contain circulation;

the adjacent synchronous method call points acting on the same synchronous object and the synchronous operation comprise operations with inconsistent locking times, and the locking times of all precursor nodes of the control flow graph nodes to which the operations with inconsistent locking times belong are different.

10. A synchronous optimization device is characterized by comprising an analysis module, a compiling module and an execution module, wherein,

the analysis module is used for performing static program analysis on the compiled method, determining a synchronous method calling point which does not need to perform synchronous operation on a synchronous object in the compiled method according to an analysis result, and marking the synchronous method calling point;

the compiling module is used for compiling and generating a local code which allows synchronous operation not to be executed on a synchronous object of the synchronous method according to the marked synchronous method calling point;

the execution module is used for executing the local code according to the marked synchronous method calling point.

Images