On Mon, 19 Jul 2010 09:36:54 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> On 07/19/2010 06:36 AM, Steven Schveighoffer wrote:
>> Just thinking out loud here, couldn't you use the predicate already in
>> AssumeSorted? I mean, if you're going to pass AssumeSorted into find,
>> you don't want to also specify the predicate as then the range just
>> becomes a standard range.
>>
>> There must be some kind of way to use template constraints to kill the
>> predicate arg to find when the range is an AssumeSorted struct. If not,
>> there should be.
>
> That's a good idea. The find predicate that could be derived from AssumeSorted's predicate pred would be !pred(a, b) && !pred(b, a).
>
> Thanks, Steve.

You're welcome :)

BTW, you don't need the combo predicate until the very end.  Basically, you do a binary search for the first element where pred(a, E) is false (where E is the target), and then see if pred(E, a) is also false on that element (to test for equality).

-Steve

On 07/19/2010 09:27 AM, Steven Schveighoffer wrote:
> On Mon, 19 Jul 2010 09:36:54 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>
>> On 07/19/2010 06:36 AM, Steven Schveighoffer wrote:
>>> Just thinking out loud here, couldn't you use the predicate already in
>>> AssumeSorted? I mean, if you're going to pass AssumeSorted into find,
>>> you don't want to also specify the predicate as then the range just
>>> becomes a standard range.
>>>
>>> There must be some kind of way to use template constraints to kill the
>>> predicate arg to find when the range is an AssumeSorted struct. If not,
>>> there should be.
>>
>> That's a good idea. The find predicate that could be derived from
>> AssumeSorted's predicate pred would be !pred(a, b) && !pred(b, a).
>>
>> Thanks, Steve.
>
> You're welcome :)
>
> BTW, you don't need the combo predicate until the very end. Basically,
> you do a binary search for the first element where pred(a, E) is false
> (where E is the target), and then see if pred(E, a) is also false on
> that element (to test for equality).

You mean like this? :o)

http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/algorithm.d?rev=1279#L4703


Andrei

On Mon, 19 Jul 2010 11:10:03 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> On 07/19/2010 09:27 AM, Steven Schveighoffer wrote:
>> On Mon, 19 Jul 2010 09:36:54 -0400, Andrei Alexandrescu
>> <SeeWebsiteForEmail@erdani.org> wrote:
>>
>>> On 07/19/2010 06:36 AM, Steven Schveighoffer wrote:
>>>> Just thinking out loud here, couldn't you use the predicate already in
>>>> AssumeSorted? I mean, if you're going to pass AssumeSorted into find,
>>>> you don't want to also specify the predicate as then the range just
>>>> becomes a standard range.
>>>>
>>>> There must be some kind of way to use template constraints to kill the
>>>> predicate arg to find when the range is an AssumeSorted struct. If not,
>>>> there should be.
>>>
>>> That's a good idea. The find predicate that could be derived from
>>> AssumeSorted's predicate pred would be !pred(a, b) && !pred(b, a).
>>>
>>> Thanks, Steve.
>>
>> You're welcome :)
>>
>> BTW, you don't need the combo predicate until the very end. Basically,
>> you do a binary search for the first element where pred(a, E) is false
>> (where E is the target), and then see if pred(E, a) is also false on
>> that element (to test for equality).
>
> You mean like this? :o)
>
> http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/algorithm.d?rev=1279#L4703

Yep.  I realized after I wrote this that you probably were already doing it :)

Interestingly, I found that when doing the redblacktree that I tried to do some optimization on the lookup of an element.  Basically, while I'm going down the tree looking for a single element, I'm using the binary predicate to move left or right.  However, if I move left (i.e. it's not less), then that could be the element I'm looking for!  So I try the opposite of the predicate to see if I should return.

But when I allow multiple identical elements (i.e. multiset), I want to find the *first* instance of the element, the code is much simpler.  If I move to the left child, I store that as the "Best result so far".  Then at the end, I simply run the opposite predicate once on the aforementioned best result.

The benefit of running the opposite predicate sooner is that if the element is higher in the tree, I'll return quicker, but I think it ends up being a wash.  I'll probably change it to be the same as the multi style tree.

It all comes from the original code which used an int return for the comparison, making it just as simple to detect equality as it is to detect less-than.

Maybe I'm the first one to make that mistake :)

-Steve

On 07/19/2010 10:24 AM, Steven Schveighoffer wrote:
> On Mon, 19 Jul 2010 11:10:03 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>
>> On 07/19/2010 09:27 AM, Steven Schveighoffer wrote:
>>> On Mon, 19 Jul 2010 09:36:54 -0400, Andrei Alexandrescu
>>> <SeeWebsiteForEmail@erdani.org> wrote:
>>>
>>>> On 07/19/2010 06:36 AM, Steven Schveighoffer wrote:
>>>>> Just thinking out loud here, couldn't you use the predicate already in
>>>>> AssumeSorted? I mean, if you're going to pass AssumeSorted into find,
>>>>> you don't want to also specify the predicate as then the range just
>>>>> becomes a standard range.
>>>>>
>>>>> There must be some kind of way to use template constraints to kill the
>>>>> predicate arg to find when the range is an AssumeSorted struct. If
>>>>> not,
>>>>> there should be.
>>>>
>>>> That's a good idea. The find predicate that could be derived from
>>>> AssumeSorted's predicate pred would be !pred(a, b) && !pred(b, a).
>>>>
>>>> Thanks, Steve.
>>>
>>> You're welcome :)
>>>
>>> BTW, you don't need the combo predicate until the very end. Basically,
>>> you do a binary search for the first element where pred(a, E) is false
>>> (where E is the target), and then see if pred(E, a) is also false on
>>> that element (to test for equality).
>>
>> You mean like this? :o)
>>
>> http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/algorithm.d?rev=1279#L4703
>>
>
> Yep. I realized after I wrote this that you probably were already doing
> it :)

Yah, it's quite the STL classic. STL commonly defines implicitly equivalence in terms of !less(a, b) && !less(b, a) but uses only one of the two comparisons until the last leg, when it's testing the opposite way.

> Interestingly, I found that when doing the redblacktree that I tried to
> do some optimization on the lookup of an element. Basically, while I'm
> going down the tree looking for a single element, I'm using the binary
> predicate to move left or right. However, if I move left (i.e. it's not
> less), then that could be the element I'm looking for! So I try the
> opposite of the predicate to see if I should return.

Indeed that's 100% what STL's lower_bound and rb_tree.find do.

By the way, I'm still eagerly waiting for your red-black tree implementation. I think it would be pure awesomeness if you massaged the red/black bit inside one of the pointers. I figured out a way of doing that without throwing off the garbage collector:

union
{
    unsigned byte * _gcHelper;
    size_t _bits;
}
bool setRed() { _bits |= 1; }
bool setBlack() { _bits &= ~(cast(size_t) 1); }
bool isRed() { return _bits & 1; }
RBTreeNode * left()
{
    return cast(RBTreeNode *) cast(size_t) (_bits & ~(cast(size_t) 1));
}

The idea is to leave _gcHelper in there as a valid pointer to either a RBTreeNode or a pointer to one byte inside the RBTreeNode. That way the GC is never confused - it will keep the node.

I think putting that one bit inside the pointer has important consequences.

I also suggest you read up on "left-leaning red-black trees" for a recent alternative approach that simplifies the code a fair amount.


Andrei

On Mon, 19 Jul 2010 12:21:36 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>
> By the way, I'm still eagerly waiting for your red-black tree implementation.

Sorry for the delay, I've been very busy at work, and I wanted to slip in a couple druntime fixes for array appending.

All that is left really is the unit testing, and making the docs more phobos-ish.

> I think it would be pure awesomeness if you massaged the red/black bit inside one of the pointers. I figured out a way of doing that without throwing off the garbage collector:

Yes, that works (BTW, you don't need the union, I hate unions :), just substitute _bits for _left everywhere, I think it would even work with a moving GC).

But I don't know how important it is to save that extra 4 bytes/node.  A redblack node already has 3 pointers in it, the flag puts it to 16 bytes instead of overhead instead of 12.  It certainly can be an implementation choice.

I can look at left-leaning trees (I've had it on my todo list for dcollections too).

-Steve

On 07/19/2010 12:23 PM, Steven Schveighoffer wrote:
> On Mon, 19 Jul 2010 12:21:36 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>>
>> By the way, I'm still eagerly waiting for your red-black tree
>> implementation.
>
> Sorry for the delay, I've been very busy at work, and I wanted to slip
> in a couple druntime fixes for array appending.
>
> All that is left really is the unit testing, and making the docs more
> phobos-ish.
>
>> I think it would be pure awesomeness if you massaged the red/black bit
>> inside one of the pointers. I figured out a way of doing that without
>> throwing off the garbage collector:
>
> Yes, that works (BTW, you don't need the union, I hate unions :), just
> substitute _bits for _left everywhere, I think it would even work with a
> moving GC).

Walter told me that union is instrumental to keeping the compiler in the know about such shenanigans. What does your idea look like? You mean keeping a possibly misaligned RBTreeNode pointer and manipulating that? I think that's a bit worse than unions because it transforms a sure thing into a maybe works thing.

> But I don't know how important it is to save that extra 4 bytes/node. A
> redblack node already has 3 pointers in it, the flag puts it to 16 bytes
> instead of overhead instead of 12. It certainly can be an implementation
> choice.
>
> I can look at left-leaning trees (I've had it on my todo list for
> dcollections too).

Sounds great. If the payload is one word, on a 32-bit system we'd have 20 bytes per node. I seem to recall the current GC can allocate 16 bytes and then 32 bytes and then 48 bytes, so with the embedded bit we're looking at halving the total allocated size. Not too shoddy! Then the relative overhead of that extra word is not felt up until a payload of 20 bytes, at which point again it jumps to 33%.

I wonder what things look like (alignment, granularity) for the 64-bit implementation.


Andrei

On 19/07/2010 18:21, Andrei Alexandrescu wrote:
> I also suggest you read up on "left-leaning red-black trees" for a
> recent alternative approach that simplifies the code a fair amount.

A few month ago (12-15) I have also made that suggestion to Steve. Meanwhile I am not that sure that LL RB Trees do offer significant complexity reduction... . R. Sedgewick's original implementation in Java is not bullet proofed.

Don't get me wrong LL RBTree have a certain appeal but read your self.

--In case that you don't want to use this link :
http://t-t-travails.blogspot.com/2008/04/left-leaning-red-black-trees-are-hard.html
--Here a quote <
Last Monday, I started implementing left-leaning red-black trees, expecting to spend perhaps 15 hours on the project. I'm here more than 60 hours of work later to tell you that left-leaning red-black trees are hard to implement, and contrary to Sedgewick's claims, their implementation appears to require approximately the same amount of code and complexity as standard red-black trees.
>
Meanwhile I am convinced that Skiplists are more interesting as RBTree alternative data-structure. Besidet QT folks are using the skiplist algo. for their MAP implementation.

@Andrei, hope you have noticed that Steve's dcollections allow the replacement of the underlaying data-structute. ;)
So IMHO let's spend some time in implementing the skiplist data-structure.
Finally > I would like to see std.datastructures. for core tree,list,graphs etc structures..
A+.
Bjoern

On Mon, 19 Jul 2010 13:47:38 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> On 07/19/2010 12:23 PM, Steven Schveighoffer wrote:
>> On Mon, 19 Jul 2010 12:21:36 -0400, Andrei Alexandrescu
>> <SeeWebsiteForEmail@erdani.org> wrote:
>>>
>>> By the way, I'm still eagerly waiting for your red-black tree
>>> implementation.
>>
>> Sorry for the delay, I've been very busy at work, and I wanted to slip
>> in a couple druntime fixes for array appending.
>>
>> All that is left really is the unit testing, and making the docs more
>> phobos-ish.
>>
>>> I think it would be pure awesomeness if you massaged the red/black bit
>>> inside one of the pointers. I figured out a way of doing that without
>>> throwing off the garbage collector:
>>
>> Yes, that works (BTW, you don't need the union, I hate unions :), just
>> substitute _bits for _left everywhere, I think it would even work with a
>> moving GC).
>
> Walter told me that union is instrumental to keeping the compiler in the know about such shenanigans. What does your idea look like? You mean keeping a possibly misaligned RBTreeNode pointer and manipulating that? I think that's a bit worse than unions because it transforms a sure thing into a maybe works thing.

I don't pretend to know what ominous problems Walter knows about regarding the compiler's view, but here is what I'm thinking:

If a pointer points to the beginning of a node, and a node has at least one pointer in it (which it must, since it's a tree), then pointing one byte into the node means you're still pointing at the same block, making sure the GC doesn't collect.

Really, the generated code will be exactly the same as your solution, but it's less of a misuse of the type system IMO (believe it or not).  I'd rather use casts when you are trying to use something that's typed as one thing as something else.  When using unions, I usually expect only one member of the union to be valid at any one time.

And wouldn't a union be more egregious with the upcoming mostly-precise scanner?

>
>> But I don't know how important it is to save that extra 4 bytes/node. A
>> redblack node already has 3 pointers in it, the flag puts it to 16 bytes
>> instead of overhead instead of 12. It certainly can be an implementation
>> choice.
>>
>> I can look at left-leaning trees (I've had it on my todo list for
>> dcollections too).
>
> Sounds great. If the payload is one word, on a 32-bit system we'd have 20 bytes per node. I seem to recall the current GC can allocate 16 bytes and then 32 bytes and then 48 bytes, so with the embedded bit we're looking at halving the total allocated size. Not too shoddy!

Not quite :)  There is one byte for padding because (insert gasp-inspiring music accent) all struct heap allocations are allocated through newArray with a size of 1.  I discovered this when working on the array append patch.

So even a 16-byte struct requires a 32-byte block.

> Then the relative overhead of that extra word is not felt up until a payload of 20 bytes, at which point again it jumps to 33%.

Most of this is mitigated if you have a custom allocator that allocates an array of nodes at once (what I do in dcollections).  As a simple implementation, you could allocate enough nodes to be under a certain threshold of wasted space.

> I wonder what things look like (alignment, granularity) for the 64-bit implementation.

They must be 8-byte aligned, and have 3 8-byte pointers, so that means at least 24 bytes.  If you store an int, then it will still fit in the 32-byte block.  I don't know what's planned as the minimum size for 64-bit GC.

-Steve

On 07/19/2010 01:50 PM, Steven Schveighoffer wrote:
> On Mon, 19 Jul 2010 13:47:38 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>
>> On 07/19/2010 12:23 PM, Steven Schveighoffer wrote:
>>> On Mon, 19 Jul 2010 12:21:36 -0400, Andrei Alexandrescu
>>> <SeeWebsiteForEmail@erdani.org> wrote:
>>>>
>>>> By the way, I'm still eagerly waiting for your red-black tree
>>>> implementation.
>>>
>>> Sorry for the delay, I've been very busy at work, and I wanted to slip
>>> in a couple druntime fixes for array appending.
>>>
>>> All that is left really is the unit testing, and making the docs more
>>> phobos-ish.
>>>
>>>> I think it would be pure awesomeness if you massaged the red/black bit
>>>> inside one of the pointers. I figured out a way of doing that without
>>>> throwing off the garbage collector:
>>>
>>> Yes, that works (BTW, you don't need the union, I hate unions :), just
>>> substitute _bits for _left everywhere, I think it would even work with a
>>> moving GC).
>>
>> Walter told me that union is instrumental to keeping the compiler in
>> the know about such shenanigans. What does your idea look like? You
>> mean keeping a possibly misaligned RBTreeNode pointer and manipulating
>> that? I think that's a bit worse than unions because it transforms a
>> sure thing into a maybe works thing.
>
> I don't pretend to know what ominous problems Walter knows about
> regarding the compiler's view, but here is what I'm thinking:
>
> If a pointer points to the beginning of a node, and a node has at least
> one pointer in it (which it must, since it's a tree), then pointing one
> byte into the node means you're still pointing at the same block, making
> sure the GC doesn't collect.
>
> Really, the generated code will be exactly the same as your solution,
> but it's less of a misuse of the type system IMO (believe it or not).
> I'd rather use casts when you are trying to use something that's typed
> as one thing as something else. When using unions, I usually expect only
> one member of the union to be valid at any one time.
>
> And wouldn't a union be more egregious with the upcoming mostly-precise
> scanner?

I don't think so (applied to all of the above) for reasons of various degree of obviousness, but perhaps it's not worth expanding on such a minor issue.

Andrei

Steven Schveighoffer:

> Not quite :)  There is one byte for padding because (insert gasp-inspiring music accent) all struct heap allocations are allocated through newArray with a size of 1.  I discovered this when working on the array append patch.

How much more hidden shit like this do I have to see?
I have filed a bug report:
http://d.puremagic.com/issues/show_bug.cgi?id=4487
Maybe Walter has to fix this before porting dmd to 64 bits.


> Most of this is mitigated if you have a custom allocator that allocates an array of nodes at once

The GC is supposed to not suck that much. If I want to do all manually and use custom allocators then maybe it's better if I start to switc to C language.
Thank you Steven.