String Interning – Trie vs. Hash Table Deathmatch

Judy arrays obtain their performance by using a myriad range of possible leaf and branch nodes. The goal is to fit as much data that could be used for decision making and branching in the first cache line that would be read. And in the case of very sparse tries this pays off handsomely.

That said, hash tables are really hard to beat. They are susceptible to denial of service attacks though.

[1] http://judy.sourceforge.net/application/shop_interm.pdf

[2] http://loup-vaillant.fr/projects/string-interning/intern_tri...

Basically all the data fit in the CPU cache, so what was being measured was mostly the number of steps needed for each algorithm.

For most real uses, the cache is a large part of the performance. If you are using the data in order, the trie may be faster because the next entry will likely already be cached. If you are using data in random order or doing other work in between lookups, the hashtable may be faster because it only has to fetch 1 or 2 lines into the cache instead of several.

It's actually reasonably easy to avoid the unnecessary copying.

Something like this would do (use a string as the buffer, pass it by reference, then use `try_emplace`). Also, it should probably be using the same hash function as your C code:

    #include <cstdint>
    #include <fstream>
    #include <string>
    #include <unordered_map>

    class Intern_pool
    {
        struct fvn_hash
        {
            // FVN-1a hash -- http://isthe.com/chongo/tech/comp/fnv/
            std::size_t operator()(const std::string& s) const
            {
                std::size_t hash = 2166136261; // offset basis (32 bits)
                for (auto c : s)
                {
                    hash ^= c;       // xor
                    hash *= 16777619;   // prime (32 bits)
                }
                
                return hash;
            }
        };

        std::unordered_map<std::string, std::uint32_t, fvn_hash> map;
        std::uint32_t next = 0;

    public:
        std::uint32_t add(const std::string& s)
        {
            auto r = map.try_emplace(s, next);
            if (r.second)
            {
                ++next;
            }

            return r.first->second;
        }
    };

    int main(int argc, const char* argv[])
    {
        for (int i = 1; i < argc; ++i)
        {
            std::ifstream file(argv[i]);

            Intern_pool intern_pool;

            std::string line;
            while (std::getline(file, line))
            {
                intern_pool.add(line);
            }
        }

        return 0;
    }

Would this be necessarily worse performance than a Trie or Hash ?