Project

General

Profile

Cleanup #1065

Create a more efficient caching structure for location lookup

Added by Eric Mikida about 3 years ago. Updated over 1 year ago.

Status:
In Progress
Priority:
Normal
Assignee:
Category:
-
Target version:
-
Start date:
05/11/2016
Due date:
% Done:

0%


Description

In the 64 bit merge, spring cleaning was eliminated in order to clean up the code and remove the large CkLocRec class hierarchy. In doing so, location lookup was changed to use a std::map, however the intent was that eventually a more efficient caching structure would be used that not only provided faster lookups, but took over some of the spring cleaning functionality by behaving similarly to a cache. The original commit can be found here: https://charm.cs.illinois.edu/gerrit/gitweb?p=charm.git;a=commit;h=337fdfc5d9628a6575fbbddba4e977d7ba9839c6

History

#1 Updated by Sam White over 2 years ago

  • Status changed from New to In Progress
  • Assignee set to Eric Mikida

Change from std::map to std::unordered_map: https://charm.cs.illinois.edu/gerrit/#/c/1978/
Use tr1/unordered_map on BGQ: https://charm.cs.illinois.edu/gerrit/#/c/2013/

#2 Updated by Sam White over 1 year ago

Change CkLocMgr's std::unordered_map's to ska::flat_hash_map's: https://charm.cs.illinois.edu/gerrit/#/c/3170/

Need to check compiler dependencies of this, benchmark its performance with applications, and potentially write a PUP routine for it.

ska::flat_hash_map is taken from: https://github.com/skarupke/flat_hash_map

ska::flat_hash_map is described and micro-benchmarked here: https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/

Another hash table implementation to look at would be tsl::hopscotch_map: https://github.com/Tessil/hopscotch-map

#3 Updated by Phil Miller over 1 year ago

There'd be no need for a pup for this particular structure - it can be completely discarded and reconstituted when the location manager instance unpacks itself.

Also available in: Atom PDF