0002395: Array.copy can be faster

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