Bck2BrwsrFlow - Revision history

JaroslavTulach at 09:41, 13 March 2013

JaroslavTulach — Wed, 13 Mar 2013 09:41:39 GMT

←Older revision		Revision as of 09:41, 13 March 2013
Line 38:		Line 38:
	continue X_22; // loop using direct jump		continue X_22; // loop using direct jump
	}		}
-	X_69: for (;;) {	+	X_69: for (;;) { IF: if (gt <= 69) {
	return;		return;
-	}}}} // close all for loops	+	}}}}} // close all for loops
	</source>		</source>

JaroslavTulach: /* Flaws */

JaroslavTulach — Wed, 13 Mar 2013 09:21:51 GMT

Flaws

←Older revision		Revision as of 09:21, 13 March 2013
Line 53:		Line 53:
	Another discovered problem revealed limitation of some [[JavaScript]] implementations. We are nesting the '''for''' loops one into another. If there is many of them, the code may get refused. For example [[Rhino]] complained when I tried to nest 268 loops. To mitigate that I limit the number of open loops to 64. When the limit is reached (only twice in the code I know: {{JDK\|java/util/zip\|Inflater}} and [[Bck2Brwsr]] code generation method) we close all the loops and start again. Fast backward jumps still work effectively when done ''locally'' - if there is a need to jump between two 64-'''for''' blocks, we need to use the old: ''gt = 22;'' '''continue X_0'''.		Another discovered problem revealed limitation of some [[JavaScript]] implementations. We are nesting the '''for''' loops one into another. If there is many of them, the code may get refused. For example [[Rhino]] complained when I tried to nest 268 loops. To mitigate that I limit the number of open loops to 64. When the limit is reached (only twice in the code I know: {{JDK\|java/util/zip\|Inflater}} and [[Bck2Brwsr]] code generation method) we close all the loops and start again. Fast backward jumps still work effectively when done ''locally'' - if there is a need to jump between two 64-'''for''' blocks, we need to use the old: ''gt = 22;'' '''continue X_0'''.

-	~~Anyone knows better way to simulate~~ '''goto''' in [[Java]]/[[JavaScript]]?	+	So much about simulating '''goto''' in [[Java]]/[[JavaScript]]. Better ideas?

	<comments/>		<comments/>

JaroslavTulach: /* Flaws */

JaroslavTulach — Wed, 13 Mar 2013 09:21:21 GMT

Flaws

←Older revision		Revision as of 09:21, 13 March 2013
Line 51:		Line 51:
	Using the current technique one can decide to optimize forward jumps or backward jumps. But not both. I am not aware of a language construct to optimize both forward/backward jumps without the control flow analyzer. Currently [[Bck2Brwsr]] optimizes for backward jumps as the common sense suggests that one needs them more when using '''while'''/'''for''' loops.		Using the current technique one can decide to optimize forward jumps or backward jumps. But not both. I am not aware of a language construct to optimize both forward/backward jumps without the control flow analyzer. Currently [[Bck2Brwsr]] optimizes for backward jumps as the common sense suggests that one needs them more when using '''while'''/'''for''' loops.

-	Another discovered problem revealed limitation of some [[JavaScript]] implementations. We are nesting the '''for''' loops one into another. If there is many of them, the code may get refused. For example [[Rhino]] complained when I tried to nest 268 loops. To mitigate that I limit the number of open loops to 64. When the limit is reached (only twice in the code I know: {{JDK\|java/util/zip\|Inflater}} and [[Bck2Brwsr]] code generation method) we close all the loops and start again. Fast backward jumps still work ''locally''~~. However~~ if there is a need to jump between two 64-'''for''' blocks, we need to use the old: ''gt = 22;'' '''continue X_0'''.	+	Another discovered problem revealed limitation of some [[JavaScript]] implementations. We are nesting the '''for''' loops one into another. If there is many of them, the code may get refused. For example [[Rhino]] complained when I tried to nest 268 loops. To mitigate that I limit the number of open loops to 64. When the limit is reached (only twice in the code I know: {{JDK\|java/util/zip\|Inflater}} and [[Bck2Brwsr]] code generation method) we close all the loops and start again. Fast backward jumps still work effectively when done ''locally'' - if there is a need to jump between two 64-'''for''' blocks, we need to use the old: ''gt = 22;'' '''continue X_0'''.

	Anyone knows better way to simulate '''goto''' in [[Java]]/[[JavaScript]]?		Anyone knows better way to simulate '''goto''' in [[Java]]/[[JavaScript]]?

	<comments/>		<comments/>

JaroslavTulach at 09:19, 13 March 2013

JaroslavTulach — Wed, 13 Mar 2013 09:19:02 GMT

←Older revision		Revision as of 09:19, 13 March 2013
Line 22:		Line 22:
	Thomas rather suggested to use [http://openjdk.java.net/projects/graal/ Graal's] flow analyzer. Especially to look into the '''GraphBuilderPhase''' class and see how it creates SSA form (using '''FrameStateBuilder''') and also '''BciBlockMapping''' class that is used for creating structured control flow from byte codes. We tried that, but it all seems too connected to the rest of the code and we were unsure how to extract that most easily.		Thomas rather suggested to use [http://openjdk.java.net/projects/graal/ Graal's] flow analyzer. Especially to look into the '''GraphBuilderPhase''' class and see how it creates SSA form (using '''FrameStateBuilder''') and also '''BciBlockMapping''' class that is used for creating structured control flow from byte codes. We tried that, but it all seems too connected to the rest of the code and we were unsure how to extract that most easily.

-	Still, we were in need of some speed up. As a poor man's solution I decided to eliminate the '''switch''' and optimize at least ~~forward~~ jumps. [[Bck2Brwsr]] now generates:	+	Still, we were in need of some speed up. As a poor man's solution I decided to eliminate the '''switch''' and optimize at least backward jumps. [[Bck2Brwsr]] now generates:

	<source lang="javascript">		<source lang="javascript">

JaroslavTulach at 09:17, 13 March 2013

JaroslavTulach — Wed, 13 Mar 2013 09:17:15 GMT

←Older revision		Revision as of 09:17, 13 March 2013
Line 43:		Line 43:
	</source>		</source>

-	The back jump (e.g. '''continue''' ''X_22'') is now a direct [[JavaScript]] control flow instruction that [[V8]] can optimize. Code using '''for'''-loops is going to be faster now. The forward jump still requires ~~using the~~ additional variable (e.g. gt = 69; '''break''' IF), but if it is ''near'', it may not need that many compare operations either.	+	The back jump (e.g. '''continue''' ''X_22'') is now a direct [[JavaScript]] control flow instruction that [[V8]] can optimize. Code using '''for'''-loops is going to be faster now. The forward jump still requires usage of additional variable (e.g. gt = 69; '''break''' IF), but if it is ''near'', it may not need that many compare operations either.

	Measurements showed about 30% speed up on our matrix multiplication benchmark (which is of course using '''for'''-cycles).		Measurements showed about 30% speed up on our matrix multiplication benchmark (which is of course using '''for'''-cycles).

JaroslavTulach at 09:16, 13 March 2013

JaroslavTulach — Wed, 13 Mar 2013 09:16:24 GMT

←Older revision		Revision as of 09:16, 13 March 2013
Line 43:		Line 43:
	</source>		</source>

-	The back jump (e.g. '''continue''' ''X_22'') is now a direct [[JavaScript]] control flow instruction that [[V8]] can optimize. Code using '''for'''-loops is going to be faster now. The forward jump still requires using the additional variable (e.g. gt = 69; '''break''' IF), but if it is ''near'', it may not need many ~~comparisons~~ operations either.	+	The back jump (e.g. '''continue''' ''X_22'') is now a direct [[JavaScript]] control flow instruction that [[V8]] can optimize. Code using '''for'''-loops is going to be faster now. The forward jump still requires using the additional variable (e.g. gt = 69; '''break''' IF), but if it is ''near'', it may not need that many compare operations either.

	Measurements showed about 30% speed up on our matrix multiplication benchmark (which is of course using '''for'''-cycles).		Measurements showed about 30% speed up on our matrix multiplication benchmark (which is of course using '''for'''-cycles).

JaroslavTulach: /* Flaws */

JaroslavTulach — Wed, 13 Mar 2013 09:15:38 GMT

Flaws

←Older revision		Revision as of 09:15, 13 March 2013
Line 51:		Line 51:
	Using the current technique one can decide to optimize forward jumps or backward jumps. But not both. I am not aware of a language construct to optimize both forward/backward jumps without the control flow analyzer. Currently [[Bck2Brwsr]] optimizes for backward jumps as the common sense suggests that one needs them more when using '''while'''/'''for''' loops.		Using the current technique one can decide to optimize forward jumps or backward jumps. But not both. I am not aware of a language construct to optimize both forward/backward jumps without the control flow analyzer. Currently [[Bck2Brwsr]] optimizes for backward jumps as the common sense suggests that one needs them more when using '''while'''/'''for''' loops.

-	Another discovered problem revealed limitation of some [[JavaScript]] implementations. We are nesting the '''for''' loops one into another. If there is many of them, the code may get refused. For example [[Rhino]] complained when I tried to nest 268 loops. To mitigate that I limit the number of open loops to 64. When the limit is reached (only twice in the code I know: {{JDK\|java/util/zip\|~~Infater~~}} and [[Bck2Brwsr]] code generation method) we close all the loops and start again. Fast backward jumps still work ''locally''. However if there is a need to jump between two 64-'''for''' blocks, we need to use the old: ''gt = 22;'' '''continue X_0'''.	+	Another discovered problem revealed limitation of some [[JavaScript]] implementations. We are nesting the '''for''' loops one into another. If there is many of them, the code may get refused. For example [[Rhino]] complained when I tried to nest 268 loops. To mitigate that I limit the number of open loops to 64. When the limit is reached (only twice in the code I know: {{JDK\|java/util/zip\|Inflater}} and [[Bck2Brwsr]] code generation method) we close all the loops and start again. Fast backward jumps still work ''locally''. However if there is a need to jump between two 64-'''for''' blocks, we need to use the old: ''gt = 22;'' '''continue X_0'''.

	Anyone knows better way to simulate '''goto''' in [[Java]]/[[JavaScript]]?		Anyone knows better way to simulate '''goto''' in [[Java]]/[[JavaScript]]?

	<comments/>		<comments/>

JaroslavTulach at 09:11, 13 March 2013

JaroslavTulach — Wed, 13 Mar 2013 09:11:19 GMT

←Older revision		Revision as of 09:11, 13 March 2013
Line 46:		Line 46:

	Measurements showed about 30% speed up on our matrix multiplication benchmark (which is of course using '''for'''-cycles).		Measurements showed about 30% speed up on our matrix multiplication benchmark (which is of course using '''for'''-cycles).
		+
		+	==== Flaws ====
		+
		+	Using the current technique one can decide to optimize forward jumps or backward jumps. But not both. I am not aware of a language construct to optimize both forward/backward jumps without the control flow analyzer. Currently [[Bck2Brwsr]] optimizes for backward jumps as the common sense suggests that one needs them more when using '''while'''/'''for''' loops.
		+
		+	Another discovered problem revealed limitation of some [[JavaScript]] implementations. We are nesting the '''for''' loops one into another. If there is many of them, the code may get refused. For example [[Rhino]] complained when I tried to nest 268 loops. To mitigate that I limit the number of open loops to 64. When the limit is reached (only twice in the code I know: {{JDK\|java/util/zip\|Infater}} and [[Bck2Brwsr]] code generation method) we close all the loops and start again. Fast backward jumps still work ''locally''. However if there is a need to jump between two 64-'''for''' blocks, we need to use the old: ''gt = 22;'' '''continue X_0'''.
		+
		+	Anyone knows better way to simulate '''goto''' in [[Java]]/[[JavaScript]]?
		+
		+	<comments/>

JaroslavTulach at 08:56, 13 March 2013

JaroslavTulach — Wed, 13 Mar 2013 08:56:39 GMT

←Older revision		Revision as of 08:56, 13 March 2013
Line 8:		Line 8:
	// and fallback		// and fallback
	case 22:		case 22:
-	// more instructions	+	// more instructions and test:
		+	if (smthng) gt = 69; continue;
	// and fallback		// and fallback
	case 67:		case 67:
	gt = 22; continue; // a loop		gt = 22; continue; // a loop
		+	case 69:
		+	return;
	}}		}}
	</source>		</source>

-	This ~~provided~~ almost 1:1 mapping between the [[ByteCode]] and its [[JavaScript]] representation (the values in the '''case''' statements are positions of the instruction in the [[ByteCode]] of each method). However [[~~Thomas_Würthinger~~]] (the most knowledgable person about [[V8]] I know) warned me that this is not going to be fast. Not only a jump requires assignment of a variable, '''continue'''-jump to beginning of the loop and yet another jump to the appropriate '''case'' statement. According to Thomas, '''switch''' statement is not well optimized in [[V8]] (as he considered it unimportant [[usecase]] when he worked on [[V8]]). I tried to convince Thomas to provide special [[V8]] optimization for the above construct - but no luck.	+	This provides almost 1:1 mapping between the [[ByteCode]] and its [[JavaScript]] representation (the values in the '''case''' statements are positions of the instruction in the [[ByteCode]] of each method). However [[Thomas Würthinger]] (the most knowledgable person about [[V8]] I know) warned me that this is not going to be fast. Not only a jump requires assignment of a variable, '''continue'''-jump to beginning of the loop and yet another jump to the appropriate '''case''' statement. According to Thomas, '''switch''' statement is not well optimized in [[V8]] (as he considered it unimportant [[usecase]] when he worked on [[V8]]). I tried to convince Thomas to provide special [[V8]] optimization for the above construct - but no luck.

-	Thomas suggested to use [http://openjdk.java.net/projects/graal/ Graal's] flow analyzer. Especially to look into the '''GraphBuilderPhase''' class and see how it creates SSA form (using '''FrameStateBuilder''') and also '''BciBlockMapping''' class that is used for creating structured control flow from byte codes. We tried that, but it all seems too connected to the rest of the code and we were unsure how to extract that most easily.	+	Thomas rather suggested to use [http://openjdk.java.net/projects/graal/ Graal's] flow analyzer. Especially to look into the '''GraphBuilderPhase''' class and see how it creates SSA form (using '''FrameStateBuilder''') and also '''BciBlockMapping''' class that is used for creating structured control flow from byte codes. We tried that, but it all seems too connected to the rest of the code and we were unsure how to extract that most easily.

-	Still, we were in need of some speed up. As a poor man's solution I decided to eliminate the '''switch''' and ~~optimze~~ at least forward jumps. [[Bck2Brwsr]] now generates:	+	Still, we were in need of some speed up. As a poor man's solution I decided to eliminate the '''switch''' and optimize at least forward jumps. [[Bck2Brwsr]] now generates:

	<source lang="javascript">		<source lang="javascript">
Line 28:		Line 31:
	}		}
	X_22: for (;;) { IF: if (gt <= 22) {		X_22: for (;;) { IF: if (gt <= 22) {
-	// more instructions	+	// more instructions and test:
		+	if (smthng) gt = 69; break IF;
	// and fallback		// and fallback
	}		}
Line 34:		Line 38:
	continue X_22; // loop using direct jump		continue X_22; // loop using direct jump
	}		}
-	}}} // close all for loops	+	X_69: for (;;) {
		+	return;
		+	}}}} // close all for loops
	</source>		</source>
		+
		+	The back jump (e.g. '''continue''' ''X_22'') is now a direct [[JavaScript]] control flow instruction that [[V8]] can optimize. Code using '''for'''-loops is going to be faster now. The forward jump still requires using the additional variable (e.g. gt = 69; '''break''' IF), but if it is ''near'', it may not need many comparisons operations either.
		+
		+	Measurements showed about 30% speed up on our matrix multiplication benchmark (which is of course using '''for'''-cycles).

JaroslavTulach: New page: Originally Bck2Brwsr simulated control flow (conditional and non-conditional '''goto''' statements in method bodies) via '''for'''/'''switch''' mapping: var...

JaroslavTulach — Wed, 13 Mar 2013 08:42:18 GMT

New page: Originally Bck2Brwsr simulated control flow (conditional and non-conditional '''goto''' statements in method bodies) via '''for'''/'''switch''' mapping: <source lang="javascript"> var...

New page

Originally [[Bck2Brwsr]] simulated control flow (conditional and non-conditional '''goto''' statements in method bodies) via '''for'''/'''switch''' mapping:

<source lang="javascript">
var gt = 0;
for (;;) { switch (gt) {
case 0:
// some instructions
// and fallback
case 22:
// more instructions
// and fallback
case 67:
gt = 22; continue; // a loop
}}
</source>

This provided almost 1:1 mapping between the [[ByteCode]] and its [[JavaScript]] representation (the values in the '''case''' statements are positions of the instruction in the [[ByteCode]] of each method). However [[Thomas_Würthinger]] (the most knowledgable person about [[V8]] I know) warned me that this is not going to be fast. Not only a jump requires assignment of a variable, '''continue'''-jump to beginning of the loop and yet another jump to the appropriate '''case'' statement. According to Thomas, '''switch''' statement is not well optimized in [[V8]] (as he considered it unimportant [[usecase]] when he worked on [[V8]]). I tried to convince Thomas to provide special [[V8]] optimization for the above construct - but no luck.

Thomas suggested to use [http://openjdk.java.net/projects/graal/ Graal's] flow analyzer. Especially to look into the '''GraphBuilderPhase''' class and see how it creates SSA form (using '''FrameStateBuilder''') and also '''BciBlockMapping''' class that is used for creating structured control flow from byte codes. We tried that, but it all seems too connected to the rest of the code and we were unsure how to extract that most easily.

Still, we were in need of some speed up. As a poor man's solution I decided to eliminate the '''switch''' and optimze at least forward jumps. [[Bck2Brwsr]] now generates:

<source lang="javascript">
var gt = 0;
X_0: for (;;) { IF: if (gt <= 0) {
// some instructions
// and fallback
}
X_22: for (;;) { IF: if (gt <= 22) {
// more instructions
// and fallback
}
X_67: for (;;) { IF: if (gt <= 67) {
continue X_22; // loop using direct jump
}
}}} // close all for loops
</source>