"ocaml_beginners"::[] min-heap algorithm

2006/11/28, drehman27 < drehman27%40yahoo.com">drehman27yahoo.com>:
>; --- In ocaml_beginners%40yahoogroups.com">ocaml_beginnersyahoogroups.com, Brian Hurt <bhurt...> wrote:
&gt; > One of the things to know about imperitive (mutable) data structures in
> > Ocaml is that the Ocaml GC doesn't want objects in the major heap to
> have
> > references to the minor heap. This means that if you write a
> pointer to
> > an object in the minor heap into an object in the major heap, a minor
>; > collection occurs.
&gt;
> I am not following you here. I am not familiar with the workings of a
> GC. Would you care to explain with an example please?

Well, in ocaml, when you create a new value (say (Some 10)) it
allocate some memory for it. It put it at first in the minor heap,
where allocation and dealocation is very quick (one addition, and one
comparison). When the minor heap is full, it move value that are still
living (that is you still use them) in the major heap, where
allocation and dealocation is more expensive.

When you use imperative code, you may put a reference from an object
of the major heap to an object in the minor heap, and this will slow
the minor heap dealocation. Note also that when you do an imperative
affectation, their is a bigger cost in ocaml than in other language,
due to the gc.

>;
>
&gt; This can get very spendy, especially if objects that
> > normally wouldn't survive to get promoted to the major heap do
> because a
> > minor collection was kicked off too early- at which point collecting
> them
> > becomes more expensive. So for reasonably small data sets (and,
>; from my
> > experience, 700 elements generally qualifies as "reasonably small";),
> O(log
>; > N) cost purely applicative structures are often faster than O(1)
> > imperitive structures.
> >
>
> I will have to create thousands of heaps of size 700 sequentially, but
> I will only need one at a time (because I will write them to disk and
> the GC can reclaim space from each dumped heap).
&gt; Even in this situation do you still recommend purely applicative
> structures?

Generaly speaking, it's better for the ocaml GC to use applicative
structure, it's optimized for them.

Note also that you can change your implementation of the MiniHeap
afterward relativley easily, and then compare the real speed for your
application.

Messages in this topic (7) Reply (via web post) | Start a new topic

.