View mode: basic / threaded / horizontal-split · Log in · Help
May 20, 2005
Re: a GC question
> I suggest for a fix that your code not preallocate arrays; it's redundant
> with what the runtime is already doing.

Is that for Linux, too? Because my code is much faster in doing that...  
ok, perhaps he's just much more aggressive.

Ciao
uwe
May 20, 2005
Re: a GC question
In article <op.sq2quseu6yjbe6@sandmann.maerchenwald.net>, Uwe Salomon says...
>
>> eek. I know that's a common C trick to extend an array at the end of a
>> struct but does D recommend that practice? I assume it could wreak havoc  
>> on
>> garbage collectors that are "type aware" since the pointers stored in the
>> extended section have unknown types to the GC. For example if the GC were
>> changed to allocate pointer-free data from a special non-scanned heap  
>> then
>> the new char[..] would allocate from that heap and they the cast(Node*)
>> would wind up meaning that pointers are stored hidden inside what the GC
>> thinks is a char[].
>
>What do you recommend, then? I thought D should be a programming language  
>that lets you access the lower levels if you need to. Now this is all not  
>true anymore, because we have a super-duper overclever garbage collector?  
>Perhaps the D garbage collector needs to be robust, and simply cannot be  
>too funky.
>
>I mean, what would the benefit of all that cleanness in the programs be?  
>Look at some code from an average open source programmer... your hairs  
>will stand on end. That is only logical, because high quality code needs a  
>lot of time. You won't find a lot of programs where the programmers took  
>this time. So why optimize the GC to the bare bone, if its total execution  
>time is under 5% in the average program? It is much better to use some  
>advanced memory techniques (as outlined in the D docs somewhere) when it  
>really matters, i think.
>
>Ciao
>uwe

Maybe instead of /byte[n]/ or /char[n]/, use /(void*)[(n+3)/4]/.  This way the
GC will think of the data as pointers, but will know that it cannot safely
modify void* objects because the type info is unknown.

I would think a skip list could be implemented as a template taking the node
level as a parameter.


There is also a data structure that has the form of a binary tree, but works
just like a skip list; ie it makes the same decisions based on all the same
comparisons in the same order.

The key observation was that in any particular skip list, many of the pointers
are never really used.  For example, if a level 4 node is followed by a level 5
node, the pointers on the level 4 node are never followed.  If you can legally
move to the level 5 node, you would have done so when you were traversing at
level 5.  Once you descend to traversal at level 4, all higher level, subsequent
nodes, have been eliminated.

Thus, for any node X followed by a higher level node Y, X is essentially a leaf
of Y.  This is not exactly how it works.  Ultimately, every decision is a binary
decision, so you can build a binary tree that represents that decision space.
Each node in the binary tree contains a random integer that corresponds
(roughly) to the "skip list node level".

I worked out the details of how to do this once and wrote it up in C++, but I
discovered that someone else had already invented what appeared to be the same
data structure.  I can never find the link when I want it though... regardless,
I think my implementation was better than his -- his required node pivoting.

Kevin
May 20, 2005
Re: a GC question
> struct FullNode(int N)
> {
>    int key;
>    int data;
>    .FullNode!(1)* prev;
>    int n = N;
>    .FullNode!(1)*[N] next;
> }
> alias FullNode!(1) Node;
> int main() {
>     Node* newNode = new Node; // 1 item
>     writefln(newNode.n);
>     newNode.next[0] = cast(Node*)new FullNode!(4); // 4 items
>     writefln(newNode.next[0].n);
>     return 0;
> }
> But there are probably plenty of options available.

After some thinking i realized this with some extra overhead:

switch (level)
{
  case 1 : neu = cast(Node*) new NodeType!(Key, T, 1); break;
  case 2 : neu = cast(Node*) new NodeType!(Key, T, 2); break;
  case 3 : neu = cast(Node*) new NodeType!(Key, T, 3); break;
  case 4 : neu = cast(Node*) new NodeType!(Key, T, 4); break;
  case 5 : neu = cast(Node*) new NodeType!(Key, T, 5); break;
  // And so on till 11...
}

Not too beautiful, but no more obscure char[] allocation. Thanks a lot for  
your hints, this is really a lot cleaner (and the extra overhead for  
traversing the switch is low, especially because the later case statements  
are seldomly needed)!

Ciao
uwe
May 20, 2005
Re: a GC question
> 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
May 20, 2005
Re: a GC question
"Uwe Salomon" <post@uwesalomon.de> wrote in message
news:op.sq3c0da86yjbe6@sandmann.maerchenwald.net...
> > I suggest for a fix that your code not preallocate arrays; it's
redundant
> > with what the runtime is already doing.
>
> Is that for Linux, too? Because my code is much faster in doing that...
> ok, perhaps he's just much more aggressive.

The same code is used for both.
May 20, 2005
Re: a GC question
"Walter" <newshound@digitalmars.com> wrote in message 
news:d6lh2e$1keg$1@digitaldaemon.com...
>
> "Ben Hinkle" <ben.hinkle@gmail.com> wrote in message
> news:d6i1ps$1osr$1@digitaldaemon.com...
>> I was doing some experiments with comparing the MinTL container
> performance
>> against the STL performance and MinTL was getting stomped because of the
> GC.
>> It seemed to be allocating twice as much memory as the STL runs. The
>> allocations I was making was for arrays with lengths a power of two. I
>> looked at gc.d and noticed all the allocations were being made with +1
> added
>> to the lengths, which means my nice power of two was being incremented to
>> the next larger bucket and hence using twice the space of the C++ code.
> Can
>> we get rid of those +1? I recompiled phobos without the +1 and it all
> seemed
>> to work ok. I think it will be common to use power-of-two sizes for
> objects
>> assuming those will fit nicely together when in fact those fit the worst
>> together.
>
> The +1 was to support the following usage:
>
>    T[] foo;
>    T[] bar;
>    ...
>    foo = foo[length .. length];
>    ...
>    foo ~= bar;
>
> Without the +1, if length is a power of 2, and the power of 2 is the 
> bucket
> size, then foo[length..length] happens to cross the bucket boundary and
> point at the start of the *next* bucket. The array append code just sees
> that foo[] is pointing to the start of a bucket, and so happilly inserts 
> bar
> overwritting whatever was already using that bucket. This would cause
> erratic, random crashes.

I suggest foo ~= bar for arrays be roughly equivalent to
 size_t oldlen = foo.length;
 foo.length = foo.length + bar.length;
 foo[oldlen .. oldlen+bar.length] = bar[];
That way when foo.length is 0 a new pointer is allocated (as you probably 
already know _d_arraysetlength checks for 0 length). When foo.length is 
non-zero and the array can be resized in place then it behaves the same as 
what it does today. So basically to make the smallest change to gc.d I would 
change _d_arrayappend to check if length == 0 just like _d_arraysetlength 
and malloc a new block if that is the case.
In fact it would be very odd if ~= had different semantics than changing the 
length and copying. I can imagine subtle bugs creeping into code if they are 
different. Of course ~= can be more efficient than the two step code but it 
shouldn't end up with a different result.

> I suggest for a fix that your code not preallocate arrays; it's redundant
> with what the runtime is already doing.

For my case I wasn't preallocating - I was allocating blocks for a deque. 
Each block has a fixed size that will never be sliced or resized. I would 
like to know how to efficiently allocate such a block of memory and 
initialize it to hold a paramtrizing type T. I'm starting to suspect a 
general-purpose deque in D will very hard to get competitive with C++.
May 21, 2005
Re: a GC question
"Ben Hinkle" <ben.hinkle@gmail.com> wrote in message
news:d6lrve$1rpt$1@digitaldaemon.com...
> I suggest foo ~= bar for arrays be roughly equivalent to
>   size_t oldlen = foo.length;
>   foo.length = foo.length + bar.length;
>   foo[oldlen .. oldlen+bar.length] = bar[];
> That way when foo.length is 0 a new pointer is allocated (as you probably
> already know _d_arraysetlength checks for 0 length). When foo.length is
> non-zero and the array can be resized in place then it behaves the same as
> what it does today. So basically to make the smallest change to gc.d I
would
> change _d_arrayappend to check if length == 0 just like _d_arraysetlength
> and malloc a new block if that is the case.
> In fact it would be very odd if ~= had different semantics than changing
the
> length and copying. I can imagine subtle bugs creeping into code if they
are
> different. Of course ~= can be more efficient than the two step code but
it
> shouldn't end up with a different result.

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.

> For my case I wasn't preallocating - I was allocating blocks for a deque.
> Each block has a fixed size that will never be sliced or resized.

Why were the sizes picked to be powers of 2?

> I would
> like to know how to efficiently allocate such a block of memory and
> initialize it to hold a paramtrizing type T. I'm starting to suspect a
> general-purpose deque in D will very hard to get competitive with C++.
May 21, 2005
Re: a GC question
In article <d6lh2e$1keg$1@digitaldaemon.com>, Walter says...
>
>The +1 was to support the following usage:
>
>    T[] foo;
>    T[] bar;
>    ...
>    foo = foo[length .. length];
>    ...
>    foo ~= bar;

Okay, I must be missing something, because the above code looks to me like it
should result in undefined behavior.  Isn't the result of foo[length..length] a
single nonexistent array element just beyond the end of the array?  Assuming it
is, why should the GC be modified to support such usage?

>This would cause erratic, random crashes.

Perhaps this should just be done in debug builds, with the appropriate bounds
checking in place.  Then the bugs could be found and corrected without any
impact on relese performance.


Sean
May 21, 2005
Re: a GC question
In article <d6m2k5$1vv6$1@digitaldaemon.com>, Sean Kelly says...
>
>Isn't the result of foo[length..length] a single nonexistent array element just beyond the end of the array?

I meant a zero length array at an invalid location.


Sean
May 21, 2005
Re: a GC question
"Walter" <newshound@digitalmars.com> wrote in message 
news:d6m0i1$1uoh$1@digitaldaemon.com...
>
> "Ben Hinkle" <ben.hinkle@gmail.com> wrote in message
> news:d6lrve$1rpt$1@digitaldaemon.com...
>> I suggest foo ~= bar for arrays be roughly equivalent to
>>   size_t oldlen = foo.length;
>>   foo.length = foo.length + bar.length;
>>   foo[oldlen .. oldlen+bar.length] = bar[];
>> That way when foo.length is 0 a new pointer is allocated (as you probably
>> already know _d_arraysetlength checks for 0 length). When foo.length is
>> non-zero and the array can be resized in place then it behaves the same 
>> as
>> what it does today. So basically to make the smallest change to gc.d I
> would
>> change _d_arrayappend to check if length == 0 just like _d_arraysetlength
>> and malloc a new block if that is the case.
>> In fact it would be very odd if ~= had different semantics than changing
> the
>> length and copying. I can imagine subtle bugs creeping into code if they
> are
>> different. Of course ~= can be more efficient than the two step code but
> it
>> shouldn't end up with a different result.
>
> 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.

Then why when foo.length==0 does "foo.length = 1" reallocate but "foo ~= x" 
doesn't? Long ago I had argued that setting length shouldn't reallocate when 
resizing from 0. Now that I know the append behavior and the impact it has 
on the GC I'd rather have resizing from 0 reallocate both for consitency 
with setlength and to save the GC performance. Either that or enfore the 
rule that the first index of a slice must be a valid index within array 
bounds. After all the section on array slicing says "slicing an array means 
to specify a subarray of it" which to me implies the pointer refers to a 
valid location. I never knew one could slice off the end but I suppose that 
could come up if you are seaching for an item and it isn't there and so you 
wind up slicing off the end.

>> For my case I wasn't preallocating - I was allocating blocks for a deque.
>> Each block has a fixed size that will never be sliced or resized.
>
> Why were the sizes picked to be powers of 2?

I'm open to suggestions. I'm trying to write a deque that competes with C++ 
implementations. Efficient memory usage is an important part of a deque and 
powers of 2 (or I suppose power-of-2*element.sizeof) are traditionally the 
most efficient packing I believe.

>> I would
>> like to know how to efficiently allocate such a block of memory and
>> initialize it to hold a paramtrizing type T. I'm starting to suspect a
>> general-purpose deque in D will very hard to get competitive with C++.
>
>
1 2 3 4
Top | Discussion index | About this forum | D home