logo

Chrysalis Software Corporation introduces

ThreeMissesTM

The fastest C++ hash table for persistent memory!

  1. What is ThreeMisses?
  2. Why is it called ThreeMisses?
  3. Do I need it?
  4. What does it do?
  5. How do I use it?
  6. Sample program
  7. Sample output from above program on Intel® Optane™ DC Persistent Memory
  8. What if I don't have persistent memory devices yet? Can I still use it?
  9. Where can I learn more about the performance of ThreeMisses? Do you have benchmarks?
  10. Is there a user manual?
  11. Is there a free version? If so, how do I get it?
  12. What about a paid version?
  13. If I can get a Free version, why would I want the Pro version?
  14. Notes


What is ThreeMisses?

ThreeMisses is a file-format (natively serialized) persistent hash table that provides an interface similar to the C++ unordered_map<string,string> data type, as well as a more advanced interface for higher performance. It is a component of the UserModeVirtualMemory C++ library.

Its Prime Directive is to be the fastest C++ hash table for persistent memory. This means minimal latency and minimal variance in latency.

ThreeMisses in advanced mode can provide near- or sub-microsecond latencies
(95th percentile) for access by key to a terabyte or more of data (e.g., 1 billion records of 1kb each) stored on Intel® Optane™ DC Persistent Memory, depending on the exact hardware and operating system configuration.

ThreeMisses runs on 64-bit versions of Windows 10 (Ubuntu version available soon).

Why is it called ThreeMisses?

It is called ThreeMisses because of its goal of causing no more than three misses in the last-level cache during the entire operation of accessing an existing value by key.
See Introduction To ThreeMisses for details on why this is important with very fast storage such as persistent memory.

Do I need it?

If your answer to at least two of these questions is "yes", and you are working in C++, then ThreeMisses is for you.

What does it do?

It makes a persistent hash table look as though all the items were in memory. This means that you can freely write and read the items, and change the lengths of variable-length data elements. The library takes care of all the details of where the data items will be stored, allocating more storage when necessary if they get larger and putting any extra storage back in its free pool if they get smaller.

How do I use it?

All you have to do is:
1.    Specify the location(s) where the index and data will be stored.
2.    Instantiate a UserModeVirtualMemoryFile variable to represent the file storage.
3.    Instantiate a ThreeMisses variable to represent the data.

Then you can use the ThreeMisses variable as though it were a memory-resident hash table like "unordered_map<string, string>". The algorithm takes care of the details of moving the data onto and off the storage device.

Of course, another benefit of the data being backed by a file is that your program can close the file and stop in the middle of a long computation. In this case, when you restart the program, just reopen the file and re-instantiate the variable(s) you were using, and everything will be as it was.

Sample program

Here is a complete C++ test program showing how easy it is to use ThreeMisses to insert, retrieve, modify, and reread variable-length strings via an interface similar to an unordered_map. (Of course you must link with the library to use this program.)


//ThreeMissesFreeSample.cpp
//Copyright 2019 by Chrysalis Software Corporation

#include <iostream>
#include <random>
#include <time.h>

#include "UMVMCommon.h"
using namespace UMVM;
using namespace std;


int main(int argc, char* argv[])
{
cout << endl << "Library revision: " << UserModeVirtualMemoryFile::GetSVNRevisionNumber() << endl;

if (argc < 4)
{
cout << endl << "Arguments are: indexfilename datafilename count maxsize" << endl;
cout << "indexfilename = full path of index file" << endl;
cout << "datafilename = full path of data file" << endl;
cout << "count = number of variable length strings, in thousands" << endl;
cout << "maxsize = maximum size of each string" << endl;
exit(1);
}

string IndexFileName = argv[1];
string DataFileName = argv[2];
const int64_t count = atoll(argv[3]) *1000;
const int64_t maxsize = atoll(argv[4]);

remove(IndexFileName.c_str());
remove(DataFileName.c_str());

clock_t Start = clock();
clock_t FinishedInit = clock();
clock_t FinishedFirstCompareAndModify = clock();

try
{
UserModeVirtualMemoryFile umvmf(IndexFileName);

ThreeMisses TestMap(&umvmf, "Test map", DataFileName);

char Progress = '0';

for (int64_t i = 0; i < count; ++i)
{
if (i % (count / 10) == 0)
cout << endl << Progress++;
else if (i % (count / 100) == 0)
cout << '.';

auto Key = std::to_string(i);

//Store value in hash table by key
TestMap[Key] = string(i % maxsize, (i % 26) + 'a');
}
}
catch (UMVMException& x)
{
cout << endl << x.what() << endl;
return 1;
}

FinishedInit = clock();
cout << endl << endl << "Finished initialization in " << FinishedInit - Start << " clock ticks" << endl;

string savekey;
string savedata;

try
{
UserModeVirtualMemoryFile umvmf(IndexFileName);

ThreeMisses TestMap(&umvmf, "Test map", DataFileName);

char Progress = '0';

string ScratchBuffer;

for (int64_t i = 0; i < count; ++i)
{
if (i % (count / 10) == 0)
cout << endl << Progress++;
else if (i % (count / 100) == 0)
cout << '.';

string test_string = string(i % maxsize, (i % 26) + 'a');
auto Key = std::to_string(i);

//Retrieve value from hash table by key
string x = TestMap[Key];

if (test_string != x)
{
cout << endl << "Error on compare before modify." << endl;
exit(1);
}

if (x.size())
{
x[0] = 'A';
TestMap[Key] = x;
}

}
}
catch (UMVMException& x)
{
cout << endl << x.what() << endl;
return 1;
}

FinishedFirstCompareAndModify = clock();

cout << endl << endl << "Finished first compare and modification in " << FinishedFirstCompareAndModify - FinishedInit << " clock ticks" << endl;

try
{
UserModeVirtualMemoryFile umvmf(IndexFileName);

ThreeMisses TestMap(&umvmf, "Test map", DataFileName);

random_device rd; // non-deterministic generator
mt19937_64 gen(rd()); // to seed mersenne twister.
uniform_int_distribution<int64_t> dist(0, count-1); // distribute results between 0 and count-1 inclusive.

char Progress = '0';

for (int64_t ii = 0; ii < count; ++ii)
{

if (ii % (count / 10) == 0)
cout << endl << Progress++;
else if (ii % (count / 100) == 0)
cout << '.';

int64_t i = dist(gen); //retrieve records in random order

{
string check = TestMap[savekey];
if (check != savedata)
{
cout << endl << "Error on compare of test element at element #" << i << "." << endl;
cout << "Savedata = " << savedata << endl;
cout << "Check == " << check << endl;
exit(1);
}
}

string test_string = string(i % maxsize, (i % 26) + 'a');

if (test_string.size())
test_string[0] = 'A';

auto Key = std::to_string(i);

//Retrieve value from hash table by key
string x = TestMap[Key];

if (test_string != x)
{
cout << endl << "Error on compare after modify at element #" << i << "." << endl;
exit(1);
}
}
}
catch (UMVMException& x)
{
cout << endl << x.what() << endl;
return 1;
}

clock_t end = clock();

cout << endl << endl << "Finished second compare in " << end - FinishedFirstCompareAndModify << " clock ticks" << endl;

cout << endl << "All values written, read, modified, and read again successfully." << endl;
cout << "Total time = " << end - Start << " clock ticks." << endl;

}



Sample output from above program on Intel® Optane™ DC Persistent Memory

d:\UMVM\UMVMTest>ThreeMissesFreeSample\x64\Release\ThreeMissesFreeSample.exe g:\qtemp\testbig.kvi g:\qtemp\testbig.kvd 10000 1000

Library revision: 4573

0.........
1.........
2.........
3.........
4.........
5.........
6.........
7.........
8.........
9.........

Finished initialization in 13379 clock ticks

0.........
1.........
2.........
3.........
4.........
5.........
6.........
7.........
8.........
9.........

Finished first compare and modification in 32574 clock ticks

0.........
1.........
2.........
3.........
4.........
5.........
6.........
7.........
8.........
9.........

Finished second compare in 40722 clock ticks

All values written, read, modified, and read again successfully.
Total time = 86675 clock ticks.


This run of the program did the following:
The result was an index file of about 1 GB (the allocation unit and minimum size) and a data file of about 6 GB, both of which were stored on an Optane DC persistent memory volume.

Note that the data must be (and is) persistent, because the ThreeMisses object was destroyed and re-instantiated in each of these steps. That is, we could have achieved the same result by running the program three times, adding the ability to select which step to perform.

This program uses the simple "unordered_map" type of access to the data, which is slower than the speed-optimized interface that minimizes memory allocation and copying of data.

As a general indication of real-world performance, random read and random update transaction rates in excess of 500k records per second are achievable with data sets that are stored on Intel® Optane™ DC Persistent Memory, using the Pro version's speed-optimized interface to the data.

Note that the Free version used in this example has a fixed initial allocation of about 1 GB of storage for the index, which will grow as needed to accommodate any number of records. The Pro version has options to increase the initial allocation size for the index and to use DRAM for the index. These options are important for maximum speed, especially if you don't have a very fast byte-accessible storage device.

What if I don't have persistent memory devices yet? Can I still use it?

Absolutely! Of course you won't get the performance that you would get with persistent memory, but it will still work. And if you buy the Pro version and have enough memory to keep the entire index file in DRAM, you will be able to get access to a very large number of records with the minimum possible latency (one access to your storage device).

Where can I learn more about the performance of ThreeMisses? Do you have benchmarks?

We certainly do! See Microsecond-range Access to a 1B Record Key-Value Store, which shows the performance of the Pro implementation of ThreeMisses on several tiers of storage and compares it to benchmarks from Aerospike (https://www.aerospike.com).  There are also benchmark results in Introduction to Three Misses.

Is there a user manual?

Yes, you can find the user manual and programmer reference here.

Is there a free version? If so, how do I get it?

Yes, there is a Free version for Visual Studio 2017. It's available for download here.

What about a paid version?

The Pro version is available for $999, including one year's priority technical support.

Login information for downloading the Pro version will be delivered via email within one business day after you pay with Paypal by clicking on the "Buy Now" button:


If I can get a Free version, why would I want the Pro version?

Because the Pro version gives you greater flexibility and performance, of course!

Feature
Free
Pro
operator []
Yes
Yes
operator =
Yes
Yes
Visual Studio 2017 .lib file
Yes Yes
File size limited only by available storage (up to 2^42 bytes) Yes
Yes
Variable-length key and value lengths up to the size of the entire file Yes
Yes
Sample program illustrating how to use basic features
Yes
Yes
Overflow to a new volume for more storage when the first volume fills up
No
Yes
Tuning parameters for better performance with large numbers of records
No
Yes
Memory buffering to improve performance
No
Yes
Advanced minimal-copy access methods
No
Yes
Sample program illustrating how to use the advanced features of the Pro version
No
Yes
Priority technical support for one year
No
Yes

Notes

  1. The current version of the ThreeMisses library is implemented for Visual Studio 2017 on Windows 10 (Ubuntu version available soon).

  2. The size of any individual variable-length item is limited only by memory/storage, and has been tested to sizes in excess of 2^32 bytes.

  3. This program relies on the LLFIO library, which is very useful when accessing memory-mapped files on Windows or Linux.

  4. All trademarks are the property of their respective owners.