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

> > > 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.

   You can always store the size _and_ capacity as part of the allocated
block of memory. It would mean an extra level of indirection for some
operations, but the dynamic array would occupy one register, instead of two.

   It's somewhat of a tradeoff, but it sounds reasonable to me: extra
indirection (optimizable in many cases), smaller register footprint and
better reallocation in the worst case.

Salutaciones,
                       JCAB

The trick to game programming memory allocation is to allocate all objects from fixed pools.  You can even do that in Java.  Too bad you can't disable the GC completely.

Sean

"Pavel Minayev" <evilone@omen.ru> wrote in message news:CFN374959716746759@news.digitalmars.com...
> 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.

One advantage of the gc being a mark & sweep rather than a refcounter is that, once you call gc.disable(), it is altogether disabled (other than the memory footprint for the gc code).

Am I wrong here?

"Pavel Minayev" <evilone@omen.ru> wrote in message news:CFN374959716746759@news.digitalmars.com...
> 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.

I'm not sure what your program is doing, but if it is a symbol table, using an associative array will get you much faster results.

> 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.

What I do for those cases is read the entire file into one array, and then map slices onto it. The wc is an example of that (also of the associative array).

"Russell Lewis" <spamhole-2001-07-16@deming-os.org> wrote in message news:3D6CDE4E.2030704@deming-os.org...
> One advantage of the gc being a mark & sweep rather than a refcounter is
> that, once you call gc.disable(), it is altogether disabled (other than
> the memory footprint for the gc code).
>
> Am I wrong here?

Nope. You're right. There are a lot of methods of eliminating the gc pause.

"Juan Carlos Arevalo Baeza" <jcab@JCABs-Rumblings.com> wrote in message news:akgq9d$8c8$1@digitaldaemon.com...
> "Walter" <walter@digitalmars.com> wrote in message news:akgeie$2qh4$1@digitaldaemon.com...
> > > > 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.
>    You can always store the size _and_ capacity as part of the allocated
> block of memory. It would mean an extra level of indirection for some
> operations, but the dynamic array would occupy one register, instead of
two.
>    It's somewhat of a tradeoff, but it sounds reasonable to me: extra
> indirection (optimizable in many cases), smaller register footprint and
> better reallocation in the worst case.

That would require a memory allocation (for the 3 word quantity) for every dynamic array. I suspect it would be a big hit on performance.

"Walter" <walter@digitalmars.com> wrote in news:aklmo8$pm3$1@digitaldaemon.com:

> That would require a memory allocation (for the 3 word quantity) for every dynamic array. I suspect it would be a big hit on performance.

Don't suspect. Just try it. A simple D program, written both
using current implementation of dynamic arrays, and then
another that emulates the proposal.

"Walter" <walter@digitalmars.com> wrote in message news:aklmo8$pm3$1@digitaldaemon.com...

> >    You can always store the size _and_ capacity as part of the allocated
> > block of memory. It would mean an extra level of indirection for some
> > operations, but the dynamic array would occupy one register, instead of
> two.
> >    It's somewhat of a tradeoff, but it sounds reasonable to me: extra
> > indirection (optimizable in many cases), smaller register footprint and
> > better reallocation in the worst case.
>
> That would require a memory allocation (for the 3 word quantity) for every dynamic array. I suspect it would be a big hit on performance.

   No. Just allocate it together (in the same block of memory as) the array
elements themselves. No performance hit besides the extra indirection and
any calculations neccessary to preserve alignment.

   It's a pretty common thing to do. All implementations of std::string that
I know (except one - flex_string by Alexandrescu, which allocates it
separately) of use this to store the string's reference counter, for
example.

   So, for example, an array of 64-bit doubles, if it allocates storage for
4 elements, it allocates 4*8 (elements) + 4 (size) + 4 (capacity) = 40
bytes. Simple and easy.

Salutaciones,
                       JCAB

"Juan Carlos Arevalo Baeza" <jcab@JCABs-Rumblings.com> wrote in message news:akm8rv$1e9n$1@digitaldaemon.com...
> "Walter" <walter@digitalmars.com> wrote in message news:aklmo8$pm3$1@digitaldaemon.com...
>
> > >    You can always store the size _and_ capacity as part of the
allocated
> > > block of memory. It would mean an extra level of indirection for some operations, but the dynamic array would occupy one register, instead
of
> > two.
> > >    It's somewhat of a tradeoff, but it sounds reasonable to me: extra
> > > indirection (optimizable in many cases), smaller register footprint
and
> > > better reallocation in the worst case.
> >
> > That would require a memory allocation (for the 3 word quantity) for
every
> > dynamic array. I suspect it would be a big hit on performance.
>
>    No. Just allocate it together (in the same block of memory as) the
array
> elements themselves. No performance hit besides the extra indirection and any calculations neccessary to preserve alignment.
>
>    It's a pretty common thing to do. All implementations of std::string
that
> I know (except one - flex_string by Alexandrescu, which allocates it separately) of use this to store the string's reference counter, for example.
>
>    So, for example, an array of 64-bit doubles, if it allocates storage
for
> 4 elements, it allocates 4*8 (elements) + 4 (size) + 4 (capacity) = 40
> bytes. Simple and easy.

Allocating it together means that slices (as currently done) cannot work. A slice would require copying the array contents.

A slice is just a pointer and size register pair, right?  So just mention in the spec that if you resize a dynamic array, all slices of it become invalid.

Or maybe resizing a dynamic array that has had slices made of it, requires it to be copied (leaving the old array untouched, until GC reclaims it)

Sean

"Walter" <walter@digitalmars.com> wrote in message news:akmeg2$1k62$1@digitaldaemon.com...
> Allocating it together means that slices (as currently done) cannot work.
A
> slice would require copying the array contents.