The CDT part of AST provides a full set of container data types, list, queue, stack, ordered set, unordered set, etc. Maps (ie, key -> value) can be constructed as sets. The structure to manage object is called a dictionary, perhaps that's why you mentioned "Dict"?
CDT uses splay trees for ordered sets and two different hash table data structures, hash table with chaining and an unpublished hashtrie structure for unordered set. The unordered search algorithms naturally use the hash values to reduce comparisons in ways similar to a quotient filter. The hashtrie data structure also allows concurrent accesses to a dictionary from separate threads and/or processes with little to no locking. We have applications that routinely manage many millions of objects (even in shared memory via multiple concurrent processes) using CDT dictionaries, for example, to track and analyze flows on the core AT&T network for network engineering purposes. So performance has been ok for us. The quotient filter trick is similar to a Bloom filter (used widely in spell checkers). It works well when you do not expect a search to succeed often. But, it's just an overhead when you expect most searches to succeed. If someday we do run into performance issues with applications that expect many failed searches, I'll consider adding a filter as an optimization option. Phong > From ast-developers-boun...@research.att.com Fri Aug 31 05:04:40 2012 > To: ast-developers@research.att.com > Subject: [ast-developers] Replacing libast Dict algorithm with Quotient > filter algorithm? > Would it make sense to replace the current libast Dict algorithm with > a Quotient filter algorithm? I'm thinking about making associative > arrays faster if there are lots of 1000000+ elements in there. > Quotient filters are described in http://en.wikipedia.org/wiki/Quotient_filter > Josh > _______________________________________________ > ast-developers mailing list > ast-developers@research.att.com > https://mailman.research.att.com/mailman/listinfo/ast-developers _______________________________________________ ast-developers mailing list ast-developers@research.att.com https://mailman.research.att.com/mailman/listinfo/ast-developers
