May 21, 2005
> 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
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
> 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
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
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


1 2 3 4
Next ›   Last »