Performance comparison: std::set vs. std::unordered_set vs. custom trie

I recently interviewed with a large company where I was asked how I would check that a given word was a valid English word.  Knowing that there were on the order of a few tens of thousands of stems, and that each stem may have many variations, I figured that there were maybe a few hundred thousand possible words in the English language.  With each word having average length probably in the 7 range, there might be a million or so characters in this set.  I concluded that the check could be performed by searching an in-memory dictionary, and proposed either a std::unordered_set, or a custom trie, with a performance test necessary to see which would be faster.

I decided to perform this test.


I decided to actually perform two tests: element addition performance, and element checking performance.

I wrote a simple Windows C++ application using the Windows performance analysis technique I described in a gist.  In this simple C++ application, lines from an input file are added into the data structure, and lines from another input file are used to search the data structure.  The application outputs a single CSV line containing information such as the number of elements added to the DS, the number of elements for which a search was performed, the number of elements found in the data structure, time to add all elements to the data structure, time to search for all elements, and more.

Then I wrote a python script to call the C++ application using slightly modified input files from the Moby Words II data set.  The data set was modified so that the files contained only letters in the ASCII table between space and tilde.  This seemingly corrected errors in the text, and allowed each trie node to have a smaller range of allowable children.  Each of the 16 files in the data set is paired with each of the 16 files in the data set as both an input and output, for a total of 256 tests.

The files in the data set can be summarized as follows, courtesy of Project Gutenberg’s description :

  • acronyms.txt: 6,213 acronyms
    common acronyms & abbreviations
  • common.txt: 74,550 common dictionary words
    A list of words in common with two or more published dictionaries.
    This gives the developer of a custom spelling checker a good
    beginning pool of relatively common words.
  • compound.txt: 256,772 compound words
    Over 256,700 hyphenated or other entries containing more than one
    word as well as all capitalized words and acronyms. Phrases were
    considered ‘common’ if they or variations of them occur in standard
    dictionaries or thesauruses.
  • crosswd.txt: 113,809 official crosswords
    A list of words permitted in crossword games such as Scrabble(tm).
    Compatible with the first edition of the Official Scrabble Players
    Dictionary(tm). Since this list has all forms: -ing, -ed, -s, and so
    on of words, it makes a good addition when building a custom spelling
  • crswd-d.txt: 4,160 official crosswords delta
    When combined with the 113,809 crosswords file, it produces the
    official crossword list compatible with the second edition of the
    Official Scrabble Players Dictionary. (Scrabble is a registered
    trademark of Milton-Bradley licensed to Merriam-Webster.)
  • fiction.txt: 467 current fiction substrings
    The most frequently occurring 467 substrings occurring in a
    best-selling novel by Amy Tan in 1990.
  • freq.txt: 1,000 by frequency
    This file consists of the 1,000 most frequently used English words
    from a wide variety of common texts listed in decreasing order of
  • freq-int.txt: 1,000 by frequency internet
    This file consists of the 1,000 most frequently used English words
    as used on the Internet computer network in 1992.
  • KJVfreq.txt: 1,185 King James Version frequent substrings
    The most frequently occurring 1,185 substrings in the King James
    Version Bible ranked and counted by order of frequency.
  • names.txt: 21,986 names
    This database contains the most common names used in the United
    States and Great Britain. Spelling checkers may want to supplement
    their basic word list with this one.
  • names-f.txt: 4,946 female names
    frequent given names of females in English speaking countries
  • names-m.txt: 3,897 male names
    frequent given names of males in English speaking countries
  • oftenmis.txt: 366 often misspelled words
    many of the most commonly misspelled words in English speaking countries
  • places.txt: 10,196 places
    a large selection of place names in the United States
  • single.txt: 354,984 single words
    Over 354,000 single words, excluding proper names, acronyms, or
    compound words and phrases. This list does not exclude archaic words
    or significant variant spellings.
  • usaconst.txt: USA Constitution
    The Constitution of the United States, including the Bill of Rights
    and all amendments current to 1993.

All the tests were run one time on my Broadwell i7-5950HQ CPU @ 2.90GHz, a quad-core hyperthreaded CPU supporting 8 threads.  This machine has 16GB of RAM.

I imported the results into an Excel spreadsheet, formatted it nicely, added some fields, and made some charts that I thought would reveal some trends.

All the source code, and the analysis Excel file, are available in my github repo.

Analysis & Discussion

Here’s the aggregations that I thought were interesting.  If you’d like to see more analysis, let me know specifics in the comments!  Or, just clone the github repo and start working with the data in the Excel file.

In the tables and charts below, I used “uos” to represent std::unordered_set, “set” to represent std::set, and trie to represent the custom trie.  This allows the tables and charts to be somewhat more concise.


Data Structure # insert wins Min insert winning time Max insert winning time Min insert time difference Average insert time difference Max insert time difference Average insert % improvement
set 162 142 117630 1 24322 134577 34
uos 94 111 2156 5 261 1406 33

There is no typo or missing data here – the trie did not win a single test of insertion performance with this input data.  Std::set won about 63% of the tests while std::unordered_set won the other 37%.  We can see by the average percent improvement that when either data structure won, it outperformed the next best performer by an average of ~33%.  However, the min winning time, max winning time, average time difference, and max time difference seem to point to a conclusion that the std::set is faster at storing larger sets of strings, while maybe the std::unordered_set is faster at storing smaller sets of strings.

This chart, with number of strings stored in the set on the x-axis and number of wins on the y-axis, shows the trend precisely.  Std::unordered_set wins almost every test of small set size, while std::set wins every test of larger set size.

Deeper investigation shows that std::unordered_set wins in the files fiction.txt, freq.txt, freq-int.txt, kjvfreq.txt, oftenmis.txt, and usaconst.txt.  These files typically contain strings where each line contains a phrase of 1 – 3 words (1 – 20 chars), though usaconst.txt contains lines with long strings containing up to 60 or more characters.

Set wins in the files acronyms.txt, common.txt, compound.txt, crosswd.txt, crswd-d.txt, names.txt, names-f.txt, names-m.txt, places.txt, and single.txt.  These files contain short strings of 1 – 3 words, up to ~20 characters.

Since std::set is typically implemented using some kind of binary search tree, and std::unordered_set is typically implemented with an open hash (array of buckets, with each bucket containing a list) it appears that in these implementations there is lower initial overhead with a std::unordered_set, but worse asymptotic performance; there is higher initial overhead with std::set, but better asymptotic performance.  Perhaps the initial rebalances in the binary tree, especially when created using sorted data, are more expensive than filling the buckets in the open hash with very few items.  However, when the buckets start to accumulate multiple items per bucket and need to be searched linearly, the binary tree can be faster.

Finally, a trie appears to have both higher initial overhead than both std containers, and worse asymptotic insertion performance; this is probably because it potentially creates multiple new nodes for each inserted string, while the std containers probably create one new node per inserted string.


Data structure # search wins Min search winning time Max search winning time Min search time difference Average search time difference Max search time difference Average search % improvement
trie 200 2 49153 5 4066 31051 78
uos 56 28 80969 10 4481 101197 42

Again, no missing data in this table – std::set did not win a single search performance test.  In this data set, the trie wins approximately 78% of the tests while std::unordered_set wins the other approximately 22%.

The trends in this data are far less clear, so let’s take a closer look at some interesting charts.

This one is a little hard to read but it’s got “percent of inserted strings found” on the x-axis and number of wins on the y-axis.

What this unsurprisingly shows is that when there’s very small intersection between the strings that were inserted and the strings that were searched for, the trie wins.  This could be because a trie can theoretically determine mismatch between a string and the dictionary with a single array element read.  For example, when comparing names.txt, which contains strings all starting with a capital letter, with freq-int.txt, which effectively contains strings starting with a number, the trie always finds that the first character of the search string has no branch in the trie’s root node, so it returns false very quickly.  On the other hand, when searching a binary tree, the search takes approximately log N time to reach a leaf and determine there’s no match.

On the other hand, when there’s a very large/complete intersection between the inserted strings and the search strings, the std::unordered_set wins.  This is again not too surprising, because the trie performs length(searchstring) array element reads which cannot be vectorized.  The binary tree must perform more than length(searchstring) character comparisons, but they can be vectorized.

So the vast majority of the trie’s search wins occur when there is very small intersection between the inserted strings and the search strings, for the obvious reason that it is very fast at determining that a search string starts with a letter that none of the inserted strings start with.  Here’s the data with those points removed, to get a better sense of general-purpose search performance:

Data structure # search wins Min search winning time Max search winning time Min search time difference Average search time difference Max search time difference Average search % improvement
trie 47 11 49153 5 6223 27741 60
uos 33 51 80969 15 7361 101197 38

The trie still wins more tests than the std::unordered_set.  Also, in the search tests where it wins, it outperforms the next best performer by an average of 60%.  On the other hand, when std::unordered_set wins, it beats the next best performer by an average of 38%.

There’s a similar trend for “percent of searched strings found” and “winning search time” with possibly a slightly more visible trend of the trie performing better with small intersection of inserted & search sets, and std::unordered_set performing better with large/complete intersection.  Those charts are in the “search wins vs % searched found” and “search wins vs winning time” tabs of the Excel spreadsheet.


With many use cases, reads/searches are performed far more often than writes/inserts – think of financial transactions, event signups, online store orders, and more.  For this reason, it’s often preferable to optimize for read/search performance rather than write performance.

When performing search operations on a string set, it seems clear that the fastest data structures are either a custom trie or a std::unordered_set.  When the search data is expected to have a small intersection with the inserted data, such as looking for strings indicating malware in the output of the unix “strings” command, a trie is likely to be the fastest data structure.  When the search data is expected to have a large/complete intersection with the inserted data, such as the grader of a spelling test, a std::unordered_set is likely to be the fastest data structure.

However, there are use cases where write/insert performance is more important than read/search performance.  For example, an algorithm that finds unique strings in a data set by inserting them into a set ought to consider using std::set for this purpose.

A final note about these performance tests: it’s likely the std::set and std::unordered_set implementations are highly optimized, and may even have specialized template implementations for std::string.  The custom trie was written by a single developer in a couple of hours.  There could be a lot of room in the trie implementation for improvement.

Finally, there was no attempt during these experiments to measure the memory usage of the various data structures.  It’s very likely that the trie uses significantly more memory than either of the std containers, since each node uses an array of almost 100 ints, where 0 or more are used.  It’s a very sparse data structure.

So that’s it!  If you’re interested in this, please take a look at the github repo that contains all the source, and the Excel sheet  that contains the analysis.  Also, I’m always interested in discussions spurred on by my posts, and learning what I’ve done wrong or suboptimally.  So if you’d like to discuss or correct anything, please let me know by leaving a comment below!

Leave a Reply

Your email address will not be published. Required fields are marked *