Parallel qsort in zel

08:43PM Apr 04, 2014 in category Java by Zoltan Farkas

I had a bit of time to implement some extra features in zel, just enough so that I can write quick sort in zel:

func qSortP(x, start, end) {
  l = end - start;
  if l < 2 {
    return
  };
  pidx = start + l / 2;
  pivot = x[pidx];
  lm1  = end - 1;
  x[pidx] <-> x[lm1];
  npv = start;
  for i = start; i < lm1; i++ {
    if x[i] < pivot {
      x[npv] <-> x[i];
      npv ++
    }
  };
  x[npv] <-> x[lm1];
  qSortP(x, start, npv)&;
  qSortP(x, npv + 1, end)&
};

qSortP(x, 0, x.length)

As you can see it is pretty much the standard implementation, and since it is ZEL it is parallel.

Parallel exec time = 510 ms
Parallel exec time = 470 ms
Parallel exec time = 473 ms
Single Threaded exec time = 1640 ms
Single Threaded exec time = 1528 ms
Single Threaded exec time = 1527ms

Tests executed on a quad core MacBook pro and show good scalability of the execution engine.

pretty cool, tests are at https://code.google.com/p/spf4j/source/browse/trunk/spf4j-zel/src/test/java/org/spf4j/zel/vm/QSort.java

enjoy

Comments[0]

Comments:

Post a Comment:
Comments are closed for this entry.