Skip to content

Commit

Permalink
finos#648 Added improvements to sort algorithm.
Browse files Browse the repository at this point in the history
  • Loading branch information
chrisjstevo committed Apr 25, 2023
1 parent 6aa8e2f commit e43e132
Show file tree
Hide file tree
Showing 22 changed files with 976 additions and 40 deletions.
496 changes: 496 additions & 0 deletions benchmark/pom.xml

Large diffs are not rendered by default.

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 benchmark/src/main/java/org/finos/vuu/benchmark/SortExample.java
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);
}



}
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()
}
}
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
}
}
2 changes: 2 additions & 0 deletions pom.xml
Original file line number Diff line number Diff line change
Expand Up @@ -75,12 +75,14 @@
<vertx.version>4.4.1</vertx.version>
<typesafe.conf.version>1.4.2</typesafe.conf.version>
<logback.version>1.2.9</logback.version>
<jmh.version>1.36</jmh.version>
</properties>

<modules>
<module>toolbox</module>
<module>vuu</module>
<module>vuu-ui</module>
<module>benchmark</module>
</modules>

<dependencies>
Expand Down
Original file line number Diff line number Diff line change
Expand Up @@ -7,7 +7,7 @@ object ImmutableArray{
def empty[T](implicit c: ClassTag[T]): ImmutableArray[T] = {
new ChunkedUniqueImmutableArraySet[T](Set(), Array(), chunkSize = 5000)
}
def from[T](array: Array[T])(implicit c: ClassTag[T]) = {
def from[T](array: Array[T])(implicit c: ClassTag[T]): ImmutableArray[T] = {
empty[T].addAll(new NaiveImmutableArray[T](array))
}
}
Expand Down
12 changes: 12 additions & 0 deletions vuu/pom.xml
Original file line number Diff line number Diff line change
Expand Up @@ -187,6 +187,18 @@
<version>${typesafe.conf.version}</version>
</dependency>

<dependency>
<groupId>org.openjdk.jmh</groupId>
<artifactId>jmh-core</artifactId>
<version>${jmh.version}</version>
</dependency>
<dependency>
<groupId>org.openjdk.jmh</groupId>
<artifactId>jmh-generator-annprocess</artifactId>
<version>${jmh.version}</version>
<!--scope>provided</scope-->
</dependency>

</dependencies>

<profiles>
Expand Down
2 changes: 1 addition & 1 deletion vuu/src/main/resources/runconfigurations/SimulMain.run.xml
Original file line number Diff line number Diff line change
@@ -1,6 +1,6 @@
<component name="ProjectRunConfigurationManager">
<configuration default="false" name="SimulMain" type="Application" factoryName="Application" folderName="runConfigs">
<option name="ALTERNATIVE_JRE_PATH" value="$USER_HOME$/.sdkman/candidates/java/11.0.2-open" />
<option name="ALTERNATIVE_JRE_PATH" value="$USER_HOME$/.sdkman/candidates/java/11.0.8.j9-adpt" />
<option name="ALTERNATIVE_JRE_PATH_ENABLED" value="true" />
<option name="MAIN_CLASS_NAME" value="org.finos.vuu.SimulMain" />
<module name="vuu" />
Expand Down
133 changes: 133 additions & 0 deletions vuu/src/main/scala/org/finos/vuu/core/sort/SortCompares.scala
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
}
}
}
Loading

0 comments on commit e43e132

Please sign in to comment.