Comment author: administrator

Dear George,

While doing some profiling I noticed that Array.copy internally
uses the "modify" function. I do not fully understand the internals
of the run-time system, but I think that it is not necessary to use
"modify" in this case. However, I think that the only way to
achieve this is to write Array.copy in C.

There's only one case where I'm sure "modify" isn't needed: when
the two arrays (source and destination) are in the young generation.
(But I'll let our GC expert comment on that.)

Did you had other cases in mind?

Best wishes,

• Xavier

Comment author: administrator

On Apr 1, 2004, at 17:28, xavier.leroy@inria.fr wrote:

There's only one case where I'm sure "modify" isn't needed: when
the two arrays (source and destination) are in the young generation.
(But I'll let our GC expert comment on that.)

I think the only interesting cases are:

(1) when the new array is in the young generation (regardless of
the position of the original array)
(2a) int arrays
(2b) float arrays

The exact condition (2) subsumes (2a) and (2b): when you are sure
that none of the fields of the array points to something in the
young generation.

I think modify is already short-circuited in case (2b).
There is no way to tell at run-time when we are in case (2a).
Caml code cannot test case (1) reliably because the condition
might change after the test.

If we move Array.copy to the C code, we can handle case (1)
more efficiently. I'm not convinced it would make a noticeable
difference in any program that really uses the arrays (as opposed
to a synthetic benchmark that copies the arrays and discards
them immediately).

On the other hand, C code is obviously more expensive to write,
debug, and maintain. The less C we have, the better.

-- Damien

Comment author: administrator

Hi,

Perhaps I do not understand the GC that ocaml uses. But when you do an
Array.copy, the new array is going to be young. I thought that one can have
a make_vect like function that also does a memcpy to copy the contents of
the old array.

I looked now at make_vect and I see that it is more complicated than I
thought it would be. So, it may very well be that I am wrong.

George.

-----Original Message-----
From: Xavier Leroy [mailto:xavier.leroy@inria.fr]
Sent: Thursday, April 01, 2004 7:28 AM
To: necula@cs.berkeley.edu
Cc: Caml bug tracking system
Subject: Re: Array.copy can be faster (#2395)

Dear George,

While doing some profiling I noticed that Array.copy
internally uses
the "modify" function. I do not fully understand the
internals of the
run-time system, but I think that it is not necessary to
use "modify"
in this case. However, I think that the only way to
achieve this is
to write Array.copy in C.

There's only one case where I'm sure "modify" isn't needed:
when the two arrays (source and destination) are in the young
generation.
(But I'll let our GC expert comment on that.)

Did you had other cases in mind?

Best wishes,

• Xavier

Comment author: administrator

From: necula@eecs.berkeley.edu

Perhaps I do not understand the GC that ocaml uses. But when you do an
Array.copy, the new array is going to be young. I thought that one can have
a make_vect like function that also does a memcpy to copy the contents of
the old array.

Well, only if its size is smaller than Max_young_wosize, which seems
currently to be 256, so this is going to be right quite often.

I looked now at make_vect and I see that it is more complicated than I
thought it would be. So, it may very well be that I am wrong.

The case < Max_young_wosize is actually pretty simple:

if (size < Max_young_wosize) {
  res = caml_alloc_small(size, 0);
  for (i = 0; i < size; i++) Field(res, i) = init;
}

So I suppose you're right this could be optimized.
I've got no idea whether it is worth it or not (considering all the
special cases).

By the way, the following cases in make_vect look like a clever
optimization to avoid creating back references to the young
generation. Which made me wonder why the last case calls
caml_initialize, while supposedly init is not young.
"Safe for the future"?

Jacques

-----Original Message-----
From: Xavier Leroy [mailto:xavier.leroy@inria.fr]

There's only one case where I'm sure "modify" isn't needed:
when the two arrays (source and destination) are in the young
generation.
(But I'll let our GC expert comment on that.)

I'm no GC expert either, but my belief was that only the destination
mattered: as long as you are initializing a young block, you should
be safe.

Comment author: @xavierleroy

Faster implementations of "Array.blit", "Array.copy", "Array.sub", "Array.append" and "Array.concat" now integrated in SVN trunk (commit 11913).