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


Steven Schveighoffer <schveiguy@yahoo.com> changed:

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


--- Comment #10 from Steven Schveighoffer <schveiguy@yahoo.com> 2010-08-26 04:56:47 PDT ---
I checked in hopefully a fix for this.

changeset http://www.dsource.org/projects/phobos/changeset/1929

Note, I changed the interface of Appender slightly to be safer.  Instead of taking an array reference pointer, it takes an array.  This means your original array passed in will *not* be appended to.  To get the resulting data after appending, use the data method.

I didn't find any cases in Phobos that were adversely affected by this change (but I did have to change a few modules that used appender in unit tests).

I tested the new version against the original code in this bug, and Don's code in comment 8, both no longer exhibit errors.

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

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



--- Comment #11 from nfxjfg@gmail.com 2010-08-26 05:20:08 PDT ---
This is still full of dirty runtime calls and attempts to emulate half of lifetime.d (though the worst part is commented).

Why doesn't it simply use the D standard way to re-allocate an array, and then use array.capacity to see how much can be safely appended?

Something along the lines of:

private struct Data {
   T[] arr;
   size_t user_length;
}

Data _data;

void put(T item) {
   if (_data.user_length == arr.length) {
      size_t newcapacity = something larger than user_length;
      reallocate(newcapacity);
   }
   _data.arr[_data.user_length++] = item;
}

void reallocate(size_t newcapacity) {
   _data.arr.length = newcapacity;
   //include the data "overallocated" by the runtime into the array
   size_t realcap = _data.arr.capacity;
   _data.arr.length = realcap;
}

T[] data() {
   T[] arr = _data.arr[0.._data.user_length];
   _data = _data.init;
   assumeSafeAppend(arr);
   return arr;
}

Or did I overlook something.

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

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



--- Comment #12 from Steven Schveighoffer <schveiguy@yahoo.com> 2010-08-26 05:51:15 PDT ---
(In reply to comment #11)
> This is still full of dirty runtime calls and attempts to emulate half of lifetime.d (though the worst part is commented).

Why are runtime calls dirty?  I don't use any undocumented runtime functions...

It doesn't emulate lifetime, except for the newCapacity function (which arguably could be a call into the runtime, but it's a simple enough function, and doesn't really have to be consistent with the runtime), and the use of GC.extend.  I'm notably not trying to store the length inside the memory block.

> Why doesn't it simply use the D standard way to re-allocate an array, and then use array.capacity to see how much can be safely appended?

Because the call to the runtime cannot be inlined, and is much slower than simply dereferencing a pointer.  Appender is supposed to be as fast as possible at appending.

If you want to use built-in appending, just use it.  Appender is for getting the highest possible performance out of an array.

> 
> Something along the lines of:
> 
> private struct Data {
>    T[] arr;
>    size_t user_length;
> }
> 
> Data _data;
> 
> void put(T item) {
>    if (_data.user_length == arr.length) {
>       size_t newcapacity = something larger than user_length;
>       reallocate(newcapacity);
>    }
>    _data.arr[_data.user_length++] = item;
> }
> 
> void reallocate(size_t newcapacity) {
>    _data.arr.length = newcapacity;
>    //include the data "overallocated" by the runtime into the array
>    size_t realcap = _data.arr.capacity;
>    _data.arr.length = realcap;
> }
> 
> T[] data() {
>    T[] arr = _data.arr[0.._data.user_length];
>    _data = _data.init;
>    assumeSafeAppend(arr);
>    return arr;
> }
> 
> Or did I overlook something.

This is a different way of doing it, though I'd probably replace reallocate with a standard ~=.  I think your way would work fine.

I agree your way seems more congruent with the runtime.  I wonder if there are any advantages to doing it that way?  I think the Appender I committed is going to be slightly faster in the long run, because it avoids using runtime appending at all.  However, it has some limitations in that it cannot use the rest of a passed in memory block (i.e. the space beyond the initial array). But your code gave me an idea of how to achieve that.  I think this should work:

this(T[] arr)
{
   _data = new Data;
   _data.arr = arr;
   auto cap = arr.capacity;
   if(cap > origlen)
      arr.length = cap; // use up the rest of the block
   _data.capacity = arr.length;
}

I'll add this change too.

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

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



--- Comment #13 from nfxjfg@gmail.com 2010-08-26 06:20:17 PDT ---
(In reply to comment #12)
> Why are runtime calls dirty?  I don't use any undocumented runtime functions...

Because they do more work than necessary and rely on more implementation details than necessary. Also, more bugs (oh hey look, we're posting in a bug report). I'm most worried about the assumptions of the array memory layout.

> Because the call to the runtime cannot be inlined, and is much slower than simply dereferencing a pointer.  Appender is supposed to be as fast as possible at appending.

My code only calls runtime functions when the capacity is exhausted. As long as there's enough capacity, not a single runtime function is called on appending. It's really similar to all the code that has been in Appender before, except less dirty.

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

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



--- Comment #14 from Steven Schveighoffer <schveiguy@yahoo.com> 2010-08-26 06:30:03 PDT ---
(In reply to comment #13)
> (In reply to comment #12)
> > Why are runtime calls dirty?  I don't use any undocumented runtime functions...
> 
> Because they do more work than necessary and rely on more implementation details than necessary. Also, more bugs (oh hey look, we're posting in a bug report). I'm most worried about the assumptions of the array memory layout.

I'm not assuming anything about the memory layout.  GC.qalloc gives me a block of data, and I'm using the data.  Its interface is well defined without any hidden assumptions.

Besides, you are calling the same runtime functions, just using a different interface.  I don't see how one is more "dirty" than the other, we are both using well-documented runtime functions.

> 
> > Because the call to the runtime cannot be inlined, and is much slower than simply dereferencing a pointer.  Appender is supposed to be as fast as possible at appending.
> 
> My code only calls runtime functions when the capacity is exhausted. As long as there's enough capacity, not a single runtime function is called on appending. It's really similar to all the code that has been in Appender before, except less dirty.

Your code calls the lifetime runtime functions, which call the GC runtime functions.  My code just calls the GC functions, skipping the lifetime functions.  Like your code, mine only calls runtime functions on exhaustion.

BTW, the statement I was responding to asked why you can't just use runtime functions to determine capacity, I interpreted that as you wishing to use the runtime management of array memory for every append.  I hadn't read your code yet.

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

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



--- Comment #15 from nfxjfg@gmail.com 2010-08-26 10:12:08 PDT ---
(In reply to comment #14)
> I'm not assuming anything about the memory layout.  GC.qalloc gives me a block of data, and I'm using the data.  Its interface is well defined without any hidden assumptions.

That mess is mostly gone, but there's still that commented stuff. Will it be readded later?

> Besides, you are calling the same runtime functions, just using a different interface.  I don't see how one is more "dirty" than the other, we are both using well-documented runtime functions.

It doesn't zero the additional memory returned by GC.extend().
If precise GC is introduced, that won't be handled correctly either.

> Your code calls the lifetime runtime functions, which call the GC runtime functions.  My code just calls the GC functions, skipping the lifetime functions.  Like your code, mine only calls runtime functions on exhaustion.

The only real overhead is due to array initialization.
If that is really so important, the runtime should provide a clean interface to
allocate arrays uninitialized (or zeroed if not NO_SCAN). Basically a
_d_arraysetlengthT without the initialization code. That would be useful for
other code too; most time you create an array, you overwrite all its contents
anyway.

Keep in mind that optimizing the runtime code might be more worthwhile than optimizing Appender.

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

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


David Simcha <dsimcha@yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED


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