Time scales in the cloud

This is still a draft of a very brief post to present and discuss time scales in the cloud.

The table below is a summary of the data needed to better understand the potential performance of distributed databases.

Let assume that 100 bytes of data is to be copied. I will assume that the network had a bandwidth of 10Gb, hence it should take approximately 100ns on the wire to send the data across.


scope communication time latency failure
VM shared memory 100 ns memory latency software
server virtual network 500 ns serialization hardware
rack physical network 1 us network hardware
data center physical network 3 us network data center
different building physical network 20 us – 100 m network data center
remote data center physical network 20 ms – 1000 km network nuclear war
different continent physical network 120 ms – 6000 km network global nuclear war

Discussion to follow


Atomicity of tuple assigment

Tuples in C# have been present since version 4.0 as a library without any language support. C# 7.0 finally introduces proper language integration of tuples. For example, the syntax to create a tuple is simply:

var pair = (1,2);

Deconstructing is also supported:

var (x,y) = pair;

Combining these two features lets us use tuple assignment to swap variables:

(a,b) = (b,a);

Which is almost equivalent to, but more compact and more explicit than, the following:

var temp = a;
a = b;
b = temp;

This behaviour of tuple is akin to atomicity, indeed the left-hand side variables, are only assigned to once all the right-hand side ones have been evaluated. In pseudo syntax of my transactional model we would have:

transaction {
  a = b;
  b = a;

where a and b are both semi-mutable variables, hence changes would only be visible after the atomic block. Or in standard C# syntax:

var tempA = a;
var tempB = b;
a = tempB;
b = tempaA;

The tuple assignment syntax to swap two variables simplifies some standard algorithms such as the partitioning in the quick sort algorithm:

    public int Partition(int[] v, int low, int high) {
        var p = v[high];
        var i = low-1;
        for (int k = low; k < high; k++) {
            if (v[k] < p) {                
                if (i != k) {
                    (v[i], v[k]) = (v[k], v[i]);
        (v[i], v[high]) = (v[high], v[i]);
        return i ;

where the big advantage is that there is no need to use a temporary value or to worry about the order of the various node references are assigned. The downside is readability which decreases as the number of variables increases.

Other algorithms which manipulate linked list can also benefit from this syntax, for example the partitioning of a linked list can be written as:

private ListNode partition(ListNode node, int value) {
if (node == null) return null;
ListNode head = node;
while (node.next != null) {
if (node.next.value < value) {
(node.next, node.next.next, head) = (node.next.next, head, node.next);
} else {
node = node.next;
return head;

where the big advantage is that there is no need to use a temporary value or to worry about the order of the various node references are assigned. The downside is readability which decreases as the number of variables increases.

The atomicity of this tuple assignment in C# is much stronger than, for example, in Python. You might have noticed that in the tuple assignment we first assign a new value to node.next and then to node.next.next. This will give a wrong result in Python, as the lhs are assigned in turn. In C#, the address of the destination variable is evaluated and stored before any assignment is performed.

In terms of atomicity of this assignment operation in case of exceptions, exceptions thrown while evaluating the right-hand side will result in none of the left-hand side value being assigned to. However, if any setter in the left-hand side throws, we can end-up with partially assigned values:

(c.r,c.i) = (1,2);

if the setter of c.i throws an exception, only c.r will have been assigned to, leaving c.i unassigned.

Albeit this assignment is only partially atomic, I find it useful in algorithms where is various variables or properties are swapped around.

Memory benchmarks – writes

All the benchmarks executed so far performed only read operations. So, what about write performance, will they be as fast as reads? In the case of writes we will only be interested in sequential and random reads. The code is almost identical to the one used for the read benchmarks, but instead of reading the value from the array, I write the value of the current index:

for (int i = 0; i &lt; steps; i++) array[(11587L*i) &amp; mask] = i;


for (int i = 0; i &lt; steps; i++) array[i] = i;

To facilitate the comparison between reads and writes I included the results of the read benchmarks. For sequential access, we have:


Where we see that single and dual threaded sequential write bandwidth is identical to read bandwidth, but for a larger number of threads these two diverge with the write bandwidth saturating at about 20 GB/s, while the read bandwidth reaches 40 GB/s with six threads.

For random access there is much less difference between the two cases:


Note that for both benchmarks a single 1 GB array of longs is accessed by all threads. In terms of access time or frequency we are speaking of 18 ns and 56 MHz.

Remember that these results are specific to C# on .Net, better performance is expected from e.g. C++ code or .Net native. It would be worth reproducing the sequential writes benchmark in C++ or in Java to confirm that we are not hitting a .Net bottleneck.

The code is available on Github.

Array based semi-mutable sets – consolidation

The approach described so far minimized the write activity by creating arrays of events that overlap in time. Storing events in arrays results in extremely fast reads, while the only-add-don’t-modify existing data limits the cost of writes. We even saw that in some cases it might not even be necessary to sort the events by time.

Although it was easy to find all events within a time range using simple binary searches, the fact that the events are not fully ordered renders some calculations impossible. For example, any calculation that relies on the time interval between events is pretty much impossible unless all the events are ordered. Similarly aggregation, compression and decimation become much easier or simply feasible when the events are ordered.

The other problem I can see arising is the multiplication of small arrays, there is a point where too many small arrays renders the approach counter productive. The solution to this is to consolidate several arrays into larger ones. This can be done at any time, even when new events are added. Alternatively it can be limited to older events, for example, when one knows that no event older than some time limit will be added to the system.

The following diagrams illustrates the process:

before consolidation

Each line represents an array of events, each dot represents an event. In this example only five arrays overlap. The state of the system after consolidation is then:

after consolidation

where the consolidated array contains all the events within a predetermined time range. Whether one will want to sort the events within the arrays is again a question of “it depends”. In particular it will depend on the size of the array and the expected queries.

My code consolidates all events older than 30 minutes over one minute periods, so that the new event batches contain on average 180’000 events. The consolidation process consists of copying the events to a new array and replacing the truncated batch instances with new one. To optimize this process and avoiding copying the events that are not consolidated unnecessarily I added a new field to the batch class that specifies the first valid event in the event array. This way the (immutable) array of events is reused by the new batch instance.

public struct TradingEvent : IComparable {
    public long Id;
    public long Time; // unix milliseconds
    public short Price;
    public short Volume;
    public short Stock;
    public short BuyerId;
    public short SellerId;
    public short TraderId;
    public long  FirstEvent; // the index of the first event after partial consolidation
    public int CompareTo(object other) {
        return Time.CompareTo(((long)other));

If the small arrays are not sorted, each has to be enumerated to extract the events to be moved to the consolidated array while the remaining ones have to be moved to another array. Potentially one could avoid the second copy operation by adding a filter field to the batch class.

Since I am consolidating over a fixed time period rather than for a fixed array size, the size of the consolidated arrays varies around an average of  5.5 MB. The CLR stores these relatively large arrays in the Large Object Heap. By default the garbage collector does not compact this heap due to the potentially high cost. The downside of this approach is memory fragmentation. There are two ways to avoid this problem, firstly one can ask the garbage collector to compact the Large Object Heap (see here) or use fixed sized arrays.

The consolidation process takes place once every minute, the cost of this operation is dominated by the sorting of the consolidated array. Currently I am using the Array.Sort method. Since the array is already partially ordered a different sort algorithm might improve performance unless it is more efficient to directly merge the arrays rather than copying them and then sort.

On my laptop the sorting takes on average 27 ms, executed every minute this represents a minuscule proportion of time.

Now there are many other ways the events can be stored, the events could be grouped by some property such as the ticket, so that for any time interval there would be as many arrays as tickets. This is just one form of indexing. Again any indexing is possible, it all depends on the use case. This can be taken even further if we have another continuous variable: events can be grouped by range in two or more dimensions. Thus providing double indexing of events.

All this is made easy by the use of transactions as all writes are performed atomically. So at any time it is extremely easy to modify or extend the way the data is stored while maintaining consistency and allowing many readers to run unobstructed.

Note that if time ordering of events is not required within a set, the events can be sorted on any other property. This becomes be particularly interesting if that other property is another continuous property.


Array based semi-mutable sets – implementation

Now a typical example where many items can be added within single transaction is when a database collects time stamped events also called  time series. One can easily imagine a system where many thousands of events are added to a database every second. Obviously there is no point in creating a single transaction per event and in general one can batch them together. The delay between consecutive batches will then depend on the acceptable delay for events to be made available to the database readers. One can imagine batching periods ranging from the order of milliseconds to many seconds or more. Overall the important parameters of such a system are:

  • event production rate
  • batching period
  • events retention period

Together these parameters will determine the liveliness and memory usage of the database. As an example consider NASDAQ trades. About 20 billion shares are traded every day on the NASDAQ, assuming an average of 300 shares per trade (approximate NYSE numbers) and a trading day of 7 hours there are, on average, about 3000 transactions per second. Assuming a retention period of 5 days, we are talking about keeping about 350 million trading transactions in memory. With a batching period of 1 second, we will be creating about 117000 arrays, each containing on average 3000 events. While events are being added to the database, transactions beyond the retention date will be removed by the system. To avoid contention, I will be doing this garbage collection in the same transaction as the one that writes the new events. Essentially I will have a system with a single threaded writer and multi threaded reader.


The trading transactions will be represented using the following data structure:

public struct TradingEvent : IComparable {
    public long Id;
    public long Time; // unix milliseconds
    public short Price;
    public short Volume;
    public short Stock;
    public short BuyerId;
    public short SellerId;
    public short TraderId;
    public int CompareTo(object other) {
        return Time.CompareTo(((long)other));

which takes up 32 bytes. The following data structure holds the array of trades ordered by time:

public struct TradeBatch : IComparable {
    public Guid Id;
    public long First;
    public long Last;
    public TradingEvent[] Trades;
    public int CompareTo(object other) {
        var that = (TradeBatch) other;
        var result = First.CompareTo(that.First);
        if (result == 0) result = Id.CompareTo(that.Id);
        return result;

which are then stored in the following semi-mutable set:

smxSet<TradeBatch> allTradeBatches;

The code first populates 5 days worth of events (about 378 million events, i.e. 11 GB) and then generates 3000 events every second. 500 events are generated with time stamps within the batching period of one second, another 500 events  within 2 seconds, then another 500 within 5 seconds, 500 within 10 seconds, 500 within 30 seconds and the last 500 are generated within 60 seconds. This models the case where events are received after some delay. Hence on average about 60 arrays overlap each other in time, or in other words, for any given time, events can be found on average in 60 arrays.

Since the events within an array are sorted, enumerating all events within a time range is just a matter of filtering the batches that overlap with the desired range and then binary chopping the array to get the required indices that match the time interval:

foreach (var batch in allTradeBatches) {
    var firstIndex = 0;
    var lastIndex = batch.Trades.Length;
    if (start >= batch.First && start <= batch.Last) {
        firstIndex = Array.BinarySearch(batch.Trades, start);
        if (firstIndex < 0) firstIndex = -(firstIndex + 1); } 
        if (end >= batch.First && end<= batch.Last) {
        lastIndex = Array.BinarySearch(batch.Trades, end);
        if (lastIndex < 0) lastIndex = -(lastIndex + 1);
    for (int i = firstIndex; i < lastIndex; i++) {
        totalVolume += batch.Trades[i].Volume;

On average, the binary search should only have to be carried twice on sixty arrays. Once the indices have been determined, all accesses to memory are sequential, i.e. rates of 10 GB/s can be expected, which should translate to 320 Mev/s. Assuming a maximum bandwidth of 50 GB/s when multithreaded, we could expect to read events at the rate of 1.6 Gev/s.

Obviously the binary search adds an overhead. The standard array implementation takes about 4 μs per array fo 3000 events on my laptop. A basic custom implementation, one which doesn’t have to go through the ICompare interface and the unboxing of the long takes 1.4 μs. Assuming 120 binary searches, the current implementation presents an overhead of up to 0.5 ms or, with a custom implementation, 170 μs. To put things in context, this corresponds to the time it takes to sequentially access respectively 160 Kev or 54 Kev.

Interestingly, the binary search time of 4 μs corresponds to reading 1280 events, double that if you have to perform two binary searches and we could have already retrieved 2560 event! Reading the whole array takes almost the same time as performing the binary search! However, this is not the case if one uses the custom implementation, but is still a remarkable fact that highlights the incredible speed of sequential reads. Actually the code to be executed would have to be something like:

for (int i = 0; i < batch.Trades.Length; i++) { 
    if (batch.Trades[i].Time > start && batch.Trades[i].Time < end) {
        totalVolume += batch.Trades[i].Volume;

So let’s see how this compares to the same loop but without the conditions on the time. On an E5 2666 Xeon machine, it took 36 ms with the conditions versus 29 ms without them to enumerate 3000*3600 events. In other words 300 Mev/s versus 372 Mev/s. So a slowdown of about 20%.

The main advantage this last version is that the arrays do not have to be sorted! Whether this is really an advantage will depend on the actual use case, and in general more time is spent reading than writing, so it is often good practice to do more work only once.

I have executed some more complete tests (still focused on enumerating large numbers of events rather than just a few, so the impact of the binary searches should be negligible). The code is executed in up to 8 threads, each threads enumerates a disjoint set of events, for example, in the case of two threads, the first one enumerates the first half of all events while the second thread enumerates the second half. This way all the data from the event batches is read from main memory rather than from the cache. The events set was populated with 5*7*3600 batches of 3000 events.


Single threaded performance stands at 315 Mev/s (almost 10 GB/s), maximum total bandwidth reaches about 1.3 Gev/s. These results include garbage collection of versions, generation of 3000 events every second, removal of old batches, but no persistence to disk.

Using this approach, the database is populated with 126’000 arrays, which is a lot, also on average 60 arrays overlap in time. Although this approach is most efficient at enumerating all the events within a given time range, it is important to note that overall the events are only partially ordered.

In the next post I shall illustrate how these small arrays can be consolidated into fully ordered larger non-overlapping ones.

Memory benchmarks: Addendum tertium: the forgotten TLB

Obviously I have completely forgotten to consider the TLB. In Haswell processors, the L1 TLB contains 64 entries while the L2 TLB holds 1024 entries. All memory accesses must be translated from virtual to physical address, so every single read operation requires a TLB lookup. An L2 TLB miss implies retrieving the TLB entry from memory, so in the worst case a single memory read requires two (chained) memory accesses.

In .Net, page size is 4K, so 1024 TLB entries will cover only 4MB of memory. Remember that the benchmarks executed so far used 1 GB arrays, so in the case of random and chained memory accesses essentially all L2 TLB lookups should fail. But the access times observed don’t seem to exhibit such large delays. So what is going on here? The only explanation I have is that the L3 cache is actually holding all the TLB entries (this could be easily tested by disabling the L3 cache). On x64 a TLB entry is 8 bytes long, so a 25 MB cache will hold one eighth that many TLB entries covering at most 12.5 GB of memory. Hence, to feel the full effect of missed L3 caches we would have to work with arrays much larger than 12.5 GB. I added a few extra tests which deal with much larger arrays. Since I am using arrays of longs and in .Net arrays cannot have more than Int32.MaxValue elements, I have used an array of arrays of longs. Here is an extract of the code for a simplified version of chained reads:

var arrays = sizes.Max().EnumerateTo().Select(t => new long[max]).ToArray();
for (int i = 0; i < steps; i++) {
    next = arrays[i%size][(11587L*(i+next)) & mask]; 
    // first array should be retrieved from cache
    // integer division should be negligible 

The loop for the random reads is the same except for the next variable not appearing on the right hand side.

Here are the results for the 8 cores machine with 30 GB of memory for chained readd:

large array

Well, the full impact of TLB misses is rather clear, memory access is gone from 110 ns to 185 ns and keeps increasing. Caches have become quite complex and I will not attempt to explain the results! Suffice to say that it exhibits a classic cache saturation curve. For 1GB arrays cache hit is close to 100% (1GB needs only 2 MB of TLB entries), while above 30GB cache hit will be close to 0% (30GB requires 60 MB of TLB entries).  Maximum values will be somewhere around 190 ns or 200 ns, which corresponds to a doubling of the access time (allowing for 10 or 15 ns for L3 access).

The other case to consider  is the random reads one:

large array rnd

For random reads, the shape of the curve is very different… and frankly, I have even less to says 🙂 But a few things are worth mentioning. Firstly it seems to start flat which was not the case for the chained reads. Secondly it saturates at already 10 GB with a latency over three times the starting value, while one could expect the maximum latency to be twice that starting value.

Unsurprisingly there, array size has no effect on the performance of sequential reads. Note that it takes about 500 ns to read 4KB. In the worst case, adding a 110 ns delay every 500 ns would increase the average latency by 20 percent. In practice, subsequent TLB entries (assuming linear organization) should be prefetched, and hence have no impact.

So it looks like some of my previous results will not be applicable to very large data sets, so I better rerun my previous benchmarks on much larger arrays!

Bottom line is that for very large arrays the impact of TLB misses due to the tiny pages has a massive effect on latency. Best solution would be to use larger pages, but, sadly enough, that option doesn’t seem to be available in .Net.

[ 10 April 2016] I have updated some previous posts with the latest version of the benchmarks which now share a single 1 GB array to minimize the impact of TLB misses.

Memory benchmarks: Addendum secundum: .Net Native

Windows 10 has been out for a while now and I eventually got a machine running it: the 4 cores machine I have used so far. So I was in a position to try out .Net Native as it seems, disappointingly enough, to be only supported for so-called universal applications on Windows 10. .Net Native uses the same optimization stages as the native C++ compiler, so one would expect to get (in some cases) the same performance level.

Note that in the context of these memory benchmarks, I wouldn’t be expecting much improvements as in most cases we are memory bandwidth limited. The most obvious exception being the sequential reads, as we already know, can be executed faster with vector instructions (15 GB/s versus 11 GB/s on the 4 cores machine). Having said that, I might try the concurrent random reads case of my Addendum primum. I haven’t updated the code which needs various changes to compile on the universal platform. The code as it stands now in Github sums the values in the array and then discards the result. This, obviously, won’t go down very well with a good optimizing compiler, which will just avoid carrying out the calculation. Actually the impact wasn’t always quite as drastic, but still better safe than sorry.

So here is the latest greatest chart for sequential access on the four cores machine using .Net Native:.Net NativeAs expected, or hoped for, .Net Native gives similar performance to C++ or AVX2.

Memory benchmarks: Addendum primum

You might have noticed that I missed one case in my previous blog post: performing multiple independent random reads within a single thread. The code was expanded:

switch (inThreadParallelismLevel) {
    case 1: {
        for (int i = 0; i < steps; i++) {
        total0 += array[(11587L*i) &amp; mask]; 
 case 2: {
    for (int i = 0; i < steps; i++) {
        total0 += array[(24317L * i) &amp; mask];
        total1 += array[(14407L * i) &amp; mask];

We saw that the random reads performance scaled nicely with number of threads up (kind of linearly up to 5 threads on the 6 cores CPU). So the question is whether we can achieve the same when performing  multiple independent random reads within a thread.

Rather disappointingly this is not the case, here are the results for the 8 cores machine, the graph represents the memory bandwidth versus the number of concurrent requests within the single thread:


So, a bit of a surprise, there is absolutely no advantage here in running multiple reads within a thread. The scaling observed in the case of chained reads doesn’t happen here. Mind you it is going about 4 times faster here, so there is less scaling potential.  More importantly the scaling across threads/cores is not present here. So it looks like this will only scale if the memory read requests originate from different cores rather than from a single one.

Memory benchmarks

I have often wondered how the current many-core CPUs can retrieve enough data from memory to feed all its cores. So I decided to carry out a few simple experiments.

I looked at three different scenarios, sequential memory access, dependent chain memory access and random memory access. The second being the case where the result of a read determines the address of the subsequent read (load-to-use).

In the first case, we expect to reach very high memory bandwidth, potentially hitting the maximum specified in the CPU spec with relatively few threads. In the case of chained memory access the bandwidth will reflect the memory’s full (huge) latency. In the third case the bandwidth should be higher but probably not by much. In all cases I am mainly interested in the scalability aspects, i.e. how does the single thread/core bandwidth scale as more threads/cores hit the memory bus.

Note that the code was put together fairly quickly, far more care should be taken to get accurate results, however this should be good enough to understand the scalability aspects I am interested in.

As the goal is to measure main memory access as opposed to cache access, to minimize the impact of the limited TLB buffer, each thread accesses these same 1GB array of 64 bit longs. The code is available on Github. For the sequential case the core loop is simply:

    for (int i = 0; i < max; i++) total += array[i];

The next benchmark is where the addresses of a memory access depends on the value of the previous read:

    for (int i = 0; i < max/8; i++) index = array[index];

where the array has been initialized so that the index performs a random walk through the whole array. This models the case where one walks down a dependency path, e.g.

    var x = a.b.c.d.e.f;

The code for the random access performance test is:

    for (int i = 0; i < max/8; i++) total += array[(i * 11587L) & (max-1)];

where we take large, non-periodic, steps to avoid prefetch and cache effects. Note that since the reads are much slower we perform 8 times fewer memory accesses.

In all of these benchmarks ten runs of one hundred such loops are executed and the best, lowest, time is taken.

I executed this code on three different machines with the following specs:

  1. 4 cores – i7 2600K 3.4- 3.5 GHz with 16GB DDR3
  2. 6 cores – Xeon E5 1650 v3 – 3.4 – 3.5 GHz with 16GB of four channels DDR4
  3. 8 cores – Xeon E5 2666 v3 – 2.9 – 3.2 GHz with 30GB of four channels DDR4

The Xeon E5 2666 v3 is a custom Intel CPU for AWS, you can find more details in The Register.

All the results can be found on Github next to the actual code. Here are the results for sequential access which represents the bandwidth in GB/s as a function of the number of concurrent threads:


First thing to mention is that there is no massive difference between the memory bandwidth of the various systems in the single threaded case. Beyond that the memory bandwidth scales similarly on all CPUs. Where the difference is however significant is how far each system scales. The oldest CPU stops at 20 GB/s (21 GB/s in the spec), while the Xeon 1650 supports double that much (spec says 68 GB/s) and the socket Xeon 2666 with 8 cores reaches 50 GB/s with 8 threads (spec says 68 GB/s). Note that the old CPU uses DDR3 with two channels while the two Haswell CPUs use DDR4 with 4 channels, so no big surprise there.

Althoug not linear, the scalability of each of these is pretty good. The slowest and oldest system scales only up to twice its single threaded performance. The 1650 scales up nearly five times its single threaded performance, while the 2666 goes up to about six or seven times the single threaded performance (albeit starting lower). Note that neither of the Haswell CPUs reaches anywhere close to their spec-ed memory bandwidth of 68 GB/s on the tested systems.

In terms of memory access time, in the single threaded case, the memory bandwidth for the 1650 is equivalent to 0.83 ns access time per long! This number is most impressive, and is down to the quality of the CPUs prefetch unit (actually the streamer) which detects the sequential read pattern and accordingly prefetches aggressively (up to 20 cache lines ahead). You can read all the details (well the ones they made public) about the prefetch unit in Intel’s manual.

Let’s move on onto the chained reads:


where the difference with sequential reads is striking, roughly speaking chained reads are one hundred times slower than the sequential case. This corresponds to a latency of about 90 ns, which is pretty much what one can expect from DRAM nowadays. Note that the bandwidth increases almost linearly with the number of threads and shows no sign of saturating.

Here are the results for random reads. Single threaded bandwidth start a bit below 0.4 GB/s which corresponds to a latency of about 18 ns. Note that in this case the bandwidth increases fairly linearly with the number of threads to saturate at around 2.4-2.6 GB/s.


The difference with the chained reads, a factor of four or five, is due to the fact that since the reads are independent, the CPU can dispatch several of them to the memory controller pretty much concurrently. The memory controller can then take full advantage of the channel and bank-level parallelism as well as memory pipelining to perform concurrent memory reads.

Since this last result seems to indicate that the memory controller is able to dispatch maybe up to five (independent) memory requests concurrently, we could try to take advantage of this by executing multiple chained reads within a given thread:

    for (int i = 0; i < max/8; i++) { 
        index0 = array[index0];
        index1 = array[index1];

I have implemented this code with up to eight concurrent indices. Since all of these dependent chains access the same array, I made sure that all indices are sufficiently distant from each to exclude any caching effect. The code was executed on up to 8 threads on the 8 cores machine. The abscissa (x-coordinate)  is the product of the number of threads and the concurrency level:


In the single threaded case, the maximum bandwidth is 255 MB/s which is very close to the single threaded random reads result of 283 MB/s. When running multithreaded, the maximum bandwidth reaches 1.94 GB/s, again close to the multithreaded random reads of 2.04 GB/s. So, in principle, and possibly at almost not cost at all, one can gain a factor of four in memory bandwidth by executing multiple chained reads within a single loop.

So the bottom line is:

  • sequential access is the king, by a factor of twenty to one hundred
  • chained reads can be made to run four times faster

In the case of chained reads, the huge 90 ns delay between consecutive memory reads should permit the execution of a large number of instructions, potentially hundreds of them, allowing quite a lot of processing of the retrieved data. This is also the case, albeit on a smaller scale, for random reads.

Many thanks to Asier for suggestions, comments,  discussions and comparisons between C++ and C# performance!

[10 April 2016] This graphs in this post have been replaced with the latest version of the benchmark that minimize TLB impact. The text has been edited accordingly.

Array based semi-mutable sets

Persistent sets, on which my semi-mutable sets are based, are usually implemented as trees and are relatively inefficient in both insertion costs and memory usage. They are particularly inefficient when inserting many items in a single transaction as each insert requires the creation of a new path to the newly inserted item. This comes with all the associated memory allocation costs and subsequent garbage collection overhead. This problem can severe when deserializing large sets. Unless of course the data structure supports a merge function.

To illustrate this I have performed some quick and dirty tests on a few .Net data structures:

  • array
  • HashSet
  • FSharpSet

Where the FSharpSet is the only persistent data structure and which I use in my semi-mutable set. The first test consist of populating the data structures with 1’000’000 random longs:

    long[]    12 ms
    long[]   112 ms    and sorted
    HashSet  180 ms    added one at a time
    FSharp  4990 ms    added one at a time

Nothing surprising here, Note that creating the FSharpSet set from an array of longs isn’t faster than adding one item at at a time. A quick look at the source code indicates that the constructor actually adds these values one at a time.

The next tests consist of measuring the enumeration speed of the above structures. 100 enumerations of 1’000’000 elements:

    long[]    820 ms
    HashSet  1400 ms    
    FSharp  14000 ms

Again here, there is no real surprise, except maybe that the HashSet is doing rather well when compared to the array. Note that as the enumeration is executed 100 times in loop, the results might well be different when executed only once due to the caching of the data.

Finally memory usage is again unsurprising:

    long[]    7 MB
    HashSet  37 MB
    FSharp   34 MB

Arrays obviously win, by a factor of four. For small objects such as a long, the difference is massive, with an overhead over the actual data of a factor of 3 for longs. 28 MB of overhead for 1’000’000 elements is about 28 bytes per element, which becomes almost negligible when dealing with large objects.

So, the idea is to combine the advantages of both array and persistent sets in a single structure that minimizes batch insertion time and memory consumption with maximum enumeration speed. We create a persistent set of arrays of values. At its simplest every new batch of values is inserted in the semi-mutable set as an ordered array of values.

Here is a short list of some of the disadvantages of this approach

  • it is expensive to enumerate all the element in order as one will have to continuously hop through all the arrays, unless all the arrays are disjoint.
  • adding or removing a few elements requires the copying of a complete array
  • there is nothing to stop having multiple copies of the same elements in a given sets

However, since the arrays are ordered, it is relatively cheap to enumerate (not in order) all elements in a given range. Though it will still be slower than when working with a fully ordered set as all the arrays have to be searched (unless again they don’t overlap).

In the next post I shall illustrate the implementation and use of this data structure with a fairly realistic example. At that point we will a system with a very large number of relatively small array and we will see how our arrays can be consolidated into fewer, larger ones.

Awelon Blue

Thoughts on Programming Experience Design

Joe Duffy's Blog

Adventures in the High-tech Underbelly

Design Matters

Furniture design blog from Design Matters author George Walker


A Blog for Woodworkers by Gary Rogowski


Woodworking, life and all things between