I tested the performance of SortMap vs. HashMap vs. std::unordered_map. I found (as expected) that SortMap performance, which uses a sorted array, is comparable to hash-maps for small lists (< 50 items or so).
A secondary, though also important, result is that all three methods perform at the million-calls per second range.
Results
36 items, 20 million lookups:
SortMap: 625 ms
HashMap: 609 ms
std::unordered_map: 734 ms
120 items, 20 million lookups:
SortMap: 1,046 ms
HashMap: 610 ms
std::unordered_map: 656 ms
1,000 items, 20 million lookups:
SortMap: 1,344 ms
HashMap: 672 ms
std::unordered_map: 812 ms
Code
#include <unordered_map>
#include <string>
#include "Foundation.h"
int main (int argc, char* argv[])
{
int i;
TArray<CString> Ports;
Ports.Insert(CString("Aeon.command"));
Ports.Insert(CString("Anacreon.command"));
Ports.Insert(CString("Celestial.command"));
Ports.Insert(CString("DrHouse.command"));
Ports.Insert(CString("Esper.command"));
Ports.Insert(CString("Exarch.command"));
Ports.Insert(CString("Hexe.command"));
Ports.Insert(CString("Hyperion.command"));
Ports.Insert(CString("Trans.command"));
for (i = 0; i < 241; i++)
Ports.Insert(strPattern("%c%c%c %c%c%c %c%c%c",
mathRandom('A', 'Z'), mathRandom('a', 'z'), mathRandom('a', 'z'),
mathRandom('A', 'Z'), mathRandom('a', 'z'), mathRandom('a', 'z'),
mathRandom('A', 'Z'), mathRandom('a', 'z'), mathRandom('a', 'z')));
TArray<CString> Addresses;
for (i = 0; i < Ports.GetCount(); i++)
{
CString sModule = ((i % 2) == 0 ? CString("CentralModule") : CString("AeonDb"));
CString sMachine = (((i / 4) % 2) == 0 ? CString("Morgaine-1238ef") : CString("Seldon-94fe6a"));
Addresses.Insert(Ports[i]);
Addresses.Insert(strPattern("%s@~/~", Ports[i]));
Addresses.Insert(strPattern("%s@~/%s", Ports[i], sModule));
Addresses.Insert(strPattern("%s@%s/%s", Ports[i], sMachine, sModule));
}
// SortMap
TSortMap<CString, void *> SortMap;
for (i = 0; i < Addresses.GetCount(); i++)
SortMap.Insert(Addresses[i], NULL);
// HashMap
THashMap<CString, void *> HashMap(4096);
for (i = 0; i < Addresses.GetCount(); i++)
HashMap.Insert(Addresses[i], NULL);
// std::map
std::unordered_map<std::string, void *> StdMap;
for (i = 0; i < Addresses.GetCount(); i++)
StdMap.insert(std::pair<std::string, void*>(std::string((LPSTR)Addresses[i]), NULL));
CString sT1 = CString("this is a test that will not be found");
CString sT2 = CString("Trans.command");
std::string stdT1 = std::string((LPSTR)sT1);
std::string stdT2 = std::string((LPSTR)sT2);
// SortMap timings
const int iLoops = 10000000;
DWORD dwStart = ::GetTickCount();
for (i = 0; i < iLoops; i++)
{
void **pFound = SortMap.GetAt(sT1);
if (pFound == NULL)
pFound = SortMap.GetAt(sT2);
if (pFound == NULL)
printf("SortMap: Not found\n");
}
DWORD dwTime = ::GetTickCount() - dwStart;
printf("SortMap: %d ms\n", dwTime);
// HashMap timings
dwStart = ::GetTickCount();
for (i = 0; i < iLoops; i++)
{
void **pFound = HashMap.GetAt(sT1);
if (pFound == NULL)
pFound = HashMap.GetAt(sT2);
if (pFound == NULL)
printf("HashMap: Not found\n");
}
dwTime = ::GetTickCount() - dwStart;
printf("HashMap: %d ms\n", dwTime);
// std::map timings
dwStart = ::GetTickCount();
for (i = 0; i < iLoops; i++)
{
std::unordered_map<std::string, void *>::const_iterator found = StdMap.find(stdT1);
if (found == StdMap.end())
found = StdMap.find(stdT2);
if (found == StdMap.end())
printf("StdMap: Not found\n");
}
dwTime = ::GetTickCount() - dwStart;
printf("StdMap: %d ms\n", dwTime);
return 0;
}
Resolve
Archive
Reopen
Create
Edit
Save
Attach File
Cancel Edit