Re: big data structure problem in ocaml

[Anil Madhavapeddy <anil@xxxxxxxxxx>]

On 28 Jan 2013, at 19:54, Thomas Gazagnaire <thomas.gazagnaire@xxxxxxxxx> wrote:

>> ********************************
>> module OrdKey = struct
>>  type t = string
>>  let compare = Pervasives.compare
>> end
> 
> If you keys are always be strings, I would suggest using the optimized 
> String.compare.
> 
>> module KVMap = Map.Make(OrdKey)
>> let kv = ref KVMap.empty
>> ……
>> (* each time when a new kv pair is set, the following is invoked *)
>> kv := KVMap.add !key_in_process line !kv
>> **********************************
> 
> You are not copying kv here, you are just setting the box where you store the 
> kv tree with an updated tree, so you can't do much.
> 
>> Does anyone have some hint? Or there are example code for similar problems 
>> in the ocaml world？
> 
> What are you testing exactly ? Do you care about fast reads or fast writes ? 
> Do you clean-up your cache regularly or is it an ever-growing one (which 
> could explain the performance issues).
> 
> Some hints: usually a cheap way to build fixed-size cache is to use 
> hash-indexed arrays: if you have few hash collision and a rough idea of the 
> number of elements you want to store, that's pretty efficient. An example 
> here:
> 
> https://github.com/samoht/ocaml-openflow/blob/master/controller/learning_switch.ml#L41

Note also that this sort of data structure work is better done in UNIX and 
userspace, where you can use conventional profiling tools to measure the size 
complexity.

You could also consider trying a normal mutable Hashtbl instead of a functional 
Map, which may operate better depending on your specific workload...

-anil