www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Replacing AA's in druntime

reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
Hi all,

My AA implementation is slowly inching closer to being ready to replace
aaA.d. So far I've been writing the implementation outside of object_.d
for ease of testing & development; now I'm ready to start moving stuff
into object_.d to start working on integration with druntime. So I'm
wondering how the current stuff works.

Is it correct that when the compiler sees a declaration like:

	int[string] aa;

it automatically translates that to struct AssociativeArray(K,V)?

What about the functions in aaA.d? I presume the compiler generates
calls to them whenever it sees an AA construct like "x in y", "x[y]",
etc?

Right now, I've implemented opBinaryRight!"in", opIndexAssign, and
opIndex; will the compiler know to invoke these methods, or will it
still go through aaA.d? I presume the latter? If so, I was thinking that
I can simply forward these calls to struct AssociativeArray, but the
problem is I wouldn't know which instance to forward it to since the
aaA.d functions only get typeinfos and an opaque pointer.

(There are also other issues, such as potential code bloat from
instantiating AssociativeArray(K,V), since everything is in the template
struct member now. But I'm not too worried about that yet; once the AA
implementation is fully dissocciated from aaA.d, it should be relatively
easy to factor out common code and/or replace the implementation with
something better.)


T

-- 
Unix was not designed to stop people from doing stupid things, because that
would also stop them from doing clever things. -- Doug Gwyn
Mar 13 2012
next sibling parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
Welcome to Hell. =D

Some of the things you can do with AAs are recognized by the compiler during 
semantic and turned into druntime calls, sometimes the constructs survive 
all the way to the glue layer (e2ir) and are turned into druntime calls 
there and sometimes the type of an expressions is magically rewritten to 
AssociativeArray and the methods are looked up normally.  (this one caused 
problems with literals)

The type needs to stay as V[K] _not_ AssociativeArray, so that error 
messages work properly.  Something needs to be done about literals too... 
Don't forget template arg deduction!

There's a function AAGetSym (or something like that) that can be searched 
for to find where dmd emits druntime calls, but there might be other places 
it generates them.

Enjoy.
Mar 13 2012
next sibling parent James Miller <james aatch.net> writes:
On 14 March 2012 14:37, Daniel Murphy <yebblies nospamgmail.com> wrote:

 Welcome to Hell. =D


Sounds fun.

(Seasoned DF player)

--
James Miller
Mar 13 2012
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Mar 14, 2012 at 12:37:08PM +1100, Daniel Murphy wrote:

 Welcome to Hell. =D


Ahhhahahaha... sounds like I leapt into the deep end of the pool without
knowing it. :-P



 Some of the things you can do with AAs are recognized by the compiler
 during semantic and turned into druntime calls, sometimes the
 constructs survive all the way to the glue layer (e2ir) and are turned
 into druntime calls there and sometimes the type of an expressions is
 magically rewritten to AssociativeArray and the methods are looked up
 normally.  (this one caused problems with literals)
 
 The type needs to stay as V[K] _not_ AssociativeArray, so that error
 messages work properly.  Something needs to be done about literals
 too...  Don't forget template arg deduction!
 
 There's a function AAGetSym (or something like that) that can be
 searched for to find where dmd emits druntime calls, but there might
 be other places it generates them.


[...]

Alright. So now I have to dig into dmd internals to do what I want.
Maybe I should complete the template implementation first before
tackling this stuff. Sounds nasty. :-P  (But then again, I *did* have to
deal with over-engineered C++ in the past, which at one point required
making an IPC call via 6 levels of abstraction, one of which involved
fork(), fwrite() and fread(). I doubt dmd attains to that level of
evil.)


T

-- 
Жил-был король когда-то, при нём блоха жила.
Mar 13 2012
parent "Daniel Murphy" <yebblies nospamgmail.com> writes:
"H. S. Teoh" <hsteoh quickfur.ath.cx> wrote in message 
news:mailman.651.1331696880.4860.digitalmars-d puremagic.com...

 On Wed, Mar 14, 2012 at 12:37:08PM +1100, Daniel Murphy wrote:

 Welcome to Hell. =D


 Ahhhahahaha... sounds like I leapt into the deep end of the pool without
 knowing it. :-P


Yeah, the AA implementation is the deepest part I've found in dmd.


 Some of the things you can do with AAs are recognized by the compiler
 during semantic and turned into druntime calls, sometimes the
 constructs survive all the way to the glue layer (e2ir) and are turned
 into druntime calls there and sometimes the type of an expressions is
 magically rewritten to AssociativeArray and the methods are looked up
 normally.  (this one caused problems with literals)

 The type needs to stay as V[K] _not_ AssociativeArray, so that error
 messages work properly.  Something needs to be done about literals
 too...  Don't forget template arg deduction!

 There's a function AAGetSym (or something like that) that can be
 searched for to find where dmd emits druntime calls, but there might
 be other places it generates them.


 [...]

 Alright. So now I have to dig into dmd internals to do what I want.
 Maybe I should complete the template implementation first before
 tackling this stuff. Sounds nasty. :-P  (But then again, I *did* have to
 deal with over-engineered C++ in the past, which at one point required
 making an IPC call via 6 levels of abstraction, one of which involved
 fork(), fwrite() and fread(). I doubt dmd attains to that level of
 evil.)


 T


Probably a good idea to finish it first.  It might be possible to just 
recognize AssociativeArray when printing error messages, and let the 
existing struct template code handle everything else.  Ideally syntax and 
error messages/stringof/pragma msg should be the only places where the 
compiler is actually aware AAs exist.  But this might not be that easy...
Mar 13 2012
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/13/12 7:54 PM, H. S. Teoh wrote:

 Hi all,

 My AA implementation is slowly inching closer to being ready to replace
 aaA.d.


Great! This will need compiler restructuring, and in fact offers the 
perfect opportunity for it. I suggest you to post your implementation 
here for review first, and assume only the minimal lowerings from the 
compiler.

Here's something that I thinks we should have:

int[string] aa;
char[] b;
...
aa[b] = 42;

The implementation should be clever enough to work, and only duplicate 
the string if it wasn't already present.


Thanks,

Andrei
Mar 13 2012
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Mar 13, 2012 at 09:30:45PM -0500, Andrei Alexandrescu wrote:

 On 3/13/12 7:54 PM, H. S. Teoh wrote:

Hi all,

My AA implementation is slowly inching closer to being ready to
replace aaA.d.


 
 Great! This will need compiler restructuring, and in fact offers the
 perfect opportunity for it. I suggest you to post your implementation
 here for review first, and assume only the minimal lowerings from the
 compiler.


Currently I have it as a struct that implements AA functionality without
needing special support from the compiler (i.e., as a template library).
The only thing that needs compiler support is AA literals and internal
mapping between V[K] and AssociativeArray!(K,V) for nicer syntax and
error messages.

I didn't do anything fancy with the implementation, just used the same
algorithms as the current aaA.d, the idea being that fancy stuff can be
added later once we have successfully extricated AA's from internal
compiler dependencies.

The current code is already nicer in that it no longer needs the void*
casts and typeinfo's now that key/value types are directly accessible.
This will allow us to address some fundamental issues with aaA.d such as
key/value types that require deep traversal of references (the current
implementation of AA.toHash is broken partly because of this). Of
course, performance issues also need to be addressed eventually, such as
possible optimizations when key/value types have no external references,
in which case some operations can use byte-level representations
instead. But IMO this should be postponed till later; the main thing
right now is to fix up the compiler. Once AA's are completely in
object.d, optimizations and other fixes/improvements will be much
easier.



 Here's something that I thinks we should have:
 
 int[string] aa;
 char[] b;
 ...
 aa[b] = 42;
 
 The implementation should be clever enough to work, and only duplicate
 the string if it wasn't already present.


[...]

Hmm, this is something nice to have. I guess get() and opIndex*() should
allow any type that is comparable with the key type? Now that the
implementation is in a template, this should be much easier to do. :)

But while we're at it, one thing that I'd like to see is that AA key
types should be *implicitly* immutable. It makes no sense for AA keys to
be mutable, and it's syntactically painful to keep typing stuff like
string[immutable(int)[]]. Especially when mutable key types *never* make
sense anyway. So why not translate string[int[]] into
string[immutable(int)[]] implicitly? Thoughts?


T

-- 
INTEL = Only half of "intelligence".
Mar 13 2012
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Mar 13, 2012 at 09:30:45PM -0500, Andrei Alexandrescu wrote:

 On 3/13/12 7:54 PM, H. S. Teoh wrote:

Hi all,

My AA implementation is slowly inching closer to being ready to
replace aaA.d.


 
 Great! This will need compiler restructuring, and in fact offers the
 perfect opportunity for it. I suggest you to post your implementation
 here for review first, and assume only the minimal lowerings from the
 compiler.


Alright, I've finished the basic functionality of my AA implementation.
I still haven't solved that problem with using suffixless string
literals to index X[dstring], so you'll have to write aa["abc"d] instead
of just aa["abc"]. But I thought I should post my code now so that
people can take a look at it:

	https://github.com/quickfur/New-AA-implementation/blob/master/newAA.d

Currently, this code is still standalone, not integrated with druntime
yet.  Since that will require compiler changes and is potentially a very
big change, I've decided to polish up the standalone version as much as
possible before attempting druntime integration.

There are still some outstanding issues:

- As mentioned above, wstring or dstring keys (in fact any array keys
  with literals that doesn't default to the key type) need an explicit
  suffix when indexing with literals. I haven't figured out how to make
  this work yet.  At the very least, wstring and dstring needs to
  support suffixless key literals; it would be nice if a general
  solution could be found for all array-typed keys.

- Declaring an AA with non-const array keys will cause reams and reams
  of compile errors. I'm not *too* worried about this at the moment
  since it doesn't make sense to have non-const AA keys anyway. I'm also
  seriously considering forcing *all* AA keys to be immutable, in which
  case this will become a non-issue.

- Some code (most notably that table of primes that I hoisted from
  aaA.d) may need to be refactored to prevent excessive code bloat when
  the AA template is instantiated.

- Array literals don't work yet (requires compiler support).

- X[Y] syntax doesn't work yet (requires druntime integration & compiler
  support); you have to explicitly declare AssociativeArray!(Y,X).

- The use of typeid.getHash. This is probably OK, except that it forces
  a lot of AA methods not to be pure nothrow  safe. It would also be
  nice if there was a uniform syntax for getting the hash of a type
  without going through typeid (may be more efficient?).

- I haven't stress-tested AA performance yet. (Any volunteers? ;-)) Some
  improvement in this area will probably be needed, though we may not
  need to address that until this is ready for druntime integration.

- (There's also some temporary development-only code, syntactic sugar
  aliases, that shouldn't end up in object_.d -- those will be removed
  when I'm ready for druntime integration. There's also some code that
  needs a bit of cleanup.)

In spite of its flaws, this implementation already addresses quite a few
AA-related issues in the bugtracker, as verified by a bunch of unittests
(search for "Issue" in the code).

Comments? Flames? ;-) Pull requests?? :-D


T

-- 
It is the quality rather than the quantity that matters. -- Lucius Annaeus
Seneca
Mar 14 2012
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
H. S. Teoh:


 - As mentioned above, wstring or dstring keys (in fact any array keys
   with literals that doesn't default to the key type) need an explicit
   suffix when indexing with literals. I haven't figured out how to make
   this work yet.  At the very least, wstring and dstring needs to
   support suffixless key literals; it would be nice if a general
   solution could be found for all array-typed keys.


This might be a problem worth fixing generally, if possible, so it's solved for
other library-defined collections too.



 I'm also
   seriously considering forcing *all* AA keys to be immutable, in which
   case this will become a non-issue.


I am for not mutable keys.



 - Some code (most notably that table of primes that I hoisted from
   aaA.d) may need to be refactored to prevent excessive code bloat when
   the AA template is instantiated.


Ah, another usage for my "static static" (or for the  templated()). I'll count
how many times they come out useful :-)



 It would also be
   nice if there was a uniform syntax for getting the hash of a type
   without going through typeid (may be more efficient?).


I agree!



 - I haven't stress-tested AA performance yet. (Any volunteers? ;-))


I have several benchmarks, but you can start quickly adapting this one,
comparing the performance of the built-in AAs with your ones:
http://rosettacode.org/wiki/Sokoban#D

Bye,
bearophile
Mar 14 2012
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
H. S. Teoh:


 - I haven't stress-tested AA performance yet. (Any volunteers? ;-))


I have just seen that the performance of the Sokoban solver is unchanged.



 In spite of its flaws, this implementation already addresses quite a few
 AA-related issues in the bugtracker,


How efficiently is this AA working with keys like:
AssociativeArray!(immutable char[60], bool) aa;
Built-in AAs become snail-slow with such keys.

Bye,
bearophile
Mar 14 2012
next sibling parent reply James Miller <james aatch.net> writes:
On 15 March 2012 13:47, bearophile <bearophileHUGS lycos.com> wrote:

 H. S. Teoh:


 - I haven't stress-tested AA performance yet. (Any volunteers? ;-))


 I have just seen that the performance of the Sokoban solver is unchanged.



 In spite of its flaws, this implementation already addresses quite a few
 AA-related issues in the bugtracker,


 How efficiently is this AA working with keys like:
 AssociativeArray!(immutable char[60], bool) aa;
 Built-in AAs become snail-slow with such keys.

 Bye,
 bearophile


Hmm, I might code up a stress-test suite for this if I get time/bored.
Any tips on where to start? Obviously you want things like lots of
entries, but is it important to test big Keys, particular types of
keys, that sort of thing.

I'll also probably do separate speed and memory benchmarks.

--
James Miller
Mar 14 2012
parent "bearophile" <bearophileHUGS lycos.com> writes:
James Miller:


 Any tips on where to start?


You have a lot of search space to cover, so before doing a 
systematic search that requires a lot of time I suggest a quick 
random sampling of the search space. If there are significantly 
wide performance inefficiencies you will hit them in less than 
one hour of tests. Such approach is sometimes missed even by 
professional engineers :-)

I have already given a link to a game solver that uses 
associative arrays a lot.

Then, this is my currently "best short solution" of one of the 
Shootout benchmarks that stresses only hashing. The input data 
comes from the Fasta benchmark (just use the Python or C++ Fasta 
code if you want the test data):
http://codepad.org/ZSlrcuad

I have few other benchmarks.

Bye,
bearophile
Mar 14 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Mar 14, 2012 at 08:47:23PM -0400, bearophile wrote:

 H. S. Teoh:
 

 - I haven't stress-tested AA performance yet. (Any volunteers? ;-))


 
 I have just seen that the performance of the Sokoban solver is
 unchanged.
 
 

 In spite of its flaws, this implementation already addresses quite a
 few AA-related issues in the bugtracker,


 
 How efficiently is this AA working with keys like:
 AssociativeArray!(immutable char[60], bool) aa;
 Built-in AAs become snail-slow with such keys.


[...]

Well, I didn't invent any clever new algorithms or anything like that, I
more-or-less followed the same implementation as aaA.d.  So I don't
think there will be any great performance gains. I'm more concerned
about drastic performances *losses* caused by code that I didn't realize
would cause a problem, perhaps an overlooked inefficiency that crept in
when I was translating the AA code into template-based code.


T

-- 
Being able to learn is a great learning; being able to unlearn is a greater
learning.
Mar 14 2012
prev sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Mar 14, 2012 at 08:47:23PM -0400, bearophile wrote:

 H. S. Teoh:
 

 - I haven't stress-tested AA performance yet. (Any volunteers? ;-))


 
 I have just seen that the performance of the Sokoban solver is
 unchanged.


I've just run the Sokoban solver in a loop that runs the solve 20 times
in a row. I consistently get around 7 seconds in total for both the
current aaA.d AA implementation and my new implementation. So far it
they seem to perform about the same.



 In spite of its flaws, this implementation already addresses quite a
 few AA-related issues in the bugtracker,


 
 How efficiently is this AA working with keys like:
 AssociativeArray!(immutable char[60], bool) aa;
 Built-in AAs become snail-slow with such keys.


[...]

I'll try something like this next.

Thanks for the feedback!


T

-- 
PNP = Plug 'N' Pray
Mar 14 2012
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/14/12 6:16 PM, H. S. Teoh wrote:

 - Declaring an AA with non-const array keys will cause reams and reams
    of compile errors. I'm not *too* worried about this at the moment
    since it doesn't make sense to have non-const AA keys anyway. I'm also
    seriously considering forcing *all* AA keys to be immutable, in which
    case this will become a non-issue.


I think the built-in associative array must allow non-constant keys. As 
long as there's no memory safety issue, the AA should work with types 
that the user doesn't change for comparison purposes but can otherwise 
modify.

A practical matter is that if we introduce this restriction we'll break 
a ton of code.


Andrei
Mar 14 2012
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Mar 14, 2012 at 11:58:01PM -0500, Andrei Alexandrescu wrote:

 On 3/14/12 6:16 PM, H. S. Teoh wrote:

- Declaring an AA with non-const array keys will cause reams and reams
   of compile errors. I'm not *too* worried about this at the moment
   since it doesn't make sense to have non-const AA keys anyway. I'm
   also seriously considering forcing *all* AA keys to be immutable,
   in which case this will become a non-issue.


 
 I think the built-in associative array must allow non-constant keys.
 As long as there's no memory safety issue, the AA should work with
 types that the user doesn't change for comparison purposes but can
 otherwise modify.
 
 A practical matter is that if we introduce this restriction we'll
 break a ton of code.


[...]

Understood. But if the user changes the keys then the AA will
malfunction. (This is no worse than the current behaviour, I suppose.)

So now I've to track down why non-const keys trigger a ton of errors...
:-/


T

-- 
"No, John.  I want formats that are actually useful, rather than over-featured
megaliths that address all questions by piling on ridiculous internal links in
forms which are hideously over-complex." -- Simon St. Laurent on xml-dev
Mar 14 2012
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:


 I think the built-in associative array must allow non-constant 
 keys. As long as there's no memory safety issue, the AA should 
 work with types that the user doesn't change for comparison 
 purposes but can otherwise modify.

 A practical matter is that if we introduce this restriction 
 we'll break a ton of code.


Related to this I have one E.R.:
http://d.puremagic.com/issues/show_bug.cgi?id=6253

Opinions welcome :-)

Bye,
bearophile
Mar 15 2012
prev sibling next sibling parent reply "foobar" <foo bar.com> writes:
On Wednesday, 14 March 2012 at 23:14:42 UTC, H. S. Teoh wrote:

 Alright, I've finished the basic functionality of my AA 
 implementation.
 I still haven't solved that problem with using suffixless string
 literals to index X[dstring], so you'll have to write 
 aa["abc"d] instead
 of just aa["abc"]. But I thought I should post my code now so 
 that
 people can take a look at it:

 	https://github.com/quickfur/New-AA-implementation/blob/master/newAA.d


 T


Thanks for tackling the AA problem.
I have one slight issue / comment regarding AAs: I really dislike 
the idea of cramming everything under the sun into object.d. In 
general, cramming lots'o'code into a single mega file is a code 
smell which Phobos greatly stinks from.
At the very least, object.d can publicly import your newAA.d 
module which gives the exact same outcome while keeping separate 
features separate.
Mar 15 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-03-15 08:59, foobar wrote:

 On Wednesday, 14 March 2012 at 23:14:42 UTC, H. S. Teoh wrote:

 Alright, I've finished the basic functionality of my AA implementation.
 I still haven't solved that problem with using suffixless string
 literals to index X[dstring], so you'll have to write aa["abc"d] instead
 of just aa["abc"]. But I thought I should post my code now so that
 people can take a look at it:

 https://github.com/quickfur/New-AA-implementation/blob/master/newAA.d


 T


 Thanks for tackling the AA problem.
 I have one slight issue / comment regarding AAs: I really dislike the
 idea of cramming everything under the sun into object.d. In general,
 cramming lots'o'code into a single mega file is a code smell which
 Phobos greatly stinks from.
 At the very least, object.d can publicly import your newAA.d module
 which gives the exact same outcome while keeping separate features
 separate.


I think object.d should be empty except for the definition of Object. 
The rest should be located in their own modules and publicly imported in 
object.d

-- 
/Jacob Carlborg
Mar 15 2012
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 Mar 2012 06:19:33 -0400, Jacob Carlborg <doob me.com> wrote:


 On 2012-03-15 08:59, foobar wrote:

 On Wednesday, 14 March 2012 at 23:14:42 UTC, H. S. Teoh wrote:

 Alright, I've finished the basic functionality of my AA implementation.
 I still haven't solved that problem with using suffixless string
 literals to index X[dstring], so you'll have to write aa["abc"d]  
 instead
 of just aa["abc"]. But I thought I should post my code now so that
 people can take a look at it:

 https://github.com/quickfur/New-AA-implementation/blob/master/newAA.d


 T


 Thanks for tackling the AA problem.
 I have one slight issue / comment regarding AAs: I really dislike the
 idea of cramming everything under the sun into object.d. In general,
 cramming lots'o'code into a single mega file is a code smell which
 Phobos greatly stinks from.
 At the very least, object.d can publicly import your newAA.d module
 which gives the exact same outcome while keeping separate features
 separate.


 I think object.d should be empty except for the definition of Object.  
 The rest should be located in their own modules and publicly imported in  
 object.d


I think the compiler would have to change for that to happen.

I would support such a change, but then again, it seems like we'd get  
little measurable benefit for it, making it difficult to get through  
Walter.

-Steve
Mar 15 2012
next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-03-15 11:39, Steven Schveighoffer wrote:

 On Thu, 15 Mar 2012 06:19:33 -0400, Jacob Carlborg <doob me.com> wrote:

 I think object.d should be empty except for the definition of Object.
 The rest should be located in their own modules and publicly imported
 in object.d


 I think the compiler would have to change for that to happen.

 I would support such a change, but then again, it seems like we'd get
 little measurable benefit for it, making it difficult to get through
 Walter.

 -Steve


Why would the compiler need to be changed for that?

-- 
/Jacob Carlborg
Mar 15 2012
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 Mar 2012 06:47:00 -0400, Jacob Carlborg <doob me.com> wrote:


 On 2012-03-15 11:39, Steven Schveighoffer wrote:

 On Thu, 15 Mar 2012 06:19:33 -0400, Jacob Carlborg <doob me.com> wrote:

 I think object.d should be empty except for the definition of Object.
 The rest should be located in their own modules and publicly imported
 in object.d


 I think the compiler would have to change for that to happen.

 I would support such a change, but then again, it seems like we'd get
 little measurable benefit for it, making it difficult to get through
 Walter.

 -Steve


 Why would the compiler need to be changed for that?


Isn't full name of TypeInfo object.TypeInfo?  Is that not hard-coded into  
the compiler?

-Steve
Mar 15 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-03-15 11:52, Steven Schveighoffer wrote:

 Isn't full name of TypeInfo object.TypeInfo? Is that not hard-coded into
 the compiler?

 -Steve


I have no idea if object.TypeInfo is hard-coded into the compiler.

-- 
/Jacob Carlborg
Mar 15 2012
prev sibling parent reply "foobar" <foo bar.com> writes:
On Thursday, 15 March 2012 at 10:39:04 UTC, Steven Schveighoffer 
wrote:

 On Thu, 15 Mar 2012 06:19:33 -0400, Jacob Carlborg

 I think object.d should be empty except for the definition of 
 Object. The rest should be located in their own modules and 
 publicly imported in object.d


 I think the compiler would have to change for that to happen.

 I would support such a change, but then again, it seems like 
 we'd get little measurable benefit for it, making it difficult 
 to get through Walter.

 -Steve


Why would that pose a problem to DMD? object.d is a regular D 
module and D provides a public import feature. If that fails for 
some modules it should be considered a bug in the compiler.

I disagree about the side of the benefit. This gains us 
readability of code which is IMO a MAJOR benefit. It's not just 
the object.d module but a lot of phobos too.
It frustrates me to no end Andrei's refusal to accept a design 
proven to work for half a century (which is already utilized by 
the compiler!) - the File System. Choosing instead to duplicate 
organization features inside DDOC as sections. This is a classic 
example of a code smell.
Mar 15 2012
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/15/12 5:59 PM, foobar wrote:

 It frustrates me to no end Andrei's refusal to accept a design proven to
 work for half a century (which is already utilized by the compiler!) -
 the File System. Choosing instead to duplicate organization features
 inside DDOC as sections. This is a classic example of a code smell.


What, what? What did I do?

Andrei
Mar 15 2012
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, March 15, 2012 21:10:43 Andrei Alexandrescu wrote:

 On 3/15/12 5:59 PM, foobar wrote:

 It frustrates me to no end Andrei's refusal to accept a design proven to
 work for half a century (which is already utilized by the compiler!) -
 the File System. Choosing instead to duplicate organization features
 inside DDOC as sections. This is a classic example of a code smell.


 What, what? What did I do?


Yeah. That comment makes no sense. More context is needed.

- Jonathan M Davis
Mar 15 2012
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2012-03-15 23:59, foobar wrote:

 On Thursday, 15 March 2012 at 10:39:04 UTC, Steven Schveighoffer wrote:



 Why would that pose a problem to DMD? object.d is a regular D module and
 D provides a public import feature. If that fails for some modules it
 should be considered a bug in the compiler.

 I disagree about the side of the benefit. This gains us readability of
 code which is IMO a MAJOR benefit. It's not just the object.d module but
 a lot of phobos too.
 It frustrates me to no end Andrei's refusal to accept a design proven to
 work for half a century (which is already utilized by the compiler!) -
 the File System. Choosing instead to duplicate organization features
 inside DDOC as sections. This is a classic example of a code smell.


I completely agree.

-- 
/Jacob Carlborg
Mar 16 2012
prev sibling parent reply Don Clugston <dac nospam.com> writes:
On 15/03/12 00:16, H. S. Teoh wrote:

 On Tue, Mar 13, 2012 at 09:30:45PM -0500, Andrei Alexandrescu wrote:

 On 3/13/12 7:54 PM, H. S. Teoh wrote:

 Hi all,

 My AA implementation is slowly inching closer to being ready to
 replace aaA.d.


 Great! This will need compiler restructuring, and in fact offers the
 perfect opportunity for it. I suggest you to post your implementation
 here for review first, and assume only the minimal lowerings from the
 compiler.


 Alright, I've finished the basic functionality of my AA implementation.
 I still haven't solved that problem with using suffixless string
 literals to index X[dstring], so you'll have to write aa["abc"d] instead
 of just aa["abc"]. But I thought I should post my code now so that
 people can take a look at it:

 	https://github.com/quickfur/New-AA-implementation/blob/master/newAA.d

 Currently, this code is still standalone, not integrated with druntime
 yet.  Since that will require compiler changes and is potentially a very
 big change, I've decided to polish up the standalone version as much as
 possible before attempting druntime integration.


This is good, and very, very important. Do *not* make any attempt at 
compiler integration until it is *completely* ready.

This includes AA literals. They need to be accepted somehow. The 
compiler will give you syntax sugar and *nothing* more.
One possibility might be to accept a pair of array literals, 
representing keys and values.
Possibly it should call a CTFE function to convert them into some other 
form?
Mar 15 2012
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/15/12 11:02 AM, Don Clugston wrote:

 This is good, and very, very important. Do *not* make any attempt at
 compiler integration until it is *completely* ready.

 This includes AA literals. They need to be accepted somehow. The
 compiler will give you syntax sugar and *nothing* more.
 One possibility might be to accept a pair of array literals,
 representing keys and values.
 Possibly it should call a CTFE function to convert them into some other
 form?


Offhand, I think this rewrite should be sufficient:

[e11:e12, e21:e22]

--->

.object.associativeArrayLiteral(e11, e12, e21, e22)

Then type manipulation and template constraints can take care of the 
rest. Am I missing something?


Andrei
Mar 15 2012
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 Mar 2012 12:05:46 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 On 3/15/12 11:02 AM, Don Clugston wrote:

 This is good, and very, very important. Do *not* make any attempt at
 compiler integration until it is *completely* ready.

 This includes AA literals. They need to be accepted somehow. The
 compiler will give you syntax sugar and *nothing* more.
 One possibility might be to accept a pair of array literals,
 representing keys and values.
 Possibly it should call a CTFE function to convert them into some other
 form?


 Offhand, I think this rewrite should be sufficient:

 [e11:e12, e21:e22]

 --->

 .object.associativeArrayLiteral(e11, e12, e21, e22)

 Then type manipulation and template constraints can take care of the  
 rest. Am I missing something?


Wouldn't this require a new template instantiation for each sized AA per  
key/value type?  Or were you planning to use varargs?

So long as the data that is actually passed to the AA is on the stack (and  
simply a slice is passed), I like Don's idea better.

-Steve
Mar 15 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/15/12 12:12 PM, Steven Schveighoffer wrote:

 On Thu, 15 Mar 2012 12:05:46 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 On 3/15/12 11:02 AM, Don Clugston wrote:

 This is good, and very, very important. Do *not* make any attempt at
 compiler integration until it is *completely* ready.

 This includes AA literals. They need to be accepted somehow. The
 compiler will give you syntax sugar and *nothing* more.
 One possibility might be to accept a pair of array literals,
 representing keys and values.
 Possibly it should call a CTFE function to convert them into some other
 form?


 Offhand, I think this rewrite should be sufficient:

 [e11:e12, e21:e22]

 --->

 .object.associativeArrayLiteral(e11, e12, e21, e22)

 Then type manipulation and template constraints can take care of the
 rest. Am I missing something?


 Wouldn't this require a new template instantiation for each sized AA per
 key/value type? Or were you planning to use varargs?


Template function takes over, does whatever is necessary, such as 
possibly conversion to varargs.


 So long as the data that is actually passed to the AA is on the stack
 (and simply a slice is passed), I like Don's idea better.


What would that look like?



Andrei
Mar 15 2012
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 Mar 2012 13:24:24 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 On 3/15/12 12:12 PM, Steven Schveighoffer wrote:

 On Thu, 15 Mar 2012 12:05:46 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 On 3/15/12 11:02 AM, Don Clugston wrote:

 This is good, and very, very important. Do *not* make any attempt at
 compiler integration until it is *completely* ready.

 This includes AA literals. They need to be accepted somehow. The
 compiler will give you syntax sugar and *nothing* more.
 One possibility might be to accept a pair of array literals,
 representing keys and values.
 Possibly it should call a CTFE function to convert them into some  
 other
 form?


 Offhand, I think this rewrite should be sufficient:

 [e11:e12, e21:e22]

 --->

 .object.associativeArrayLiteral(e11, e12, e21, e22)

 Then type manipulation and template constraints can take care of the
 rest. Am I missing something?


 Wouldn't this require a new template instantiation for each sized AA per
 key/value type? Or were you planning to use varargs?


 Template function takes over, does whatever is necessary, such as  
 possibly conversion to varargs.


Right, but with a template:

[1:1]
[1:1, 2:2]

become two separate template instantiations, but with something that just  
takes two arrays, it's only one template, no matter how many elements you  
are initializing with.


 So long as the data that is actually passed to the AA is on the stack
 (and simply a slice is passed), I like Don's idea better.


 What would that look like?


auto aa = [1:1];

  becomes:

int[1] __k = [1]; // obviously, no heap allocation should happen here,  
that needs fixing in the compiler
int[1] __v = [1];
auto aa = AssociativeArray!(int, int)(__k, __v); // same instantiation, no  
matter how many elements are in literal.

-Steve
Mar 15 2012
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 Mar 2012 13:39:19 -0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:


 On Thu, 15 Mar 2012 13:24:24 -0400, Andrei Alexandrescu  
 <SeeWebsiteForEmail erdani.org> wrote:

 What would that look like?


 auto aa = [1:1];

   becomes:

 int[1] __k = [1]; // obviously, no heap allocation should happen here,  
 that needs fixing in the compiler
 int[1] __v = [1];
 auto aa = AssociativeArray!(int, int)(__k, __v); // same instantiation,  
 no matter how many elements are in literal.


Sorry, that should really be:

auto aa = AssociativeArray!(int, int)(__k[], __v[]);

-Steve
Mar 15 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/15/12 12:39 PM, Steven Schveighoffer wrote:

 On Thu, 15 Mar 2012 13:24:24 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 Template function takes over, does whatever is necessary, such as
 possibly conversion to varargs.


 Right, but with a template:

 [1:1]
 [1:1, 2:2]

 become two separate template instantiations, but with something that
 just takes two arrays, it's only one template, no matter how many
 elements you are initializing with.


I guess I should ask this then: why is instantiating a template function 
a problem?


 So long as the data that is actually passed to the AA is on the stack
 (and simply a slice is passed), I like Don's idea better.


 What would that look like?


 auto aa = [1:1];

 becomes:

 int[1] __k = [1]; // obviously, no heap allocation should happen here,
 that needs fixing in the compiler
 int[1] __v = [1];
 auto aa = AssociativeArray!(int, int)(__k, __v); // same instantiation,
 no matter how many elements are in literal.


That should work, too. Use braces to not require a fix:

int[1] __k = {1};
int[1] __v = {1};
auto aa = AssociativeArray!(int, int)(__k, __v);

Off the top of my head it changes the order of evaluation in the general 
case (or complicates code generation if left-to-right preservation is 
needed). Also the constructor needs to be  trusted because references to 
static arrays can't escape in safe code. All workable matters, but 
generally I prefer migrating cleverness from code generation into 
library code.


Andrei
Mar 15 2012
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 Mar 2012 14:11:11 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 On 3/15/12 12:39 PM, Steven Schveighoffer wrote:

 On Thu, 15 Mar 2012 13:24:24 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 Template function takes over, does whatever is necessary, such as
 possibly conversion to varargs.


 Right, but with a template:

 [1:1]
 [1:1, 2:2]

 become two separate template instantiations, but with something that
 just takes two arrays, it's only one template, no matter how many
 elements you are initializing with.


 I guess I should ask this then: why is instantiating a template function  
 a problem?


1. non-inlined functions (dmd doesn't inline by default) result in extra  
calls.
2. I think even if it's inlined, dmd generates a function and sticks it in  
the object file, which will never be called. (bloat).  I'm not sure if  
anything else is put into the binary, or if the function is optimized out  
on linking.


 Off the top of my head it changes the order of evaluation in the general  
 case (or complicates code generation if left-to-right preservation is  
 needed). Also the constructor needs to be  trusted because references to  
 static arrays can't escape in safe code. All workable matters, but  
 generally I prefer migrating cleverness from code generation into  
 library code.


All good points.  One thing to be sure, given the fact that this is one  
hook implemented in one location, it should be easy to fix later if we use  
a bad approach.

Perhaps the best way to address my concerns are to fix how unused  
templates are included in the binary.  I could also be wrong about that.

-Steve
Mar 15 2012
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Mar 15, 2012 at 05:02:06PM +0100, Don Clugston wrote:

 On 15/03/12 00:16, H. S. Teoh wrote:


[...]

 This is good, and very, very important. Do *not* make any attempt at
 compiler integration until it is *completely* ready.
 
 This includes AA literals. They need to be accepted somehow. The
 compiler will give you syntax sugar and *nothing* more.


How does the compiler currently work with AA literals? I see two
functions in aaA.d for constructing AA's from literals. Which one is the
one actually being used?



 One possibility might be to accept a pair of array literals,
 representing keys and values.


OK. This shouldn't be hard to do. I'll take a stab at it.



 Possibly it should call a CTFE function to convert them into some
 other form?


This is one major area that I forgot to mention, and that is, making AA
literals work at compile-time. Currently things like this don't work:

	enum myAA = ["abc":123, "def":456];

I'd like to make that work. That would require compile-time construction
of the AA and storing it in some form that the compiler can put into the
object file. I'm thinking of something along the lines of using mixins
to generate explicit instances of Slot structs, so the above would
translate to something like:

	Impl __myAA_literal_impl = Impl(__myAA_literal_slots[0..$], 2);
	Slot[4] __myAA_literal_slots = [
		// The exact order in here will depend on precise hash
		// values, which will need to be somehow computed by
		// CTFE. Is that even remotely possible right now??
		null,
		&__myAA_literal_slot1,
		null,
		&__myAA_literal_slot2
	];
	Slot __myAA_literal_slot1 = Slot(null, /*hash value*/, "abc", 123);
	Slot __myAA_literal_slot2 = Slot(null, /*hash value*/, "def", 456);
	enum myAA = AssociativeArray!(string,int)(&__myAA_literal_impl);

Would something like this be workable? Is it even possible to compute
the necessary hashes at compile-time?


T

-- 
Never step over a puddle, always step around it. Chances are that whatever made
it is still dripping.
Mar 15 2012
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 15.03.2012 21:22, H. S. Teoh wrote:

 On Thu, Mar 15, 2012 at 05:02:06PM +0100, Don Clugston wrote:

 On 15/03/12 00:16, H. S. Teoh wrote:


 [...]

 This is good, and very, very important. Do *not* make any attempt at
 compiler integration until it is *completely* ready.

 This includes AA literals. They need to be accepted somehow. The
 compiler will give you syntax sugar and *nothing* more.


 How does the compiler currently work with AA literals? I see two
 functions in aaA.d for constructing AA's from literals. Which one is the
 one actually being used?



 One possibility might be to accept a pair of array literals,
 representing keys and values.


 OK. This shouldn't be hard to do. I'll take a stab at it.



 Possibly it should call a CTFE function to convert them into some
 other form?


 This is one major area that I forgot to mention, and that is, making AA
 literals work at compile-time. Currently things like this don't work:

 	enum myAA = ["abc":123, "def":456];

 I'd like to make that work. That would require compile-time construction
 of the AA and storing it in some form that the compiler can put into the
 object file.


What's wrong with AA structure itself, it's link-pointer based?
At any rate, I stored complex structs as immutable, though links were 
index-based.

I'm thinking of something along the lines of using mixins

 to generate explicit instances of Slot structs, so the above would
 translate to something like:

 	Impl __myAA_literal_impl = Impl(__myAA_literal_slots[0..$], 2);
 	Slot[4] __myAA_literal_slots = [
 		// The exact order in here will depend on precise hash
 		// values, which will need to be somehow computed by
 		// CTFE. Is that even remotely possible right now??
 		null,
 		&__myAA_literal_slot1,
 		null,
 		&__myAA_literal_slot2
 	];
 	Slot __myAA_literal_slot1 = Slot(null, /*hash value*/, "abc", 123);
 	Slot __myAA_literal_slot2 = Slot(null, /*hash value*/, "def", 456);
 	enum myAA = AssociativeArray!(string,int)(&__myAA_literal_impl);

 Would something like this be workable? Is it even possible to compute
 the necessary hashes at compile-time?


 T



-- 
Dmitry Olshansky
Mar 15 2012
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Mar 15, 2012 at 11:50:47PM +0400, Dmitry Olshansky wrote:
[...]

This is one major area that I forgot to mention, and that is, making
AA literals work at compile-time. Currently things like this don't
work:

	enum myAA = ["abc":123, "def":456];

I'd like to make that work. That would require compile-time
construction of the AA and storing it in some form that the compiler
can put into the object file.


 
 What's wrong with AA structure itself, it's link-pointer based?  At
 any rate, I stored complex structs as immutable, though links were
 index-based.


Yes, that's what I had in mind.

In fact, I've starting testing a statically-declared AA (written by hand
for now), that uses the same structures as heap-allocated AA's. The
basic stuff (declaring Slots statically, linking them together, etc.)
works, and in principle can be generated by mixins at compile-time to
give us "true" compile-time AA literals (as in, the AA struct is
computed at compile-time and stored in the static data segment in the
object file). This can be used for implementing immutable AA's at
compile-time (and maybe also "fast" initialization of AA literals which
can be .dup'd at runtime into mutable AA's when needed).

However, I've run into a major roadblock: the hash computation of the
keys itself. Unfortunately, currently there's no (reliable) way to
compute the hash of built-in types unless you use its TypeInfo, and
TypeInfo's are currently not CTFE-accessible, so hash values cannot be
computed at compile-time. :-(


T

-- 
He who laughs last thinks slowest.
Mar 15 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Mar 15, 2012 at 10:22:06AM -0700, H. S. Teoh wrote:
[...]

 This is one major area that I forgot to mention, and that is, making AA
 literals work at compile-time. Currently things like this don't work:
 
 	enum myAA = ["abc":123, "def":456];
 
 I'd like to make that work. That would require compile-time construction
 of the AA and storing it in some form that the compiler can put into the
 object file. I'm thinking of something along the lines of using mixins
 to generate explicit instances of Slot structs, so the above would
 translate to something like:


[...]

Hmm. I just did a little test to see how feasible this is, and I create
the AA Slots and array of pointers to slots fine, but hashOf() doesn't
work in CTFE:

/usr/src/d/druntime/src/rt/util/hash.d(38): Error: reinterpreting cast from
const(ubyte)* to ushort* is not supported in CTFE
/usr/src/d/druntime/src/rt/util/hash.d(72):        called from here:
get16bits(data)

Should I submit a pull request for a __ctfe variant of hashOf so that it
can be used for this purpose? Any gotchas I should be aware of?


T

-- 
"I'm running Windows '98."
"Yes."
"My computer isn't working now."
"Yes, you already said that."
-- User-Friendly
Mar 15 2012
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Mar 15, 2012 at 05:02:06PM +0100, Don Clugston wrote:
[...]

 This is good, and very, very important. Do *not* make any attempt at
 compiler integration until it is *completely* ready.
 
 This includes AA literals. They need to be accepted somehow. The
 compiler will give you syntax sugar and *nothing* more.
 One possibility might be to accept a pair of array literals,
 representing keys and values.


Alright, I've made a preliminary implementation of AA literals as a
function that constructs an AA given an array of keys and and an array
of values (just like the current aaA.d implementation).  The changes
have been pushed to github:

	https://github.com/quickfur/New-AA-implementation/commit/c272909626f09829f333467499996250c2a1e8d2

Currently this function is a static member; I'm thinking maybe it might
be better to make it an external template function instead. That way, we
only need the compiler to do array type inference for the input arrays,
and the function will use the inferred types to determine the AA
key/value types.



 Possibly it should call a CTFE function to convert them into some
 other form?


I do intend to do more with AA literals, including making them
compileable into object code directly (using static struct instances and
mixins), but that will be more involved, and will require implementing
toHash() for all native types using UFCS, that I proposed in another
thread. A quick hand-crafted test earlier today showed that it *can* be
done; it's just a matter of getting the various pieces in place.


T

-- 
Curiosity kills the cat. Moral: don't be the cat.
Mar 15 2012
parent reply bearophile <bearophileHUGS lycos.com> writes:
H. S. Teoh:


 Alright, I've made a preliminary implementation of AA literals as a
 function that constructs an AA given an array of keys and and an array
 of values (just like the current aaA.d implementation).


See also:
http://d.puremagic.com/issues/show_bug.cgi?id=5502
http://d.puremagic.com/issues/show_bug.cgi?id=5466

Bye,
bearophile
Mar 16 2012
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Mar 16, 2012 at 08:25:08AM -0400, bearophile wrote:

 H. S. Teoh:
 

 Alright, I've made a preliminary implementation of AA literals as a
 function that constructs an AA given an array of keys and and an array
 of values (just like the current aaA.d implementation).


 
 See also:
 http://d.puremagic.com/issues/show_bug.cgi?id=5502
 http://d.puremagic.com/issues/show_bug.cgi?id=5466


[...]

I took a look at these issues, but they seem tricky to implement in
druntime because they depend on phobos features. So probably
constructing an AA from zip() should be in phobos; the current AA
methods should be already be good enough for implementing this.

For iterating AA's as key/value pairs, though, I'll have to think about
how to do it in a nice way. Internally, there's already a Range struct
that iterates by Slot (which amounts to the same thing as iterating by
pairs), so it's just a matter of exposing this in the right way to the
phobos code that will implement by-pair iteration.


T

-- 
This is a tpyo.
Mar 16 2012
prev sibling parent reply "Jakob Bornecrantz" <wallbraker gmail.com> writes:
On Wednesday, 14 March 2012 at 00:52:32 UTC, H. S. Teoh wrote:

 Hi all,

 My AA implementation is slowly inching closer to being ready to 
 replace aaA.d. So far I've been writing the implementation
 outside of object_.d for ease of testing & development; now I'm
 ready to start moving stuff into object_.d to start working on
 integration with druntime.


Hi,

If I'm understanding this correctly you are moving the entire
implementation of the AA into object.d and as such letting
programs be purview to its inner working? In sort meaning you
are making the entire AA implementation D ABI locked.

This will make it impossible to either change the AA
implementation in any ABI breaking fashion or make it impossible
to pass AA's between libraries compiled against different
versions of druntime.

Is this what we really want?

Cheers, Jakob.
Mar 13 2012
next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 14.03.2012 6:39, Jakob Bornecrantz wrote:

 On Wednesday, 14 March 2012 at 00:52:32 UTC, H. S. Teoh wrote:

 Hi all,

 My AA implementation is slowly inching closer to being ready to
 replace aaA.d. So far I've been writing the implementation
 outside of object_.d for ease of testing & development; now I'm
 ready to start moving stuff into object_.d to start working on
 integration with druntime.


 Hi,

 If I'm understanding this correctly you are moving the entire
 implementation of the AA into object.d and as such letting
 programs be purview to its inner working? In sort meaning you
 are making the entire AA implementation D ABI locked.

 This will make it impossible to either change the AA
 implementation in any ABI breaking fashion or make it impossible
 to pass AA's between libraries compiled against different
 versions of druntime.


I will just point out that the major point of ABI is to make sure 
different D compiler produce compatible object code. Thus it makes AA 
implementation locked already anyway, right?


 Is this what we really want?

 Cheers, Jakob.



-- 
Dmitry Olshansky
Mar 14 2012
parent reply "Jakob Bornecrantz" <wallbraker gmail.com> writes:
On Wednesday, 14 March 2012 at 09:07:40 UTC, Dmitry Olshansky 
wrote:

 On 14.03.2012 6:39, Jakob Bornecrantz wrote:

 On Wednesday, 14 March 2012 at 00:52:32 UTC, H. S. Teoh wrote:

 Hi all,

 My AA implementation is slowly inching closer to being ready 
 to
 replace aaA.d. So far I've been writing the implementation
 outside of object_.d for ease of testing & development; now 
 I'm
 ready to start moving stuff into object_.d to start working on
 integration with druntime.


 Hi,

 If I'm understanding this correctly you are moving the entire
 implementation of the AA into object.d and as such letting
 programs be purview to its inner working? In sort meaning you
 are making the entire AA implementation D ABI locked.

 This will make it impossible to either change the AA
 implementation in any ABI breaking fashion or make it 
 impossible
 to pass AA's between libraries compiled against different
 versions of druntime.


 I will just point out that the major point of ABI is to make 
 sure different D compiler produce compatible object code. Thus 
 it makes AA implementation locked already anyway, right?


Not true, as Steven said a opaque pImpl implementation would
work, most modern C library design follow this principle with
only using opaque except for pointers. This is because the ABI
will then only require you call a certain set of functions (that
can be extended to) not what that pointers points to, the
details can be completely hidden.

Cheers, Jakob.
Mar 14 2012
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 15.03.2012 2:44, Jakob Bornecrantz wrote:

 On Wednesday, 14 March 2012 at 09:07:40 UTC, Dmitry Olshansky wrote:

 On 14.03.2012 6:39, Jakob Bornecrantz wrote:

 On Wednesday, 14 March 2012 at 00:52:32 UTC, H. S. Teoh wrote:

 Hi all,

 My AA implementation is slowly inching closer to being ready to
 replace aaA.d. So far I've been writing the implementation
 outside of object_.d for ease of testing & development; now I'm
 ready to start moving stuff into object_.d to start working on
 integration with druntime.


 Hi,

 If I'm understanding this correctly you are moving the entire
 implementation of the AA into object.d and as such letting
 programs be purview to its inner working? In sort meaning you
 are making the entire AA implementation D ABI locked.

 This will make it impossible to either change the AA
 implementation in any ABI breaking fashion or make it impossible
 to pass AA's between libraries compiled against different
 versions of druntime.


 I will just point out that the major point of ABI is to make sure
 different D compiler produce compatible object code. Thus it makes AA
 implementation locked already anyway, right?


 Not true, as Steven said a opaque pImpl implementation would
 work, most modern C library design follow this principle with
 only using opaque except for pointers. This is because the ABI
 will then only require you call a certain set of functions (that
 can be extended to) not what that pointers points to, the
 details can be completely hidden.


Trouble is when one dynamic lib uses one version of druntime and AA, and 
your app another one. Guess what happens with this opaque pointer?


-- 
Dmitry Olshansky
Mar 15 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 03/15/2012 09:40 AM, Dmitry Olshansky wrote:

 On 15.03.2012 2:44, Jakob Bornecrantz wrote:

 Not true, as Steven said a opaque pImpl implementation would
 work, most modern C library design follow this principle with
 only using opaque except for pointers. This is because the ABI
 will then only require you call a certain set of functions (that
 can be extended to) not what that pointers points to, the
 details can be completely hidden.


 Trouble is when one dynamic lib uses one version of druntime and AA, and
 your app another one. Guess what happens with this opaque pointer?


AA should probably be a class with virtual methods.
Mar 15 2012
next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 15.03.2012 12:52, Timon Gehr wrote:

 On 03/15/2012 09:40 AM, Dmitry Olshansky wrote:

 On 15.03.2012 2:44, Jakob Bornecrantz wrote:

 Not true, as Steven said a opaque pImpl implementation would
 work, most modern C library design follow this principle with
 only using opaque except for pointers. This is because the ABI
 will then only require you call a certain set of functions (that
 can be extended to) not what that pointers points to, the
 details can be completely hidden.


 Trouble is when one dynamic lib uses one version of druntime and AA, and
 your app another one. Guess what happens with this opaque pointer?


 AA should probably be a class with virtual methods.


If its V-table layout is consistent and fixed in say ABI spec, it could 
work.

-- 
Dmitry Olshansky
Mar 15 2012
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 Mar 2012 04:52:41 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:


 On 03/15/2012 09:40 AM, Dmitry Olshansky wrote:

 On 15.03.2012 2:44, Jakob Bornecrantz wrote:

 Not true, as Steven said a opaque pImpl implementation would
 work, most modern C library design follow this principle with
 only using opaque except for pointers. This is because the ABI
 will then only require you call a certain set of functions (that
 can be extended to) not what that pointers points to, the
 details can be completely hidden.


 Trouble is when one dynamic lib uses one version of druntime and AA, and
 your app another one. Guess what happens with this opaque pointer?


 AA should probably be a class with virtual methods.


First, that only works if the vtable layout doesn't change (I've had more  
trouble with binary compatibility because of this vs. binary compatibility  
 from different function implementations in C++).

Second, that breaks a *LOT* of code which expects AA's to just be declared  
and used.

-Steve
Mar 15 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 03/15/2012 11:41 AM, Steven Schveighoffer wrote:

 Second, that breaks a *LOT* of code which expects AA's to just be
 declared and used.


Not necessarily. The compiler could still do the auto-initialization.
Mar 15 2012
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 Mar 2012 13:28:00 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:


 On 03/15/2012 11:41 AM, Steven Schveighoffer wrote:

 Second, that breaks a *LOT* of code which expects AA's to just be
 declared and used.


 Not necessarily. The compiler could still do the auto-initialization.


Auto initialization is done by the type, not the compiler (even in  
previous implementation that did not use template wrapper).  AFAIK,  
classes can't initialize themselves.

You could make the pImpl a class.  And actually, this might be a good  
thing.  But the basic AA type should be a struct.

-Steve
Mar 15 2012
prev sibling next sibling parent reply Don Clugston <dac nospam.com> writes:
On 14/03/12 03:39, Jakob Bornecrantz wrote:

 On Wednesday, 14 March 2012 at 00:52:32 UTC, H. S. Teoh wrote:

 Hi all,

 My AA implementation is slowly inching closer to being ready to
 replace aaA.d. So far I've been writing the implementation
 outside of object_.d for ease of testing & development; now I'm
 ready to start moving stuff into object_.d to start working on
 integration with druntime.


 Hi,

 If I'm understanding this correctly you are moving the entire
 implementation of the AA into object.d and as such letting
 programs be purview to its inner working? In sort meaning you
 are making the entire AA implementation D ABI locked.

 This will make it impossible to either change the AA
 implementation in any ABI breaking fashion or make it impossible
 to pass AA's between libraries compiled against different
 versions of druntime.


Much less so than the existing AA implementation.
Mar 14 2012
parent "Jakob Bornecrantz" <wallbraker gmail.com> writes:
On Wednesday, 14 March 2012 at 13:55:23 UTC, Don Clugston wrote:

 On 14/03/12 03:39, Jakob Bornecrantz wrote:

 On Wednesday, 14 March 2012 at 00:52:32 UTC, H. S. Teoh wrote:

 Hi all,

 My AA implementation is slowly inching closer to being ready 
 to
 replace aaA.d. So far I've been writing the implementation
 outside of object_.d for ease of testing & development; now 
 I'm
 ready to start moving stuff into object_.d to start working on
 integration with druntime.


 Hi,

 If I'm understanding this correctly you are moving the entire
 implementation of the AA into object.d and as such letting
 programs be purview to its inner working? In sort meaning you
 are making the entire AA implementation D ABI locked.

 This will make it impossible to either change the AA
 implementation in any ABI breaking fashion or make it 
 impossible
 to pass AA's between libraries compiled against different
 versions of druntime.


 Much less so than the existing AA implementation.


In what way moving the entire implementation into templates
that gets compiled into the object code of all the uses, got
to be worse (for ABI) then having the implementation separate?

I think you are not seeing the implementation off calling
into the opaque implementation as two separate things. Yes the
current implementation off calling into is bad and should be
replaced.

Ponder this for example:

struct AA(K, V)
{
   void *ptr;

   void init() { ptr = rt_aaInit(typeinfo!K, typeinfo!V; }

   static if (isData!K)
      void add(K k, V ref v) { rt_aaAddData(ptr, cast(ulong)k, v); 
}
   else static if (isPointer!K)
      void add(K k, V ref v) { rt_aaAddPointerWithHash(ptr, k, 
toHash!K(k), v); }
   else
      void add(K ref k, V ref v) { rt_aaAdd(ptr, k, v); }
}

Adding to this implementation wouldn't require changing DMD
at all only _object.d and the aa implementation in druntime.

The use of the AA struct isn't required by the ABI, only
that functions gets called for doing things to a AA.


Cheers, Jakob.
Mar 14 2012
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 13 Mar 2012 22:39:25 -0400, Jakob Bornecrantz  
<wallbraker gmail.com> wrote:


 On Wednesday, 14 March 2012 at 00:52:32 UTC, H. S. Teoh wrote:

 Hi all,

 My AA implementation is slowly inching closer to being ready to replace  
 aaA.d. So far I've been writing the implementation
 outside of object_.d for ease of testing & development; now I'm
 ready to start moving stuff into object_.d to start working on
 integration with druntime.


 Hi,

 If I'm understanding this correctly you are moving the entire
 implementation of the AA into object.d and as such letting
 programs be purview to its inner working? In sort meaning you
 are making the entire AA implementation D ABI locked.

 This will make it impossible to either change the AA
 implementation in any ABI breaking fashion or make it impossible
 to pass AA's between libraries compiled against different
 versions of druntime.

 Is this what we really want?


This is unavoidable, whether it's a template or not.  What changes do you  
envision would be transparent using an opaque pImpl model (as was done in  
previous versions of phobos), but would break using templates?

-Steve
Mar 14 2012
parent reply "Jakob Bornecrantz" <wallbraker gmail.com> writes:
On Wednesday, 14 March 2012 at 14:02:30 UTC, Steven Schveighoffer 
wrote:

 On Tue, 13 Mar 2012 22:39:25 -0400, Jakob Bornecrantz 
 <wallbraker gmail.com> wrote:


 On Wednesday, 14 March 2012 at 00:52:32 UTC, H. S. Teoh wrote:

 Hi all,

 My AA implementation is slowly inching closer to being ready 
 to replace aaA.d. So far I've been writing the implementation
 outside of object_.d for ease of testing & development; now 
 I'm
 ready to start moving stuff into object_.d to start working on
 integration with druntime.


 Hi,

 If I'm understanding this correctly you are moving the entire
 implementation of the AA into object.d and as such letting
 programs be purview to its inner working? In sort meaning you
 are making the entire AA implementation D ABI locked.

 This will make it impossible to either change the AA
 implementation in any ABI breaking fashion or make it 
 impossible
 to pass AA's between libraries compiled against different
 versions of druntime.

 Is this what we really want?


 This is unavoidable, whether it's a template or not.  What 
 changes do you envision would be transparent using an opaque 
 pImpl model (as was done in previous versions of phobos), but 
 would break using templates?


struct AAver1(K, V)
{
    K[] tbl; V[] tlb2; uint size;
}

struct AAver2(K, V)
{
    K[] tbl; V[] tbl2; V[] optimizationTbl;
}

Would break if a AAver1 table was ever passed to code that
was compiled against a AAver2 table. In sort you could never
add anything to the AA struct. Without going in roundabout
ways of making sure you never access outside of any struct
version ever out there.

Or for that matter change how the internal tables are
populated by add and remove.

Cheers, Jakob.
Mar 14 2012
next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Mar 15, 2012 at 12:20:43AM +0100, Jakob Bornecrantz wrote:
[...]

 struct AAver1(K, V)
 {
    K[] tbl; V[] tlb2; uint size;
 }
 
 struct AAver2(K, V)
 {
    K[] tbl; V[] tbl2; V[] optimizationTbl;
 }
 
 Would break if a AAver1 table was ever passed to code that
 was compiled against a AAver2 table. In sort you could never
 add anything to the AA struct. Without going in roundabout
 ways of making sure you never access outside of any struct
 version ever out there.
 
 Or for that matter change how the internal tables are
 populated by add and remove.


[...]

How is this different from any other templates in druntime/phobos?

And FYI, the current AA implementation *already* suffers from this
problem, because the Range interface already assumes a specific
implementation behind the opaque pImpl pointer (see object_.d -- it
*duplicates* the struct definitions from aaA.d and casts the void* into
pointers to those structs). If aaA.d were to change its implementation
today, the Range stuff in struct AssociativeArray would break horribly.

The motivation behind my rewriting AA's is to fix this schizophrenic
mess. The internal aaA.d structs should *not* be duplicated in
object_.d, but currently they are. So there are two options, either (1)
we move everything back into aaA.d (and introduce a whole bunch more
void* pImpl and C-linkage functions for the structs that Range support
requires), or (2) we move everything out of aaA.d.

Personally, I feel the second option is better. If we want to improve or
add to AA's API, we can just change it in object_.d. Key and value types
are directly accessible, so we never have to play around with typeinfos
and pointer arithmetic to do simple stuff.

If we go with the first option, every little change will require changes
to aaA.d, and trying to add new functionality will constantly introduce
new C-linkage functions in aaA.d, new void* pImpl's in object_.d, with
the associated hacks using typeinfos (because Key/Value types are
essentially opaque to aaA.d, so you have to rely on typeinfos and
pointer arithmetic instead of letting the compiler figure it out for
you). This is very hard to maintain, and much more bug-prone.


T

-- 
"I suspect the best way to deal with procrastination is to put off the
procrastination itself until later. I've been meaning to try this, but haven't
gotten around to it yet. " -- swr
Mar 14 2012
parent "Jakob Bornecrantz" <wallbraker gmail.com> writes:
On Wednesday, 14 March 2012 at 23:51:30 UTC, H. S. Teoh wrote:

 On Thu, Mar 15, 2012 at 12:20:43AM +0100, Jakob Bornecrantz 
 wrote:
 [...]

 struct AAver1(K, V)
 {
    K[] tbl; V[] tlb2; uint size;
 }
 
 struct AAver2(K, V)
 {
    K[] tbl; V[] tbl2; V[] optimizationTbl;
 }
 
 Would break if a AAver1 table was ever passed to code that
 was compiled against a AAver2 table. In sort you could never
 add anything to the AA struct. Without going in roundabout
 ways of making sure you never access outside of any struct
 version ever out there.
 
 Or for that matter change how the internal tables are
 populated by add and remove.


 [...]

 How is this different from any other templates in 
 druntime/phobos?


Its not, I at least like to see it being possible to keep a
stable ABI in druntime, and as such making it possible to
share inbuilt language features like AA across libraries,
phobos is a lost cause.


 And FYI, the current AA implementation *already* suffers
 from this problem, because the Range interface already
 assumes a specific implementation behind the opaque pImpl
 pointer (see object_.d -- it *duplicates* the struct
 definitions from aaA.d and casts the void* into pointers to
 those structs). If aaA.d were to change its implementation
 today, the Range stuff in struct AssociativeArray would break 
 horribly.

 The motivation behind my rewriting AA's is to fix this 
 schizophrenic mess. The internal aaA.d structs should *not*
 be duplicated in object_.d, but currently they are. So there
 are two options, either (1) we move everything back into aaA.d
 (and introduce a whole bunch more void* pImpl and C-linkage
 functions for the structs that Range support requires), or
 (2) we move everything out of aaA.d.


Yes that is bad, I of course would like to see (2). I don't
feel that just because I wasn't around to hit people over
the head when this was introduced as reason for losing the
ability of D libraries, or making it even harder for people
to do them.


 Personally, I feel the second option is better. If we want
 to improve or add to AA's API, we can just change it in
 object_.d. Key and value types are directly accessible, so
 we never have to play around with typeinfos and pointer
 arithmetic to do simple stuff.

 If we go with the first option, every little change will
 require changes to aaA.d, and trying to add new functionality
 will constantly introduce new C-linkage functions in aaA.d,
 new void* pImpl's in object_.d, with the associated hacks
 using typeinfos (because Key/Value types are essentially
 opaque to aaA.d, so you have to rely on typeinfos and pointer
 arithmetic instead of letting the compiler figure it out for
 you). This is very hard to maintain, and much more bug-prone.


I'm assuming you mean "changes to aaA.d and _object.d".

I'm glad you listed cons of doing it as a opaque pointer,
I don't agree completely that it will be that much more
difficult to maintain or be that much more buggy.

Yes the current one of doing it in DMD, _object.d and in
druntime is bad and can be improved. Did you see my response
to Don? What do you think of that?

Yes there will be a cost to doing it the second way, but
we as a language provider are taking that cost so that
our users don't have to take it via being locked to the
exact same druntime/compiler version between libraries.

Yes doing a stable ABI isn't easy and free, so I think we
need to weigh the pros and cons of supporting language
level primitives easily (for users) across library
boundaries. I think we should just htfu[1] and provide
this feature.

I just wanted to make sure people understand what they are
loosing and what this means. And that they should't have
any illusions of things just magically working. I don't see
me changing my view on thism I want this feature, if I don't
get sure I'll be sad and D will be less attractive to me but
it isn't the end of the world. I want to thank you again for
taking the time to explain everything to me and taking the
time to respond.


What I really want to get to is: Do we really want to do this?


Cheers, Jakob.

[1] http://www.youtube.com/watch?v=unkIVvjZc9Y
Mar 14 2012
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 14 Mar 2012 19:20:43 -0400, Jakob Bornecrantz  
<wallbraker gmail.com> wrote:


 On Wednesday, 14 March 2012 at 14:02:30 UTC, Steven Schveighoffer wrote:

 This is unavoidable, whether it's a template or not.  What changes do  
 you envision would be transparent using an opaque pImpl model (as was  
 done in previous versions of phobos), but would break using templates?


 struct AAver1(K, V)
 {
     K[] tbl; V[] tlb2; uint size;
 }

 struct AAver2(K, V)
 {
     K[] tbl; V[] tbl2; V[] optimizationTbl;
 }

 Would break if a AAver1 table was ever passed to code that
 was compiled against a AAver2 table. In sort you could never
 add anything to the AA struct. Without going in roundabout
 ways of making sure you never access outside of any struct
 version ever out there.

 Or for that matter change how the internal tables are
 populated by add and remove.


So you are expecting druntime to be a .so/dll then.  When that happens, we  
can worry about this.  But right now, each dll gets it's own copy of  
druntime, so there still is no compatibility.

-Steve
Mar 15 2012