Yet another strike against the current AA implementation

[dsimcha]

== Quote from Steve Teale (steve.teale at britseyeview.com)'s article
> dsimcha Wrote:
> > So I tried to create a struct to allow iteration over the keys or values of a
> > builtin associative array using a lazy forward range.  This would allow one to
> > pass the keys or values of an AA to any function that expects a regular old
> > forward range w/o any heap activity, eager copying, etc. and with O(1)
> > auxiliary memory usage.  Now that ranges are the lingua franca of iteration in
> > D, this seems like a pretty necessary feature.
> >
> > The problem is that D's current AAs are based on a hash table with collision
> > resolution done using binary trees.  I guess this decision was made to allow
> > for O(log N) worst case performance even when there are ridiculous amounts of
> > hash collisions.  However, this is a very bad decision because, in exchange
> > for more bulletproof performance in corner cases, you lose:
> >
> > 1.  Every element is now (void*).sizeof bytes larger because you have to store
> > a left and right pointer.
> > 2.  You can't iterate over a binary tree in O(1) auxiliary space, at least not
> > in any way I'm aware of.  This means that a lazy range to iterate over the
> > keys or values is relatively useless because it would generate heap activity
> > anyhow to store the stack or queue necessary to iterate over the tree, so you
> > may as well just use the current .keys or .values properties, which just
> > return an array.  (Because of the way that ranges are designed, you can't just
> > use the call stack, unless you use fibers or something, which is obviously not
> > a win from an efficiency point of view.)
> >
> > Both of these are important in the more common, general case of sane hashing
> > performance.
> Ranges, ranges! That's all I hear these days, and it looks to me like the
continuing advance of D toward being a complete meta-language.
> Where do I see ranges described in terms that an old hand can understand?
> I'm constantly having to roll my own in many areas when I see how the meta stuff
is implemented - like x ~= c to add a character to the end of an array -
reallocation every time?
> I thought D was supposed to be a systems programming language, not something
that was guaranteed to win the universe obfuscated code  competition.
> I've been trying to keep my projects up to date and compilable with D2.0xx, but
I think I'm going to give up on that and rewrite them for whatever the current
version of D1 is.
> I seriously think that the crew who are driving the development should realize
that not all computer programmers are going to have an IQ of 140, and that any
practical language should be comprehensible to a majority of its users.
> Maybe the problem I'm complaining about is just a lack of documentation.
Generating said from comments really does not hack it - comments are always
skimped, and usually lie.
> Before something like Ranges are implemented, there should be some sort of RFC
process where they are properly described rather than a reliance on D users to
have read every thread of the newsgroup, and remembered it all.

But there was an RFC, and it was even called that.  It just happened to take place
on this newsgroup.  Also, keep in mind that D2 is still in alpha.  Worrying about
how to explain this stuff to people who aren't heavily involved with D at this
point would slow down the pace of evolution and generate more confusion.  The time
to do this is when the dust has settled a little.