Changeset 12064


Ignore:
Timestamp:
07/26/09 21:48:15 (14 years ago)
Author:
ehuelsmann
Message:

Lisp stack efficiency: Use a stack of linked objects,
instead of Cons or LinkedList?.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/abcl/src/org/armedbear/lisp/LispThread.java

    r12062 r12064  
    448448    }
    449449
    450     private static class StackFrame extends LispObject
     450    private static class StackFrame
    451451    {
    452452        public final LispObject operator;
    … …  
    455455        private final LispObject third;
    456456        private final LispObject[] args;
    457 
    458         public StackFrame(LispObject operator)
     457        final StackFrame next;
     458
     459        public StackFrame(LispObject operator, StackFrame next)
    459460        {
    460461            this.operator = operator;
    … …  
    463464            third = null;
    464465            args = null;
    465         }
    466 
    467         public StackFrame(LispObject operator, LispObject arg)
     466            this.next = next;
     467        }
     468
     469        public StackFrame(LispObject operator, LispObject arg, StackFrame next)
    468470        {
    469471            this.operator = operator;
    … …  
    472474            third = null;
    473475            args = null;
     476            this.next = next;
    474477        }
    475478
    476479        public StackFrame(LispObject operator, LispObject first,
    477                           LispObject second)
     480                          LispObject second, StackFrame next)
    478481        {
    479482            this.operator = operator;
    … …  
    482485            third = null;
    483486            args = null;
     487            this.next = next;
    484488        }
    485489
    486490        public StackFrame(LispObject operator, LispObject first,
    487                           LispObject second, LispObject third)
     491                          LispObject second, LispObject third, StackFrame next)
    488492        {
    489493            this.operator = operator;
    … …  
    492496            this.third = third;
    493497            args = null;
    494         }
    495 
    496         public StackFrame(LispObject operator, LispObject[] args)
     498            this.next = next;
     499        }
     500
     501        public StackFrame(LispObject operator, LispObject[] args, StackFrame next)
    497502        {
    498503            this.operator = operator;
    … …  
    501506            third = null;
    502507            this.args = args;
     508            this.next = next;
    503509        }
    504510
    … …  
    535541    }
    536542
    537     private LispObject stack = NIL;
    538 
     543    private StackFrame stack = null;
     544
     545    @Deprecated
    539546    public LispObject getStack()
    540547    {
    541         return stack;
    542     }
    543 
     548        return NIL;
     549    }
     550
     551    @Deprecated
    544552    public void setStack(LispObject stack)
    545553    {
    546         this.stack = stack;
    547554    }
    548555
    … …  
    559566        throws ConditionThrowable
    560567    {
    561         stack = new Cons((new StackFrame(operator)), stack);
     568        stack = new StackFrame(operator, stack);
    562569        doProfiling();
    563570    }
    … …  
    566573        throws ConditionThrowable
    567574    {
    568         stack = new Cons((new StackFrame(operator, arg)), stack);
     575        stack = new StackFrame(operator, arg, stack);
    569576        doProfiling();
    570577    }
    … …  
    574581        throws ConditionThrowable
    575582    {
    576         stack = new Cons((new StackFrame(operator, first, second)), stack);
     583        stack = new StackFrame(operator, first, second, stack);
    577584        doProfiling();
    578585    }
    … …  
    582589        throws ConditionThrowable
    583590    {
    584         stack = new Cons((new StackFrame(operator, first, second, third)),
    585                          stack);
     591        stack = new StackFrame(operator, first, second, third, stack);
    586592        doProfiling();
    587593    }
    … …  
    590596        throws ConditionThrowable
    591597    {
    592         stack = new Cons((new StackFrame(operator, args)), stack);
     598        stack = new StackFrame(operator, args, stack);
    593599        doProfiling();
    594600    }
    595601
     602    public final void popStackFrame()
     603    {
     604        if (stack != null)
     605            stack = stack.next;
     606    }
     607
    596608    public void resetStack()
    597609    {
    598         stack = NIL;
     610        stack = null;
    599611    }
    600612
    … …  
    605617            return function.execute();
    606618
    607         LispObject oldStack = stack;
    608619        pushStackFrame(function);
    609620        try {
    … …  
    612623        finally {
    613624            doProfiling();
    614             stack = oldStack;
     625            popStackFrame();
    615626        }
    616627    }
    … …  
    623634            return function.execute(arg);
    624635
    625         LispObject oldStack = stack;
    626636        pushStackFrame(function, arg);
    627637        try {
    … …  
    630640        finally {
    631641            doProfiling();
    632             stack = oldStack;
     642            popStackFrame();
    633643        }
    634644    }
    … …  
    642652            return function.execute(first, second);
    643653
    644         LispObject oldStack = stack;
    645654        pushStackFrame(function, first, second);
    646655        try {
    … …  
    649658        finally {
    650659            doProfiling();
    651             stack = oldStack;
     660            popStackFrame();
    652661        }
    653662    }
    … …  
    661670            return function.execute(first, second, third);
    662671
    663         LispObject oldStack = stack;
    664672        pushStackFrame(function, first, second, third);
    665673        try {
    … …  
    668676        finally {
    669677            doProfiling();
    670             stack = oldStack;
     678            popStackFrame();
    671679        }
    672680    }
    … …  
    681689            return function.execute(first, second, third, fourth);
    682690
    683         LispObject oldStack = stack;
    684691        pushStackFrame(function, first, second, third, fourth);
    685692        try {
    … …  
    688695        finally {
    689696            doProfiling();
    690             stack = oldStack;
     697            popStackFrame();
    691698        }
    692699    }
    … …  
    701708            return function.execute(first, second, third, fourth, fifth);
    702709
    703         LispObject oldStack = stack;
    704710        pushStackFrame(function, first, second, third, fourth, fifth);
    705711        try {
    … …  
    708714        finally {
    709715            doProfiling();
    710             stack = oldStack;
     716            popStackFrame();
    711717        }
    712718    }
    … …  
    722728            return function.execute(first, second, third, fourth, fifth, sixth);
    723729
    724         LispObject oldStack = stack;
    725730        pushStackFrame(function, first, second, third, fourth, fifth, sixth);
    726731        try {
    … …  
    729734        finally {
    730735            doProfiling();
    731             stack = oldStack;
     736            popStackFrame();
    732737        }
    733738    }
    … …  
    744749                                    seventh);
    745750
    746         LispObject oldStack = stack;
    747751        pushStackFrame(function, first, second, third, fourth, fifth, sixth,
    748752                                    seventh);
    … …  
    753757        finally {
    754758            doProfiling();
    755             stack = oldStack;
     759            popStackFrame();
    756760        }
    757761    }
    … …  
    768772                                    seventh, eighth);
    769773
    770         LispObject oldStack = stack;
    771774        pushStackFrame(function, first, second, third, fourth, fifth, sixth,
    772775                                    seventh, eighth);
    … …  
    777780        finally {
    778781            doProfiling();
    779             stack = oldStack;
     782            popStackFrame();
    780783        }
    781784    }
    … …  
    787790            return function.execute(args);
    788791
    789         LispObject oldStack = stack;
    790792        pushStackFrame(function, args);
    791793        try {
    … …  
    794796        finally {
    795797            doProfiling();
    796             stack = oldStack;
     798            popStackFrame();
    797799        }
    798800    }
    … …  
    805807    public void backtrace(int limit)
    806808    {
    807         if (stack != NIL) {
     809        if (stack != null) {
    808810            try {
    809811                int count = 0;
    … …  
    812814                out._writeLine("Evaluation stack:");
    813815                out._finishOutput();
    814                 while (stack != NIL) {
     816
     817                StackFrame s = stack;
     818                while (s != null) {
    815819                    out._writeString("  ");
    816820                    out._writeString(String.valueOf(count));
    817821                    out._writeString(": ");
    818                     StackFrame frame = (StackFrame) stack.car();
    819                     pprint(frame.toList(), out.getCharPos(), out);
     822                   
     823                    pprint(s.toList(), out.getCharPos(), out);
    820824                    out.terpri();
    821825                    out._finishOutput();
    822826                    if (limit > 0 && ++count == limit)
    823827                        break;
    824                     stack = stack.cdr();
     828                    s = s.next;
    825829                }
    826830            }
    … …  
    834838    {
    835839        LispObject result = NIL;
    836         if (stack != NIL) {
     840        if (stack != null) {
    837841            int count = 0;
    838842            try {
    839                 LispObject s = stack;
    840                 while (s != NIL) {
    841                     StackFrame frame = (StackFrame) s.car();
    842                     if (frame != null) {
    843                         result = result.push(frame.toList());
    844                         if (limit > 0 && ++count == limit)
    845                             break;
    846                     }
    847                     s = s.cdr();
     843                StackFrame s = stack;
     844                while (s != null) {
     845                    result = result.push(s.toList());
     846                    if (limit > 0 && ++count == limit)
     847                        break;
     848                    s = s.next;
    848849                }
    849850            }
    … …  
    857858    public void incrementCallCounts() throws ConditionThrowable
    858859    {
    859         LispObject s = stack;
    860         while (s != NIL) {
    861             StackFrame frame = (StackFrame) s.car();
    862             if (frame != null) {
    863                 LispObject operator = frame.operator;
    864                 if (operator != null)
    865                     operator.incrementCallCount();
    866             }
    867             s = s.cdr();
     860        StackFrame s = stack;
     861        while (s != null) {
     862            LispObject operator = s.operator;
     863            if (operator != null)
     864                operator.incrementCallCount();
     865            s = s.next;
    868866        }
    869867    }
Note: See TracChangeset for help on using the changeset viewer.