www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 3930] New: AAs horribly broken

reply d-bugmail puremagic.com writes:
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



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: -------
Mar 10 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3930


Steven Schveighoffer <schveiguy yahoo.com> changed:

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



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: -------
Mar 11 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3930


Steven Schveighoffer <schveiguy yahoo.com> changed:

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



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: -------
Mar 11 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3930


Steven Schveighoffer <schveiguy yahoo.com> changed:

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



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: -------
Mar 11 2010
prev sibling parent d-bugmail puremagic.com writes:
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



Fixed DMD2.042.

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