Benchmarks

The benchmarks we'll be examining in this chapter are meant to test the performance of code that updates and queries the state of relational automata, and compare it to equivalent hand-written Java or C# code (Benchmarks that test the functional subset of the language for purely computational tasks are available here). The code generated by the Cell compiler is very close, in terms of performance, to equivalent, hand-written object-oriented code, and in some cases even outperforms it.

Compared to garbage-collected, object-oriented languages like Java or C#, Cell has a number of both structural advantages and disadvantages in terms of performance. One major disadvantage is the deferred update model of relational automata: when an instruction that updates a member or mutable relation variable is executed, the update is not applied immediately, but stored in temporary memory until the message handler returns, which obviously involves a certain amount of overhead. A separate but related source of overhead is support for transactions. Another disadvantage is that in Cell, you can (and usually will) specify a set of integrity constraints (that is, keys and foreign keys) on the state of relational automata that need to be checked at runtime. A static analysis of the codebase can remove some of this overhead, but not all of it all the time. A more general problem is that mutability in Cell is subject to a number of restrictions that are bound to negatively affect performance in at least some situations.

On the other hand, relational automata naturally lend themselves to being implemented using techniques borrowed from the Entity/Component architecture and more generally from data-oriented design. One advantage of these architectures is that they vastly reduce the number of cache misses by improving the locality of the data. As we'll see later, they also seem to put less strain on the garbage collector, which is not suprising: having, say, a million instances of a class with five member variables in OOP means having a million distinct blocks of memory to keep track of, but with the E/C architecture you would end up with five arrays of one million elements each plus a hashtable (another array), which are much easier for the garbage collector to deal with.

While the code generated by the Cell compiler is already pretty fast, remember that optimization is still a work in progress: there's a lot left to do and, presumably, at least some margin for improvement. Among other things, the generated code still performs many useless integrity checks that could be eliminated by a more sophisticated static analysis; sending a message to an automaton currently involves more overhead that a method call in an imperative language, but in many cases that overhead could be eliminated; and several of the optimizations the compiler already performs would be more effective if combined with aggressive inlining of methods. The effects of these shortcomings are clearly visible in the example we will be examining.

The other thing to consider is that compiling to Java or C# (or any other garbage-collected, memory-safe language I know) is far from being ideal. Only compiling to C/C++ could fully take advantage, in terms of performance, of Cell's unique design, but a C/C++ code generator is not yet available.

The IMDB movie database

This example will make use of a a subset of the data in the IMDB movie database. The dataset is contained in a number of CSV files of moderate size (~140 MB in total). The various versions of the code will parse and load the dataset into memory, run a number of queries on it and finally update it in various ways. Both the code and the dataset are available on github (the relevant files are main.cell and imdb.cell for Cell, imdb.java for Java and imdb.cs for C#). If you have any questions or comments or if there's anything you would like to see added to this set of benchmarks, just leave a message in the forum.

All tests were run on a dual-core Intel Celeron 1005M running Lubuntu Linux 18.10, using either the Java HotSpot Server VM (version 12.0.1) or the .NET Core SDK (version 2.2.301). We will examine the single-core results first, since all versions of the code are single-threaded, and discuss dual-core performance later.

Each test was run 25 times, but the first 5 iteractions were discarded, so as to give the JVM/CLR time to warm up, and the remaining 20 were averaged. Cell took longer than Java to warm up (it's just more code) and C# took barely any time at all.

Here's the visual representation of the structure of input dataset:

and this is the definition of the relational automaton we'll be using to store it:

schema MoviesDB {
  actor(Actor)
    first_name  : String,
    last_name   : String,
    gender      : Gender;

  movie(Movie)
    name    : String,
    year    : Int,
    rank    : Float,
    genre*  : Genre;

  director(Director)
    director_first_name : String,
    director_last_name  : String;

  acted_in(Actor, Movie)
    role* : String;

  directed(Director, Movie);

  acted_in(a, m) -> actor(a), movie(m);
  directed(d, m) -> director(d), movie(m);

  // More stuff here
  ...
}

Loading the dataset

The first test consists of parsing each of the CSV files and inserting the data into the corresponding relation variables in the case of Cell, or creating and wiring the corresponding set of objects for Java and C#. The results are show in the following table (all times are in milliseconds):

Cell/Java Java Cell/C# C#
movies.csv 369 315 1357 1047
actors.csv 1756 2619 3705 3994
directors.csv 83 129 402 92
movies_directors.csv 234 267 437 369
movies_genres.csv 229 135 450 511
roles.csv 6017 4631 12826 9150
Total 8688 8096 19177 15163

The second and forth columns show the loading times for Java and C# respectively, while the first and third ones show the loading times for Cell when compiling to Java and C# respectively. Each row correspond to a different CSV file, save for the last one which shows the totals. The next table shows the same results normalized:

Cell/Java Java Cell/C# C#
movies.csv 1.17 1.00 4.30 3.32
actors.csv 1.00 1.49 2.10 2.27
directors.csv 1.00 1.55 4.84 1.10
movies_directors.csv 1.00 1.14 1.86 1.57
movies_genres.csv 1.69 1.00 3.33 3.78
roles.csv 1.29 1.00 2.76 1.97
Total 1.07 1.00 2.36 1.87

For each row the times are scaled so that the best one becames 1.0. As you can see Java is generally the fastest of the bunch, followed by Cell compiled to Java, then C# and finally Cell compiled to C#.

Note that the individual numbers in the above tables are not particularly reliable (only the totals are), because a lot depends on when the garbage collector decides to kick in, which varies depending on how the tests are set up. Since this phase of the test is dominated by object creation, which puts a lot of pressure on the garbage collector, it's actually interesting to see what the numbers would be in an "infinite memory" scenario, which can be approximated by setting (with the -Xms and -Xmx options) the amount of memory available to the JVM to a sufficiently large amount, and by explicitly invoking the garbage collector before loading each individual file (obviously, the times spent doing the preventive garbage collection is not included in the figures shown here):

Cell/Java Java Ratio
movies.csv 265 116 2.28
actors.csv 1553 973 1.59
directors.csv 48 23 2.08
movies_directors.csv 204 148 1.37
movies_genres.csv 167 73 2.28
roles.csv 5711 2138 2.67
Total 7948 3472 2.28

As you can see, with the garbage collector out of the way, Java is consistently and significantly faster than Cell, which is not particularly surprising: object creation is extremely fast in Java, while the data structures used by Cell are more complex, and updates are also slowed down by a number of factors (transactions, integrity checks, etc.) mentioned in the introduction. But much of that advantage is then lost by overloading the garbage collector.

Updating the dataset

We'll now be performing a number of update operation, that are described here:

  • U1: Increments the rank of all movies released before a given year by a specified amount.
  • U2: For each actor, computes the average rank of the movies they appear in, and stores the result in the actor_rank relation variable or in the avgMoviesRank member variable.
  • U3: For each director, computes the average rank of the movies they directed, and stores the result in the director_rank relation variable or in the avgMoviesRank member variable.
  • U4: Randomly generates a list of movie ids, and for each of them increments their rank and updates the rank of all actors and directors that worked on it.
  • U5: Deletes all movies below a given rank.
  • U6: Deletes all actors that do not appear in at least one of the remaining movies.
  • U7: Deletes all directors that did not work on any of the remaining movies.

The results are shown here:

Cell/Java Java Cell/C# C#
U1 43 36 96 45
U2 218 222 407 361
U3 22 25 44 29
U4 192 334 320 351
U5 1798 1167 1991 1899
U6 214 450 289 66
U7 8 11 12 7

and here are the normalized ones:

Cell/Java Java Cell/C# C#
U1 1.19 1.00 2.66 1.25
U2 1.00 1.01 1.86 1.65
U3 1.00 1.13 2.00 1.31
U4 1.00 1.73 1.66 1.82
U5 1.54 1.00 1.70 1.62
U6 3.24 6.81 4.37 1.00
U7 1.14 1.57 1.71 1.00

As you can see, when compiling to Java the speed of the code generated by the Cell compiler is generally similar to that of handwritten code, the most notable exception being update U6 where the handwritten C# clearly outperforms all the alternatives.

Queries

Let's now compare the performance of computation that does not update the dataset. We'll be running the following set of queries:

  • Q1: Counting the number of movies whose rank is no less that a given threshold. Repeated for several different values of the threshold.
  • Q2: Counting the number of actors who played in at least one movie whose rank was no less than a given threshold. Repeated for several different values of the threshold.
  • Q3: For each actor, finding all co-actors in movies with a given minimum rank.
  • Q4: Calculating a histogram of movie ages.
  • Q5: Calculating the average age of all movies with a given minimum rank.
  • Q6: Calculating the sum of the ages of all movies in the dataset.
  • Q7: For each movie in a randomly generated set, finding all movies that have actors in common with it.
  • Q8: For each actor in a randomly generated set, retrieving the last names of all actors with the same first name. Duplicates are eliminated.
  • Q9: Same as Q3, but also returning the number of movies they appeared in together.
  • Q10: Same as Q8, but duplicates are not eliminated.
  • Q11: For each director, checking if they ever also worked as actors.
  • Q12: For each actor, computing the full name by concatenating first and last names.

Some of the queries are a bit bizarre, but they actually manage to test all the basic operations on relations: attribute lookups, navigation, searches and linear scans. The results are shown here in milliseconds:

Cell/Java Java Cell/C# C#
Q1 228 418 527 1142
Q2 4930 9359 8388 10174
Q3 4473 6339 8047 10191
Q4 207 223 374 530
Q5 175 219 424 526
Q6 548 872 1685 1972
Q7 3433 4016 6498 4877
Q8 4239 3918 8838 5049
Q9 3466 1744 6965 3119
Q10 3190 2192 14417 3071
Q11 318 309 483 159
Q12 512 237 855 94

and here is the normalized version:

Cell/Java Java Cell/C# C#
Q1 1.00 1.83 2.31 5.00
Q2 1.00 1.89 1.70 2.06
Q3 1.00 1.41 1.79 2.27
Q4 1.00 1.07 1.80 2.56
Q5 1.00 1.25 2.42 3.00
Q6 1.00 1.59 3.07 3.59
Q7 1.00 1.16 1.89 1.42
Q8 1.08 1.00 2.25 1.28
Q9 1.98 1.00 3.99 1.78
Q10 1.45 1.00 6.57 1.40
Q11 2.00 1.94 3.03 1.00
Q12 5.44 2.52 9.09 1.00

When compiling to Java Cell is noticeably slower than equivalent Java code only for queries Q9, Q10 and Q12. Let's take a look at each of them in turn. Q9 makes use of a map/dictionary which is repeatedly mutated. In Cell maps only support functional updates, which are reasonably fast, but cannot compete with Java's mutable, hashtable-based maps. In Q10, an optimization made by the Cell compiler clashes with the limitation of Java's object model. The same problem would not present itself when compiling to C/C++. In this specific case though, it could be solved with a more sophisticated analysis of the source code. Q12 is a special case: the cause of the bad performance is just a weird problem with string concatenation that will be fixed soon.

When compiling to C# there are still some performance problems. The generated code is significantly slower than equivalent handwritten code for all queries from Q8 to Q12, but the reasons for that haven't been properly investigated yet.

Embedded mode

Cell is primarily meant to be used as an embedded language, so we'll now take a look at its performance for that specific use case. As one might expect, the generated code can sometimes be slower in embedded mode, because of all the data conversion and validation that takes place at the boundary between handwritten and generated code.

The performance hit varies considerably, and it's impossible to quantify exactly, because it depends on the "surface to volume ratio" of a given method or message handler, that is, the ratio between the amount of data that needs to be converted back and forth and the amount of actual work the method/handler needs to perform.

In order to maximize performance it's important to carefully design the public interface of relational automata in order to minimize the amount of data that has to be transferred between the hand-written and the generated parts of the codebase. Guidelines and examples of how to do so will be published soon, but in practice that's easier than it sounds. That's because, even though it can be used to replace an embedded database, Cell is not a database but a fully-featured programming language, and computation that needs to access the data held by the Cell side of the code can, in the vast majority of cases, be done directly in Cell, without involving the host language. Most of the time, you'll need to transfer only data that is used for I/O operations, which cannot be done directly in Cell: for example, when such data has to be displayed to the user or sent to another computer or application. In those cases, the computational costs or the intrinsic latency of the I/O will typically dwarf the costs of the data conversions.

Time to look at some numbers. These are the loading times for Cell embedded into Java (the numbers are for version 0.4 of the compiler, which is somewhat slower than the most recent one):

Standalone Embedded Ratio
movies.csv 402 519 1.29
actors.csv 1936 1844 0.95
directors.csv 82 75 0.91
movies_directors.csv 258 238 0.92
movies_genres.csv 233 190 0.81
roles.csv 8136 8940 1.09
Total 11047 11806 1.06

The first column shows the results when running the Cell-only program, and are exactly the same numbers we saw previously, the second column shows the result of running the tests in embedded mode, and the last one the ratio between the two. Not much of a difference. Updates are shown here:

Standalone Embedded Ratio
U1 47 40 0.85
U2 256 248 0.96
U3 25 23 0.92
U4 262 257 0.98
U5 2717 3752 1.38
U6 201 119 0.59
U7 7 8 1.14

It looks like U5 has become somewhat slower, but that's probably an illusion. It's more likely that the performance hit is taken during the loading phase, and it only appears to happen here because the garbage collector decides to kick in at this particular time. Finally, these are the results for our set of queries:

Standalone Embedded Ratio
Q1 223 226 1.01
Q2 5705 5680 0.99
Q3 5149 5972 1.15
Q4 201 198 0.98
Q5 176 180 1.02
Q6 537 526 0.97
Q7 3859 3927 1.01
Q8 4941 8665 1.75
Q9 3538 4159 1.17
Q10 4210 15406 3.65
Q11 360 796 2.21
Q12 511 1492 2.91

Apart from Q11 the queries that exhibit the worst slowdowns are Q8, Q10, Q12, which is not surprising, since they all do very little work but return a lot of data that needs to be converted. Q11 on the other hand is an example of a computation that is unnecessarily split between the Cell and Java sides of the code. The overhead almost entirely disappears if it is performed entirely in Cell.

Saving and loading the dataset

The last thing we need to check is how long it takes to load and save the dataset using the generated void load(Reader) and void save(Writer) methods. Those methods use the standard literal representation of Cell data, which is rather verbose: the ~140 MB of CSV files used as input increase in size to ~400 MB when saved in the standard Cell format. The tests have also been performed on smaller version of the dataset, which results in a file size of ~170 MB.

When compiling to Java (results for the C# code generator will be added soon) saving the entire dataset takes between 10s and 11s on first run, which goes down to around 6.5s once the JVM warms up on the machine used these tests. In order to get those results though, it's necessary to manually increase (with the -Xms and -Xms command line flags) the amount of memory used by the JVM, otherwise the number stays at ~10s even after the JVM has warmed up. Saving the smaller version of the dataset takes between 6s and 7s on first run, which goes down to less than 3s after a couple iterations. There's no need to tweak the memory settings of the JVM in this case.

Loading the dataset takes around 25s on first run, and about 15s once the JVM has warmed up. The latter time is not too bad (it is, after all, more or less the same time it takes the handwritten C# code to load the data from the original CSV files), but since loading the data is typically one of the first things an application would do, in most cases you would be stuck with the cold-run performance. Loading the smaller dataset takes about 15s seconds on the first run, and a little over 6s seconds afterwards.

Here there's still room for improvement, for example by replacing java.io.Reader and java.io.Writer with the NIO API, and by switching to asynchronous I/O. The longer term solution though is to define a more compact binary format that is equivalent to the textual representation (with a tool to convert between the two) but faster to read and write.