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 data structures used to implement ternary relations, while reasonably fast, are still too generic and don't take advantage of the specific usage of each individual relation variable and the constraints that are placed on it; many-to-many binary relations seem to have performance problems under deletion that haven't been investigated yet; 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:
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):
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:
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
-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):
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.
This also shows where Cell lags the most compared to Java: loading the data in
roles.csv. The vast majority of that time is spent updating the
role ternary relation. As already explained in the introduction, optimization of ternary relations is still a work in progress. Fixing that should be enough to close most of the performance gap between Cell and Java in this particular test.
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_rankrelation variable or in the
- U3: For each director, computes the average rank of the movies they directed, and stores the result in the
director_rankrelation variable or in the
- 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:
and here are the normalized ones:
As you can see, the speed of the code generated by the Cell compiler is generally similar to that of handwritten code in the same language, the most notable exception being update
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:
and here is the normalized version:
When compiling to Java Cell is significantly slower than equivalent Java code only for queries
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# the generated code is noticeably slower than equivalent handwritten C# code also for
Q11, but the reasons for that haven't been properly investigated yet.
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 a bit slower than the most recent one):
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:
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:
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
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 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
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.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.