www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Phobos 'collections' question

reply Robert McGinley <mcginley.robert gmail.com> writes:
Hey all,
Mostly as an exercise I'm considering writing an ArrayList, AVL tree, =
and possible other standard data structures in D.  I have two questions.
1.) If completed should I send these around for review and inclusion or =
do they not belong in phobos?
2.) If I'm working on including these in phobos should I put them in =
container.d (that has RedBlack Trees and a Singlelinked List) or is =
there a better location?
Rob=
Sep 14 2011
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/14/2011 04:08 PM, Robert McGinley wrote:

 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree, and
possible other standard data structures in D.  I have two questions.
 1.) If completed should I send these around for review and inclusion or do
they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in
container.d (that has RedBlack Trees and a Singlelinked List) or is there a
better location?
 Rob



As far as I know, the reason why std.container is not under active 
development, is that phobos does not have an allocator abstraction yet. 
As soon as there is one, the module will probably undergo some breaking 
changes. But I think the more well implemented standard data structures 
there are in Phobos, the better. I think as soon as the standard 
allocator interface is settled on, your efforts will be welcome. Steve 
can probably answer your question better though.
Sep 14 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:


 On 09/14/2011 04:08 PM, Robert McGinley wrote:

 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,  
 and possible other standard data structures in D.  I have two questions.
 1.) If completed should I send these around for review and inclusion or  
 do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in  
 container.d (that has RedBlack Trees and a Singlelinked List) or is  
 there a better location?
 Rob



 As far as I know, the reason why std.container is not under active  
 development, is that phobos does not have an allocator abstraction yet.  
 As soon as there is one, the module will probably undergo some breaking  
 changes. But I think the more well implemented standard data structures  
 there are in Phobos, the better. I think as soon as the standard  
 allocator interface is settled on, your efforts will be welcome. Steve  
 can probably answer your question better though.



Certainly more containers are welcome.

The review for getting things into phobos is done via github.  You do not  
need write permission to generate a pull request.  Yes, they should all be  
put into std.container for now.

I'd recommend doing one pull request per container, that way one container  
type does not detract from the inclusion of another.

I don't think that lack of allocators should prevent implementing  
containers.  My collection package (www.dsource.org/projects/dcollections)  
uses allocators, and they're pretty orthogonal to the operation of the  
container.

BTW, feel free to use any ideas/code from dcollections, it's also boost  
licensed.  Note that the red black tree implementation in phobos is copied  
verbatim from dcollections.  If you implement a good AVL tree, I might  
even steal it for dcollections ;)  (with attribution, of course!)

-Steve
Sep 14 2011
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, September 14, 2011 09:57 Steven Schveighoffer wrote:

 On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:

 On 09/14/2011 04:08 PM, Robert McGinley wrote:

 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,
 and possible other standard data structures in D. I have two questions.
 1.) If completed should I send these around for review and inclusion or
 do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in
 container.d (that has RedBlack Trees and a Singlelinked List) or is
 there a better location?
 Rob



 As far as I know, the reason why std.container is not under active
 development, is that phobos does not have an allocator abstraction yet.
 As soon as there is one, the module will probably undergo some breaking
 changes. But I think the more well implemented standard data structures
 there are in Phobos, the better. I think as soon as the standard
 allocator interface is settled on, your efforts will be welcome. Steve
 can probably answer your question better though.



 Certainly more containers are welcome.
 
 The review for getting things into phobos is done via github. You do not
 need write permission to generate a pull request. Yes, they should all be
 put into std.container for now.



That depends on the scope of the changes. If they're big enough or complicated 
enough, then they'd need to go in the review queue. With new containers, I 
don't know whether that's necessary or not. They're potentially large pieces 
of functionality, but much of their API is already stipulated by 
std.container, so not as thorough a review is necessary as might otherwise be 
the case. Simpler containers may not really need a formal review in the 
newsgroup, but if a particularly complicated container were being added to 
Phobos, then it would probably merit a more thorough review than you'd get via 
pull requests. It is a bit of a fuzzy area though.

- Jonathan M Davis
Sep 14 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 14 Sep 2011 13:12:30 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:


 On Wednesday, September 14, 2011 09:57 Steven Schveighoffer wrote:

 On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch>  
 wrote:

 On 09/14/2011 04:08 PM, Robert McGinley wrote:

 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,
 and possible other standard data structures in D. I have two  







 1.) If completed should I send these around for review and inclusion  







 do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in
 container.d (that has RedBlack Trees and a Singlelinked List) or is
 there a better location?
 Rob



 As far as I know, the reason why std.container is not under active
 development, is that phobos does not have an allocator abstraction  




 As soon as there is one, the module will probably undergo some  




 changes. But I think the more well implemented standard data  




 there are in Phobos, the better. I think as soon as the standard
 allocator interface is settled on, your efforts will be welcome. Steve
 can probably answer your question better though.



 Certainly more containers are welcome.

 The review for getting things into phobos is done via github. You do not
 need write permission to generate a pull request. Yes, they should all  
 be
 put into std.container for now.



 That depends on the scope of the changes. If they're big enough or  
 complicated
 enough, then they'd need to go in the review queue. With new containers,  
 I
 don't know whether that's necessary or not. They're potentially large  
 pieces
 of functionality, but much of their API is already stipulated by
 std.container, so not as thorough a review is necessary as might  
 otherwise be
 the case. Simpler containers may not really need a formal review in the
 newsgroup, but if a particularly complicated container were being added  
 to
 Phobos, then it would probably merit a more thorough review than you'd  
 get via
 pull requests. It is a bit of a fuzzy area though.



Regardless, the best way to get your code reviewed is by creating a github  
fork.  At least then it's easy to try out.

IMO, I think a pull request is fine, we already have established that we  
want a std.container and what the interface should be.

I'd recommend to Robert to identify exactly what containers you intend to  
implement, and have an informal discussion on the NG before creating the  
code.  This will at least give you an idea of what's likely to be accepted.

-Steve
Sep 14 2011
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, September 14, 2011 10:23 Steven Schveighoffer wrote:

 Regardless, the best way to get your code reviewed is by creating a github
 fork. At least then it's easy to try out.



Indeed. Such a fork is pretty much necessary to get the code into Phobos 
anyway.


 IMO, I think a pull request is fine, we already have established that we
 want a std.container and what the interface should be.



My primary concern would be that if a container were particularly complicated, 
then it would merit a more thorough review than is likely to occur on github 
(github frequently does not have enough people looking at pull requests and 
giving feedback on them). It is true that the primary thing that formal 
reviews deal with is the API, which has mostly been sorted out for 
std.container already, but particularly large/complex chunks of new 
functionality or larg/complex changes could merit more thorough reviews. 
Simpler containers won't have that issue. However, an informal review in the 
newsgroup might be enough for any particularly complex container. As I said, 
it's fuzzy. We just need to make sure that any containers which get added get 
a thorough enough review, whether that's simply reviewing it in github or a 
more thorough review in the newsgroup.


 I'd recommend to Robert to identify exactly what containers you intend to
 implement, and have an informal discussion on the NG before creating the
 code. This will at least give you an idea of what's likely to be accepted.



Good advice. A related note would be that the basic design of std.container is 
that the containers be based around data structures, not what they're used for 
(hence why we have RedBlackTree and not Set or Map), and new containers should 
stick to that. We may or may not create simple wrapper functions, types, or 
aliases which are based on usage (e.g. Set and Map), but the actual container 
types should be specific data structures.

- Jonathan M Davis
Sep 14 2011
prev sibling next sibling parent Robert McGinley <mcginley.robert gmail.com> writes:
Thanks everybody.  I'll have to plan things out more (my time wise more =
then anything) and I'll check with the NG before I move on anything.
Rob
On Sep 14, 2011, at 1:55 PM, Jonathan M Davis wrote:


 On Wednesday, September 14, 2011 10:23 Steven Schveighoffer wrote:

 Regardless, the best way to get your code reviewed is by creating a =







 fork. At least then it's easy to try out.



 Indeed. Such a fork is pretty much necessary to get the code into =




 anyway.
=20

 IMO, I think a pull request is fine, we already have established that =







 want a std.container and what the interface should be.



 My primary concern would be that if a container were particularly =




 then it would merit a more thorough review than is likely to occur on =




 (github frequently does not have enough people looking at pull =




 giving feedback on them). It is true that the primary thing that =




 reviews deal with is the API, which has mostly been sorted out for=20
 std.container already, but particularly large/complex chunks of new=20
 functionality or larg/complex changes could merit more thorough =




 Simpler containers won't have that issue. However, an informal review =




 newsgroup might be enough for any particularly complex container. As I =




 it's fuzzy. We just need to make sure that any containers which get =




 a thorough enough review, whether that's simply reviewing it in github =




 more thorough review in the newsgroup.
=20

 I'd recommend to Robert to identify exactly what containers you =







 implement, and have an informal discussion on the NG before creating =







 code. This will at least give you an idea of what's likely to be =







=20
 Good advice. A related note would be that the basic design of =




 that the containers be based around data structures, not what they're =




 (hence why we have RedBlackTree and not Set or Map), and new =




 stick to that. We may or may not create simple wrapper functions, =




 aliases which are based on usage (e.g. Set and Map), but the actual =




 types should be specific data structures.
=20
 - Jonathan M Davis
Sep 14 2011
prev sibling next sibling parent "Marco Leise" <Marco.Leise gmx.de> writes:
Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer  
<schveiguy yahoo.com>:


 On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:


 On 09/14/2011 04:08 PM, Robert McGinley wrote:

 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,  
 and possible other standard data structures in D.  I have two  
 questions.
 1.) If completed should I send these around for review and inclusion  
 or do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in  
 container.d (that has RedBlack Trees and a Singlelinked List) or is  
 there a better location?
 Rob



 As far as I know, the reason why std.container is not under active  
 development, is that phobos does not have an allocator abstraction yet.  
 As soon as there is one, the module will probably undergo some breaking  
 changes. But I think the more well implemented standard data structures  
 there are in Phobos, the better. I think as soon as the standard  
 allocator interface is settled on, your efforts will be welcome. Steve  
 can probably answer your question better though.



 Certainly more containers are welcome.

 The review for getting things into phobos is done via github.  You do  
 not need write permission to generate a pull request.  Yes, they should  
 all be put into std.container for now.

 I'd recommend doing one pull request per container, that way one  
 container type does not detract from the inclusion of another.

 I don't think that lack of allocators should prevent implementing  
 containers.  My collection package  
 (www.dsource.org/projects/dcollections) uses allocators, and they're  
 pretty orthogonal to the operation of the container.

 BTW, feel free to use any ideas/code from dcollections, it's also boost  
 licensed.  Note that the red black tree implementation in phobos is  
 copied verbatim from dcollections.  If you implement a good AVL tree, I  
 might even steal it for dcollections ;)  (with attribution, of course!)

 -Steve



I recently had the need for a priority queue and your library was the  
obvious choice. But it did the same that my code did when I ported it from  
32-bit to 64-bit: array.length is no longer a uint, but a ulong, so the  
code breaks. So my advice is to use size_t when you deal with a natural  
number that can be up to the amount of addressable memory.
Oct 24 2011
prev sibling next sibling parent Andrew Wiley <wiley.andrew.j gmail.com> writes:
--20cf303bff6099192004b0186dfd
Content-Type: text/plain; charset=ISO-8859-1

On Mon, Oct 24, 2011 at 9:50 PM, Marco Leise <Marco.Leise gmx.de> wrote:


 Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer <
 schveiguy yahoo.com>:


  On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:

  On 09/14/2011 04:08 PM, Robert McGinley wrote:

 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,
 and possible other standard data structures in D.  I have two questions.
 1.) If completed should I send these around for review and inclusion or
 do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in
 container.d (that has RedBlack Trees and a Singlelinked List) or is there a
 better location?
 Rob



 As far as I know, the reason why std.container is not under active
 development, is that phobos does not have an allocator abstraction yet. As
 soon as there is one, the module will probably undergo some breaking
 changes. But I think the more well implemented standard data structures
 there are in Phobos, the better. I think as soon as the standard allocator
 interface is settled on, your efforts will be welcome. Steve can probably
 answer your question better though.



 Certainly more containers are welcome.

 The review for getting things into phobos is done via github.  You do not
 need write permission to generate a pull request.  Yes, they should all be
 put into std.container for now.

 I'd recommend doing one pull request per container, that way one container
 type does not detract from the inclusion of another.

 I don't think that lack of allocators should prevent implementing
 containers.  My collection package (www.dsource.org/projects/**
 dcollections <http://www.dsource.org/projects/dcollections>) uses
 allocators, and they're pretty orthogonal to the operation of the container.

 BTW, feel free to use any ideas/code from dcollections, it's also boost
 licensed.  Note that the red black tree implementation in phobos is copied
 verbatim from dcollections.  If you implement a good AVL tree, I might even
 steal it for dcollections ;)  (with attribution, of course!)

 -Steve



 I recently had the need for a priority queue and your library was the
 obvious choice. But it did the same that my code did when I ported it from
 32-bit to 64-bit: array.length is no longer a uint, but a ulong, so the code
 breaks. So my advice is to use size_t when you deal with a natural number
 that can be up to the amount of addressable memory.



Wait, dcollections has a PriorityQueue?
You could use a tree for that, but my understanding is that a heap is much
more efficient?

--20cf303bff6099192004b0186dfd
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<br><br><div class=3D"gmail_quote">On Mon, Oct 24, 2011 at 9:50 PM, Marco L=
eise <span dir=3D"ltr">&lt;<a href=3D"mailto:Marco.Leise gmx.de">Marco.Leis=
e gmx.de</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=
=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer &lt;<a href=3D"mailt=
o:schveiguy yahoo.com" target=3D"_blank">schveiguy yahoo.com</a>&gt;:<div><=
div></div><div class=3D"h5"><br>
<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr &lt;<a href=3D"mailto:timon.=
gehr gmx.ch" target=3D"_blank">timon.gehr gmx.ch</a>&gt; wrote:<br>
<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
On 09/14/2011 04:08 PM, Robert McGinley wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
Hey all,<br>
Mostly as an exercise I&#39;m considering writing an ArrayList, AVL tree, a=
nd possible other standard data structures in D. =A0I have two questions.<b=
r>
1.) If completed should I send these around for review and inclusion or do =
they not belong in phobos?<br>
2.) If I&#39;m working on including these in phobos should I put them in co=
ntainer.d (that has RedBlack Trees and a Singlelinked List) or is there a b=
etter location?<br>
Rob<br>
</blockquote>
<br>
As far as I know, the reason why std.container is not under active developm=
ent, is that phobos does not have an allocator abstraction yet. As soon as =
there is one, the module will probably undergo some breaking changes. But I=
 think the more well implemented standard data structures there are in Phob=
os, the better. I think as soon as the standard allocator interface is sett=
led on, your efforts will be welcome. Steve can probably answer your questi=
on better though.<br>


</blockquote>
<br>
Certainly more containers are welcome.<br>
<br>
The review for getting things into phobos is done via github. =A0You do not=
 need write permission to generate a pull request. =A0Yes, they should all =
be put into std.container for now.<br>
<br>
I&#39;d recommend doing one pull request per container, that way one contai=
ner type does not detract from the inclusion of another.<br>
<br>
I don&#39;t think that lack of allocators should prevent implementing conta=
iners. =A0My collection package (<a href=3D"http://www.dsource.org/projects=
/dcollections" target=3D"_blank">www.dsource.org/projects/<u></u>dcollectio=
ns</a>) uses allocators, and they&#39;re pretty orthogonal to the operation=
 of the container.<br>


<br>
BTW, feel free to use any ideas/code from dcollections, it&#39;s also boost=
 licensed. =A0Note that the red black tree implementation in phobos is copi=
ed verbatim from dcollections. =A0If you implement a good AVL tree, I might=
 even steal it for dcollections ;) =A0(with attribution, of course!)<br>


<br>
-Steve<br>
</blockquote>
<br></div></div>
I recently had the need for a priority queue and your library was the obvio=
us choice. But it did the same that my code did when I ported it from 32-bi=
t to 64-bit: array.length is no longer a uint, but a ulong, so the code bre=
aks. So my advice is to use size_t when you deal with a natural number that=
 can be up to the amount of addressable memory.<br>


</blockquote></div><br><div>Wait, dcollections has a PriorityQueue?</div><d=
iv>You could use a tree for that, but my understanding is that a heap is mu=
ch more efficient?</div>

--20cf303bff6099192004b0186dfd--
Oct 24 2011
prev sibling next sibling parent Gor Gyolchanyan <gor.f.gyolchanyan gmail.com> writes:
I really REALLY miss a doubly-linked list. That's all i can think of
right now, which is missing from D's containers :-)

On Tue, Oct 25, 2011 at 9:00 AM, Andrew Wiley <wiley.andrew.j gmail.com> wr=
ote:

 On Mon, Oct 24, 2011 at 9:50 PM, Marco Leise <Marco.Leise gmx.de> wrote:

 Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer
 <schveiguy yahoo.com>:


 On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch> wrot=










 On 09/14/2011 04:08 PM, Robert McGinley wrote:

 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,
 and possible other standard data structures in D. =A0I have two quest=
















 1.) If completed should I send these around for review and inclusion =
















 do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in
 container.d (that has RedBlack Trees and a Singlelinked List) or is t=
















 better location?
 Rob



 As far as I know, the reason why std.container is not under active
 development, is that phobos does not have an allocator abstraction yet=













 soon as there is one, the module will probably undergo some breaking
 changes. But I think the more well implemented standard data structure=













 there are in Phobos, the better. I think as soon as the standard alloc=













 interface is settled on, your efforts will be welcome. Steve can proba=













 answer your question better though.



 Certainly more containers are welcome.

 The review for getting things into phobos is done via github. =A0You do=










 need write permission to generate a pull request. =A0Yes, they should a=










 put into std.container for now.

 I'd recommend doing one pull request per container, that way one
 container type does not detract from the inclusion of another.

 I don't think that lack of allocators should prevent implementing
 containers. =A0My collection package (www.dsource.org/projects/dcollect=










 uses allocators, and they're pretty orthogonal to the operation of the
 container.

 BTW, feel free to use any ideas/code from dcollections, it's also boost
 licensed. =A0Note that the red black tree implementation in phobos is c=










 verbatim from dcollections. =A0If you implement a good AVL tree, I migh=










 steal it for dcollections ;) =A0(with attribution, of course!)

 -Steve



 I recently had the need for a priority queue and your library was the
 obvious choice. But it did the same that my code did when I ported it fr=







 32-bit to 64-bit: array.length is no longer a uint, but a ulong, so the =







 breaks. So my advice is to use size_t when you deal with a natural numbe=







 that can be up to the amount of addressable memory.



 Wait, dcollections has a PriorityQueue?
 You could use a tree for that, but my understanding is that a heap is muc=




 more efficient?
Oct 25 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 24 Oct 2011 22:50:33 -0400, Marco Leise <Marco.Leise gmx.de> wrote:


 Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer  
 <schveiguy yahoo.com>:


 On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch>  
 wrote:


 On 09/14/2011 04:08 PM, Robert McGinley wrote:

 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,  
 and possible other standard data structures in D.  I have two  
 questions.
 1.) If completed should I send these around for review and inclusion  
 or do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in  
 container.d (that has RedBlack Trees and a Singlelinked List) or is  
 there a better location?
 Rob



 As far as I know, the reason why std.container is not under active  
 development, is that phobos does not have an allocator abstraction  
 yet. As soon as there is one, the module will probably undergo some  
 breaking changes. But I think the more well implemented standard data  
 structures there are in Phobos, the better. I think as soon as the  
 standard allocator interface is settled on, your efforts will be  
 welcome. Steve can probably answer your question better though.



 Certainly more containers are welcome.

 The review for getting things into phobos is done via github.  You do  
 not need write permission to generate a pull request.  Yes, they should  
 all be put into std.container for now.

 I'd recommend doing one pull request per container, that way one  
 container type does not detract from the inclusion of another.

 I don't think that lack of allocators should prevent implementing  
 containers.  My collection package  
 (www.dsource.org/projects/dcollections) uses allocators, and they're  
 pretty orthogonal to the operation of the container.

 BTW, feel free to use any ideas/code from dcollections, it's also boost  
 licensed.  Note that the red black tree implementation in phobos is  
 copied verbatim from dcollections.  If you implement a good AVL tree, I  
 might even steal it for dcollections ;)  (with attribution, of course!)

 -Steve



 I recently had the need for a priority queue and your library was the  
 obvious choice. But it did the same that my code did when I ported it  
 from 32-bit to 64-bit: array.length is no longer a uint, but a ulong, so  
 the code breaks. So my advice is to use size_t when you deal with a  
 natural number that can be up to the amount of addressable memory.



The latest (unreleased) version of dcollections uses size_t and ptrdiff_t  
everywhere instead of uint and int.  See here:  
http://www.dsource.org/projects/dcollections/ticket/14

I have to release a new beta soon, especially when inout works in the  
latest impending compiler release.

-Steve
Oct 26 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 25 Oct 2011 01:00:51 -0400, Andrew Wiley  
<wiley.andrew.j gmail.com> wrote:


 On Mon, Oct 24, 2011 at 9:50 PM, Marco Leise <Marco.Leise gmx.de> wrote:


 Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer <
 schveiguy yahoo.com>:


  On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch>  
 wrote:

  On 09/14/2011 04:08 PM, Robert McGinley wrote:

 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,
 and possible other standard data structures in D.  I have two  
 questions.
 1.) If completed should I send these around for review and inclusion  
 or
 do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in
 container.d (that has RedBlack Trees and a Singlelinked List) or is  
 there a
 better location?
 Rob



 As far as I know, the reason why std.container is not under active
 development, is that phobos does not have an allocator abstraction  
 yet. As
 soon as there is one, the module will probably undergo some breaking
 changes. But I think the more well implemented standard data  
 structures
 there are in Phobos, the better. I think as soon as the standard  
 allocator
 interface is settled on, your efforts will be welcome. Steve can  
 probably
 answer your question better though.



 Certainly more containers are welcome.

 The review for getting things into phobos is done via github.  You do  
 not
 need write permission to generate a pull request.  Yes, they should  
 all be
 put into std.container for now.

 I'd recommend doing one pull request per container, that way one  
 container
 type does not detract from the inclusion of another.

 I don't think that lack of allocators should prevent implementing
 containers.  My collection package (www.dsource.org/projects/**
 dcollections <http://www.dsource.org/projects/dcollections>) uses
 allocators, and they're pretty orthogonal to the operation of the  
 container.

 BTW, feel free to use any ideas/code from dcollections, it's also boost
 licensed.  Note that the red black tree implementation in phobos is  
 copied
 verbatim from dcollections.  If you implement a good AVL tree, I might  
 even
 steal it for dcollections ;)  (with attribution, of course!)

 -Steve



 I recently had the need for a priority queue and your library was the
 obvious choice. But it did the same that my code did when I ported it  
 from
 32-bit to 64-bit: array.length is no longer a uint, but a ulong, so the  
 code
 breaks. So my advice is to use size_t when you deal with a natural  
 number
 that can be up to the amount of addressable memory.



 Wait, dcollections has a PriorityQueue?



No.  Not yet.


 You could use a tree for that, but my understanding is that a heap is  
 much
 more efficient?



Yes.  I have a feeling dcollections will use heap from phobos (to avoid  
duplication) for a full priority queue.

-Steve
Oct 26 2011
prev sibling next sibling parent "Marco Leise" <Marco.Leise gmx.de> writes:
 You could use a tree for that, but my understanding is that a heap is  
 much
 more efficient?



 Yes.  I have a feeling dcollections will use heap from phobos (to avoid  
 duplication) for a full priority queue.

 -Steve



I tried a Fibonacci tree. It didn't beat the good old array based priority  
queue. And the more I read about garbage collection and CPU L1/L2 caches,  
my understanding is that packed arrays and indexes are the best choice if  
the amount of data is not too much.
I did a test with a circular linked list. As long as it is correctly  
ordered in memory, the CPU is able to prefetch everything into L1 by the  
time the next pointer is read, independent of the byte count. It could be  
a few KB up to a GB.
But when I randomly reordered the locations of the list nodes in memory it  
was up to 80x slower for the cases from several MB on. It only stayed fast  
as long as the complete data fit into the L1 cache. So what I learned from  
that is to avoid pointers to memory outside the current allocation block  
and to use a ushort now and then where appropriate ^^. I hope these didn't  
get slower on amd64.
Nov 01 2011
prev sibling parent "Marco Leise" <Marco.Leise gmx.de> writes:
Am 26.10.2011, 16:00 Uhr, schrieb Steven Schveighoffer  
<schveiguy yahoo.com>:


 On Mon, 24 Oct 2011 22:50:33 -0400, Marco Leise <Marco.Leise gmx.de>  
 wrote:


 Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer  
 <schveiguy yahoo.com>:


 On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch>  
 wrote:


 On 09/14/2011 04:08 PM, Robert McGinley wrote:

 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL  
 tree, and possible other standard data structures in D.  I have two  
 questions.
 1.) If completed should I send these around for review and inclusion  
 or do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in  
 container.d (that has RedBlack Trees and a Singlelinked List) or is  
 there a better location?
 Rob



 As far as I know, the reason why std.container is not under active  
 development, is that phobos does not have an allocator abstraction  
 yet. As soon as there is one, the module will probably undergo some  
 breaking changes. But I think the more well implemented standard data  
 structures there are in Phobos, the better. I think as soon as the  
 standard allocator interface is settled on, your efforts will be  
 welcome. Steve can probably answer your question better though.



 Certainly more containers are welcome.

 The review for getting things into phobos is done via github.  You do  
 not need write permission to generate a pull request.  Yes, they  
 should all be put into std.container for now.

 I'd recommend doing one pull request per container, that way one  
 container type does not detract from the inclusion of another.

 I don't think that lack of allocators should prevent implementing  
 containers.  My collection package  
 (www.dsource.org/projects/dcollections) uses allocators, and they're  
 pretty orthogonal to the operation of the container.

 BTW, feel free to use any ideas/code from dcollections, it's also  
 boost licensed.  Note that the red black tree implementation in phobos  
 is copied verbatim from dcollections.  If you implement a good AVL  
 tree, I might even steal it for dcollections ;)  (with attribution, of  
 course!)

 -Steve



 I recently had the need for a priority queue and your library was the  
 obvious choice. But it did the same that my code did when I ported it  
 from 32-bit to 64-bit: array.length is no longer a uint, but a ulong,  
 so the code breaks. So my advice is to use size_t when you deal with a  
 natural number that can be up to the amount of addressable memory.



 The latest (unreleased) version of dcollections uses size_t and  
 ptrdiff_t everywhere instead of uint and int.  See here:  
 http://www.dsource.org/projects/dcollections/ticket/14

 I have to release a new beta soon, especially when inout works in the  
 latest impending compiler release.

 -Steve



Ah that's good to know. I've gotten into writing my own containers now  
though. :) It is a good playground to learn some aspects of D as well.
Nov 01 2011