Request for guidance to add a slightly different ValueType

[gshanemiller]

As I commented in https://github.com/speedskater/hot/issues/3 I was able to get your code to build and run. I am hopeful that with a little more work I can bring insertion times to under 100ns/insert. With finds already running under 100ns/op this trie code would confer distinction for running at the same order of 10 as hashmap code. Let's see.

My latest comparison of HOT to a two hashmap algorithms can be found here https://github.com/rodgarrison/kvbench. In this code I test the equivalent of your CString trie.

However, what I prefer to do is work in terms of the key structure I really have:

template<typename T>
struct Slice<T> {
  unsigned int d_size; 
  T  *d_data;
};

Here I know the size of the string before working with your trie code, and I don't necessarily require a zero terminator. A Slice opens me up to blob keys.

With respect to your code what'd be the best way to code up a Slice<T>? If this is done right I can eliminate some calls to strlen, and perhaps even provide a SIMD key comparator to replace the library's default call to strcmp:

class CStringComparator {
public:
        inline bool operator()(const char* first, const char* second) const {
                return strcmp(first, second) < 0;
        };
}

There are two parts here that I need help with. The library does not like this typedef:

# error: too big
typedef hot::singlethreaded::HOTSingleThreaded<const Slice<char>, ....> HOTTrie;

because a Slice<T> object is too big. Therefore I'll have to fallback to Slice pointers or may be Slice references:

# ok HOT likes this
typedef hot::singlethreaded::HOTSingleThreaded<const Slice<char> *, ....> HOTTrie;

But when I provide my own type I have to also provide a comparator (which I can do) but also a key extractor. The key extractor confuses me. Here's the default implementation for const char*. Note how it defines the key type to be the value type. But I thought I defined the key type to be Slice<T>* already? This API seems to treat Slice<T>* as the value type. Then what's the key type for?

template<typename ValueType>
struct IdentityKeyExtractor {
        typedef ValueType KeyType;

        inline KeyType operator()(ValueType const &value) const {
                return value;
        }
}

What the point of returning self is here? In what sense does HOT need an identity? How should I approach writing a IdentityKeyExtractor for a Slice?