"Burton Radons" <loth@users.sourceforge.net> wrote in message news:3D6938BA.1070809@users.sourceforge.net...
> Pavel Minayev wrote:
> > On Sun, 25 Aug 2002 09:25:23 -0700 "Walter" <walter@digitalmars.com>
wrote:
> >>The problem is distinguishing a slice from the original allocation.
Having
> >>an extra bit I suspect will kill off any performance gains that you'd
get
> >>from resizing in place.
> > Why? It would be just a single bitwise AND to check the bit, and, if it
is a
> > slice, another one to
> > reset it. On the other hand, adding elements to end of list would be
_hundred_
> > times faster
> > on large lists.
> I've done this for my port.  Works nice.  Assignment, returning, and passing as an in argument also clear the bit, although that doesn't have to be done if the previous owner doesn't take advantage of it or is going out of scope.  The only costly operation is in finding out how much more space a list has in it, but this is nothing compared to doing allocation too much.

for (i = 0; i < a.length; i++)

becomes:

   for (i = 0; i < (a.length & 7FFFFFFF); i++)

which can have a significant speed penalty.

"Walter" <walter@digitalmars.com> wrote in message news:akdohj$2m1h$1@digitaldaemon.com...


> for (i = 0; i < a.length; i++)
>
> becomes:
>
>    for (i = 0; i < (a.length & 7FFFFFFF); i++)
>
> which can have a significant speed penalty.

   Of course, you can always make a case for this, even when bitmasking is
not necessary:

int n = a.length & 7FFFFFFF;
for (i = 0; i < n; i++)

   Although, I would expect any decent compiler (wink, wink) to do that
optimization for you. Ahem...

Salutaciones,
                       JCAB

On Mon, 26 Aug 2002 10:28:16 -0700 "Walter" <walter@digitalmars.com> wrote:

> for (i = 0; i < a.length; i++)
> 
> becomes:
> 
>    for (i = 0; i < (a.length & 7FFFFFFF); i++)
> 
> which can have a significant speed penalty.
> 

Store the flag in the capacity field, not in the length (capacity as in
std::vector).
It is only queried whenever new element is added.

>>    for (i = 0; i < (a.length & 7FFFFFFF); i++)
>>
>> which can have a significant speed penalty.
>
>   Of course, you can always make a case for this, even when bitmasking is
>not necessary:
>
>int n = a.length & 7FFFFFFF;
>for (i = 0; i < n; i++)
>
>   Although, I would expect any decent compiler (wink, wink) to do that
>optimization for you. Ahem...

Unfortunately, while this is valid in most cases, it is not always valid.  If something inside the 'for' loop resized 'a', the original loop would still be correct (at least in terms of not going outside the loop.  'i' would usually also have to be manipulated by whatever did the resizing to make the loop logically correct).  The optimized loop would not notice the change to length, and could cause a memory violation, corruption, or incomplete loop.  If it were a compiler optimization, presumably the compiler could note the array resizing inside the loop body and avoid the optimization.

Mac

"Juan Carlos Arevalo Baeza" <jcab@JCABs-Rumblings.com> wrote in message news:akds2h$2pvb$1@digitaldaemon.com...
> "Walter" <walter@digitalmars.com> wrote in message news:akdohj$2m1h$1@digitaldaemon.com...
> > for (i = 0; i < a.length; i++)
> > becomes:
> >    for (i = 0; i < (a.length & 7FFFFFFF); i++)
> > which can have a significant speed penalty.
>    Of course, you can always make a case for this, even when bitmasking is
> not necessary:
>
> int n = a.length & 7FFFFFFF;
> for (i = 0; i < n; i++)
>
>    Although, I would expect any decent compiler (wink, wink) to do that
> optimization for you. Ahem...

It's not so easy, because the compiler has to prove that a.length doesn't change inside the loop.

"Pavel Minayev" <evilone@omen.ru> wrote in message news:CFN374949765569907@news.digitalmars.com...
> On Mon, 26 Aug 2002 10:28:16 -0700 "Walter" <walter@digitalmars.com>
wrote:
>
> > for (i = 0; i < a.length; i++)
> >
> > becomes:
> >
> >    for (i = 0; i < (a.length & 7FFFFFFF); i++)
> >
> > which can have a significant speed penalty.
> Store the flag in the capacity field, not in the length (capacity as in
> std::vector).
> It is only queried whenever new element is added.

That makes a dynamic array a 3 word quantity instead of a 2 word one. There's a significant penalty for that.

On Mon, 26 Aug 2002 17:46:32 -0700 "Walter" <walter@digitalmars.com> wrote:

> That makes a dynamic array a 3 word quantity instead of a 2 word one. There's a significant penalty for that.

Just how many dynamic arrays you have in your program? std::vector also uses
3 words, by the way, but I haven't heard anyone complaining yet. I don't
remember
exactly, but Delphi dynamic strings might also use 3 words.

On other hand, current implementation of dynamic arrays makes them simply
useless
(at least for me). When you have an "append to end" ~= operator, but advised
against
using it because it is extremely slow, it is awful. What you propose is doing
memory
management manually, preallocating chunks of memory and filling them - back to
REDIM days? What's the point of D dynamic arrays then?

One of the nice features of D is that it claims to cover large area of STL
functionality,
but with simpler approach. std::vector is probably the most basic container
type,
yet there's nothing in D so far that can be really used instead of it...

"Pavel Minayev" <evilone@omen.ru> wrote in message news:CFN374955394183796@news.digitalmars.com...
> On Mon, 26 Aug 2002 17:46:32 -0700 "Walter" <walter@digitalmars.com>
wrote:
> > That makes a dynamic array a 3 word quantity instead of a 2 word one. There's a significant penalty for that.
> Just how many dynamic arrays you have in your program?

I use them all over the place <g>. As a technical aside, being two words means they can be implemented using register pairs, which should make them pretty efficient. Three words means they don't get enregistered.

> std::vector also uses
> 3 words, by the way, but I haven't heard anyone complaining yet. I don't
> remember
> exactly, but Delphi dynamic strings might also use 3 words.

I didn't know that.

> On other hand, current implementation of dynamic arrays makes them simply
> useless
> (at least for me). When you have an "append to end" ~= operator, but
advised
> against
> using it because it is extremely slow, it is awful. What you propose is
doing
> memory
> management manually, preallocating chunks of memory and filling them -
back to
> REDIM days? What's the point of D dynamic arrays then?

The tradeoff is to get faster loops on arrays at the expense of slower
resizing. The only time the resize speed is really a problem are things
like:
    for (i = 0; i < 1000; i++)
        a ~= "hello";
and I suggest that such uses aren't that common.

> One of the nice features of D is that it claims to cover large area of STL
> functionality,
> but with simpler approach. std::vector is probably the most basic
container
> type,
> yet there's nothing in D so far that can be really used instead of it...

On Tue, 27 Aug 2002 10:36:10 -0700 "Walter" <walter@digitalmars.com> wrote:

> The tradeoff is to get faster loops on arrays at the expense of slower
> resizing. The only time the resize speed is really a problem are things
> like:
>     for (i = 0; i < 1000; i++)
>         a ~= "hello";
> and I suggest that such uses aren't that common.

You get something close to that in a parser. For a large program, with thousands
of identifiers (e.g. Win32 headers =)), dynamic arrays grow very large, and
every
new declared identifier requires reallocation... I noticed it when I ran my
PAS2D
converter. It is _very_ noticeable. The same will happen in a game if one
decides
to use a dynamic array to store game entities - due to constant creation of new
objects (projectiles, particles, blood etc). This also happens when somebody
reads a string character by character, which is quite a common operation.

In article <CFN374959716746759@news.digitalmars.com>, Pavel Minayev says...
>
>On Tue, 27 Aug 2002 10:36:10 -0700 "Walter" <walter@digitalmars.com> wrote:
>
>> The tradeoff is to get faster loops on arrays at the expense of slower
>> resizing. The only time the resize speed is really a problem are things
>> like:
>>     for (i = 0; i < 1000; i++)
>>         a ~= "hello";
>> and I suggest that such uses aren't that common.
>
>You get something close to that in a parser. For a large program, with thousands
>of identifiers (e.g. Win32 headers =)), dynamic arrays grow very large, and
>every
>new declared identifier requires reallocation... I noticed it when I ran my
>PAS2D
>converter. It is _very_ noticeable. The same will happen in a game if one
>decides
>to use a dynamic array to store game entities - due to constant creation of new
>objects (projectiles, particles, blood etc). This also happens when somebody
>reads a string character by character, which is quite a common operation.

Firstly, I suspect that Walter has a very good understanding of how parsers work...

Secondly, wouldn't an associative array be better for some of these applications?  Parsers, at least, need fast lookups, and depending on what you're doing in your game you may also need fast lookups (dunno -- not a great deal of real game programming experience yet -- all book learnin')  Associative arrays *do* automatically increase in size as necessary, although I do not know the exact details of the underlying extendible hash mechanism.  The rehash mechanism is also quite nice for optimizing lookups after loading in an associative array.

I would assume that associative arrays are also more efficient, at least in the space domain, for sparse array usages.

This is not meant as an argument against auto-resizing arrays.  I just wanted to mention that at least one form of auto-resizing array does appear to exist. Personally, I always use .reserve even on my STL vectors.  It doesn't bother me to determine my own growth rate mechanism.  But other people have different tastes...

Mac