[Issue 3637] New: Array append patch to prevent stomping and to enhance thread-local append performance

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=3637

           Summary: Array append patch to prevent stomping and to enhance
                    thread-local append performance
           Product: D
           Version: future
          Platform: x86
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: druntime
        AssignedTo: sean at invisibleduck.org
        ReportedBy: schveiguy at yahoo.com


--- Comment #0 from Steven Schveighoffer <schveiguy at yahoo.com> 2009-12-21 12:10:42 PST ---
Created an attachment (id=528)
Patch to prevent array stomping and increase append performance

The attached patch fixes 2 problems:

1. Array stomping.  A slice of an array can stomp on another array if the slice
starts at the beginning of the other array.  This patch prevents such problems
by storing the "allocated length" or the length of valid data at the end of the
array.

2. Array append previously required acquiring the GC lock, even when the array
can be extended in-place.  The patch makes use of an 8-element MRU (most
recently used) cache in thread-local storage that allows the runtime to avoid
taking the global lock to look up an array's allocated length.  This allows one
to append to up to 8 arrays per thread without taking the global lock unless an
actual re-allocation is required.  Shared array appending still requires a
global lock for appending, and does not have a cache associated with it. 
However, shared appending is still safe as far as stomping goes.

Note that with this patch, the following trick *no longer works*:

int[] bigarray = new int[10000];
bigarray.length = 0;
foreach(i; 0..10000)
   bigarray ~= i;

Because truncating the array this way can cause stomping, the first append will
reallocate bigarray and you will lose the benefit of preallocating the original
array.

A (yet unwritten) library function is required to preallocate an array.

To apply the patch, download the 2.037 distribution (this code was only tested
against the distribution), and apply the patch from the src/druntime directory:

cd dmd2/src/druntime
patch -p0 < append.patch

then build and re-install druntime and phobos libraries.

The patch was tested on Linux dmd version 2.037.  An earlier version of the
patch which was mostly the same was tested on Windows dmd 2.036 and Mac OSX
10.6 dmd 2.037.  The difference between the earlier and this version of the
patch is the handling of appending dchar to char[] and wchar[].

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------