View mode: basic / threaded / horizontal-split · Log in · Help
May 21, 2005
Re: a GC question
> The idea was to support the idea of 'reserving' a length for an array by
> setting the .length property to the reserved size, then setting .length to
> 0. This means that while filling the array, reallocation wouldn't be
> happening and it'd be more efficient.

I should add that reserving using this technique is very inefficient (as 
I've posted about long ago) because of the 0 checks in setlength. More 
precisely, suppose foo.length is 0 and we want to reserve some space for it. 
Trace the memory allocations:
 foo.length = 100; // allocates and sets the ptr and length
 foo.length = 0; // nulls the ptr and sets length to 0
 // let's try again...
 foo = new Foo[100];
 foo = foo[0 .. 0]; // now ptr is set and length is 0
 foo.length = 1; // throws away old ptr and allocates a new length 1 array

So basically reserving length using 0 does not work. You lose the ptr when 
you resize from 0 and you lose the ptr when you resize to 0. That's why I 
always resize to/from 1 - it keeps the ptr. It makes the code uglier. I 
wouldn't mind resizing to/from 0 preserving the ptr, though.
May 23, 2005
Re: a GC question
Hi.

> The idea was to support the idea of 'reserving' a length for an array by
> setting the .length property to the reserved size, then setting .length to
> 0. This means that while filling the array, reallocation wouldn't be
> happening and it'd be more efficient.

That really shouldn't be supported, since it depends heavily on the current 
implementation of the araray.  For all you know (I mean, not _you_, since 
you wrote it :-S), setting length to zero will immediately free the memory. 
To reserve memory before filling an array, you simply keep track of a 
seperate 'count', resizing if it tends to get higher than array.length. And 
if this is too much work, use a container class for god's sake.

Walter, I really love the way D is progressing. But I'm so scared that some 
strange things are left in the language, just because people have grown used 
to them, as they tend to do, with ALL side effects in a language. This 
'length =0' is just one example. My fear also applies to casting arrays to 
pointer implicitely, and printf("%.*s",x), etc.. I really should write them 
down.

It's just bad practice to let "length = 0" mean anything else than it says: 
empty array. Of course, it's just an optimization. Any implementation that 
immediately frees the array will reallocate it again when being filled, so 
it will always work.

What about adding a 'member' function to arrays to allocate new memory. This 
member function would also not call any constructors, since it's just 
allocating memory, leaving the length 0. The current 'approach' of a = new 
someclass[x]; a.length=0; calls the constructors for all x elements, when 
these (probably) get overwritten later on. Wasting cycles.

L.
May 23, 2005
Re: a GC question
> What i wanted to say is that i think it is better to have a robust, but
> slightly slower GC, than a very complex GC that spoils all optimization 
> efforts.

With this, I can only agree.

L.
May 23, 2005
Re: a GC question
On Mon, 23 May 2005 11:14:08 +0300, Lionello Lunesu  
<lio@lunesu.removethis.com> wrote:
>> The idea was to support the idea of 'reserving' a length for an array by
>> setting the .length property to the reserved size, then setting .length  
>> to
>> 0. This means that while filling the array, reallocation wouldn't be
>> happening and it'd be more efficient.
>
> That really shouldn't be supported, since it depends heavily on the  
> current
> implementation of the araray.  For all you know (I mean, not _you_, since
> you wrote it :-S), setting length to zero will immediately free the  
> memory.
> To reserve memory before filling an array, you simply keep track of a
> seperate 'count', resizing if it tends to get higher than array.length.  
> And
> if this is too much work, use a container class for god's sake.
>
> Walter, I really love the way D is progressing. But I'm so scared that  
> some
> strange things are left in the language, just because people have grown  
> used
> to them, as they tend to do, with ALL side effects in a language. This
> 'length =0' is just one example. My fear also applies to casting arrays  
> to
> pointer implicitely, and printf("%.*s",x), etc.. I really should write  
> them
> down.
>
> It's just bad practice to let "length = 0" mean anything else than it  
> says:
> empty array. Of course, it's just an optimization. Any implementation  
> that
> immediately frees the array will reallocate it again when being filled,  
> so
> it will always work.
>
> What about adding a 'member' function to arrays to allocate new memory.  
> This
> member function would also not call any constructors, since it's just
> allocating memory, leaving the length 0. The current 'approach' of a =  
> new
> someclass[x]; a.length=0; calls the constructors for all x elements, when
> these (probably) get overwritten later on. Wasting cycles.

Like 'reserve' proposed several times over the last year or two...
  a.reserve(50);

Regan
May 25, 2005
Re: a GC question
In article <op.sq3exlzr6yjbe6@sandmann.maerchenwald.net>, Uwe Salomon says...
>
>> Each node in the binary tree contains a random integer that corresponds
>> (roughly) to the "skip list node level".
>
>Hmm, i read something similar back then, about randomized binary trees...  
>But that is some other issue, i think. Your approach reads interesting.  
>Does it only save some space, or does it also speed the map up?
>
>Ciao
>uwe

I would say it has the following advantages:

1. Easier memory management than a skip list, nodes are the same size.

2. I don't know if its faster than a skip list, but I'm fairly sure its
faster than a balanced tree.  You don't need to check for balance, and you
don't need to balance the tree explicitely.

3. There is no worst-case input sequence.  Most balanced trees do poorly with
sequential input for example.

Other notes:

Disadvantages:

1. Computing and storing the random number.  Should be very fast, but not
instant of course.  This is probably an overhead relative to a perfect skip
list, but almost all balanced binaries trees need a little overhead.

2. No guarantee of balance -- random is random.

3. Less common and less studied.  I have a partial implementation of it
somewhere.  I described it in more detail in other locations, which I could also
track down.

Other Notes:

It should have properties that are very similar to the skip list -- after all,
it is supposed to have the same "decision tree" that a skip list has, and the
design of the balancing technique is based on the corresponding skip list.

Compared to a red-black tree (for example), it trades some determinism for speed
and other properties.

A normal non-balanced binary tree has GC-friendly properties.  If you have two
pointers to one such binary tree and you add X nodes to each of them, the number
of nodes that need to be rebuilt is approximately ln2(N) * X, where N is the
size of the tree and X is the number of elements added.

This is true because an ordinary binary tree adds elements in the downward
direction, never "pivoting" parts of the tree.  Each node is immutable.  Now, in
C++, trees are not handled this way, but in LISP they normally are (AFAIK),
because GC is available.

The randomized balancing preserves this property -- it adds about ln2(N) nodes
and always builds nodes in the downward direction.  A C++ implementation would
not be concerned with this property because sharing is not std. operating
procedure, but in GC languages this can be a really useful thing.  For example,
a text editor can get the "undo" feature very cheaply using an adaptation of
this binary tree sharing.

In practical terms, if you have 1000000 elements in a shared tree, and add 3
elements, you end up generating and GC-ing 60 elements, but the old million are
still shared and only the modified tree has the new items.

I'm not sure if this practice is still in vogue, or if not, if that is just
because GC has been less mainstream for a few decades.

Kevin
Next ›   Last »
1 2 3 4
Top | Discussion index | About this forum | D home