View mode: basic / threaded / horizontal-split · Log in · Help
May 20, 2005
Re: a GC question
> *sweet-question*). I think the +1 comes from the string handling... The GC 
> puts a 0 after them to help you cope with the native C api...

Oh my.. I'd say: remove the possibility for an array to be castable to a 
pointer; remove this hack; add a property .ptr...

It all seems too big a price to pay for compatibility with old C libraries. 
New D libraries, Phobos in particular, should just use D arrays, with no 
pointer whatsoever.

L.
May 20, 2005
Re: a GC question
> New D libraries, Phobos in particular, should just use D arrays, with no
> pointer whatsoever.

Nope. Sorry, but if you program some data structure and try to optimize  
it, it is really necessary to work with these pointers. Removing this  
possibility would simply make a lot of things impossible. And one of the  
goals of D is having the possibility to work at low level when necessary.  
And to say something about the 0 after strings (i'm not sure if the +1  
comes from that issue!) ... my containers do the same thing, and my  
toUtfXXX converters too. It costs a byte (or a dchar for an UTF-32  
string), and opens up the whole world of existing C APIs. Rewrite ICU &  
friends for D, and i will not need that any more and delete it from my  
containers...

Just a simple example for the necessity of low-level pointer access: A  
skip-list is used to build a map-like structure. It is basically a linked  
list, but some of the nodes not only link to their direct successor, but  
also to some node much further in the list. The basic node looks like this:

struct Node
{
  SomeType key;
  OtherType data;

  Node* prev;
  Node*[1] next;
}

This node has only one pointer, which points to the next node. If the node  
has level 1 (that means it has 1 extra pointer to a node which is about 7  
nodes ahead), it is allocated like that:

Node* newNode = cast(Node*) new char[Node.sizeof + level * (Node*).sizeof];
// where level == 1.

Now you can access that extra pointer if you know for sure that the node  
has level 1 (the internal structure lets you know):

newNode.next.ptr[1] = xxx;

This simple and very fast approach relies on pointers, casts and all that  
low-level stuff. And the benefit is that you don't have to declare the  
Node like that:

struct Node
{
  SomeType key;
  OtherType data;

  Node* prev;
  Node*[11] next;
}

Wasting 40 bytes for every level-0-node (7 of 8 are level 0). Now imagine  
you do some real work, with about a million elements (if you have only  
1000, you could simply run through all of them to find a peculiar one):

7/8 * 1000000 * 40 = 35 MByte.

See what i mean?

Ciao
uwe
May 20, 2005
Re: a GC question
> Just a simple example for the necessity of low-level pointer access: A 
> skip-list is used to build a map-like structure. It is basically a linked 
> list, but some of the nodes not only link to their direct successor, but 
> also to some node much further in the list. The basic node looks like 
> this:
>
> struct Node
> {
>   SomeType key;
>   OtherType data;
>
>   Node* prev;
>   Node*[1] next;
> }
>
> This node has only one pointer, which points to the next node. If the node 
> has level 1 (that means it has 1 extra pointer to a node which is about 7 
> nodes ahead), it is allocated like that:
>
> Node* newNode = cast(Node*) new char[Node.sizeof + level * 
> (Node*).sizeof];
> // where level == 1.
>
> Now you can access that extra pointer if you know for sure that the node 
> has level 1 (the internal structure lets you know):
>
> newNode.next.ptr[1] = xxx;
>
> This simple and very fast approach relies on pointers, casts and all that 
> low-level stuff. And the benefit is that you don't have to declare the 
> Node like that:
>
> struct Node
> {
>   SomeType key;
>   OtherType data;
>
>   Node* prev;
>   Node*[11] next;
> }
>
> Wasting 40 bytes for every level-0-node (7 of 8 are level 0). Now imagine 
> you do some real work, with about a million elements (if you have only 
> 1000, you could simply run through all of them to find a peculiar one):
>
> 7/8 * 1000000 * 40 = 35 MByte.
>
> See what i mean?

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[].
May 20, 2005
Re: a GC question
> 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
May 20, 2005
Re: a GC question
Hey,

> Nope. Sorry, but if you program some data structure and try to optimize 
> it, it is really necessary to work with these pointers. Removing this 
> possibility would simply make a lot of things impossible. And one of the 
> goals of D is having the possibility to work at low level when necessary.

You make it sound as if I asked for the removal of pointers from the D spec!
I said no such thing. The only thing I'm suggesting is that calling 
functions in old libraries that rely heavily on pointers (like the C 
run-time) should not be done implicitely.

I should get a compiler error if I try passing a char[] to puts() cause that 
puts doesn't know about char[], it wants char* and wants the string to be 
zero terminated! Fixed by adding a simple toStringz(x), or a ~ '\0'.

> And to say something about the 0 after strings (i'm not sure if the +1 
> comes from that issue!) ... my containers do the same thing, and my 
> toUtfXXX converters too. It costs a byte (or a dchar for an UTF-32 
> string), and opens up the whole world of existing C APIs. Rewrite ICU & 
> friends for D, and i will not need that any more and delete it from my 
> containers...

Yes, sure, they can add a zero to the array, but shouldn't pretend it's not 
there. I mean, the array.length should grow by one, because of that extra 
element. Not assuming the GC/mem.manager added it and "just pass the 
pointer, it'll work". :-S

> Just a simple example for the necessity of low-level pointer access: A 
> skip-list is used to build a map-like structure. It is basically a linked 
> list, but some of the nodes not only link to their direct successor, but 
> also to some node much further in the list. The basic node looks like 
> this:

<snip>

> See what i mean?

Yes. First of all, you can use templates for that, using an integer template 
argument that defines how large the array should be.
Furthermore, I really have nothing against that kind of coding. It is not 
what meant to 'attack' in my previous post.

Sometimes it just feels that people want to be able to compile old C code 
with a D compiler without changing anything. Not only that, they _expect_ D 
to compile old C code, cursing if it doesn't. Of course, D should be able to 
interface with the C run-time, but should arrays therefor be implicetely 
castable to pointers? Or worse, char[] to char* ?

L.
May 20, 2005
Re: a GC question
"Uwe Salomon" <post@uwesalomon.de> wrote in message 
news:op.sq2quseu6yjbe6@sandmann.maerchenwald.net...
>> 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.

Low level memory management tricks should use malloc instead of the GC. If 
one wants to use the GC one has to accept some rules. Your code would work 
fine with today's GC so it's not like all GC's would have trouble with it so 
if you want you could keep that code and just say it is only usable with 
certain GC's - but that probably isn't what you want.
What would I recommend... the first thing that comes to mind is just live 
with the 'next' list as a separate allocation stored as a dynamic array:
struct Node
{
  SomeType key;
  OtherType data;

  Node* prev;
  Node*[] next;
}
Node* newNode = new Node;
newNode.next = new Node*[4]; // this node has 4 next pointers.

If profiling indicates that is unacceptable then I'd look into more complex 
solutions. For example
import std.stdio;
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.

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

I don't understand your point. Are you saying low level memory tricks are 
good or bad - or that the advanced memory techniques section in the doc 
needs changing? I can't keep up with your thought stream.

>
> Ciao
> uwe
May 20, 2005
Re: a GC question
> I said no such thing. The only thing I'm suggesting is that calling
> functions in old libraries that rely heavily on pointers (like the C
> run-time) should not be done implicitely.

Hm. This sounds like a good idea to me. Yes. I misunderstood you then,  
sorry.

> Yes. First of all, you can use templates for that, using an integer  
> template argument that defines how large the array should be.

Regrettably not, because the level of the node is only known at compile  
time...

Ciao
uwe
May 20, 2005
Re: a GC question
> Node* newNode = new Node;
> newNode.next = new Node*[4]; // this node has 4 next pointers.

This almost doubles the costs of inserting an element, as there are 2  
allocations instead of one. And most of the time i allocate an array with  
1 or 2 elements...

> newNode.next[0] = cast(Node*)new FullNode!(4); // 4 items

The level is dynamically calculated at runtime.

>> 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.
>
> I don't understand your point. Are you saying low level memory tricks are
> good or bad - or that the advanced memory techniques section in the doc
> needs changing? I can't keep up with your thought stream.

I think low level memory tricks are very useful, and therefore good in  
situations where the benefit is high. You have to weight simplicity and  
therefore understandability and maintainability against performance. But  
for generic containers i would always vote for the performance, as peoply  
simply use them and don't think about it much.

The advanced memory section in the docs is very good.

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.

Ciao
uwe
May 20, 2005
Re: a GC question
>> Yes. First of all, you can use templates for that, using an integer  
>> template argument that defines how large the array should be.
>
> Regrettably not, because the level of the node is only known at compile  
> time...

Err, it is only known at runtime. Sorry for that.

uwe
May 20, 2005
Re: a GC question
"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 for a fix that your code not preallocate arrays; it's redundant
with what the runtime is already doing.
1 2 3 4
Top | Discussion index | About this forum | D home