Re: Null references redux + Cyclone
Thanks Don! \o/
Re: Null references redux + Cyclone
Dejan Lekic wrote: Walter, is that article publicly available? http://www.codeproject.com/KB/cpp/FastDelegate.aspx
Re: Null references redux + Cyclone
Walter, is that article publicly available?
Re: Null references redux + Cyclone
Saaa wrote: Andrei Alexandrescu wrote I wonder whether this would be a good topic for TDPL. Currently I'm thinking it's too low-level. I do plan to insert a short section about implementation, just not go deep inside the object model. Andrei I'd really love to see more about implementations as it makes me twitch to use something I don't really know the impact of. As for using diagrams and other visual presentations: Please use them as much as possible; e.g. Pointers without arrows is like a film without moving pictures :) I do have the clasic arrow drawings that illustrate how reference semantics works, but by and large I'm not talented with drawing. If anyone in this group has such an inclination and would want to collaborate with me on the book, let me know. Send me your portfolio :o). Andrei
Re: Null references redux + Cyclone
Andrei Alexandrescu wrote > > I wonder whether this would be a good topic for TDPL. Currently I'm > thinking it's too low-level. I do plan to insert a short section about > implementation, just not go deep inside the object model. > > Andrei I'd really love to see more about implementations as it makes me twitch to use something I don't really know the impact of. As for using diagrams and other visual presentations: Please use them as much as possible; e.g. Pointers without arrows is like a film without moving pictures :)
Re: Null references redux + Cyclone
Andrei Alexandrescu: > I wonder whether this would be a good topic for TDPL. Currently I'm > thinking it's too low-level. I do plan to insert a short section about > implementation, just not go deep inside the object model. It's a very good topic for the book. Any good book about computer languages teaches not just a language, but also good programming practices and some general computer science too. In a big book about a system language I want to see "under the cover" topics too, otherwise I'll need to buy another book to learn them :-) So it's good for a book about a system language to explain how some parts of the compiler are implemented, because such parts are code too (and the level of such code can be the same, if someday will translate the D front-end to D). For example I have appreciated the chapter about Python Dict implementation in a chapter of "Beautiful code". I think you aren't interested in my help any more, but I hope you will follow this suggestion of mine (I'll buy your book anyway, but I know what I'd like to find in it). On the other hand writing about topics you don't know enough about may be negative, in such situation avoiding the topic may be better. Bye, bearophile
Re: Null references redux + Cyclone
Andrei Alexandrescu wrote: Saaa wrote: bearophile wrote Walter Bright: No, it is done with one indirection.< If even Andrei, a quite intelligent person that has written big books on C++, may be wrong on such a basic thing, then I think there's a problem. It can be good to create an html page that explains how some basic things of D are implemented in the front-end. Such page can also contain box & arrow images that show how structures and memory are organized for various of such data structures. Such html page is useful for both normal programmers that want to understand what's under the hood, and for people that may want to fix/modify the front-end. ?:) I seem to have requested the thing you here ask for. (within 24 hours even) http://d.puremagic.com/issues/show_bug.cgi?id=3351 I wonder whether this would be a good topic for TDPL. Currently I'm thinking it's too low-level. I do plan to insert a short section about implementation, just not go deep inside the object model. Andrei Maybe that's a topic for an appendix of the book. It is really useful to know the internals of a language, even if you don't directly use them it can impact design choices. Right now the best way to learn these internals is still to go hack and slash with the compiler's runtime implementation. Besides, there is no such thing as too low-level :)
Re: Null references redux + Cyclone
Saaa wrote: bearophile wrote Walter Bright: No, it is done with one indirection.< If even Andrei, a quite intelligent person that has written big books on C++, may be wrong on such a basic thing, then I think there's a problem. It can be good to create an html page that explains how some basic things of D are implemented in the front-end. Such page can also contain box & arrow images that show how structures and memory are organized for various of such data structures. Such html page is useful for both normal programmers that want to understand what's under the hood, and for people that may want to fix/modify the front-end. ?:) I seem to have requested the thing you here ask for. (within 24 hours even) http://d.puremagic.com/issues/show_bug.cgi?id=3351 I wonder whether this would be a good topic for TDPL. Currently I'm thinking it's too low-level. I do plan to insert a short section about implementation, just not go deep inside the object model. Andrei
Re: Null references redux + Cyclone
bearophile wrote > Walter Bright: > >>No, it is done with one indirection.< > > If even Andrei, a quite intelligent person that has written big books on > C++, may be wrong on such a basic thing, then I think there's a problem. > > It can be good to create an html page that explains how some basic things > of D are implemented in the front-end. Such page can also contain box & > arrow images that show how structures and memory are organized for various > of such data structures. > > Such html page is useful for both normal programmers that want to > understand what's under the hood, and for people that may want to > fix/modify the front-end. ?:) I seem to have requested the thing you here ask for. (within 24 hours even) http://d.puremagic.com/issues/show_bug.cgi?id=3351
Re: Null references redux + Cyclone
bearophile Wrote: > If even Andrei, a quite intelligent person that has written big books on C++, > may be wrong on such a basic thing, then I think there's a problem. > > It can be good to create an html page that explains how some basic things of > D are implemented in the front-end. Such page can also contain box & arrow > images that show how structures and memory are organized for various of such > data structures. > > Such html page is useful for both normal programmers that want to understand > what's under the hood, and for people that may want to fix/modify the > front-end. An averagely porfficient programmer should understand what a "pointer fixup" means, and fixups are discussed somewhere in the docs, if I recall it correctly. D fixes pointers up just in order to fasten interface calls. This also prevents generics from being implemented in D.
Re: Null references redux + Cyclone
Andrei Alexandrescu wrote:
I seem to recall that
interface dispach in D does a linear search in the interfaces list, so
you may want to repeat your tests with a variable number of interfaces,
and a variable position of the interface being used.
Such numbers are not interesting to me. On average, each class I write
implements one interface. I rarely use inheritance and interfaces in the
same class.
But your information is incorrect. Here's what happens:
object of class A
| vtable
| | classinfo pointer
| | methods...
| fields...
| interface vtable
| | struct Interface*
| | methods
struct Interface
{
ptrdiff_t this_offset;
ClassInfo interfaceInfo;
}
There are two ways to implement interface calls with this paradigm. The
compiler way:
interface I
{
void doStuff(int arg);
}
class A
{
void doStuff(int arg) { writefln("do stuff! %s", arg); }
// this method actually goes into the interface vtable
ReturnType!doStuff __I_doStuff(ParameterTypeTuple!doStuff args)
{
auto iface = cast(Interface*)this.vtable[0];
this = this + iface.this_offset;
return doStuff(args);
}
}
You can also do it with the runtime, but that's a lot harder. It would
be effectively the same code.
Re: Null references redux + Cyclone
bearophile wrote: If even Andrei, a quite intelligent person that has written big books on C++, may be wrong on such a basic thing, then I think there's a problem. Not everyone is an expert on everything, and how vptrs and vtbl[]s and casting actually work for multiple inheritance is far from being a basic thing. Furthermore, different compilers implement these things differently. Last I heard, Java did it the way Andrei described. Don Clugston wrote an article a few years ago on this, and found a wide variety of implementation strategies. The Digital Mars one was the fastest .
Re: Null references redux + Cyclone
bearophile wrote:
Walter Bright:
No, it is done with one indirection.<
If even Andrei, a quite intelligent person that has written big books on C++,
may be wrong on such a basic thing, then I think there's a problem.
It can be good to create an html page that explains how some basic things of D are
implemented in the front-end. Such page can also contain box & arrow images
that show how structures and memory are organized for various of such data
structures.
Such html page is useful for both normal programmers that want to understand
what's under the hood, and for people that may want to fix/modify the front-end.
Bye,
bearophile
I agree, the ABI documentation on digitalmars.com is far from complete,
I had to learn a lot of it through trial and error. What was especially
confusing was the interface reference vs the interface info vs the
interface's classinfo vs the referenced object, I wrote an internal
wrapper struct to make most of the casts go away:
struct Interface {
Object object() const {
return cast(Object)(cast(void*)&this - interfaceinfo.offset);
}
immutable(InterfaceInfo)* interfaceinfo() const {
return **cast(InterfaceInfo***)&this;
}
immutable(ClassInfo) classinfo() const {
return interfaceinfo.classinfo;
}
}
immutable struct InterfaceInfo {
ClassInfo classinfo;
void*[] vtbl;
ptrdiff_t offset;
}
These two made implementing D internals a whole lot easier! I think only
InterfaceInfo is in druntime (and its confusingly named Interface in there).
Re: Null references redux + Cyclone
Walter Bright: >No, it is done with one indirection.< If even Andrei, a quite intelligent person that has written big books on C++, may be wrong on such a basic thing, then I think there's a problem. It can be good to create an html page that explains how some basic things of D are implemented in the front-end. Such page can also contain box & arrow images that show how structures and memory are organized for various of such data structures. Such html page is useful for both normal programmers that want to understand what's under the hood, and for people that may want to fix/modify the front-end. Bye, bearophile
Re: Null references redux + Cyclone
Andrei Alexandrescu wrote:
Thanks for posting these interesting numbers. I seem to recall that
interface dispach in D does a linear search in the interfaces list, so
you may want to repeat your tests with a variable number of interfaces,
and a variable position of the interface being used.
No, it is done with one indirection.
interface IA { void foo(); }
interface IB : IA { }
class C : IA { void foo() { } }
void test(C c)
{
c.foo();
}
test:
enter 4,0
mov ECX,[EAX]
calldword ptr 014h[ECX]
leave
ret
Re: Null references redux + Cyclone
On 2009-09-28 15:36:05 -0400, bearophile said: Compiled with DMD the running time seems about unchanged. I have no idea why. Maybe some of you can tell me. If I recall correctly, implementing an interface adds a variable to an class which contains a pointer to that interface's vtable implementation for that particular class. An interface pointer points to that variable inside the object instead (not at the beginning of the object allocated space), and calling a function on it involves dereferencing the interface's vtable, and calling the right function. Obtaining the real "this" pointer for calling the function involves looking at the first value in the interface's vtable which contains an offset you can substract from the interface pointer to get the object pointer. So basically, if I recall well how it works, calling a function on an interface reference involves one more substraction than calling a member function a class reference, which is pretty marginal. -- Michel Fortin michel.for...@michelf.com http://michelf.com/
Re: Null references redux + Cyclone
"bearophile" wrote in message news:h9qo0l$75...@digitalmars.com... > > But beside normal C unions that I don't want to remove from C, it can be > also useful to have safe automatic tagged unions of Cyclone. They are > safer and give just a little less performance compared to C unions. In D > they may be denoted with "record" or "tunion" or just "safe union" to save > keywords. They always contain an invisible tag (that can be read with a > special built-in union method, like Unioname.tagcheck). Such "safe unions" > may even become the only ones allowed in SafeD modules! > > The following is from Cyclone docs: > << > The C Standard says that if you read out any member of a union other than > the last one written, the result is undefined. > To avoid this problem, Cyclone provides a built-in form of tagged union > and always ensures that the tag is correlated with the last member written > in the union. In particular, whenever a tagged union member is updated, > the compiler inserts code to update the tag associated with the union. > Whenever a member is read, the tag is consulted to ensure that the member > was the last one written. If not, an exception is thrown. > Sounds like a variant to me, but just without automatic conversion. Or am I misunderstanding?
Re: Null references redux + Cyclone
Christopher Wright: > > Certainly agreed on virtual calls: on my machine, I timed a simple > > example as executing 65 interface calls per microsecond, 85 virtual > > calls per microsecond, and 210 non-member function calls per > > microsecond. So you should almost never worry about the cost of > > interface calls since they're so cheap, but they are 3.5 times slower > > than non-member functions. The main problem of virtual calls in D are the missed inlining opportunities. Andrei Alexandrescu: > I seem to recall that > interface dispach in D does a linear search in the interfaces list, so > you may want to repeat your tests with a variable number of interfaces, > and a variable position of the interface being used. The following is a D port of the well known "Richards" benchmark. This specific version is object oriented, its classes are final (otherwise the code gets quite slower with LDC) and it has getters/setters. It contains an interface: http://codepad.org/kO3MJK60 You can run it at the command line giving it 1000. On a Celeron 2 GHz if you replace the interface with an abstract class the running time goes from 2.16 to 1.58 seconds, compiled with: ldc -O5 -release -inline Compiled with DMD the running time seems about unchanged. I have no idea why. Maybe some of you can tell me. In a day or two I'll release many more timings and tests about this Richards benchmark. Bye, bearophile
Re: Null references redux + Cyclone
Christopher Wright wrote: bearophile wrote: Jeremie Pelletier: Again, that's a lazy view on programming. High level constructs are useful to isolate small and simple algorithms which are implemented at low level. Software is inherently multi-scale. Probably in 90-95% of the code of a program micro-optimizations aren't that necessary because those operations are done only once in a while. But then it often happens that certain loops are done an enormous amount of times, so even small inefficiencies inside them lead to low performance. That's why profiling helps. This can be seen by how HotSpot (and modern dynamic language JITters work): usually virtual calls like you can find in a D program are quick, they don't slow down code. Yet if a dynamic call prevents the compile to perform a critical inlining or such dynamic call is left in the middle of a critical code, it may lead to a slower program. That's why I have Java code go 10-30% faster than D code compiled with LDC, not because of the GC and memory allocations, but just because LDC isn't smart enough to inline certain virtual methods. Certainly agreed on virtual calls: on my machine, I timed a simple example as executing 65 interface calls per microsecond, 85 virtual calls per microsecond, and 210 non-member function calls per microsecond. So you should almost never worry about the cost of interface calls since they're so cheap, but they are 3.5 times slower than non-member functions. Thanks for posting these interesting numbers. I seem to recall that interface dispach in D does a linear search in the interfaces list, so you may want to repeat your tests with a variable number of interfaces, and a variable position of the interface being used. Andrei
Re: Null references redux + Cyclone
bearophile wrote: Jeremie Pelletier: Again, that's a lazy view on programming. High level constructs are useful to isolate small and simple algorithms which are implemented at low level. Software is inherently multi-scale. Probably in 90-95% of the code of a program micro-optimizations aren't that necessary because those operations are done only once in a while. But then it often happens that certain loops are done an enormous amount of times, so even small inefficiencies inside them lead to low performance. That's why profiling helps. This can be seen by how HotSpot (and modern dynamic language JITters work): usually virtual calls like you can find in a D program are quick, they don't slow down code. Yet if a dynamic call prevents the compile to perform a critical inlining or such dynamic call is left in the middle of a critical code, it may lead to a slower program. That's why I have Java code go 10-30% faster than D code compiled with LDC, not because of the GC and memory allocations, but just because LDC isn't smart enough to inline certain virtual methods. Certainly agreed on virtual calls: on my machine, I timed a simple example as executing 65 interface calls per microsecond, 85 virtual calls per microsecond, and 210 non-member function calls per microsecond. So you should almost never worry about the cost of interface calls since they're so cheap, but they are 3.5 times slower than non-member functions. In most cases, the body of a method is a lot more expensive than the method call, so even when optimizing, it won't often benefit you to use free functions rather than class or interface methods.
Re: Null references redux + Cyclone
Jeremie Pelletier:
> Not always true.
I agree, I'm using D also because it offers unions. Sometimes they are useful.
But beside normal C unions that I don't want to remove from C, it can be also
useful to have safe automatic tagged unions of Cyclone. They are safer and give
just a little less performance compared to C unions. In D they may be denoted
with "record" or "tunion" or just "safe union" to save keywords. They always
contain an invisible tag (that can be read with a special built-in union
method, like Unioname.tagcheck). Such "safe unions" may even become the only
ones allowed in SafeD modules!
The following is from Cyclone docs:
<<
The C Standard says that if you read out any member of a union other than the
last one written, the result is undefined.
To avoid this problem, Cyclone provides a built-in form of tagged union and
always ensures that the tag is correlated with the last member written in the
union. In particular, whenever a tagged union member is updated, the compiler
inserts code to update the tag associated with the union. Whenever a member is
read, the tag is consulted to ensure that the member was the last one written.
If not, an exception is thrown.
Thus, the aforementioned example can be rewritten in Cyclone like this:
@tagged union U { int i; int *p; };
void pr(union U x) {
if (tagcheck(x.i))
printf("int(%d)",x.i);
else
printf("ptr(%d)",*x.p);
}
The @tagged qualifier indicates to the compiler that U should be a tagged
union. The operation tagcheck(x.i) returns true when i was the last member
written so it can be used to extract the value.
>>
> Again, that's a lazy view on programming. High level constructs are
> useful to isolate small and simple algorithms which are implemented at
> low level.
Software is inherently multi-scale. Probably in 90-95% of the code of a program
micro-optimizations aren't that necessary because those operations are done
only once in a while. But then it often happens that certain loops are done an
enormous amount of times, so even small inefficiencies inside them lead to low
performance. That's why profiling helps.
This can be seen by how HotSpot (and modern dynamic language JITters work):
usually virtual calls like you can find in a D program are quick, they don't
slow down code. Yet if a dynamic call prevents the compile to perform a
critical inlining or such dynamic call is left in the middle of a critical
code, it may lead to a slower program. That's why I have Java code go 10-30%
faster than D code compiled with LDC, not because of the GC and memory
allocations, but just because LDC isn't smart enough to inline certain virtual
methods.
More quotations from the Cyclone documentation:
>In contrast, Cyclone's analysis extends to struct, union members, and pointer
>contents to ensure everything is initialized before it is used. This has two
>benefits: First, we tend to catch more bugs this way, and second, programmers
>don't pay for the overhead of automatic initialization on top of their own
>initialization code.<
This is right on-topic:
>This requires little effort from the programmer, but the NULL checks slow down
>getc. To repair this, we have extended Cyclone with a new kind of pointer,
>called a never-NULL pointer, and indicated with �...@ instead of *. For
>example, in Cyclone you can declare
int getc(FILE @);
indicating that getc expects a non-NULL FILE pointer as its argument. This
one-character change tells Cyclone that it does not need to insert NULL checks
into the body of getc. If getc is called with a possibly-NULL pointer, Cyclone
will insert a NULL check at the call :<
>Goto C's goto statements can lead to safety violations when they are used to
>jump into scopes. Here is a simple example:
int z;
{ int x = 0xBAD; goto L; }
{ int *y = &z;
L: *y = 3; // Possible segfault
}
Cyclone's static analysis detects this situation and signals an error. A goto
that does not enter a scope is safe, and is allowed in Cyclone. We apply the
same analysis to switch statements, which suffer from a similar vulnerability
in C.<
Bye,
bearophile
