www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Better AAs

reply "bearophile" <bearophileHUGS lycos.com> writes:
Recently some people have said that D has about two thousand bugs 
open, so there is no hope to fix them, etc. But not all bugs are 
equally important. Probably less than about one hundred of those 
bugs are significantly important, so if you manage to fix those, 
D becomes something different (some of those bugs are enhancement 
requests).

Lately a bug that has plagued D has apparently being fixed, now D 
is a bit more adult language.

This code:

import std.stdio, std.typecons;
struct Foo { string s; }
alias Bar = Tuple!string;
auto s1 = "he";
auto s2 = "llo";
void main() {
     int[Foo] aa1;
     aa1[Foo("hello")] = 1;
     aa1[Foo(s1 ~ s2)] = 2;
     aa1.writeln;
     int[Bar] aa2;
     aa2[Bar("hello")] = 1;
     aa2[Bar(s1 ~ s2)] = 2;
     aa2.writeln;
}


Now compiles and outputs something right:

[Foo("hello"):2]
[Tuple!string("hello"):2]

More problems are left in the D AAs, but now you can actually 
start using D associative arrays in your code.

Rust has not done the significant D design mistake of putting the 
associative arrays inside the language/runtime, but D AAs are 
getting better.

Bye,
bearophile
Jul 06 2014
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 7/6/2014 3:53 PM, bearophile wrote:

 Rust has not done the significant D design mistake of putting the associative
 arrays inside the language/runtime, but D AAs are getting better.


It wasn't a mistake early on, as D did not have sufficient abstraction power to 
do them.
Jul 06 2014
parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Sun, Jul 06, 2014 at 04:02:24PM -0700, Walter Bright via Digitalmars-d wrote:

 On 7/6/2014 3:53 PM, bearophile wrote:

Rust has not done the significant D design mistake of putting the
associative arrays inside the language/runtime, but D AAs are getting
better.


 
 It wasn't a mistake early on, as D did not have sufficient abstraction
 power to do them.


Also, as I understand it, the current design worked well for early
versions of D, but it didn't keep pace with new developments in D2 that
introduced holes in the implementation.

In any case, I'm hopeful for D AA's, as recently there's been a slow but
steady stream of AA-related fixes in druntime and dmd, so soon, we may
be able to have a sane, up-to-date AA implementation. I think we're also
inching closer to abstracting away the compiler hacks that cause much of
the present mess, so a library-based AA seems to be within reach in the
hopefully not-too-distant future.


T

-- 
"You know, maybe we don't *need* enemies." "Yeah, best friends are about all I
can take." -- Calvin & Hobbes
Jul 06 2014
parent "w0rp" <devw0rp gmail.com> writes:
I wrote my own hashmap a little while ago for fun, and also 
because I couldn't get  safe pure nothrow ranges through maps at 
the time, and it turned out that I could also add in  nogc too 
for the ranges and a lot of functions, so I could make a lot of 
my graph types also provide the same guarantees.

https://github.com/w0rp/dstruct/blob/master/source/dstruct/map.d

Maybe there's something in there which might be useful to someone 
else. Maybe I did something horribly wrong for which I must be 
punished.

One thing I did find interesting is the results I got from 
following the OpenJDK method of computing an index in the bucket 
with hash & (length - 1). Because my bucket lengths are always 
powers of 2, the 'bitwise and' achieves fairly uniform 
distribution from what I can tell without needing to execute 
division, which can be slow.
Jul 06 2014
prev sibling next sibling parent "AsmMan" <lol.themask gmail.com> writes:
On Sunday, 6 July 2014 at 22:53:56 UTC, bearophile wrote:

 Recently some people have said that D has about two thousand 
 bugs open, so there is no hope to fix them, etc.

 Bye,
 bearophile


Where was that?
Jul 06 2014
prev sibling parent reply "Tom Compton" <orgolone yahoo.com> writes:
On Sunday, 6 July 2014 at 22:53:56 UTC, bearophile wrote:


 Rust has not done the significant D design mistake of putting 
 the associative arrays inside the language/runtime, but D AAs 
 are getting better.


Can someone explain why having AA's builtin to the language is 
such a bad thing. I would have thought that it is a good thing 
because of greater efficiency.
Jul 10 2014
next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Friday, 11 July 2014 at 02:32:33 UTC, Tom Compton wrote:

 On Sunday, 6 July 2014 at 22:53:56 UTC, bearophile wrote:


 Rust has not done the significant D design mistake of putting 
 the associative arrays inside the language/runtime, but D AAs 
 are getting better.


 Can someone explain why having AA's builtin to the language is 
 such a bad thing. I would have thought that it is a good thing 
 because of greater efficiency.


There are 3 thing that you don't want to know how they are done: 
sausages, law and D's AA.
Jul 10 2014
prev sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Fri, Jul 11, 2014 at 02:32:31AM +0000, Tom Compton via Digitalmars-d wrote:

 On Sunday, 6 July 2014 at 22:53:56 UTC, bearophile wrote:
 

Rust has not done the significant D design mistake of putting the
associative arrays inside the language/runtime, but D AAs are getting
better.


 
 Can someone explain why having AA's builtin to the language is such a
 bad thing. I would have thought that it is a good thing because of
 greater efficiency.


IMO, it's not a bad thing to put AA's in a language in general. In fact,
when I was first considering using D, having built-in AA's in the
language was one of the big plusses for me. To this day, I still can't
get over the fact that C++ didn't even have AA's in the standard until
C++11, and the AA's in C++11 are so cumbersome to use that the last time
I tried, I almost tore out all my hair. In contrast, D's AA's, for all
their flaws, are at least *pleasant* to use without needing to reinvent
your own hash functions for every single struct, every single time.

However, due to historical reasons, the current *implementation* of AA's
in D leaves a lot to be desired. That's rather disappointing, but I
*will* say that for the most common, basic use cases of AA's, even the
current AA's in D are actually quite useful, and quite handy for simple
problems. We're all hoping the implementation could be improved, though,
so that it would also work for the not-so-simple cases, and that some
current nasty design-related bugs would finally be fixed.


T

-- 
Caffeine underflow. Brain dumped.
Jul 11 2014