Category Archives: Scalability

Benchmarking dynamic array implementations

Continuing looking at the performance of data structures and different implementations and languages, let’s look at a simpler but very common container, the dynamic array.

The interesting performance properties of a dynamic array is constant, O(1), lookup time and amortized constant insertion and deletion at the end of the array. Random insertion on the other hand is linear, O(n), and typically something you want to avoid.

Continue reading Benchmarking dynamic array implementations

libdynamic – vector

I think the lack of simple and basic dynamic data structures is a major reason why people sometimes struggle with programming in C.

To take a simple example the naive task of splitting a string into words is near trivial in C++ using the standard library, while in C you are challenged with how to dimension the resulting array. In most cases likely the solution here would be to declare a fixed size array with a MAX_WORDS constant size, and later when the parsing is done and you know the number of words, declare a new array into which you copy the result, and then return. Hardly an elegant solution, and you end up with making difficult assumptions regarding how many words a line realistically can contain.

Continue reading libdynamic – vector

Benchmarking hash table implementations – Java

Java implementations

It was pointed out that some Java hash table implementations were supposed to be faster than the native HashMap. This test was run enabling the Java process access to all 8 virtual cores, which was not the case in the previous benchmarks.

Candidates

  • Java native HashMap – Java(TM) SE Runtime Environment (build 1.7.0_51-b13)
  • Java Colt – v1.0.2
  • Java Trove – v3.0.3

Continue reading Benchmarking hash table implementations – Java

Benchmarking hash table implementations

A first iteration of benchmarks of different hash table implementations.

Candidates

Tested implementations

  • C++11 unordered_map – Apple LLVM version 5.0 (clang-500.2.79) (based on LLVM 3.3svn)
  • C++ Google DenseHash – Google SparseHash v2.0.2
  • Java native HashMap – Java(TM) SE Runtime Environment (build 1.7.0_51-b13)
  • C khash – Above clang environment with khash v0.2.8
  • Lua builtin – LuaJIT v2.0.3

Continue reading Benchmarking hash table implementations

Benchmarking the benchmarks (part 3)

This is a continuation of the previous post

Optimizing the operating system

First a few words about optimization in general.

There is a lot to be said for default configurations. They tend to be very well tested and (hopefully) they are balanced for good all-round performance. Do underestimate the value of this. Introducing an optimization may look great in your synthetic test case, but could very well lower the performance in an actual real life scenario. Or it could improve performance for 95% of your users but leave the remaining 5% complaining about service failures. None of the 95% of the users are going to give you a gold medal for saving some servers, but you can be sure that users with problems will do the opposite.

Continue reading Benchmarking the benchmarks (part 3)