Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0002395OCamlOCaml generalpublic2004-03-30 20:502011-12-21 11:39
Reporteradministrator 
Assigned To 
PrioritynormalSeverityfeatureReproducibilityalways
StatusclosedResolutionfixed 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version3.13.0+dev 
Summary0002395: Array.copy can be faster
DescriptionFull_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.

TagsNo tags attached.
Attached Files

- Relationships
related to 0004591closedxleroy A faster version of Array.sub implemented in C 

-  Notes
(0000209)
administrator (administrator)
2004-04-01 17:28

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

(0000210)
administrator (administrator)
2004-04-01 18:12

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

(0000211)
administrator (administrator)
2004-04-04 17:23


 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 (PR#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
>

(0000212)
administrator (administrator)
2004-04-05 17:31

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.

(0006434)
xleroy (administrator)
2011-12-21 11:39

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

- Issue History
Date Modified Username Field Change
2005-11-18 10:13 administrator New Issue
2008-08-07 14:12 xleroy Relationship added related to 0004591
2011-12-21 11:39 xleroy Note Added: 0006434
2011-12-21 11:39 xleroy Status acknowledged => closed
2011-12-21 11:39 xleroy Resolution open => fixed
2011-12-21 11:39 xleroy Fixed in Version => 3.13.0+dev
2011-12-21 11:39 xleroy Description Updated View Revisions


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker