Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Array.copy can be faster #2395

Closed
vicuna opened this issue Mar 30, 2004 · 5 comments

Comments

Projects
None yet
1 participant
@vicuna
Copy link

commented Mar 30, 2004

Original bug ID: 2395
Reporter: administrator
Status: closed (set by @xavierleroy on 2011-12-21T10:39:17Z)
Resolution: fixed
Priority: normal
Severity: feature
Fixed in version: 3.13.0+dev
Category: ~DO NOT USE (was: OCaml general)
Related to: #4591

Bug description

Full_Name: George Necula
Version: 3.07
OS: cygwin
Submission from: raw.cs.berkeley.edu (128.32.153.230)

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.

George.

@vicuna

This comment has been minimized.

Copy link
Author

commented Apr 1, 2004

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
@vicuna

This comment has been minimized.

Copy link
Author

commented Apr 1, 2004

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

@vicuna

This comment has been minimized.

Copy link
Author

commented Apr 4, 2004

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
@vicuna

This comment has been minimized.

Copy link
Author

commented Apr 5, 2004

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.

@vicuna

This comment has been minimized.

Copy link
Author

commented Dec 21, 2011

Comment author: @xavierleroy

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.