Index » General » a GC question (page 2)

May 20, 2005
> *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
> 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
> 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
> 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
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
"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
> 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
> 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
>> 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
"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