8000 implemented multidim quick sort · plotly/ndarray-sort@91e9e9b · GitHub
[go: up one dir, main page]
Skip to content

Commit 91e9e9b

Browse files
mikolalysenkomikolalysenko
committed
implemented multidim quick sort
1 parent a8e3d9f commit 91e9e9b

File tree

3 files changed

+1042
-672
lines changed

3 files changed

+1042
-672
lines changed

‎lib/compile_sort.js

Lines changed: 141 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -202,7 +202,7 @@ function createQuickSort(order, dtype, insertionSort) {
202202
var funcName = ["ndarrayQuickSort", order.join("d"), dtype].join("")
203203
var funcArgs = ["left", "right", "data", "offset" ].concat(shapeArgs(order.length))
204204
var allocator = getMallocFree(dtype)
205-
205+
var labelCounter=0
206206

207207
code.push(["function ", funcName, "(", funcArgs.join(","), "){"].join(""))
208208

@@ -241,7 +241,18 @@ function createQuickSort(order, dtype, insertionSort) {
241241
ele_size.push("n"+i)
242242
vars.push("i"+i)
243243
}
244-
vars.push("elementSize="+ele_size.join("*"))
244+
for(var i=0; i<8; ++i) {
245+
vars.push("b_ptr"+i)
246+
}
247+
vars.push(
248+
"ptr3",
249+
"ptr4",
250+
"ptr5",
251+
"ptr6",
252+
"ptr7",
253+
"pivot_ptr",
254+
"ptr_shift",
255+
"elementSize="+ele_size.join("*"))
245256
if(allocator) {
246257
vars.push("pivot1=malloc(elementSize)",
247258
"pivot2=malloc(elementSize)")
@@ -273,6 +284,85 @@ function createQuickSort(order, dtype, insertionSort) {
273284
return ["data[",ptr,"]=",v].join("")
274285
}
275286

287+
function cacheLoop(ptrs, usePivot, body) {
288+
if(ptrs.length === 1) {
289+
code.push("ptr0="+toPointer(ptrs[0]))
290+
} else {
291+
for(var i=0; i<ptrs.length; ++i) {
292+
code.push(["b_ptr",i,"=s0*",ptrs[i]].join(""))
293+
}
294+
}
295+
if(usePivot) {
296+
code.push("pivot_ptr=0")
297+
}
298+
code.push("ptr_shift=offset")
299+
for(var i=order.length-1; i>=0; --i) {
300+
var j = order[i]
301+
if(j === 0) {
302+
continue
303+
}
304+
code.push(["for(i",j,"=0;i",j,"<n",j,";++i",j,"){"].join(""))
305+
}
306+
if(ptrs.length > 1) {
307+
for(var i=0; i<ptrs.length; ++i) {
308+
code.push(["ptr",i,"=b_ptr",i,"+ptr_shift"].join(""))
309+
}
310+
}
311+
code.push(body)
312+
if(usePivot) {
313+
code.push("++pivot_ptr")
314+
}
315+
for(var i=0; i<order.length; ++i) {
316+
var j = order[i]
317+
if(j === 0) {
318+
continue
319+
}
320+
if(ptrs.length>1) {
321+
code.push("ptr_shift+=d"+j)
322+
} else {
323+
code.push("ptr0+=d"+j)
324+
}
325+
code.push("}")
326+
}
327+
}
328+
329+
function lexicoLoop(label, ptrs, usePivot, body) {
330+
if(ptrs.length === 1) {
331+
code.push("ptr0="+toPointer(ptrs[0]))
332+
} else {
333+
for(var i=0; i<ptrs.length; ++i) {
334+
code.push(["b_ptr",i,"=s0*",ptrs[i]].join(""))
335+
}
336+
code.push("ptr_shift=offset")
337+
}
338+
if(usePivot) {
339+
code.push("pivot_ptr=0")
340+
}
341+
if(label) {
342+
code.push(label+":")
343+
}
344+
for(var i=1; i<order.length; ++i) {
345+
code.push(["for(i",i,"=0;i",i,"<n",i,";++i",i,"){"].join(""))
346+
}
347+
if(ptrs.length > 1) {
348+
for(var i=0; i<ptrs.length; ++i) {
349+
code.push(["ptr",i,"=b_ptr",i,"+ptr_shift"].join(""))
350+
}
351+
}
352+
code.push(body)
353+
for(var i=order.length-1; i>=1; --i) {
354+
if(usePivot) {
355+
code.push("pivot_ptr+=f"+i)
356+
}
357+
if(ptrs.length > 1) {
358+
code.push("ptr_shift+=e"+i)
359+
} else {
360+
code.push("ptr0+=e"+i)
361+
}
362+
code.push("}")
363+
}
364+
}
365+
276366
function cleanUp() {
277367
if(order.length > 1 && allocator) {
278368
code.push("free(pivot1)", "free(pivot2)")
@@ -283,8 +373,12 @@ function createQuickSort(order, dtype, insertionSort) {
283373
var a = "el"+a_id
284374
var b = "el"+b_id
285375
if(order.length > 1) {
286-
//TODO:
287-
// if (compare(el1, el2) > 0) { var t = el1; el1 = el2; el2 = t; }
376+
var lbl = "__l" + (++labelCounter)
377+
lexicoLoop(lbl, [a, b], false, [
378+
"comp=",dataRead("ptr0"),"-",dataRead("ptr1"),"\n",
379+
"if(comp>0){tmp0=", a, ";",a,"=",b,";", b,"=tmp0;break ", lbl,"}\n",
380+
"if(comp<0){break ", lbl, "}"
381+
].join(""))
288382
} else {
289383
code.push(["if(", dataRead(toPointer(a)), ">", dataRead(toPointer(b)), "){tmp0=", a, ";",a,"=",b,";", b,"=tmp0}"].join(""))
290384
}
@@ -300,18 +394,18 @@ function createQuickSort(order, dtype, insertionSort) {
300394
compareSwap(2, 3)
301395
compareSwap(4, 5)
302396

303-
if(order.length > 1) {
304-
//TODO:
305-
// pivot1 = a[el2]
306-
// pivot2 = a[el4]
307-
// pivots_are_equal = pivot1 == pivot2
308-
// x = a[el1]
309-
// y = a[el3]
310-
// z = a[el5]
311-
// a[index1] = x
312-
// a[index3] = y
313-
// a[index5] = z
314-
//
397+
if(order.length > 1) {
398+
cacheLoop(["el1", "el2", "el3", "el4", "el5", "index1", "index3", "index5"], true, [
399+
"pivot1[pivot_ptr]=",dataRead("ptr1"),"\n",
400+
"pivot2[pivot_ptr]=",dataRead("ptr3"),"\n",
401+
"pivots_are_equal=pivots_are_equal&&(pivot1[pivot_ptr]===pivot2[pivot_ptr])\n",
402+
"x=",dataRead("ptr0"),"\n",
403+
"y=",dataRead("ptr2"),"\n",
404+
"z=",dataRead("ptr4"),"\n",
405+
dataWrite("ptr5", "x"),"\n",
406+
dataWrite("ptr6", "y"),"\n",
407+
dataWrite("ptr7", "z")
408+
].join(""))
315409
} else {
316410
code.push([
317411
"pivot1=", dataRead(toPointer("el2")), "\n",
@@ -329,31 +423,36 @@ function createQuickSort(order, dtype, insertionSort) {
329423

330424
function moveElement(dst, src) {
331425
if(order.length > 1) {
332-
//TODO:
333-
// a[dst] = a[src]
426+
cacheLoop([dst, src], false,
427+
dataWrite("ptr0", dataRead("ptr1"))
428+
)
334429
} else {
335430
code.push(dataWrite(toPointer(dst), dataRead(toPointer(src))))
336431
}
337432
}
338433

339434
moveElement("index2", "left")
340435
moveElement("index4", "right")
341-
342436

343437
function comparePivot(result, ptr, n) {
344438
if(order.length > 1) {
345-
//TODO:
346-
// result=compare(a[ptr], pivot[n])
439+
var lbl = "__l" + (++labelCounter)
440+
lexicoLoop(lbl, [ptr], true, [
441+
result,"=",dataRead("ptr0"),"-pivot",n,"[pivot_ptr]\n",
442+
"if(",result,"!==0){break ", lbl, "}"
443+
].join(""))
347444
} else {
348445
code.push([result,"=", dataRead(toPointer(ptr)), "-pivot", n].join(""))
349446
}
350447
}
351448

352449
function swapElements(a, b) {
353450
if(order.length > 1) {
354-
//TODO:
355-
// a[k] = a[less];
356-
// a[less] = ak;
451+
cacheLoop([a,b],false,[
452+
"tmp=",dataRead("ptr0"),"\n",
453+
dataWrite("ptr0", dataRead("ptr1")),"\n",
454+
dataWrite("ptr1", "tmp")
455+
].join(""))
357456
} else {
358457
code.push([
359458
"ptr0=",toPointer(a),"\n",
@@ -367,10 +466,13 @@ function createQuickSort(order, dtype, insertionSort) {
367466

368467
function tripleSwap(k, less, great) {
369468
if(order.length > 1) {
370-
//TODO:
371-
// a[k] = a[less];
372-
// a[less++] = a[great];
373-
// a[great--] = ak;
469+
cacheLoop([k,less,great], false, [
470+
"tmp=",dataRead("ptr0"),"\n",
471+
dataWrite("ptr0", dataRead("ptr1")),"\n",
472+
dataWrite("ptr1", dataRead("ptr2")),"\n",
473+
dataWrite("ptr2", "tmp")
474+
].join(""))
475+
code.push("++"+less, "--"+great)
374476
} else {
375477
code.push([
376478
"ptr0=",toPointer(k),"\n",
@@ -450,10 +552,11 @@ function createQuickSort(order, dtype, insertionSort) {
450552

451553
//Move pivots to correct place
452554
function storePivot(mem_dest, pivot_dest, pivot) {
453-
if(order>1) {
454-
//TODO:
455-
// a[left] = a[less - 1];
456-
// a[less - 1] = pivot1;
555+
if(order.length>1) {
556+
cacheLoop([mem_dest, pivot_dest], true, [
557+
dataWrite("ptr0", dataRead("ptr1")), "\n",
558+
dataWrite("ptr1", ["pivot",pivot,"[pivot_ptr]"].join(""))
559+
].join(""))
457560
} else {
458561
code.push(
459562
dataWrite(toPointer(mem_dest), dataRead(toPointer(pivot_dest))),
@@ -483,11 +586,13 @@ function createQuickSort(order, dtype, insertionSort) {
483586
code.push("return")
484587
code.push("}")
485588

486-
487589
function walkPointer(ptr, pivot, body) {
488590
if(order.length > 1) {
489-
//TODO:
490-
//while (compare(a[less], pivot1) == 0) { less++; }
591+
code.push(["__l",++labelCounter,":while(true){"].join(""))
592+
cacheLoop([ptr], true, [
593+
"if(", dataRead("ptr0"), "!==pivot", pivot, "[pivot_ptr]){break __l", labelCounter, "}"
594+
].join(""))
595+
code.push(body, "}")
491596
} else {
492597
code.push(["while(", dataRead(toPointer(ptr)), "===pivot", pivot, "){", body, "}"].join(""))
493598
}
@@ -541,7 +646,7 @@ function createQuickSort(order, dtype, insertionSort) {
541646
//Compile and link
542647
if(order.length > 1 && allocator) {
543648
var compiled = new Function("insertionSort", "malloc", "free", code.join("\n"))
544-
return compiled(insertionSort, allocator.malloc, allocator.free)
649+
return compiled(insertionSort, allocator[0], allocator[1])
545650
}
546651
var compiled = new Function("insertionSort", code.join("\n"))
547652
return compiled(insertionSort)

0 commit comments

Comments
 (0)
0