Motivation

C++11 has introduced the move semantic which can also be used in containers instead of "old-school" pointers. The specific containers owning objects has been proposed earlier by third-party libraries like Boost (for example, ptr_map or ptr_vector).

Hash indexes are used as entry points for memory-optimized tables; both features were introduced in SQL Server 2014. Let's look at index performance in scenario "key-value store".

Scenario and environment

The table stores a significant volume (about 10 millions rows) of pairs key-value. The key is of integer type and the value is a small random string.

The table store is used :

• random read of a value from a key
• random update of a value by a key

We will tests the scenario for the following types of table :

Some countries have integer numbers printed on the transport tickets, for example, in ex-USSR. The ticket is "happy" when the sum of the first half of digits equals to the second one. Then you should eat it and make a wish.

Example:

123456 and 111222 are not happy tickets
123123 and 123222 are the happy tickets

In theory, hash map structure should be very fast on retrieving by key operations, close to O(1) like for an array. A sorted map (keys are sorted) should be O(log₂ N) instead. The following test checks the difference.

Common scenario

We will use one tester class per type of tested structure. The keys are string[10] and are generated randomly in prepared array to avoid additional checks whether the key exists or not.

Let's perform a simple benchmark testing the random and sequential access to arrays and lists. I would like to compare:

• static array with predefined size (allocated on stack)
• TList container class (allocated on heap)
• dynamic array (allocated on heap)
• generic Delphi TList or Free Pascal TFPGList (allocated on heap)

I use an array/list of 10M elements of integer and varaint data type. You can change the type definition in "type" section if need to test other cases.