The CDT part of AST provides a full set of container data types, list, queue, 
ordered set, unordered set, etc. Maps (ie, key -> value) can be constructed as 
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 
hash table with chaining and an unpublished  hashtrie structure for unordered 
The unordered search algorithms naturally use the hash values to reduce 
in ways similar to a quotient filter. The hashtrie data structure also allows 
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 
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 
has been ok for us.

The quotient filter trick is similar to a Bloom filter (used widely in spell 
It works well when you do not expect a search to succeed often. But, it's just 
overhead when you expect most searches to succeed. If someday we do run into 
issues with applications that expect many failed searches, I'll consider adding 
a filter
as an optimization option.


> From Fri Aug 31 05:04:40 2012
> To:
> 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

> Josh
> _______________________________________________
> ast-developers mailing list

ast-developers mailing list

Reply via email to