Thread overview
[Issue 3930] New: AAs horribly broken
Mar 11, 2010
David Simcha
Mar 27, 2010
Don
March 11, 2010
http://d.puremagic.com/issues/show_bug.cgi?id=3930

           Summary: AAs horribly broken
           Product: D
           Version: 2.041
          Platform: Other
        OS/Version: Windows
            Status: NEW
          Severity: regression
          Priority: P1
         Component: druntime
        AssignedTo: sean@invisibleduck.org
        ReportedBy: dsimcha@yahoo.com


--- Comment #0 from David Simcha <dsimcha@yahoo.com> 2010-03-10 20:17:54 PST ---
The following code tests the builtin associative array by comparing its behavior to the behavior of an AA implemented via linear search.  It works on 2.040 but produces an access violation on 2.041.

import std.stdio, std.random;

// Quick, dirty and inefficient AA using linear search, useful for testing.
struct LinearAA(K, V) {
    K[] keys;
    V[] values;

    V opIndex(K key) {
        foreach(i, k; keys) {
            if(k == key) {
                return values[i];
            }
        }

        assert(0, "Key not present.");
    }

    V opIndexAssign(V val, K key) {
        foreach(i, k; keys) {
            if(k == key) {
                return values[i] = val;
            }
        }

        keys ~= key;
        values ~= val;
        return val;
    }

    V* opIn_r(K key) {
        foreach(i, k; keys) {
            if(key == k) {
                return values.ptr + i;
            }
        }

        return null;
    }

    void remove(K key) {
        size_t i = 0;
        for(; i < keys.length; i++) {
            if(keys[i] == key) {
                break;
            }
        }

        assert(i < keys.length);

        for(; i < keys.length - 1; i++) {
            keys[i] = keys[i + 1];
            values[i] = values[i + 1];
        }

        keys = keys[0..$ - 1];
        values = values[0..$ - 1];
    }

    uint length() {
        return values.length;
    }
}

void main() {
    foreach(iter; 0..10) {  // Bug only happens after a few iterations.
        writeln(iter);
        uint[uint] builtin;
        LinearAA!(uint, uint) linAA;
        uint[] nums = new uint[100_000];
        foreach(ref num; nums) {
            num = uniform(0U, uint.max);
        }

        foreach(i; 0..10_000) {
            auto index = uniform(0, nums.length);
            if(index in builtin) {
                assert(index in linAA);
                assert(builtin[index] == nums[index]);
                assert(linAA[index] == nums[index]);
                builtin.remove(index);
                linAA.remove(index);
            } else {
                assert(!(index in linAA));
                builtin[index] = nums[index];
                linAA[index] = nums[index];
            }
        }

        assert(builtin.length == linAA.length);
        foreach(k, v; builtin) {
            assert(k in linAA);
            assert(*(k in builtin) == *(k in linAA));
            assert(linAA[k] == v);
        }
    }
}

This is probably related to Bug 3929.  Since the current builtin AA implementation uses free() quite liberally as a practical necessity due to false pointer issues, we see some very subtle, hard to reproduce bugs.  (The only way I can reproduce them is by monte carlo unittesting different AA implementations against each other like above.  Even then it depends somewhat sensitively on what code was executed previously, hence the multiple iterations.)  For me, this is a blocker for using this version of DMD, as the project I'm working on lately uses AAs very heavily.  I think this is severe enough to merit its own release.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
March 11, 2010
http://d.puremagic.com/issues/show_bug.cgi?id=3930


Steven Schveighoffer <schveiguy@yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |schveiguy@yahoo.com


--- Comment #1 from Steven Schveighoffer <schveiguy@yahoo.com> 2010-03-11 04:07:31 PST ---
I can only find two places that AA's use free, one when an element is removed via gc_free, and once to delete the hash array itself.  Commenting out both of those, I still get the segmentation fault.

I'm still not convinced that the stomping fixes I put in are not to blame, I will try commenting those out.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
March 11, 2010
http://d.puremagic.com/issues/show_bug.cgi?id=3930


Steven Schveighoffer <schveiguy@yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bugzilla@digitalmars.com


--- Comment #2 from Steven Schveighoffer <schveiguy@yahoo.com> 2010-03-11 05:10:16 PST ---
I found the problem.  It has nothing to do with the cache, but it has to do with a bug with how I store the length in the block.

Because I must store the length of a block that is page size or greater at the front of the block (smaller blocks I store the length at the end), the start of an array is offset by 2*size_t.sizeof bytes.

The problem comes when initializing a newly allocated array.  I forgot to add the offset for larger arrays when calling memset, so the last 2*size_t.sizeof bytes are not initialized.  In addition, if you allocated a large array of structs which had a non-uniform initializer, they could all be skewed!

I think this fix is worth a new release of dmd.  I checked in the changes, but druntime doesn't build at the moment, I think someone is adding stack tracing. Try this patch on your local copy of druntime and see if it fixes the problem for you: http://www.dsource.org/projects/druntime/changeset/261/trunk?format=diff&new=261

cc'ing walter to notify him.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
March 11, 2010
http://d.puremagic.com/issues/show_bug.cgi?id=3930


Steven Schveighoffer <schveiguy@yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |r.sagitario@gmx.de


--- Comment #3 from Steven Schveighoffer <schveiguy@yahoo.com> 2010-03-11 05:44:03 PST ---
*** Issue 3898 has been marked as a duplicate of this issue. ***

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
March 27, 2010
http://d.puremagic.com/issues/show_bug.cgi?id=3930


Don <clugdbug@yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |clugdbug@yahoo.com.au
         Resolution|                            |FIXED


--- Comment #4 from Don <clugdbug@yahoo.com.au> 2010-03-27 07:50:20 PDT ---
Fixed DMD2.042.

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