bearophile:
> (Your code doesn't work (on D1) if T is a static array,

Sorry, ignore what I have written, I'm a little nervous...

Bye,
bearophile

bearophile wrote:
> bearophile:
>> (Your code doesn't work (on D1) if T is a static array,
> 
> Sorry, ignore what I have written, I'm a little nervous...

I think I've unnecessarily overstated my case, which has put both of us in defensive.

You are very right that tests on D1 and D2 are not comparable. And Walter has at one point made crucial changes in the allocator at my behest. Specifically, he introduced in-place growth whenever possible and added the expand() primitive to the gc. These are present in D2 but I don't know whether and when he has regressed those to D1. (And btw why wouldn't you try it :o).)


Andrei

Andrei Alexandrescu wrote:
> 
> I gave it some more thought and I have a theory for the root of the issue. My implementation assumes there's exponential (multiplicative) increase of capacity in the built-in ~=. I hope Walter wouldn't do anything else. If there are differences in growth strategies between D1 and D2, that could explain the difference between bearophile's benchmarks and mine.

Arrays larger than 4k grow logarithmically, smaller than 4k they grow exponentially.  This is certainly true of D1 and Tango, and I'd assume D2 is no different.


Sean

Andrei Alexandrescu wrote:
> bearophile wrote:
>> bearophile:
>>> (Your code doesn't work (on D1) if T is a static array,
>>
>> Sorry, ignore what I have written, I'm a little nervous...
> 
> I think I've unnecessarily overstated my case, which has put both of us in defensive.
> 
> You are very right that tests on D1 and D2 are not comparable. And Walter has at one point made crucial changes in the allocator at my behest. Specifically, he introduced in-place growth whenever possible and added the expand() primitive to the gc. These are present in D2 but I don't know whether and when he has regressed those to D1. (And btw why wouldn't you try it :o).)

For the record, in-place growth has been in D1 for as long as it's been in D2.


Sean

Sean Kelly wrote:
> Andrei Alexandrescu wrote:
>>
>> I gave it some more thought and I have a theory for the root of the issue. My implementation assumes there's exponential (multiplicative) increase of capacity in the built-in ~=. I hope Walter wouldn't do anything else. If there are differences in growth strategies between D1 and D2, that could explain the difference between bearophile's benchmarks and mine.
> 
> Arrays larger than 4k grow logarithmically, smaller than 4k they grow exponentially.  This is certainly true of D1 and Tango, and I'd assume D2 is no different.

Yes, but with in-place expansion, effective growth stays exponential even beyond 4k. So I'm not that worried that it could become quadratic, unless there are some really wicked workloads.

I modified my putNext to print what's happening:

    void putNext(T item)
    {
        if (_end < _eos)
        {
            // Should do in-place construction here
            *_end++ = item;
        }
        else
        {
            // Time to reallocate, do it and cache capacity
            auto tmp = _begin[0 .. _end - _begin];
            tmp ~= item;
            if (_begin != tmp.ptr)
            {
                _begin = tmp.ptr;
                _end = _begin + tmp.length;
                writeln(_end - _begin);
            }
            else
            {
                ++_end;
            }
            _eos = _begin + .capacity(_begin) / T.sizeof;
        }
    }

Notice the writeln. On my system the console reads:

benchmark 10, N=75000000:
1
5
9
17
33
65
129
257
513
253953
1155073
4743169
18505729
68861953

That's exponential alright. On the other hand, if you move the writeln after the if, indeed:

1
5
9
17
33
65
129
257
513
1025
2049
3073
4097
5121
6145
7169
8193
9217
10241
11265
12289

But it's the former column that matters, because moving chinks is where real work is being done. In-place block expansion should take constant time.

With this behavior in place, my code amortizes calls to capacity() by a factor of 1024, and keeps amortized append complexity constant.


Andrei

== Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
> Benji Smith wrote:
> > bearophile wrote:
> >> 5) The source code of the current algorithm module of D2 is already very complex to follow, it smells of over-generalization here and there. Sometimes it's better to reduce the generality of things, even if that reduces their power a little, to reduce complexity, etc. Tango code too isn't perfect, but it often looks more human. While you have created the algorithm module I too have created something similar, but based on different grounds.
> >
> > Along these same lines, while D is still young, the documentation is often thin, and code examples are scarce.
> >
> > I've been doing a lot of programming lately with Tango, and despite the growing documentation, I've had to refer directly to the Tango source code on more occasions than I can count. Luckily, the Tango sources are well-written and pretty easy to read and understand, and I've had very few problems figuring out how to use the library.
> >
> > I hope the range implementation makes readability a high priority.
> Speaking of examples and readability, and to tie this with the
> discussion on array reallocation, I was curious on an array appender
> built on the output range interface. I've seen a quite complicated array
> builder in digitalmars.d. I wanted a simpler appender that should not do
> worse than the built-in ~= and that works with algorithm2 whenever data
> is written out.
> It turned out quite simple and it improved performance of a large-scale
> data preprocessing task of mine (which involved reading and parsing
> about 1M lines of integers) by 15%. I'd be curious how it fares with
> other tests that you guys may have.
> The idea is very simple: just use D's native append operation, but cache
> the capacity to avoid too many lookups (I understand that that's the
> bottleneck).
> I paste the code below, I'd be indebted if you guys grabbed it and
> tested it.
> Andrei
> struct ArrayAppender(T)
> {
>      private T* _buffer;
>      private size_t _length;
>      private size_t _capacity;
>      this(T[] array)
>      {
>          _buffer = array.ptr;
>          _length = array.length;
>          if (_buffer) _capacity = .capacity(array.ptr) / T.sizeof;
>      }
>      size_t capacity() const { return _capacity; }
>      void putNext(T item)
>      {
>          invariant desiredLength = _length + 1;
>          if (desiredLength <= _capacity)
>          {
>              // Should do in-place construction here
>              _buffer[_length] = item;
>          }
>          else
>          {
>              // Time to reallocate, do it and cache capacity
>              auto tmp = _buffer[0 .. _length];
>              tmp ~= item;
>              _buffer = tmp.ptr;
>              _capacity = .capacity(_buffer) / T.sizeof;
>          }
>          _length = desiredLength;
>      }
>      T[] release()
>      {
>          // Shrink-to-fit
>          auto result = cast(T[]) realloc(_buffer, _length * T.sizeof);
>          // Relinquish state
>          _buffer = null;
>          _length = _capacity = 0;
>          return result;
>      }
> }
> unittest
> {
>      auto app = arrayAppender(new char[0]);
>      string b = "abcdefg";
>      foreach (char c; b) app.putNext(c);
>      assert(app.release == "abcdefg");
> }

One definite problem that I've just realized is that there's no putNext(T[]). What if you need to append another array to your ArrayAppender, not just a single element?

dsimcha:
> One definite problem that I've just realized is that there's no putNext(T[]). What if you need to append another array to your ArrayAppender, not just a single element?

Just add a simple method overload for that purpose, it's easy enough to do. (the ArrayBuilder of my dlibs has this already, of course).

Bye,
bearophile

dsimcha Wrote:

> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article

> > The idea is very simple: just use D's native append operation, but cache
> > the capacity to avoid too many lookups (I understand that that's the
> > bottleneck).
> > I paste the code below, I'd be indebted if you guys grabbed it and
> > tested it.
> > Andrei
> > struct ArrayAppender(T)
> > {
> >      size_t capacity() const { return _capacity; }
> >      void putNext(T item)

I have thoughts:

1) There should probably be a length/size call
2) How about add() or append() for a shorter name
3) What about using ~=?  Maybe this is too short...

Jerry

dsimcha wrote:
> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
[snip]
> One definite problem that I've just realized is that there's no putNext(T[]).
> What if you need to append another array to your ArrayAppender, not just a single
> element?

My current codebase has that. It's about time I commit.

Andrei

jq wrote:
> dsimcha Wrote:
> 
>> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
> 
>>> The idea is very simple: just use D's native append operation, but cache
>>> the capacity to avoid too many lookups (I understand that that's the
>>> bottleneck).
>>> I paste the code below, I'd be indebted if you guys grabbed it and
>>> tested it.
>>> Andrei
>>> struct ArrayAppender(T)
>>> {
>>>      size_t capacity() const { return _capacity; }
>>>      void putNext(T item)
> 
> I have thoughts:
> 
> 1) There should probably be a length/size call
> 2) How about add() or append() for a shorter name
> 3) What about using ~=?  Maybe this is too short...

Length sounds good. The other two I'm more hesitant about because ArrayAppender supports the interface of an output range. The output range only allows putting one element and making a step simultaneously, hence putNext. The ~= is also a bit of an unfortunate choice because it's odd to define a type with ~= but no meaningful/desirable binary ~.

Andrei