Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Browse code

fiber optimization

  • Loading branch information...
commit a55449ee5fe9d4fad1b7de30520260d8785a2e8b 1 parent 1794372
Kresten Krab Thorup krestenkrab authored
10 pom.xml
@@ -23,6 +23,14 @@
23 23 </execution>
24 24 </executions>
25 25 </plugin>
  26 + <plugin>
  27 + <groupId>org.apache.maven.plugins</groupId>
  28 + <artifactId>maven-compiler-plugin</artifactId>
  29 + <configuration>
  30 + <source>1.5</source>
  31 + <target>1.5</target>
  32 + </configuration>
  33 + </plugin>
26 34 </plugins>
27 35 </build>
28 36 <dependencies>
@@ -52,4 +60,4 @@
52 60 <version>3.2</version>
53 61 </dependency>
54 62 </dependencies>
55   -</project>
  63 +</project>
90 src/kilim/java/kilim/Fiber.java
@@ -42,7 +42,9 @@
42 42 * One State object for each activation frame in the call hierarchy.
43 43 */
44 44 private State[] stateStack = new State[10];
45   -
  45 + private Object[] selfStack = new Object[10];
  46 + private int[] pcStack = new int[10];
  47 +
46 48 /*
47 49 * Index into stateStack and equal to depth of call hierarchy - 1
48 50 */
@@ -60,7 +62,9 @@
60 62 /*
61 63 * Special marker state used by pause
62 64 */
  65 + private static final int PAUSE_STATE_PC = 1;
63 66 private static final State PAUSE_STATE = new State();
  67 + private static final State EMPTY_STATE = new State();
64 68
65 69 /*
66 70 * Status indicators returned by down()
@@ -85,10 +89,6 @@
85 89 */
86 90 private static final int PAUSING__HAS_STATE = 3;
87 91
88   - static {
89   - PAUSE_STATE.pc = 1;
90   - }
91   -
92 92 public Fiber(Task t) {
93 93 task = t;
94 94 }
@@ -152,33 +152,14 @@ public int up() {
152 152 return NOT_PAUSING__NO_STATE;
153 153 } else {
154 154 stack[d] = null; // clean up
155   - pc = cs.pc;
  155 + pc = pcStack[d];
156 156 // if (debug) System.out.println("\nup(not pausing)" + this);;
157 157 // if (debug) ds();
158   - cs.releaseTo(this);
159 158 return NOT_PAUSING__HAS_STATE;
160 159 }
161 160 }
162 161 }
163 162
164   - private static final int STATE_POOL_SIZE = 10;
165   - int pool_count = 0;
166   - State[] pool = new State[STATE_POOL_SIZE];
167   -
168   - public final State allocState()
169   - {
170   - if (pool_count==0) return new State();
171   - return pool[--pool_count];
172   - }
173   -
174   - final void release(State s) {
175   - if (pool_count != STATE_POOL_SIZE) {
176   - pool[pool_count++] = s;
177   - s.self = null;
178   - }
179   - }
180   -
181   -
182 163 public final Fiber begin() {
183 164 return down();
184 165 }
@@ -219,7 +200,7 @@ public Fiber down() {
219 200 } else {
220 201 State s = stateStack[d];
221 202 curState = s;
222   - pc = (s == null) ? 0 : s.pc;
  203 + pc = (s == null) ? 0 : pcStack[d];
223 204 }
224 205 // if (debug) System.out.println("down:\n" + this);
225 206 // if (debug) ds();
@@ -262,16 +243,17 @@ static void ds() {
262 243 */
263 244 public int upEx() {
264 245 // compute new iStack.
265   - int is = task.getStackDepth() - 2; // remove upEx and convert to 0-based index.
  246 + final int is = task.getStackDepth() - 2; // remove upEx and convert to 0-based index.
266 247 State cs = stateStack[is];
267 248
268 249 for (int i = iStack; i >= is; i--) {
269 250 stateStack[i] = null; // release state
  251 + selfStack[i] = null; // release state
270 252 }
271 253
272 254 iStack = is;
273 255 curState = cs;
274   - return (cs == null) ? 0 : cs.pc;
  256 + return (cs == null) ? 0 : pcStack[is];
275 257 }
276 258
277 259 /**
@@ -282,16 +264,25 @@ public int upEx() {
282 264 public Object getCallee() {
283 265 assert stateStack[iStack] != PAUSE_STATE : "No callee: this state is the pause state";
284 266 assert stateStack[iStack] != null : "Callee is null";
285   - return stateStack[iStack + 1].self;
  267 + return selfStack[iStack + 1];
286 268 }
287 269
288   - private State[] ensureSize(int newsize) {
  270 + private void ensureSize(int newsize) {
289 271 // System.out.println("ENSURE SIZE = " + newsize);
  272 + int len = stateStack.length;
  273 +
290 274 State[] newStack = new State[newsize];
291   - System.arraycopy(stateStack, 0, newStack, 0, stateStack.length);
  275 + System.arraycopy(stateStack, 0, newStack, 0, len);
292 276 stateStack = newStack;
293   - return newStack;
294   - }
  277 +
  278 + Object[] newSelfStack = new Object[newsize];
  279 + System.arraycopy(selfStack, 0, newSelfStack, 0, len);
  280 + selfStack = newSelfStack;
  281 +
  282 + int[] newPCStack = new int[newsize];
  283 + System.arraycopy(pcStack, 0, newPCStack, 0, len);
  284 + pcStack = newPCStack;
  285 +}
295 286
296 287 /**
297 288 * Called by the generated code before pausing and unwinding its stack
@@ -299,8 +290,34 @@ public Object getCallee() {
299 290 *
300 291 * @param state
301 292 */
302   - public void setState(State state) {
  293 + public void setState(State state, Object self, int pc) {
303 294 stateStack[iStack] = state;
  295 + selfStack[iStack] = self;
  296 + pcStack[iStack] = pc;
  297 + isPausing = true;
  298 +// System.out.println("setState[" + + iStack + "] = " + this);
  299 + }
  300 +
  301 + public void setState(State state, int pc) {
  302 + stateStack[iStack] = state;
  303 + selfStack[iStack] = null;
  304 + pcStack[iStack] = pc;
  305 + isPausing = true;
  306 +// System.out.println("setState[" + + iStack + "] = " + this);
  307 + }
  308 +
  309 + public void setState(Object self, int pc) {
  310 + stateStack[iStack] = EMPTY_STATE;
  311 + selfStack[iStack] = self;
  312 + pcStack[iStack] = pc;
  313 + isPausing = true;
  314 +// System.out.println("setState[" + + iStack + "] = " + this);
  315 + }
  316 +
  317 + public void setState(int pc) {
  318 + stateStack[iStack] = EMPTY_STATE;
  319 + selfStack[iStack] = null;
  320 + pcStack[iStack] = pc;
304 321 isPausing = true;
305 322 // System.out.println("setState[" + + iStack + "] = " + this);
306 323 }
@@ -311,9 +328,10 @@ void togglePause() {
311 328 // upto date.
312 329
313 330 if (curState == null) {
314   - setState(PAUSE_STATE);
  331 + setState(PAUSE_STATE, PAUSE_STATE_PC);
315 332 } else {
316   - assert curState == PAUSE_STATE : "togglePause: Expected PAUSE_STATE, instead got: iStack == " + iStack + ", state = " + curState;
  333 + assert curState == PAUSE_STATE :
  334 + "togglePause: Expected PAUSE_STATE, instead got: iStack == " + iStack + ", state = " + curState;
317 335 stateStack[iStack] = null;
318 336 isPausing = false;
319 337 }
11 src/kilim/java/kilim/State.java
@@ -25,13 +25,6 @@
25 25 */
26 26
27 27 public class State {
28   - public int pc;
29   - public Object self;
30   -
31   - /**
32   - * @param fiber
33   - */
34   - void releaseTo(Fiber fiber) {
35   - fiber.release(this);
36   - }
  28 + //public int pc;
  29 + //public Object self;
37 30 }
70 src/kilim/java/kilim/analysis/CallWeaver.java
@@ -516,32 +516,41 @@ private void genSave(MethodVisitor mv, Label saveLabel) {
516 516 * the method weaver's list. This allows us to do a switch in the
517 517 * method's entry.
518 518 */
519   - if (stateClassName.equals(STATE_CLASS)) {
  519 + boolean is_simple_state = stateClassName.equals(STATE_CLASS);
  520 +
  521 + if (is_simple_state) {
  522 +
520 523 loadVar(mv, TOBJECT, methodWeaver.getFiberVar());
521   - mv.visitMethodInsn(INVOKEVIRTUAL, FIBER_CLASS, "allocState", "()" + D_STATE);
  524 +
  525 + if (!bb.flow.isStatic()) {
  526 + mv.visitInsn(ALOAD_0); // for state.self == this
  527 + }
  528 +
  529 + int pc = methodWeaver.getPC(this);
  530 + if (pc < 6) {
  531 + mv.visitInsn(ICONST_0 + pc);
  532 + } else {
  533 + mv.visitIntInsn(BIPUSH, pc);
  534 + }
  535 +
  536 + if (!bb.flow.isStatic()) {
  537 + methodWeaver.ensureMaxStack(3);
  538 + mv.visitMethodInsn(INVOKEVIRTUAL, FIBER_CLASS, "setState", "(Ljava/lang/Object;I)V");
  539 + } else {
  540 + methodWeaver.ensureMaxStack(2);
  541 + mv.visitMethodInsn(INVOKEVIRTUAL, FIBER_CLASS, "setState", "(I)V");
  542 + }
  543 +
  544 +
522 545 } else {
523 546 mv.visitTypeInsn(NEW, stateClassName);
524 547 mv.visitInsn(DUP); //
525 548 // call constructor
526 549 mv.visitMethodInsn(INVOKESPECIAL, stateClassName, "<init>", "()V");
527   - }
  550 +
528 551 // save state in register
529 552 int stateVar = allocVar(1);
530 553 storeVar(mv, TOBJECT, stateVar);
531   - // state.self = this if the current executing method isn't static
532   - if (!bb.flow.isStatic()) {
533   - loadVar(mv, TOBJECT, stateVar);
534   - mv.visitInsn(ALOAD_0); // for state.self == this
535   - mv.visitFieldInsn(PUTFIELD, STATE_CLASS, "self", D_OBJECT);
536   - }
537   - int pc = methodWeaver.getPC(this);
538   - loadVar(mv, TOBJECT, stateVar); // state.pc
539   - if (pc < 6) {
540   - mv.visitInsn(ICONST_0 + pc);
541   - } else {
542   - mv.visitIntInsn(BIPUSH, pc);
543   - }
544   - mv.visitFieldInsn(PUTFIELD, STATE_CLASS, "pc", D_INT);
545 554
546 555 // First save bottom stack into state
547 556 int i = getNumBottom() - 1;
@@ -585,9 +594,32 @@ private void genSave(MethodVisitor mv, Label saveLabel) {
585 594 // Fiber.setState(state);
586 595 loadVar(mv, TOBJECT, methodWeaver.getFiberVar());
587 596 loadVar(mv, TOBJECT, stateVar);
588   - mv.visitMethodInsn(INVOKEVIRTUAL, FIBER_CLASS, "setState", "("
589   - + D_STATE + ")V");
  597 +
  598 + if (!bb.flow.isStatic()) {
  599 + mv.visitInsn(ALOAD_0); // for state.self == this
  600 + }
  601 +
  602 + int pc = methodWeaver.getPC(this);
  603 + if (pc < 6) {
  604 + mv.visitInsn(ICONST_0 + pc);
  605 + } else {
  606 + mv.visitIntInsn(BIPUSH, pc);
  607 + }
  608 +
  609 + if (!bb.flow.isStatic()) {
  610 + methodWeaver.ensureMaxStack(4);
  611 + mv.visitMethodInsn(INVOKEVIRTUAL, FIBER_CLASS, "setState", "("
  612 + + D_STATE + "Ljava/lang/Object;I)V");
  613 + } else {
  614 + methodWeaver.ensureMaxStack(3);
  615 + mv.visitMethodInsn(INVOKEVIRTUAL, FIBER_CLASS, "setState", "("
  616 + + D_STATE + "I)V");
  617 + }
  618 +
590 619 releaseVar(stateVar, 1);
  620 + }
  621 +
  622 +
591 623 // Figure out the return type of the calling method and issue the
592 624 // appropriate xRETURN instruction
593 625 retType = TypeDesc.getReturnTypeDesc(bb.flow.desc);
6 src/kilim/java/kilim/analysis/ClassWeaver.java
@@ -190,12 +190,6 @@ String createStateClass(ValInfoList valInfoList) {
190 190 ClassWriter cw = new ClassWriter(0);
191 191 cw.visit(V1_1, ACC_PUBLIC | ACC_FINAL, className, null, "kilim/State", null);
192 192
193   - MethodVisitor mv = cw.visitMethod(0, "releaseTo", "(Lkilim/Fiber;)V" , null, null);
194   - mv.visitCode();
195   - mv.visitInsn(RETURN);
196   - mv.visitMaxs(1, 2);
197   - mv.visitEnd();
198   -
199 193 // Create default constructor
200 194 // <init>() {
201 195 // super(); // call java/lang/Object.<init>()
69 src/main/erl/fib.erl
... ... @@ -0,0 +1,69 @@
  1 +-module(fib).
  2 +-export([fibo/1, fibo2/1, fibo3/1, print_nfibos/2, main/0, runLength/2, main2/0]).
  3 +
  4 +%% print fibo arg. and result, with function as parameter
  5 +
  6 +print_nfibos( N, FiboFunc) -> printfibos( N, FiboFunc, 0).
  7 +
  8 +printfibos( 0, FiboFunc, N) -> %% last recursion
  9 + Res = FiboFunc(N),
  10 + io:format("~w ~w~n", [N, Res]) ;
  11 +
  12 +printfibos( Iter, FiboFunc, N) when Iter > 0 ->
  13 + Res = FiboFunc(N),
  14 + io:format("~w ~w~n", [N, Res]),
  15 + printfibos( Iter -1, FiboFunc, N +1).
  16 +
  17 +
  18 +
  19 +fibo(0) -> 0 ;
  20 +fibo(1) -> 1 ;
  21 +fibo(N) when N > 0 -> fibo(N-1) + fibo(N-2) .
  22 +
  23 +
  24 +fibo2_tr( 0, Result, _Next) -> Result ; %% last recursion output
  25 +
  26 +fibo2_tr( Iter, Result, Next) when Iter > 0 -> fibo2_tr( Iter -1, Next, Result + Next) .
  27 +
  28 +fibo2( N) -> fibo2_tr( N, 0, 1) .
  29 +
  30 +
  31 +fibo3(N) ->
  32 + {Fib, _} = fibo3(N, {1, 1}, {0, 1}),
  33 + Fib.
  34 +
  35 +fibo3(0, _, Pair) -> Pair;
  36 +fibo3(N, {Fib1, Fib2}, Pair) when N rem 2 == 0 ->
  37 + SquareFib1 = Fib1*Fib1,
  38 + fibo3(N div 2, {2*Fib1*Fib2 - SquareFib1, SquareFib1 + Fib2*Fib2}, Pair);
  39 +fibo3(N, {FibA1, FibA2}=Pair, {FibB1, FibB2}) ->
  40 + fibo3(N-1, Pair, {FibA1*FibB2 + FibB1*(FibA2 - FibA1), FibA1*FibB1 + FibA2*FibB2}).
  41 +
  42 +
  43 +time(F,N) ->
  44 + {Time,_Res} = timer:tc(fib,F,[N]),
  45 + io:format("~w,~w,~w~n", [F,N,Time]).
  46 +
  47 +tlength(L) -> tlength(L,0).
  48 +tlength([_|T],Acc) -> tlength(T,Acc+1);
  49 +tlength([],Acc) -> Acc.
  50 +
  51 +makeList(N) when N==0 -> [];
  52 +makeList(N) -> [N,makeList(N-1)].
  53 +
  54 +runLength(_,N) when N==0 -> done;
  55 +runLength(L,N) -> tlength(L), runLength(L,N-1).
  56 +
  57 +main() ->
  58 + List = makeList(2000),
  59 + io:format("time=~w~n", [timer:tc(fib,runLength,[List,1000000])]).
  60 +
  61 +main2() ->
  62 + time(fibo3,10),
  63 + time(fibo3,100),
  64 + time(fibo3,1000),
  65 + time(fibo3,10000),
  66 + time(fibo3,100000),
  67 + time(fibo3,1000000).
  68 +
  69 +
2  src/main/java/erjang/ERT.java
@@ -348,7 +348,7 @@ public static EObject apply(EProc proc, EObject mod, EObject fun) throws Pausabl
348 348 if (m==null||f==null) throw ERT.badarg(mod, fun);
349 349
350 350 EFun efun = EModule.resolve(new FunID(m,f,0));
351   - return efun.invoke(proc, new EObject[] { });
  351 + return efun.invoke(proc, new EObject[0]);
352 352 }
353 353
354 354 public static EObject apply$last(EProc proc, EObject arg1, EObject mod, EObject fun)
1  src/main/java/erjang/Erj.java
@@ -62,6 +62,7 @@ public static void main(String[] args) throws ClassNotFoundException, MalformedU
62 62 }
63 63
64 64 EModule.load_module(EAtom.intern("io"), new File("target/classes").toURL());
  65 + EModule.load_module(EAtom.intern("timer"), new File("target/classes").toURL());
65 66
66 67 load(new File("src/main/erl/" + m + ".classes"), m);
67 68

0 comments on commit a55449e

Please sign in to comment.
Something went wrong with that request. Please try again.