I was rewriting our production code since there were performance concerns and switched from our monstrous std::map to boost multi_index_containers which looked exactly what we need. Then when running performance tests I've noticed that once I use composite_key which includes string the performance drops in orders of magnitude, to be precise, 5 orders. Which, I would say, not reasonable at all. So I created a minimal repro case to post here and ran it on Coliru. Surprise! This behavior does not reproduce on GCC, moreover, the composite key with string for some reason was searched twice faster than int only composite. To me it sounds like a bug or in Boost.MultiIndex MS specific implementation (if such exists) or in MSVC. Tech details: VS2012, Win7x64. The code was compiled and linked targeting x64 architecture. Test output on my local machine: Populating data. Index size: 999999 Running FlyweightMICTest::deepTest Checking getTestData perf. 999999 sum of all IDs. 1M calls took 0 seconds or 125ns per call. ------------------------------------------------------------- Populating data. Index size: 999999 Running FlyweightMICTestWithString::deepTest Checking getTestData perf. 99 sum of all IDs. 99 calls took 1 seconds or 10132326ns per call. =============================================================== Coliru output (live example can be found here http://coliru.stacked-crooked.com/a/ef76d297279f15a8): Populating data. Index size: 999999 Running deepTest Checking getTestData perf. 999999 sum of all IDs. 1M calls took 0 seconds or 395ns per call. ------------------------------------------------------------- Populating data. Index size: 999999 Running deepTest Checking getTestData perf. 999999 sum of all IDs. 999999 calls took 0 seconds or 181ns per call. =============================================================== [Read More]http://feeds.feedburner.com/~r/sizmek-blog/~6/1 [http://www.sizmek.com/Sizmek.png]http://www.sizmek.com/