forked from finos/vuu
-
Notifications
You must be signed in to change notification settings - Fork 0
Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
finos#648 Added improvements to sort algorithm.
- Loading branch information
1 parent
6aa8e2f
commit e43e132
Showing
22 changed files
with
976 additions
and
40 deletions.
There are no files selected for viewing
Large diffs are not rendered by default.
Oops, something went wrong.
27 changes: 27 additions & 0 deletions
27
benchmark/src/main/java/org/finos/vuu/benchmark/SortBenchmark2.java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,27 @@ | ||
package org.finos.vuu.benchmark; | ||
|
||
import org.openjdk.jmh.annotations.*; | ||
|
||
import java.io.IOException; | ||
import java.util.concurrent.TimeUnit; | ||
|
||
@State(Scope.Benchmark) | ||
public class SortBenchmark2 { | ||
|
||
private SortBenchmark benchmark; | ||
|
||
@Setup | ||
public void setup(){ | ||
benchmark = new SortBenchmark(); | ||
benchmark.setup(); | ||
} | ||
|
||
@Benchmark | ||
@OutputTimeUnit(TimeUnit.MILLISECONDS) | ||
@Warmup(iterations = 3) | ||
@Measurement(iterations = 2) | ||
@BenchmarkMode(Mode.AverageTime) | ||
public void sortLargeTable() throws IOException { | ||
benchmark.sortLargeTable(); | ||
} | ||
} |
66 changes: 66 additions & 0 deletions
66
benchmark/src/main/java/org/finos/vuu/benchmark/SortExample.java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,66 @@ | ||
package org.finos.vuu.benchmark; | ||
|
||
import java.util.Arrays; | ||
import java.util.Comparator; | ||
import java.util.Random; | ||
|
||
public class SortExample { | ||
|
||
private static void print(Object[][] arr){ | ||
for(int c=0; c<arr.length; c++){ | ||
Object[] row = arr[c]; | ||
System.out.println(row[0] + "," + row[1] + "," + row[2]); | ||
} | ||
} | ||
|
||
public static void main(String[] args){ | ||
|
||
int size = 10_000_000; | ||
|
||
Object[][] values = new Object[size][3]; | ||
|
||
int i = 0; | ||
|
||
Random rand = new Random(); | ||
|
||
for(int c=0; c < size; c++){ | ||
values[c][0] = "c" + c; | ||
values[c][1] = rand.nextInt(3); | ||
values[c][2] = rand.nextInt(3); | ||
} | ||
|
||
|
||
|
||
Arrays.sort(values, new Comparator<Object[]>() { | ||
@Override | ||
public int compare(Object[] o1, Object[] o2) { | ||
int res = 0; | ||
|
||
int i1 = (int)o1[1]; | ||
int i2 = (int)o2[1]; | ||
|
||
int i3 = (int)o1[2]; | ||
int i4 = (int)o2[2]; | ||
|
||
if(i1 < i2){ | ||
res = -1; | ||
}else if(i2 < i1){ | ||
res = 1; | ||
}else { | ||
if(i3 < i4){ | ||
res = -1; | ||
}else if(i4 < i3){ | ||
res = 1; | ||
} | ||
} | ||
|
||
return res; | ||
} | ||
}); | ||
|
||
//print(values); | ||
} | ||
|
||
|
||
|
||
} |
62 changes: 62 additions & 0 deletions
62
benchmark/src/main/scala/org/finos/vuu/benchmark/SortBenchmark.scala
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,62 @@ | ||
package org.finos.vuu.benchmark | ||
|
||
import org.finos.toolbox.collection.array.ImmutableArray | ||
import org.finos.toolbox.time.{Clock, DefaultClock} | ||
import org.finos.vuu.core.sort.{GenericSort, GenericSort2} | ||
import org.finos.vuu.core.table.{SimpleDataTable, ViewPortColumnCreator} | ||
import org.finos.vuu.net.{SortDef, SortSpec} | ||
import org.openjdk.jmh.annotations._ | ||
import org.openjdk.jmh.runner.Runner | ||
import org.openjdk.jmh.runner.options.OptionsBuilder | ||
|
||
import java.io.IOException | ||
import java.util.concurrent.TimeUnit | ||
|
||
@State(Scope.Benchmark) | ||
class SortBenchmark { | ||
|
||
import SortBenchmarkHelper._ | ||
|
||
var table: SimpleDataTable = null | ||
|
||
@Setup(Level.Invocation) | ||
def setup(): Unit = { | ||
table = createBigTable(2_000_000) | ||
} | ||
|
||
def doSort(table: SimpleDataTable, sort: GenericSort2): ImmutableArray[String] = { | ||
val viewPortColumns = ViewPortColumnCreator.create(table, table.columns().filter(_.name.equals("exchange")).map(_.name).toList) | ||
sort.doSort(table, table.primaryKeys, viewPortColumns) | ||
} | ||
|
||
@Benchmark | ||
@OutputTimeUnit(TimeUnit.MILLISECONDS) | ||
@Warmup(iterations = 5) | ||
@Measurement(iterations = 10) | ||
@BenchmarkMode(Array(Mode.AverageTime)) | ||
@throws[IOException] | ||
def sortLargeTable(): Unit = { | ||
implicit val clock: Clock = new DefaultClock | ||
val sort = GenericSort2(SortSpec(List(SortDef("exchange", 'A'))), table.getTableDef.columns.filter(_.name == "exchange").toList) | ||
doSort(table, sort) | ||
} | ||
|
||
def main(args: Array[String]): Unit = { | ||
val opts = new OptionsBuilder() | ||
.include(classOf[SortBenchmark].getSimpleName) | ||
.warmupIterations(5) | ||
.measurementIterations(5) | ||
//.forks(1) | ||
.build | ||
new Runner(opts).run | ||
} | ||
|
||
} | ||
|
||
object SortRun { | ||
def main(args: Array[String]): Unit = { | ||
val benchmark = new SortBenchmark() | ||
benchmark.setup() | ||
benchmark.sortLargeTable() | ||
} | ||
} |
51 changes: 51 additions & 0 deletions
51
benchmark/src/main/scala/org/finos/vuu/benchmark/SortBenchmarkHelper.scala
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,51 @@ | ||
package org.finos.vuu.benchmark | ||
|
||
import org.finos.toolbox.jmx.MetricsProviderImpl | ||
import org.finos.toolbox.lifecycle.LifecycleContainer | ||
import org.finos.toolbox.time.{Clock, DefaultClock} | ||
import org.finos.vuu.api.{Index, Indices, TableDef} | ||
import org.finos.vuu.core.table.{Columns, DataTable, RowWithData, SimpleDataTable, TableContainer} | ||
import org.finos.vuu.provider.JoinTableProviderImpl | ||
|
||
object SortBenchmarkHelper { | ||
|
||
def createBigTable(rows: Int): SimpleDataTable = { | ||
implicit val clock: Clock = new DefaultClock | ||
implicit val lifecycle: LifecycleContainer = new LifecycleContainer | ||
implicit val metrics: MetricsProviderImpl = new MetricsProviderImpl | ||
|
||
val joinProvider = JoinTableProviderImpl() // new EsperJoinTableProviderImpl() | ||
|
||
val tableContainer = new TableContainer(joinProvider) | ||
|
||
// val outQueue = new OutboundRowPublishQueue() | ||
// val highPriorityQueue = new OutboundRowPublishQueue() | ||
// val viewPortContainer = new ViewPortContainer(tableContainer) | ||
|
||
val pricesDef = TableDef( | ||
"prices", "ric", | ||
Columns.fromNames("ric:String", "bid:Double", "ask:Double", "last:Double", "open:Double", "close:Double", "exchange:String"), | ||
indices = Indices( | ||
Index("exchange") | ||
), | ||
"ric" | ||
) | ||
|
||
val table = new SimpleDataTable(pricesDef, joinProvider) | ||
|
||
(1 to rows).foreach(i => { | ||
|
||
val ric = "TST-" + i | ||
|
||
val exchange = if (i % 2 == 0) "A" | ||
else if (i % 3 == 0) "B" | ||
else if (i % 4 == 0) "C" | ||
else "D" | ||
|
||
val row = RowWithData(ric, Map("ask" -> 100, "bid" -> 101, "last" -> 105, "exchange" -> exchange)) | ||
|
||
table.processUpdate(ric, row, 1l) | ||
}) | ||
table | ||
} | ||
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
133 changes: 133 additions & 0 deletions
133
vuu/src/main/scala/org/finos/vuu/core/sort/SortCompares.scala
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,133 @@ | ||
package org.finos.vuu.core.sort | ||
|
||
import org.finos.vuu.core.table.{Column, DataType, RowData} | ||
|
||
import scala.annotation.tailrec | ||
|
||
object SortCompares { | ||
|
||
@tailrec | ||
def compare(o1: RowData, o2: RowData, columns: List[Column], sortDirections: List[Char], columnIndex: Int): Int = { | ||
|
||
val activeColumn = columns(columnIndex) | ||
val direction = sortDirections(columnIndex) | ||
|
||
val compareValue = if(activeColumn.dataType.equals(DataType.StringDataType)){ | ||
compareString(o1, o2, activeColumn, direction) | ||
}else if(activeColumn.dataType.equals(DataType.charDataType)){ | ||
compareChar(o1, o2, activeColumn, direction) | ||
} else if (activeColumn.dataType.equals(DataType.IntegerDataType)) { | ||
compareInt(o1, o2, activeColumn, direction) | ||
} else if (activeColumn.dataType.equals(DataType.BooleanDataType)) { | ||
compareBoolean(o1, o2, activeColumn, direction) | ||
} else if (activeColumn.dataType.equals(DataType.DoubleDataType)) { | ||
compareDouble(o1, o2, activeColumn, direction) | ||
} else if (activeColumn.dataType.equals(DataType.LongDataType)) { | ||
compareLong(o1, o2, activeColumn, direction) | ||
}else { | ||
throw new Exception("have field but don't know what it is....") | ||
} | ||
|
||
if(compareValue != 0){ | ||
compareValue | ||
}else if(columnIndex == (columns.length - 1)){ | ||
compareValue | ||
}else{ | ||
compare(o1, o2, columns, sortDirections, columnIndex + 1) | ||
} | ||
} | ||
|
||
def compareChar(o1: RowData, o2: RowData, column: Column, direction: Char): Int = { | ||
|
||
val c1 = o1.get(column).asInstanceOf[Int] | ||
val c2 = o2.get(column).asInstanceOf[Int] | ||
|
||
val lessThan = if(direction == 'A') 1 else -1 | ||
val greaterThan = if(direction == 'A') -1 else 1 | ||
|
||
if(c1 < c2){ | ||
lessThan | ||
}else if(c1 > c2){ | ||
greaterThan | ||
}else{ | ||
0 | ||
} | ||
} | ||
|
||
def compareString(o1: RowData, o2: RowData, column: Column, direction: Char): Int = { | ||
val c1 = o1.get(column).asInstanceOf[String] | ||
val c2 = o2.get(column).asInstanceOf[String] | ||
|
||
val multiplier = if(direction == 'A'){ | ||
-1 | ||
}else{ | ||
1 | ||
} | ||
|
||
c1.compareToIgnoreCase(c2) * multiplier | ||
} | ||
|
||
def compareDouble(o1: RowData, o2: RowData, column: Column, direction: Char): Int = { | ||
val c1 = o1.get(column).asInstanceOf[Double] | ||
val c2 = o2.get(column).asInstanceOf[Double] | ||
|
||
val lessThan = if (direction == 'A') 1 else -1 | ||
val greaterThan = if (direction == 'A') -1 else 1 | ||
|
||
if (c1 < c2) { | ||
lessThan | ||
} else if (c1 > c2) { | ||
greaterThan | ||
} else { | ||
0 | ||
} | ||
} | ||
|
||
def compareBoolean(o1: RowData, o2: RowData, column: Column, direction: Char): Int = { | ||
val c1 = o1.get(column).asInstanceOf[Boolean] | ||
val c2 = o2.get(column).asInstanceOf[Boolean] | ||
|
||
val lessThan = if (direction == 'A') 1 else -1 | ||
val greaterThan = if (direction == 'A') -1 else 1 | ||
|
||
if (c1 == true && c2 == false) { | ||
lessThan | ||
} else if (c1 == false && c2 == true) { | ||
greaterThan | ||
} else { | ||
0 | ||
} | ||
} | ||
|
||
def compareInt(o1: RowData, o2: RowData, column: Column, direction: Char): Int = { | ||
val c1 = o1.get(column).asInstanceOf[Int] | ||
val c2 = o2.get(column).asInstanceOf[Int] | ||
|
||
val lessThan = if (direction == 'A') 1 else -1 | ||
val greaterThan = if (direction == 'A') -1 else 1 | ||
|
||
if (c1 < c2) { | ||
lessThan | ||
} else if (c1 > c2) { | ||
greaterThan | ||
} else { | ||
0 | ||
} | ||
} | ||
|
||
def compareLong(o1: RowData, o2: RowData, column: Column, direction: Char): Int = { | ||
val c1 = o1.get(column).asInstanceOf[Long] | ||
val c2 = o2.get(column).asInstanceOf[Long] | ||
|
||
val lessThan = if (direction == 'A') 1 else -1 | ||
val greaterThan = if (direction == 'A') -1 else 1 | ||
|
||
if (c1 < c2) { | ||
lessThan | ||
} else if (c1 > c2) { | ||
greaterThan | ||
} else { | ||
0 | ||
} | ||
} | ||
} |
Oops, something went wrong.