performance of ocamlgraph and ocaml batteries

performance of ocamlgraph and ocaml batteries

[Kihong Heo]

Dear all.

I have a big program using ocaml graph and ocaml batteries.
When I was improving performance of the program, I was curious about 
the performance of those library.

I use old version of ocaml batteries (maybe beta version?) and the latest version of ocamlgraph.
And I just use PMap and PSet among ocaml batteries. 
(now those are changed to BatPMap and BatPSet as I know).

I want to know 
1. Is there a big difference in memory consumption between old and new version of ocaml batteries?
2. Generally, is the memory consumption of ocamlgraph is effective?

Please let me know.

Best,

- Kihong Heo

Re: [Caml-list] performance of ocamlgraph and ocaml batteries

[Michael Ekstrand]

On 12/12/2010 11:09 PM, Kihong Heo wrote:
> I have a big program using ocaml graph and ocaml batteries.
> When I was improving performance of the program, I was curious about 
> the performance of those library.
>
> I use old version of ocaml batteries (maybe beta version?) and the latest version of ocamlgraph.
> And I just use PMap and PSet among ocaml batteries. 
> (now those are changed to BatPMap and BatPSet as I know).
>
> I want to know 
> 1. Is there a big difference in memory consumption between old and new version of ocaml batteries?

There shouldn't be.

> 2. Generally, is the memory consumption of ocamlgraph is effective?

In my experience, it is quite reasonable in its memory use (particularly
compared with a Java library I tried).  The ultimate test, though, is
your application.  Can you do the computations you need within the
resources you have available?  I'm guessing it'll be pretty hard to beat
ocamlgraph, though, except with a very tight array-based implementation
with integer nodes.

-Michael

Re: [Caml-list] performance of ocamlgraph and ocaml batteries

[Eray Ozkural]

[-- Attachment #1: Type: text/plain, Size: 987 bytes --]

On Mon, Dec 13, 2010 at 4:47 PM, Michael Ekstrand <michael@elehack.net>wrote:
>
> > 2. Generally, is the memory consumption of ocamlgraph is effective?
>
> In my experience, it is quite reasonable in its memory use (particularly
> compared with a Java library I tried).  The ultimate test, though, is
> your application.  Can you do the computations you need within the
> resources you have available?  I'm guessing it'll be pretty hard to beat
> ocamlgraph, though, except with a very tight array-based implementation
> with integer nodes.
>
>

Oww, is the imperative implementation using hash tables or maps then? You
can always implement an adjacency list structure with dynamically sized
arrays. That's what boost::graph does. Shouldn't be too hard to plug your
own in ocamlgraph if needed.

Cheers,


-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

[-- Attachment #2: Type: text/html, Size: 1523 bytes --]

Re: [Caml-list] performance of ocamlgraph and ocaml batteries

[Julien Signoles]

[-- Attachment #1: Type: text/plain, Size: 613 bytes --]

Hello,

2010/12/13 Eray Ozkural <examachine@gmail.com>

> Oww, is the imperative implementation using hash tables or maps then?
>

Imperative implementations use hash tables (except the ones called Matrix
which use arrays of bitvectors) while persistent implementations use maps.


> Shouldn't be too hard to plug your own in ocamlgraph if needed.
>

OcamlGraph is designed for such an use : each algorithm provided by the
library is a functor parameterized by the required graph operations
(iterators over vertices and edges, ...). Thus you can provide your own in
an easy way.

Hope this helps,
Julien Signoles

[-- Attachment #2: Type: text/html, Size: 1080 bytes --]

Re: [Caml-list] performance of ocamlgraph and ocaml batteries

[Eray Ozkural]

[-- Attachment #1: Type: text/plain, Size: 1670 bytes --]

On Mon, Dec 13, 2010 at 5:51 PM, Julien Signoles
<julien.signoles@gmail.com>wrote:

> Hello,
>
> 2010/12/13 Eray Ozkural <examachine@gmail.com>
>
> Oww, is the imperative implementation using hash tables or maps then?
>>
>
> Imperative implementations use hash tables (except the ones called Matrix
> which use arrays of bitvectors) while persistent implementations use maps.
>

Yes, I noticed, the incidence matrix is pretty good for dense unlabeled
graphs, that's probably better than the one boost provides.


>
>
>> Shouldn't be too hard to plug your own in ocamlgraph if needed.
>>
>
> OcamlGraph is designed for such an use : each algorithm provided by the
> library is a functor parameterized by the required graph operations
> (iterators over vertices and edges, ...). Thus you can provide your own in
> an easy way.
>
> Hope this helps,
>

Sure it does. I've used ocamlgraph in a number of projects and I'm very glad
with the functor interface. It feels right! One of the big reasons I'm using
ocaml is the higher-order module feature, it's great for writing truly
extensible and re-usable software.

Regarding the above discussion, hash table is actually appropriate for a
very large number of use-cases and I've seen it recommended it in a software
engineering journal. That's true especially if you need to query individual
edges, although many classical graph algorithms work best with an adjacency
list representation, which can be easily implemented as you suggest.

Best,

-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

[-- Attachment #2: Type: text/html, Size: 2843 bytes --]