Posted at 2014-02-05 by @gfwilliams

The issue really is stack space. As the parse tree is effectively on the stack, having two things running concurrently is likely to fill it up pretty quick. You could just rewrite the quicksort to jump out early.

Can you post your quicksort? I'd like to add it as a benchmark.

The best solution here would be to implement the quicksort natively though. It should be quite easy (and fast) with iterators and I imagine it would be used a lot.

Posted at 2014-02-06 by TiCPU

I forgot that you would need to instantiate a second parsing tree.

I attached the tests I made with sorts. Here is the output:

start: 162142.4207250000035855
qsort: 162142.9275999999954365 (0.506874999991850927472)
bsort: 162144.6809749999956693 (1.753375000000232830643)

Posted at 2014-02-06 by TiCPU

Attaching did not work, I'll just paste it inline:

// Useful functions
Array.prototype.median = function () {
  return this[Math.floor(this.length/2)];
};
Uint16Array.prototype.median = Array.prototype.median;

Array.prototype.swap = function (left, right) {
  var tmp = this[left];
  
  this[left] = this[right];
  this[right] = tmp;
  
  return this;
};
Uint16Array.prototype.swap = Array.prototype.swap;

Uint16Array.prototype.clear = function () {
  for (var i = 0; i < this.length; i++) this[i] = 0;
};

// Bubble sort
Array.prototype.sort = function () {
  var len = this.length - 1;

  for (var i = 0; i < len; i++) {
    for (var j = 0, swapping, endIndex = len - i; j < endIndex; j++) {
      if (this[j] > this[j + 1]) {
        swapping = this[j];
        this[j] = this[j + 1];
        this[j + 1] = swapping;
      }
    }
  }
  return this;
};
Uint16Array.prototype.sort = Array.prototype.sort;

// Quick sort
Array.prototype.qsort_partition = function (pivot, left, right) {
  var tmp, storeIndex = left, pivotVal = this[pivot];

  this.swap(pivot, right);
  for (var i = left; i < right; i++) {
    if (this[i] < pivotVal) {
      this.swap(i, storeIndex);
      storeIndex++;
    }
  }
  this.swap(right, storeIndex);

  return storeIndex;
};
Uint16Array.prototype.qsort_partition = Array.prototype.qsort_partition;

Array.prototype.qsort = function (left, right) {
  var pivot, newPivot;

  if (left === undefined) {
    left = 0;
    right = this.length - 1;
  }

  if (left < right) {
    pivot = left + Math.ceil((right - left) / 2);
    newPivot = this.qsort_partition(pivot, left, right);
    this.qsort(left, newPivot - 1);
    this.qsort(newPivot + 1, right);
  }

  return this;
};
Uint16Array.prototype.qsort = Array.prototype.qsort;

// Tests
var tQsort = new Uint16Array([5454,5449,5380,5412,5380,5366,5344,5395,5398,5424,5422,5473,5420,5432,5376,5354,5561,5288,5393,5388,5422,5427,5476,5407,5385,5180,5363,5324,5395,5393,5410,5405,5349,5361,5385,5412,5373,5373,5478,5420,5446,5395,5339,5407,5420,5356,5336,5427,5459,5378,5336,5349,5420,5405,5434,5383,5446,5422,5349,5329,5405,5434,5446,5336,5427,5473,5402,5170,5388,5412,5456,123,456,789]);
var tBsort = new Uint16Array([5454,5449,5380,5412,5380,5366,5344,5395,5398,5424,5422,5473,5420,5432,5376,5354,5561,5288,5393,5388,5422,5427,5476,5407,5385,5180,5363,5324,5395,5393,5410,5405,5349,5361,5385,5412,5373,5373,5478,5420,5446,5395,5339,5407,5420,5356,5336,5427,5459,5378,5336,5349,5420,5405,5434,5383,5446,5422,5349,5329,5405,5434,5446,5336,5427,5473,5402,5170,5388,5412,5456,123,456,789]);

var qsortTime, bsortTime, startTime = getTime();
tQsort.qsort();
qsortTime = getTime();
tBsort.sort();
bsortTime = getTime();

print("start: " + startTime);
print("qsort: " + qsortTime + " (" + (qsortTime-startTime) + ")");
print("bsort: " + bsortTime + " (" + (bsortTime-qsortTime) + ")");

Posted at 2014-02-06 by TiCPU

I tried optimizing the function, removing functions call seem to help quite a bit, and prevent stack overflows just a bit since it is easy to get one.

qsort: 165526.5649749999865889 (0.398799999995389953255)

swap and qsort_partition not needed anymore:
// Quick sort
Array.prototype.qsort = function (left, right) {
var pivot, newPivot, pivotVal, tmp;

  if (left === undefined) {
    left = 0;
    right = this.length - 1;
  }

  if (left < right) {
    pivot = left + Math.ceil((right - left) / 2);

	// Partition
    pivotVal = this[pivot];
    newPivot = left;
    this[pivot] = this[right]; this[right] = pivotVal;
    for (var i = left; i < right; i++) {
      if (this[i] < pivotVal) {
        tmp = this[i]; this[newPivot++] = i; this[i] = tmp;
      }
    }

    this.qsort(left, newPivot - 1);
    this.qsort(newPivot + 1, right);
  }
};
Uint16Array.prototype.qsort = Array.prototype.qsort;

Posted at 2014-02-06 by TiCPU

And here is my final code for my needs, this won't stack overflow:

nqsort: 425.1626749999999788087 (0.343325)

// Non-nested quick sort
Array.prototype.nqsort = function(depth) {
  var pivot, i=0, left, right;
  if (depth === undefined) {
    depth = parseInt(Math.floor(this.length/5), 10);
  }
  var begin = Uint16Array(depth);
  var end = Uint16Array(depth);

  begin[0] = 0;
  end[0] = this.length;

  while (i >= 0) {
    left = begin[i]; right = end[i]-1;
    if (left < right) {
      pivot = this[left];
      if (i === depth-1) return false;
      while (left < right) {
        while (this[right] >= pivot && left < right) right--;
        if (left < right) this[left++] = this[right];
        while (this[left] <= pivot && left < right) left++;
        if (left < right) this[right--] = this[left];
      }
      this[left] = pivot; begin[i+1] = left+1;
      end[i+1] = end[i]; end[i++] = left;
    } else i--;
  }
  return true;
};
Uint16Array.prototype.nqsort = Array.prototype.nqsort;

References: http://alienryderflex.com/quicksort/

Posted at 2014-02-06 by @gfwilliams

This is great - thanks! I'll stick these in the benchmark suite - they should be really useful to help work on function call/array access overhead.

By the way, if you want a little more speed, you can minify the function:

Array.prototype.nqsort=function(d){var f,c=0,a,b;void 0===d&&(d=parseInt(Math.floor(this.length/5),10));var g=new Uint16Array(d),e=new Uint16Array(d);g[0]=0;for(e[0]=this.length;0<=c;)if(a=g[c],b=e[c]-1,a<b){f=this[a];if(c===d-1)return!1;for(;a<b;){for(;this[b]>=f&&a<b;)b--;for(a<b&&(this[a++]=this[b]);this[a]<=f&&a<b;)a++;a<b&&(this[b--]=this[a])}this[a]=f;g[c+1]=a+1;e[c+1]=e[c];e[c++]=a}else c--;return!0};

Posted at 2014-05-17 by user7029

Minifying is nice, bumped on github a javascript string compressor http://pieroxy.net/blog/pages/lz-string/demo.html which compress the minified (on a PC the 830 bytes becomes 322 bytes net).
The original code is 1788 bytes compressed to 498 bytes.
Serial links are slow, so the MCU got time to decompress with this kind of option.
More bang for the memory buck, and probably more throughput in serial links?
It also makes the original JS code probably closer to a compiled C code, which would be used for speed?

Posted at 2014-05-19 by @gfwilliams

Looks handy - it would be good to have as an Espruino module...

To be honest the USB link is more than fast enough for sending code, and unless I can make Espruino execute direct from the compressed strings I wonder how much memory this would save on Espruino itself.

However being able to compress data could be very handy - especially when doing things like sending it over the internet or storing it on EEPROMs.

Posted at 2014-05-19 by user7029

That's right. Actually, when I looked at Tessel's add-on board animation which gets inserted on the MCU board, it reminded me of the impractical USB custom devices: when plugged in the first time: It's plug and pray because compiled drivers need to be found (on top of being admin)... for the host (win, iOS, Android, Linux...)

Would developers' life be easier if each "shield" comes with an EEPROM which contains the javascript drivers and web pointers (where to get spec, upgrades etc...), so the platform (whatever the MCU) can use it right away, like dynamic added resource? This would justify interpreted language implementation for portability.

By the way, surveying around, got some questions:

• What are the pros and cons of embedded Javascript vs eLua (which could be precompiled)?
• Can Espruino's interpreter get extensions that would allow specific boost of performance for MCU embedded applications? (because maybe supporting type strong C var types to complement the flex var type of Jscript?)

Posted at 2014-05-20 by DrAzzy

Can Espruino's interpreter get extensions that would allow specific boost of performance for MCU embedded applications? (because maybe supporting type strong C var types to complement the flex var type of Jscript?)

How about inline assembler? http://www.espruino.com/Assembler

Posted at 2014-05-20 by user7029

Assembly is not portable across cores (not future proof): C helps to be core agnostic. Few years back we learnt to optimize the way we code in C so the compiler is generating efficient machine code. I try to use only the NOP instruction for basic S/W delays. Javascript evolves and adopt what is popularly implemented new features in browsers. How about Embedded JavaScript? (no V8 engine to compete with eLua's performance)

Posted at 2014-05-20 by @gfwilliams

What are the pros and cons of embedded Javascript vs eLua (which could be precompiled)?

It's a language that people actually know, there's lots of code available on the net, and you don't need a toolchain on the host. It's almost certainly not as fast, but if you were after raw speed and didn't mind pre-compiling then you'd probably be using C.

maybe supporting type strong C var types to complement the flex var type of Jscript?

Without a JIT compiler I don't think that will help a great deal - if you want a fast pre-compiled language that looks a lot like C, I'd suggest that you use C.

Assembly is not portable across cores (not future proof)

This is true, however I think it's safe to assume that every Espruino device for the next few years at least will run ARM Thumb, so you're pretty safe.

There are instructions on the link @drazzy posted that show you how to use C code in Espruino. Ideally the Web IDE would directly support 'inline C' - but I'm yet to find a compiler that can be compiled to JavaScript that targets thumb. If someone wants to port TCC (which can be compiled with emscripten) from ARM to ARM Thumb then I'd be only too happy to directly include inline C :)