• =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (5/5) Feb 20 2015 What's the policy on using GC or not in std.container.* ?
• Steven Schveighoffer (10/15) Feb 23 2015 RedBlackTree was ported from dcollections, which has an allocator hierar...
• =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (4/9) Feb 23 2015 Does this mean that in the long run RBTree should allocate its
• Steven Schveighoffer (6/12) Feb 23 2015 It means that it can do that, and does do that in dcollections.
• =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (6/11) Feb 26 2015 Have anybody done any benchmarks on which allocators are suitable

=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:

What's the policy on using GC or not in std.container.* ?

- std.container.Array uses malloc for its allocation but
- RedBlackTree.allocate() returns a: new RBNode!Elem*

Is this because RBNode* should be reachable outside of 
RedBlackTree or is this a todo?

Steven Schveighoffer <schveiguy yahoo.com> writes:

On 2/20/15 4:26 PM, "Nordlöw" wrote:
 What's the policy on using GC or not in std.container.* ?

 - std.container.Array uses malloc for its allocation but
 - RedBlackTree.allocate() returns a: new RBNode!Elem*

 Is this because RBNode* should be reachable outside of RedBlackTree or
 is this a todo?

RedBlackTree was ported from dcollections, which has an allocator hierarchy.

The code in dcollections looked like this originally:

https://github.com/schveiguy/dcollections/blob/master/dcollections/RBTree.d#L1244

return alloc.allocate();

where alloc is the allocator for the tree.

In answer to your question, RBNode should not be accessible direction 
outside of RedBlackTree. But we don't have allocators inside of Phobos, 
so I used the easiest thing I could for portability.

-Steve

=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:

On Monday, 23 February 2015 at 19:24:32 UTC, Steven Schveighoffer 
wrote:
 In answer to your question, RBNode should not be accessible 
 direction outside of RedBlackTree. But we don't have allocators 
 inside of Phobos, so I used the easiest thing I could for 
 portability.

 -Steve

Does this mean that in the long run RBTree should allocate its 
RBNodes using a non-GC allocator (such as std.allocator) instead?

Steven Schveighoffer <schveiguy yahoo.com> writes:

On 2/23/15 3:16 PM, "Nordlöw" wrote:
 On Monday, 23 February 2015 at 19:24:32 UTC, Steven Schveighoffer wrote:
 In answer to your question, RBNode should not be accessible direction
 outside of RedBlackTree. But we don't have allocators inside of
 Phobos, so I used the easiest thing I could for portability.

 Does this mean that in the long run RBTree should allocate its RBNodes
 using a non-GC allocator (such as std.allocator) instead?

It means that it can do that, and does do that in dcollections. 
std.container does not have all the code to do it, dcollections.RBTree 
has some extra calls that would probably help. However, the allocation 
is done in one spot so the code can easily use an allocator.

-Steve

=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:

On Monday, 23 February 2015 at 21:33:35 UTC, Steven Schveighoffer 
wrote:
 It means that it can do that, and does do that in dcollections. 
 std.container does not have all the code to do it, 
 dcollections.RBTree has some extra calls that would probably 
 help. However, the allocation is done in one spot so the code 
 can easily use an allocator.

Have anybody done any benchmarks on which allocators are suitable 
for which containers? I'm especially interested in optimizing 
RBTree because I want a fast Dikjstra implementation in D:

http://rosettacode.org/wiki/Dijkstra%27s_algorithm#D