"ocaml_beginners"::[] performance of list vs. variant

Hello,
in the hashtbl.ml you can find

type ('a, 'b) bucketlist =
Empty
| Cons of 'a * 'b * ('a, 'b) bucketlist

I think this is the same es

type ('a, 'b) bucketlist = ('a * 'b) list

Is there any difference?

peter

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

.

On Mon, May 21, 2007 at 06:14:02PM +0200, Peter Halacsy wrote:
> Hello,
> in the hashtbl.ml you can find
>;
> type ('a, 'b) bucketlist =
> Empty
> | Cons of 'a * 'b * ('a, 'b) bucketlist
>
>
> I think this is the same es
>
> type ('a, 'b) bucketlist = ('a * 'b) list
>;
> Is there any difference?

Yes, a small one. The first is:

+--------+--------+--------+
| a | b | tail | --> (next cell)
+--------+--------+--------+

while the second is:

+--------+--------+
| a * b | tail | --> (next cell)
+--------+--------+
|
V
+--------+--------+
| a | b |
+--------+--------+

So the list representation (second one) takes up a bit more memory and
is a little bit less efficient.

Rich.

--
Richard Jones
Red Hat

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

.

Le 21 mai 07 à 18:30, Richard Jones a écrit :

>; On Mon, May 21, 2007 at 06:14:02PM +0200, Peter Halacsy wrote:
>> Hello,
>> in the hashtbl.ml you can find
>;>
>;> type ('a, 'b) bucketlist =
>> Empty
>> | Cons of 'a * 'b * ('a, 'b) bucketlist
>>
>>
>> I think this is the same es
>>
>> type ('a, 'b) bucketlist = ('a * 'b) list
>;>
>;> Is there any difference?
>
> Yes, a small one. The first is:
>
> +--------+--------+--------+
> | a | b | tail | --> (next cell)
> +--------+--------+--------+
>
>; while the second is:
>
> +--------+--------+
> | a * b | tail | --> (next cell)
> +--------+--------+
> |
> V
> +--------+--------+
> | a | b |
> +--------+--------+
>
> So the list representation (second one) takes up a bit more memory and
> is a little bit less efficient.

Would making list as a functor change this ?

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

.

On Mon, May 21, 2007 at 06:46:05PM +0200, Vincent Aravantinos wrote:
> Would making list as a functor change this ?

If you mean something like:

module type InpType =
sig
type t
end

module Make (Inp : InpType) : List with type elt = Inp.t

then I _think_ the answer is no. If InpType contained any functions,
then I suspect it'd be even worse because of the problems described
here:

http://www.lri.fr/~signoles/ocamldefun/manual.html

Rich.

--
Richard Jones
Red Hat

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

.

Le 21 mai 07 à 19:38, Richard Jones a écrit :

>; On Mon, May 21, 2007 at 06:46:05PM +0200, Vincent Aravantinos wrote:
>> Would making list as a functor change this ?
>
> If you mean something like:
>
> module type InpType =
> sig
> type t
> end
>
> module Make (Inp : InpType) : List with type elt = Inp.t
>
> then I _think_ the answer is no. If InpType contained any functions,
> then I suspect it'd be even worse because of the problems described
> here:
>
> http://www.lri.fr/~signoles/ocamldefun/manual.html

That's what I meant (sorry for being so unclear).

I've read this and I'm quite disappointed.
It's surprising it has not been integrated to the compiler
(ocamldefun is 4 years old now), isn't it ?
Maybe it's not so painful after all ?

Vincent

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

.

On Monday 21 May 2007 20:20:39 Vincent Aravantinos wrote:
> I've read this and I'm quite disappointed.
> It's surprising it has not been integrated to the compiler
> (ocamldefun is 4 years old now), isn't it ?
> Maybe it's not so painful after all ?

I think this is a whole-program optimization.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?e

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

.

On Monday 21 May 2007 20:20:39 Vincent Aravantinos wrote:
> I've read this and I'm quite disappointed.
> It's surprising it has not been integrated to the compiler
> (ocamldefun is 4 years old now), isn't it ?
> Maybe it's not so painful after all ?

I think this is a whole-program optimization.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?e

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

.

Le 21 mai 07 à 22:34, Jon Harrop a écrit :

>; On Monday 21 May 2007 20:20:39 Vincent Aravantinos wrote:
>> I've read this and I'm quite disappointed.
>> It's surprising it has not been integrated to the compiler
>> (ocamldefun is 4 years old now), isn't it ?
>> Maybe it's not so painful after all ?
>
> I think this is a whole-program optimization.

Definitely, I have should express myself in a better way, I meant :
maybe not doing this optimization is not so painfull after all.

Vincent

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

.

On May 21, 2007, at 6:30 PM, Richard Jones wrote:

> On Mon, May 21, 2007 at 06:14:02PM +0200, Peter Halacsy wrote:
>> Hello,
>> in the hashtbl.ml you can find
>;>
>;> type ('a, 'b) bucketlist =
>> Empty
>> | Cons of 'a * 'b * ('a, 'b) bucketlist
>>
>>
>> I think this is the same es
>>
>> type ('a, 'b) bucketlist = ('a * 'b) list
>;>
>;> Is there any difference?
>
> Yes, a small one. The first is:
>
> +--------+--------+--------+
> | a | b | tail | --> (next cell)
> +--------+--------+--------+
>
>; while the second is:
>
> +--------+--------+
> | a * b | tail | --> (next cell)
> +--------+--------+
> |
> V
> +--------+--------+
> | a | b |
> +--------+--------+
>
> So the list representation (second one) takes up a bit more memory and
> is a little bit less efficient.
>
> Rich.

Thank you Rich. Very clear.

peter

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

.