[Project_owners] how to implement bounded stack in javascript?

Axel Hecht axel at pike.org
Mon Apr 17 02:56:57 EDT 2006


Konstantin Svist wrote:
> lemme take a crack at it..
> 
> _boundedStack: {
>   _max: 500,
>   _stack: [],
>   _current: 0,   // next position to be written
>   _overfly: false,
>   push: function(obj) {
>     var current = this._current;    // minor optimization
>     this._stack[current] = obj;

This needs to realloc the array, unless js is really clever about those, 
you realloc 500 times, which is slow and consumes basically 1000 entries 
in memory at max. Not really worth it, if you usually do hit the 500 
soonish.

>     if (current >= this._max) {
>       this._current = 0;
>       this._overfly = true;
>     }
>   },
>   length: function() { return this._stack.length; },    // note_1
>   item: function(idx) {        // note_2
>     if (this._overfly) {
>       idx += this._current;
>       if (idx >= this._max) { idx -= this._max; }
>     }
>     return this._stack[idx];
>   }
> }
> 
> note_1: it'll probably be a little faster to call myStack._stack.length 
> directly
> 
> note_2: caller needs to bound-check. this can be done implicitly: get 
> the length first, then only ask for elements within that length.
> 
> 
> logic check: _current points to next field to write into. when getting 
> an element by index, _current points to oldest element iff there was an 
> overflow.
> 
> 
> By the way, never skimp on the curly braces {}: for some reason Fx 1.0 
> favors the code with lots of {}s, by a slight margin (or so my testing 
> showed).
> 
> 
> 
> 
> 
> 
> also, does it have to be an array? what if you just use a linked list of 
> objects? it may work faster if you keep retrieving the whole list each 
> time, not just a certain item
> 
> _boundedStack: {
>   first: null,
>   last: null,
>   len: 0,
>   max: 500,
>   push: function(obj) {
>     if (null == this.last) { this.last = obj; }
>     else {
>       this.last.next = obj;
>       this.last = obj;
>     }
>     this.len++;
>     if (null == first) { first = obj; }
>     else if (this.len >= this.max) {
>         this.first = this.first.next;
>         this.len--;
>     }
>   }
> }
> 
> obj should be fairly easy to implement, i think..
> to get the length of your stack, just grab the len variable
> to get the list, get the first element then .next until .next == null
> 

Linked lists are non-local in storage, that may or may not have an 
impact on perf. In theory, I bet that doesn't matter at all in an 
interpreted language.
It may be a little stressful on GC to have 500 additional objects.
It looks like you're polluting obj with next members, too.

Axel


More information about the Project_owners mailing list