www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Kinds of containers

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
I'm finally getting the cycles to get to thinking about Design by 
Introspection containers. First off, there are several general 
categories of containers. I think D should support all properly. One 
question is which we go for in the standard library.

1. Functional containers.

These are immutable; once created, neither their topology nor their 
elements may be observably changed. Manipulating a container entails 
creating an entire new container, often based on an existing container 
(e.g. append takes a container and an element and creates a whole new 
container).

Internally, functional containers take advantage of common substructure 
and immutability to share actual data. The classic resource for defining 
and implementing functional containers is 
http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.

2. Reference containers.

These have classic reference semantics (à la Java). Internally, they may 
be implemented either as class objects or as reference counted structs.

They're by default mutable. Qualifiers should apply to them gracefully.

3. Eager value containers.

These are STL-style. Somewhat surprisingly I think these are the worst 
of the pack; they expensively duplicate at the drop of a hat and need to 
be carefully passed around by reference lest performance silently drops. 
Nevertheless, when used as members inside other data structures value 
semantics might be the appropriate choice. Also, thinking of them as 
values often makes code simpler.

By default eager value containers are mutable. They should support 
immutable and const meaningfully.

4. Copy-on-write containers.

These combine the advantages of value and reference containers: you get 
to think of them as values, yet they're not expensive to copy. Copying 
only occurs by necessity upon the first attempt to change them.

The disadvantage is implementations get somewhat complicated. Also, they 
are shunned in C++ because there is no proper support for COW; for 
example, COW strings have been banned starting with C++11 which is quite 
the bummer.

Together with Scott Meyers, Walter figured out a way to change D to 
support COW properly. The language change consists of two attributes.

=======

I'll attempt to implement a few versions of each and see what they look 
like. The question here is what containers are of interest for D's 
standard library.


Andrei
Oct 21 2015
next sibling parent Rikki Cattermole <alphaglosined gmail.com> writes:
On 22/10/15 12:05 AM, Andrei Alexandrescu wrote:
 I'm finally getting the cycles to get to thinking about Design by
 Introspection containers. First off, there are several general
 categories of containers. I think D should support all properly. One
 question is which we go for in the standard library.

 1. Functional containers.

 These are immutable; once created, neither their topology nor their
 elements may be observably changed. Manipulating a container entails
 creating an entire new container, often based on an existing container
 (e.g. append takes a container and an element and creates a whole new
 container).

 Internally, functional containers take advantage of common substructure
 and immutability to share actual data. The classic resource for defining
 and implementing functional containers is
 http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.


 2. Reference containers.

 These have classic reference semantics (à la Java). Internally, they may
 be implemented either as class objects or as reference counted structs.

 They're by default mutable. Qualifiers should apply to them gracefully.

 3. Eager value containers.

 These are STL-style. Somewhat surprisingly I think these are the worst
 of the pack; they expensively duplicate at the drop of a hat and need to
 be carefully passed around by reference lest performance silently drops.
 Nevertheless, when used as members inside other data structures value
 semantics might be the appropriate choice. Also, thinking of them as
 values often makes code simpler.

 By default eager value containers are mutable. They should support
 immutable and const meaningfully.

 4. Copy-on-write containers.

 These combine the advantages of value and reference containers: you get
 to think of them as values, yet they're not expensive to copy. Copying
 only occurs by necessity upon the first attempt to change them.

 The disadvantage is implementations get somewhat complicated. Also, they
 are shunned in C++ because there is no proper support for COW; for
 example, COW strings have been banned starting with C++11 which is quite
 the bummer.

 Together with Scott Meyers, Walter figured out a way to change D to
 support COW properly. The language change consists of two attributes.

 =======

 I'll attempt to implement a few versions of each and see what they look
 like. The question here is what containers are of interest for D's
 standard library.


 Andrei
I've got a list and a map implementation using allocators. They are pretty primitive but they may lead to insight so links provided. https://github.com/rikkimax/alphaPhobos/blob/master/source/std/experimental/internal/containers/list.d https://github.com/rikkimax/alphaPhobos/blob/master/source/std/experimental/internal/containers/map.d
Oct 21 2015
prev sibling next sibling parent reply Russel Winder via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wed, 2015-10-21 at 07:05 -0400, Andrei Alexandrescu via Digitalmars-
d wrote:
=20
[=E2=80=A6]
 1. Functional containers.
=20
 These are immutable; once created, neither their topology nor their=20
 elements may be observably changed. Manipulating a container entails=20
 creating an entire new container, often based on an existing
 container=20
 (e.g. append takes a container and an element and creates a whole new
 container).
=20
 Internally, functional containers take advantage of common
 substructure=20
 and immutability to share actual data. The classic resource for
 defining=20
 and implementing functional containers is=20
 http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0
 521663504.
I believe (currently, I am open to being re-educated) that most of the rest of the world calls these persistent data structures, despite the title of Okasaki's thesis. I am not sure I like either of the labels "functional" or "persistent", there is little affordance with the concept underneath.
 2. Reference containers.
=20
 These have classic reference semantics (=C3=A0 la Java). Internally, they
 may=20
 be implemented either as class objects or as reference counted
 structs.
=20
 They're by default mutable. Qualifiers should apply to them
 gracefully.
=20
 3. Eager value containers.
=20
 These are STL-style. Somewhat surprisingly I think these are the
 worst=20
 of the pack; they expensively duplicate at the drop of a hat and need
 to=20
 be carefully passed around by reference lest performance silently
 drops.=20
 Nevertheless, when used as members inside other data structures value
 semantics might be the appropriate choice. Also, thinking of them as=20
 values often makes code simpler.
=20
 By default eager value containers are mutable. They should support=20
 immutable and const meaningfully.
Is there a need for separate eager structures explicity? Is it not enough for all structures to be lazy with there being a pull operation?
 4. Copy-on-write containers.
=20
 These combine the advantages of value and reference containers: you
 get=20
 to think of them as values, yet they're not expensive to copy.
 Copying=20
 only occurs by necessity upon the first attempt to change them.
=20
 The disadvantage is implementations get somewhat complicated. Also,
 they=20
 are shunned in C++ because there is no proper support for COW; for=20
 example, COW strings have been banned starting with C++11 which is
 quite=20
 the bummer.
=20
 Together with Scott Meyers, Walter figured out a way to change D to=20
 support COW properly. The language change consists of two attributes.
=20
 =3D=3D=3D=3D=3D=3D=3D
=20
 I'll attempt to implement a few versions of each and see what they
 look=20
 like. The question here is what containers are of interest for D's=20
 standard library.
N-dimensional arrays, N-dimensional dynamic array, singly-linked list, doubly-linked list, hash map (aka dictionary, associative array,=E2=80=A6), red-black tree, 2-3 tree, doubly-linked tree, tree map, b-tree. And no doubt a few others will be proposed since they are classic, appear in undergraduate courses, and are actually used for real. However these are classic sequential data structures. We should be looking to support data structures that can be used in a multi-threaded=20 context without having explicit locks. The obvious exemplars to indicate the way are ConcurrentHashMap in Java and NumPy array. (cf. other thread talking about these quasi-weird array data structures.) NumPy array is an opaque data structure that should never be accessed in any way other than the functions and higher-order functions from the library. It is a nice design, works well enough for data scientists, quants, bioinformatics people to think it is great, but fundamentally is seriously slow. If D could provide data structures that did NumPy/SciPy/Pandas things significantly faster than NumPy/SciPy/Pandas, there would be traction.=C2=A0 In this sense std.concurrent, std.parallelism, and std.datastructures (?) whilst almost certainly remaining separate, must be able to interwork. The alternative is the sort of hack that goes on in Java where data structures are sequential but you can provide thread-safe versions. This is fine for small data structures, but is not acceptable for large ones in a multicore situation. =C2=A0Hence ConcurrentHashMap, and the ilke. Then there is the question whether to try and do the sort of thing Chapel and X10 are doing. They have the ideas of domain and places which allow for partitioned arrays that can be mapped to clusters of multicore, multiprocessor machines =E2=80=94 Partitioned Global Address Spa= ce. IBM have now released their APGAS stuff over Hazelcast for Java users. This will begin to challenge Apache Spark (and Hadoop). Apache Spark is in many ways like NumPy in it's architecture, an opaque data N-dimensional array operated on by functions and higher-order functions. Obviously I am conflicted here: I use Go for networking (but mostly because I earn money running learning workshops), quite like Rust because it is the fastest language currently on my microbenchmarks, like D because it's nice, love Chapel because it is great (better than D in so many ways), sort of like X10 (because it is a bit Scala like and can be JVM or native), but end up having to work on some C++ codebases. I am not entirely sure D can compete with Chapel in HPC and increasingly the Python-verse. Laeeth and others are championing D instead of Python, but really the competition is Python/Chapel vs. Python/NumPy/SciPy/Pandas. Unless that is D can get the Pandas style data structures. Which brings my ramblings back on point.=C2=A0 --=20 Russel. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.n= et 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Oct 21 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 09:01 AM, Russel Winder via Digitalmars-d wrote:
 I believe (currently, I am open to being re-educated) that most of the
 rest of the world calls these persistent data structures, despite the
 title of Okasaki's thesis. I am not sure I like either of the labels
 "functional" or "persistent", there is little affordance with the
 concept underneath.
OK. We should go with the more widespread name.
 By default eager value containers are mutable. They should support
 immutable and const meaningfully.
Is there a need for separate eager structures explicity? Is it not enough for all structures to be lazy with there being a pull operation?
Well it is but I wanted to clarify where STL-style containers fit.
 N-dimensional arrays, N-dimensional dynamic array, singly-linked list,
 doubly-linked list, hash map (aka dictionary, associative array,…),
 red-black tree, 2-3 tree, doubly-linked tree, tree map, b-tree. And no
 doubt a few others will be proposed since they are classic, appear in
 undergraduate courses, and are actually used for real.
These are orthogonal on the kinds I discussed. So we have container topologies (which you enumerate a few of) and container kinds, which concerns copying semantics of the entire containers.
 However these are classic sequential data structures.
Hashes and some of the trees would actually be associative data structures.
 We should be
 looking to support data structures that can be used in a multi-threaded
 context without having explicit locks. The obvious exemplars to
 indicate the way are ConcurrentHashMap in Java and NumPy array. (cf.
 other thread talking about these quasi-weird array data structures.)
 NumPy array is an opaque data structure that should never be accessed
 in any way other than the functions and higher-order functions from the
 library. It is a nice design, works well enough for data scientists,
 quants, bioinformatics people to think it is great, but fundamentally
 is seriously slow. If D could provide data structures that did
 NumPy/SciPy/Pandas things significantly faster than NumPy/SciPy/Pandas,
 there would be traction.
Cool thoughts, thanks. Those would have their own APIs, separate from mainstream containers.
 Then there is the question whether to try and do the sort of thing
 Chapel and X10 are doing. They have the ideas of domain and places
 which allow for partitioned arrays that can be mapped to clusters of
 multicore, multiprocessor machines — Partitioned Global Address Space.
 IBM have now released their APGAS stuff over Hazelcast for Java users.
 This will begin to challenge Apache Spark (and Hadoop).
We don't support PGAS at language level, but I'll need to look into how APGAS works with Java.
 Obviously I am conflicted here: I use Go for networking (but mostly
 because I earn money running learning workshops), quite like Rust
 because it is the fastest language currently on my microbenchmarks,
 like D because it's nice, love Chapel because it is great (better than
 D in so many ways), sort of like X10 (because it is a bit Scala like
 and can be JVM or native), but end up having to work on some C++
 codebases. I am not entirely sure D can compete with Chapel in HPC and
 increasingly the Python-verse. Laeeth and others are championing D
 instead of Python, but really the competition is Python/Chapel vs.
 Python/NumPy/SciPy/Pandas. Unless that is D can get the Pandas style
 data structures. Which brings my ramblings back on point.
My finance folks also rave about Pandas. I wish I could fork myself to look into it. Nevertheless, what I'm working on now should help libraries such as Pandas for D. We have a large language but are unclear on recipe-style idioms for writing library code. Andrei
Oct 21 2015
next sibling parent reply Russel Winder via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wed, 2015-10-21 at 09:11 -0400, Andrei Alexandrescu via Digitalmars-d
wrote:
=20
[=E2=80=A6]
 My finance folks also rave about Pandas. I wish I could fork myself to=
=20
 look into it.
Pandas is what makes Python a viable competitor to R. Most data science people will use one or the other these days. Though some (with budgets) wil= l use Matlab or Mathematica.=C2=A0
 Nevertheless, what I'm working on now should help libraries such as=20
 Pandas for D. We have a large language but are unclear on recipe-style=
=20
 idioms for writing library code.
=20
Can I suggest that we avoid "should" and ensure that we have more of a "will". =C2=A0Instead of a bottom up approach, we perhaps need a top-down approach: Applications programmers do X, Y, Z, that are best support by dat= a structures A, B, C, and A, B, and C are realized by library architecture = =CE=B1, =CE=B2, =CE=B3. --=20 Russel. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D Dr Russel Winder t:+44 20 7585 2200 voip:sip: russel.winder ekiga.net 41 Buckmaster Road m:+44 7770 465 077 xmpp:russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype:russel_winder
Oct 21 2015
parent jmh530 <john.michael.hall gmail.com> writes:
On Wednesday, 21 October 2015 at 15:44:36 UTC, Russel Winder 
wrote:
 On Wed, 2015-10-21 at 09:11 -0400, Andrei Alexandrescu via 
 Digitalmars-d wrote:
 
[…]
 My finance folks also rave about Pandas. I wish I could fork 
 myself to look into it.
Pandas is what makes Python a viable competitor to R. Most data science people will use one or the other these days. Though some (with budgets) will use Matlab or Mathematica.
Yeah, R has had the functionality of what Pandas provides for a while. Data frames and zoo/xts cover most of Pandas. I think there has made some effort to get some of the functionality of dplyr as well (blaze).
Oct 21 2015
prev sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Wed, Oct 21, 2015 at 09:11:38AM -0400, Andrei Alexandrescu via Digitalmars-d
wrote:
[...]
 My finance folks also rave about Pandas. I wish I could fork myself to
 look into it.
[...] Unfortunately, forking a human process takes 9 months to spawn the new process (slow OS, y'know), and the new process's module constructor takes about 18 or so years to run before it's ready for use. :-D Also, the specs are ambiguous in some key areas of the semantics, so implementations in practice don't quite manage to replicate the original process exactly. T -- Chance favours the prepared mind. -- Louis Pasteur
Oct 21 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 12:12 PM, H. S. Teoh via Digitalmars-d wrote:
 On Wed, Oct 21, 2015 at 09:11:38AM -0400, Andrei Alexandrescu via
Digitalmars-d wrote:
 [...]
 My finance folks also rave about Pandas. I wish I could fork myself to
 look into it.
[...] Unfortunately, forking a human process takes 9 months to spawn the new process (slow OS, y'know), and the new process's module constructor takes about 18 or so years to run before it's ready for use. :-D Also, the specs are ambiguous in some key areas of the semantics, so implementations in practice don't quite manage to replicate the original process exactly.
As one with two spawned forks underway, I totally agree. Besides, early versions tend to consume a lot of resources, emit many nonmaskable interrupts, and leak a lot. -- Andrei
Oct 21 2015
prev sibling next sibling parent reply Andrea Fontana <nospam example.com> writes:
On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
Alexandrescu wrote:
 I'll attempt to implement a few versions of each and see what 
 they look like. The question here is what containers are of 
 interest for D's standard library.


 Andrei
Tree (binary, quad, octo, r/b, etc...), graph (directed, undirected, sparse, weighted, etc...) have my votes. They enable a lot of algorithms to be implemented.
Oct 21 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 09:13 AM, Andrea Fontana wrote:
 On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei Alexandrescu wrote:
 I'll attempt to implement a few versions of each and see what they
 look like. The question here is what containers are of interest for
 D's standard library.


 Andrei
Tree (binary, quad, octo, r/b, etc...), graph (directed, undirected, sparse, weighted, etc...) have my votes. They enable a lot of algorithms to be implemented.
As I also replied to Russel, I am now discussing semantics of container values. -- Andrei
Oct 21 2015
prev sibling next sibling parent reply Robert burner Schadek <rburners gmail.com> writes:
On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
Alexandrescu wrote:
 I'm finally getting the cycles to get to thinking about Design 
 by Introspection containers.
What do you have in mind about the Design by Introspection (DyI, DbI is taken) for the container? How do you plan to use the allocators? Have the container create and handle the allocator, pass it at container construction, or (YOUR IDEA HERE)? anyway, container yuhu http://www.alfabetajuega.com/multimedia/imagenes/201310/53112.homer_yuhu_simpsons.jpg
Oct 21 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 09:46 AM, Robert burner Schadek wrote:
 On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei Alexandrescu wrote:
 I'm finally getting the cycles to get to thinking about Design by
 Introspection containers.
What do you have in mind about the Design by Introspection (DyI, DbI is taken) for the container?
Containers will obey subsets of a nomenclature of primitives.
 How do you plan to use the allocators? Have the container create and
 handle the allocator, pass it at container construction, or (YOUR IDEA
 HERE)?
Container will pick the current allocator reference, or get it as a creation parameters, and store it for the life of the container. Andrei
Oct 21 2015
parent reply Robert burner Schadek <rburners gmail.com> writes:
On Wednesday, 21 October 2015 at 14:20:23 UTC, Andrei 
Alexandrescu wrote:
 Containers will obey subsets of a nomenclature of primitives.
Just to be crystal clear, something like this? void fun(Container)(ref Container c) if (hasAppend!Container) { // append stuff to c }
Oct 21 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 10:51 AM, Robert burner Schadek wrote:
 On Wednesday, 21 October 2015 at 14:20:23 UTC, Andrei Alexandrescu wrote:
 Containers will obey subsets of a nomenclature of primitives.
Just to be crystal clear, something like this? void fun(Container)(ref Container c) if (hasAppend!Container) { // append stuff to c }
Even simpler, hasMethod!(Container, "append") -- Andrei
Oct 21 2015
parent reply Robert burner Schadek <rburners gmail.com> writes:
On Wednesday, 21 October 2015 at 17:23:15 UTC, Andrei 
Alexandrescu wrote:
 Even simpler, hasMethod!(Container, "append") -- Andrei
I know this goes against your talk at DConf, but having to write string parameters does not feel good. I'm will properly not be the only one who will mistype "apend" and wonder why the other template function will be chosen. I rather have the compiler scream at me telling me there is no symbol hasApend. And hasAppend!Container is less typing than hasMethod!(Container, "append").
Oct 21 2015
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, 21 October 2015 at 18:24:30 UTC, Robert burner 
Schadek wrote:
 On Wednesday, 21 October 2015 at 17:23:15 UTC, Andrei 
 Alexandrescu wrote:
 Even simpler, hasMethod!(Container, "append") -- Andrei
I know this goes against your talk at DConf, but having to write string parameters does not feel good. I'm will properly not be the only one who will mistype "apend" and wonder why the other template function will be chosen. I rather have the compiler scream at me telling me there is no symbol hasApend. And hasAppend!Container is less typing than hasMethod!(Container, "append").
The other concern is that hasMethod isn't going to be checking anything other than the name, whereas a hasAppend could actually check that the function accepts the right arguments and returns the correct type. And it's not like the list of the functions to check for is going to be infinite. It needs to be a known list of functions where each of those functions has a signature that meets certain requirements. You can't just be checking for a random function name and expect it to do what you want. So, having a list of explicit traits to use for testing for the expected set of functions will both allow for the tests to be more thorough than simply checking the name, _and_ it will serve as a way to help document what the list of expected functions is for a particular domain. I really think that using hasMethod by itself like that is getting too ad hoc and doesn't really benefit us over having an explicit list of traits for the specific domain that we're dealing with. I totally buy that testing for each of the specific functions rather than trying to put all of that information in the type itself (e.g. ContainerWithAppendAndRemove) simply isn't going to scale, but I don't at all buy that using hasMethod to test for the existence of member functions is a good way to go. - Jonathan M Davis
Oct 21 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 02:32 PM, Jonathan M Davis wrote:
 On Wednesday, 21 October 2015 at 18:24:30 UTC, Robert burner Schadek wrote:
 On Wednesday, 21 October 2015 at 17:23:15 UTC, Andrei Alexandrescu wrote:
 Even simpler, hasMethod!(Container, "append") -- Andrei
I know this goes against your talk at DConf, but having to write string parameters does not feel good. I'm will properly not be the only one who will mistype "apend" and wonder why the other template function will be chosen. I rather have the compiler scream at me telling me there is no symbol hasApend. And hasAppend!Container is less typing than hasMethod!(Container, "append").
The other concern is that hasMethod isn't going to be checking anything other than the name, whereas a hasAppend could actually check that the function accepts the right arguments and returns the correct type. And it's not like the list of the functions to check for is going to be infinite. It needs to be a known list of functions where each of those functions has a signature that meets certain requirements. You can't just be checking for a random function name and expect it to do what you want. So, having a list of explicit traits to use for testing for the expected set of functions will both allow for the tests to be more thorough than simply checking the name, _and_ it will serve as a way to help document what the list of expected functions is for a particular domain. I really think that using hasMethod by itself like that is getting too ad hoc and doesn't really benefit us over having an explicit list of traits for the specific domain that we're dealing with. I totally buy that testing for each of the specific functions rather than trying to put all of that information in the type itself (e.g. ContainerWithAppendAndRemove) simply isn't going to scale, but I don't at all buy that using hasMethod to test for the existence of member functions is a good way to go.
I'd say let's first have a Pope before becoming more Catholic than him. -- Andrei
Oct 21 2015
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, 21 October 2015 at 19:19:23 UTC, Andrei 
Alexandrescu wrote:
 I'd say let's first have a Pope before becoming more Catholic 
 than him. -- Andrei
I confess that I really don't understand that one. - Jonathan M Davis
Oct 21 2015
next sibling parent MobPassenger <MobPassenger nowhere.fi> writes:
On Wednesday, 21 October 2015 at 19:38:37 UTC, Jonathan M Davis 
wrote:
 On Wednesday, 21 October 2015 at 19:19:23 UTC, Andrei 
 Alexandrescu wrote:
 I'd say let's first have a Pope before becoming more Catholic 
 than him. -- Andrei
I confess that I really don't understand that one. - Jonathan M Davis
It sounds like he say that you are a bit too orthodox when you argue about the way to test the traits that a Container have.
Oct 21 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 03:38 PM, Jonathan M Davis wrote:
 On Wednesday, 21 October 2015 at 19:19:23 UTC, Andrei Alexandrescu wrote:
 I'd say let's first have a Pope before becoming more Catholic than
 him. -- Andrei
I confess that I really don't understand that one.
"More Catholic than the Pope" = overdoing something all too pedantically. What I mean is: let's get things started and if there's any need for isXxx we'll add them. -- Andrei
Oct 21 2015
next sibling parent Robert burner Schadek <rburners gmail.com> writes:
On Wednesday, 21 October 2015 at 20:06:41 UTC, Andrei 
Alexandrescu wrote:
 "More Catholic than the Pope" = overdoing something all too 
 pedantically. What I mean is: let's get things started and if 
 there's any need for isXxx we'll add them. -- Andrei
+1
Oct 21 2015
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, 21 October 2015 at 20:06:41 UTC, Andrei 
Alexandrescu wrote:
 On 10/21/2015 03:38 PM, Jonathan M Davis wrote:
 On Wednesday, 21 October 2015 at 19:19:23 UTC, Andrei 
 Alexandrescu wrote:
 I'd say let's first have a Pope before becoming more Catholic 
 than
 him. -- Andrei
I confess that I really don't understand that one.
"More Catholic than the Pope" = overdoing something all too pedantically. What I mean is: let's get things started and if there's any need for isXxx we'll add them. -- Andrei
In principle, I agree with the sentiment, but I would have thought that our experience thus far already showed that being imprecise with code involving compile time introspection was problematic at best. This sort of thing in static ifs probably isn't as bad as it would likely be in template constraints, but it seems like way too often we end up with problems like user code compiling at first and then not compiling later due to a small change in Phobos or dmd, just because someone did something differently from what we expected, and the template constraints or static ifs didn't take it into account properly. - Jonathan M Davis
Oct 22 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 02:24 PM, Robert burner Schadek wrote:
 On Wednesday, 21 October 2015 at 17:23:15 UTC, Andrei Alexandrescu wrote:
 Even simpler, hasMethod!(Container, "append") -- Andrei
I know this goes against your talk at DConf, but having to write string parameters does not feel good. I'm will properly not be the only one who will mistype "apend" and wonder why the other template function will be chosen. I rather have the compiler scream at me telling me there is no symbol hasApend. And hasAppend!Container is less typing than hasMethod!(Container, "append").
Yah, but defining isXxx for dozens of Xxx doesn't sit well either. -- Andrei
Oct 21 2015
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, 21 October 2015 at 19:18:44 UTC, Andrei 
Alexandrescu wrote:
 On 10/21/2015 02:24 PM, Robert burner Schadek wrote:
 On Wednesday, 21 October 2015 at 17:23:15 UTC, Andrei 
 Alexandrescu wrote:
 Even simpler, hasMethod!(Container, "append") -- Andrei
I know this goes against your talk at DConf, but having to write string parameters does not feel good. I'm will properly not be the only one who will mistype "apend" and wonder why the other template function will be chosen. I rather have the compiler scream at me telling me there is no symbol hasApend. And hasAppend!Container is less typing than hasMethod!(Container, "append").
Yah, but defining isXxx for dozens of Xxx doesn't sit well either. -- Andrei
So, instead we make it ad hoc where only the name is tested rather than anything about what the function is or does, and we make it that much harder for folks to know what the vocabulary list of functions is, because there's no list of traits to test for them and just a table in some piece of documentation somewhere? I just don't see this scaling well if we're not more rigorous about it than hasMethod!(Container, "append"). If all of the containers are in Phobos and nothing outside of Phobos is actually testing for any of these methods, then it's a much smaller issue, but if any of this method testing is going to happen outside of Phobos, then I definitely think that it's a bad idea to be this ad hoc about it. - Jonathan M Davis
Oct 21 2015
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
Alexandrescu wrote:
 I'm finally getting the cycles to get to thinking about Design 
 by Introspection containers. First off, there are several 
 general categories of containers. I think D should support all 
 properly. One question is which we go for in the standard 
 library.

 1. Functional containers.
I fully expect that these have their place, but I honestly have no idea what they would be. When I've used functional languages, I've only ever found these attributes to be a royal pain to deal with, not a benefit. From what I've seen, containers are the sort of thing that almost always always need to be mutable to be of any real benefit. Upon occasion, constructing a container up front and then never tweaking it after that is useful, but that's pretty rare from what I've seen. The only cases that I can think of where this could be really beneficial would be something like strings, and we're using arrays for those currently (though they are arguably functional containers given that they have immutable elements).
 2. Reference containers.
These are where it's at IMHO. 99.999999% this is what makes sense.
 3. Eager value containers.
_Maybe_ this makes sense for specific container types, but in general, it's a horrible idea IMHO. Almost all containers involve allocating something on the heap internally, so the fact that they're treated as values doesn't avoid heap allocations, and reference-counting reference containers solves the problem of the containers living past the end of the lifetime of whatever owns them. And having value type containers is incredibly error-prone - both from an efficiency standpoint and correctness standpoint. It's _way_ too easy to copy them when you don't mean to, and simple stuff like vector<T> foo() {...} for(auto iter = foo().begin(); iter != foo().end(); ++iter) {...} ends up doing nasty things, because you have iterators (or ranges) to a container that's already been destroyed. Honestly, unless you're counting something like a point or tuple as a container, I really don't see any value in these sort of containers. They're just too error-prone without adding any real value.
 4. Copy-on-write containers.
This could be interesting for some applications (probably more so than functional containers), but I would expect that it would only really be useful for very specific containers. I certainly wouldn't want to end up with a copy of my vector or list because I added a value to it. COW for strings makes a lot of sense, because they don't tend to get mutated much (which is also why string is immutable(char)[]). But since we're already using arrays for strings, a COW string would then be for special cases only. Overall, I think that we should focus on getting good reference containers while leaving the door open for cool stuff from the other container types. It's the reference containers that most programs are going to need, whereas I expect that the others are more likely to be nice-to-haves for a minority of applications and outright useless for the majority. - Jonathan M Davis
Oct 21 2015
next sibling parent reply Ice Cream Man <thegreatone google.com> writes:
On Wednesday, 21 October 2015 at 14:06:43 UTC, Jonathan M Davis 
wrote:
 1. Functional containers.
I fully expect that these have their place, but I honestly have no idea what they would be. When I've used functional languages, I've only ever found these attributes to be a royal pain to deal with, not a benefit. From what I've seen, containers are the sort of thing that almost always always need to be mutable to be of any real benefit. Upon occasion, constructing a container up front and then never tweaking it after that is useful, but that's pretty rare from what I've seen. The only cases that I can think of where this could be really beneficial would be something like strings, and we're using arrays for those currently (though they are arguably functional containers given that they have immutable elements).
I've found immutable containers useful when working with configuration files. There are only a few places in a program where you want to actively change values in a configuration files (configure the values). For these instances it's useful for the GUI or whatever to grab a mutable container to work with. For all other areas, immutable containers are very helpful in ensuring nobody accidentally modifies something they shouldn't be outside of the provided sandboxes.
Oct 21 2015
parent Ice Cream Man <thegreatone google.com> writes:
On Wednesday, 21 October 2015 at 15:18:08 UTC, Ice Cream Man 
wrote:
 On Wednesday, 21 October 2015 at 14:06:43 UTC, Jonathan M Davis 
 wrote:
 [...]
I've found immutable containers useful when working with configuration files. There are only a few places in a program where you want to actively change values in a configuration files (configure the values). For these instances it's useful for the GUI or whatever to grab a mutable container to work with. For all other areas, immutable containers are very helpful in ensuring nobody accidentally modifies something they shouldn't be outside of the provided sandboxes.
Actually, I think functional containers are probably more often than not the right tool for whatever it is you are doing. They just aren't convenient, because you might have to rethinking the architecture.
Oct 21 2015
prev sibling next sibling parent reply Russel Winder via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wed, 2015-10-21 at 14:06 +0000, Jonathan M Davis via Digitalmars-d wrote=
:
=20
[=E2=80=A6]
 1. Functional containers.
=20 I fully expect that these have their place, but I honestly have=20 no idea what they would be. When I've used functional languages,=20 I've only ever found these attributes to be a royal pain to deal=20 with, not a benefit. From what I've seen, containers are the sort=20 of thing that almost always always need to be mutable to be of=20 any real benefit. Upon occasion, constructing a container up=20 front and then never tweaking it after that is useful, but that's=20 pretty rare from what I've seen. =20 The only cases that I can think of where this could be really=20 beneficial would be something like strings, and we're using=20 arrays for those currently (though they are arguably functional=20 containers given that they have immutable elements).
I am confused as to why you would find these functional/persistent data structures to be a problem in functional languages. The whole point of them is they can be easily shared without any locks. In effect each amendment of the structure creates a fork (effectively a copy but without the copy bit) of it. This goes hand in hand with the functional, and especially tail recursive computational model. The Groovy team is currently debating adding persistent data structures to the Groovy armoury. Clojure and Scala have had persistent data structures for ages. The Clojure ones are really good. The Scala ones have some issues so there is currently discussion of a third rewrite.
 2. Reference containers.
=20 These are where it's at IMHO. 99.999999% this is what makes sense.
Except in a concurrent and parallel world! For big mutable data structures you end up creating agents (or so we can use hyper trendy nomenclature, pico-services) to avoid messing around with locks, mutexes, etc. the use of which generally kills performance.
 3. Eager value containers.
=20 =20
[=E2=80=A6] As noted in an earlier email, I am not yes convinced by this one.
 4. Copy-on-write containers.
=20 This could be interesting for some applications (probably more so=20 than functional containers), but I would expect that it would=20 only really be useful for very specific containers. I certainly=20 wouldn't want to end up with a copy of my vector or list because=20 I added a value to it. COW for strings makes a lot of sense,=20 because they don't tend to get mutated much (which is also why=20 string is immutable(char)[]). But since we're already using=20 arrays for strings, a COW string would then be for special cases=20 only.
I'd say the opposite. I would suggest that persistent/functional data structures would be more generally useful than COW ones. =C2=A0
 Overall, I think that we should focus on getting good reference=20
 containers while leaving the door open for cool stuff from the=20
 other container types. It's the reference containers that most=20
 programs are going to need, whereas I expect that the others are=20
 more likely to be nice-to-haves for a minority of applications=20
 and outright useless for the majority.
I am not convinced by this argument. Yes these are the type of containers C++/D/=E2=80=A6 programmers are used to and have a lot of code using, but a= re they really the ones that should be used. Experience from Clojure and Scala is that persistent/functional data structures lead to much nicer/easier concurrent and parallel code.=C2=A0 --=20 Russel. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D Dr Russel Winder t:+44 20 7585 2200 voip:sip: russel.winder ekiga.net 41 Buckmaster Road m:+44 7770 465 077 xmpp:russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype:russel_winder
Oct 21 2015
next sibling parent Ice Cream Man <thegreatone google.com> writes:
On Wednesday, 21 October 2015 at 15:34:14 UTC, Russel Winder 
wrote:
 On Wed, 2015-10-21 at 14:06 +0000, Jonathan M Davis via 
 Digitalmars-d wrote:
 [...]
[…]
 [...]
I am confused as to why you would find these functional/persistent data structures to be a problem in functional languages. The whole point of them is they can be easily shared without any locks. In effect each amendment of the structure creates a fork (effectively a copy but without the copy bit) of it. This goes hand in hand with the functional, and especially tail recursive computational model. The Groovy team is currently debating adding persistent data structures to the Groovy armoury. Clojure and Scala have had persistent data structures for ages. The Clojure ones are really good. The Scala ones have some issues so there is currently discussion of a third rewrite.
 [...]
Except in a concurrent and parallel world! For big mutable data structures you end up creating agents (or so we can use hyper trendy nomenclature, pico-services) to avoid messing around with locks, mutexes, etc. the use of which generally kills performance.
 [...]
[…] As noted in an earlier email, I am not yes convinced by this one.
 [...]
I'd say the opposite. I would suggest that persistent/functional data structures would be more generally useful than COW ones.
 [...]
I am not convinced by this argument. Yes these are the type of containers C++/D/… programmers are used to and have a lot of code using, but are they really the ones that should be used. Experience from Clojure and Scala is that persistent/functional data structures lead to much nicer/easier concurrent and parallel code.
 [...]
These are where it's at IMHO. 99.999999% this is what makes sense.
Except in a concurrent and parallel world! For big mutable data structures you end up creating agents (or so we can use hyper trendy nomenclature, pico-services) to avoid messing around with locks, mutexes, etc. the use of which generally kills performance. I actually find these annoying in C#. People modify things they shouldn't be all of the time. Which makes errors so much more prevalent. Every property that returns a List<T> is frequently exposed for the world to use. The best workaround I've found is to use interfaces that restrict what methods they have access to, but even then people resort to just casting it away. I'd prefer immutable by default. Personally.
Oct 21 2015
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, 21 October 2015 at 15:34:14 UTC, Russel Winder 
wrote:
 On Wed, 2015-10-21 at 14:06 +0000, Jonathan M Davis via 
 Digitalmars-d wrote:
 
[…]
 1. Functional containers.
I fully expect that these have their place, but I honestly have no idea what they would be. When I've used functional languages, I've only ever found these attributes to be a royal pain to deal with, not a benefit. From what I've seen, containers are the sort of thing that almost always always need to be mutable to be of any real benefit. Upon occasion, constructing a container up front and then never tweaking it after that is useful, but that's pretty rare from what I've seen. The only cases that I can think of where this could be really beneficial would be something like strings, and we're using arrays for those currently (though they are arguably functional containers given that they have immutable elements).
I am confused as to why you would find these functional/persistent data structures to be a problem in functional languages. The whole point of them is they can be easily shared without any locks. In effect each amendment of the structure creates a fork (effectively a copy but without the copy bit) of it. This goes hand in hand with the functional, and especially tail recursive computational model.
My experience with immutable containers is that their performance is trash precisely because you can't mutate them. They end up being copied just to add elements or to change elements. And even if their internals are smart and share data as much as possible (though that starts moving into COW pretty quickly), the efficiency is still worse than having a properly mutable container would be. I'm sure that there are use cases where they would be useful, but I've sure never had one. I've found that functional languages can be great from an algorithmic perspective, but for data structures? Not so much. And I'm by no means against having data structures like this in Phobos, but I think that having normal, reference containers is far more useful for the common case. Certainly, it's what most programs currently use and what most programmers expect. I'd much prefer that we get a solid set of reference containers working than spend a lot of time worrying about more exotic containers up front. IMHO, they can wait. We'll see what the future may hold, and I could certainly end up being surprised, but I fully expect that I'll never use any functional containers if they're put into Phobos. They're just too unwieldy and inefficient. - Jonathan M Davis
Oct 21 2015
next sibling parent reply Ice Cream Man <thegreatone google.com> writes:
On Wednesday, 21 October 2015 at 16:25:19 UTC, Jonathan M Davis 
wrote:
 They're just too unwieldy and inefficient.

 - Jonathan M Davis
Only if you don't know how to use them. They are very wieldy, efficient AND safe, if you do know how to swing the ax. Its all about learning to work with them.
Oct 21 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 12:34 PM, Ice Cream Man wrote:
 On Wednesday, 21 October 2015 at 16:25:19 UTC, Jonathan M Davis wrote:
 They're just too unwieldy and inefficient.

 - Jonathan M Davis
Only if you don't know how to use them. They are very wieldy, efficient AND safe, if you do know how to swing the ax. Its all about learning to work with them.
Yep, and part of learning is knowing when they shouldn't be used. -- Andrei
Oct 21 2015
parent Ice Cream Man <thegreatone google.com> writes:
On Wednesday, 21 October 2015 at 18:50:05 UTC, Andrei 
Alexandrescu wrote:
 On 10/21/2015 12:34 PM, Ice Cream Man wrote:
 On Wednesday, 21 October 2015 at 16:25:19 UTC, Jonathan M 
 Davis wrote:
 They're just too unwieldy and inefficient.

 - Jonathan M Davis
Only if you don't know how to use them. They are very wieldy, efficient AND safe, if you do know how to swing the ax. Its all about learning to work with them.
Yep, and part of learning is knowing when they shouldn't be used. -- Andrei
I definitely won't disagree with that.
Oct 21 2015
prev sibling next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 10/21/2015 06:25 PM, Jonathan M Davis wrote:
 My experience with immutable containers is that their performance is
 trash precisely because you can't mutate them. They end up being copied
 just to add elements or to change elements.
I don't think this is what's being proposed here. Updates are fast.
 And even if their internals
 are smart and share data as much as possible (though that starts moving
 into COW pretty quickly),
COW copies the entire container.
 the efficiency is still worse than having a
 properly mutable container would be.
Not if you need access to older versions. If this is the case, then the "properly" mutable container carries a lot of runtime and memory overhead due to copying. Also, the difference is not very large for good implementations.
 I'm sure that there are use cases
 where they would be useful, but I've sure never had one. I've found that
 functional languages can be great from an algorithmic perspective, but
 for data structures? Not so much.
It's not tied to the language.
Oct 21 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 12:25 PM, Jonathan M Davis wrote:
 My experience with immutable containers is that their performance is
 trash precisely because you can't mutate them.
That's actually the experience in the Scala community. Over and again people start with immutable containers all over the place because they're cool, and end up with mutable containers because they work. -- Andrei
Oct 21 2015
next sibling parent Russel Winder via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wed, 2015-10-21 at 14:49 -0400, Andrei Alexandrescu via Digitalmars-
d wrote:
=20
[=E2=80=A6]
 That's actually the experience in the Scala community. Over and again
 people start with immutable containers all over the place because=20
 they're cool, and end up with mutable containers because they work. -
=20
For some applications, I am sure this true. For the majority no. I have no doubt that for some people fashion and trendy are decision making criteria when clearly they should be thinking about efficacy and efficiency. However it is important to remember that persistent/functional data structures are generally both efficacious and efficient in a fine-grain parallel context. Sadly a lot of this is advocacy research because there is no systematic, statistically significant research that is credible. Scala might have been a nice context to try some experimentation but they still do not have really good data structure implementations. Hence the recent notification of another rewrite. --=20 Russel. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.n= et 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Oct 22 2015
prev sibling parent reply Ulrich =?UTF-8?B?S8O8dHRsZXI=?= <kuettler gmail.com> writes:
On Wednesday, 21 October 2015 at 18:49:26 UTC, Andrei 
Alexandrescu wrote:
 On 10/21/2015 12:25 PM, Jonathan M Davis wrote:
 My experience with immutable containers is that their 
 performance is
 trash precisely because you can't mutate them.
That's actually the experience in the Scala community. Over and again people start with immutable containers all over the place because they're cool, and end up with mutable containers because they work. -- Andrei
Ranges and loops. Same story. Ranges are cool, loops get stuff done.
Oct 26 2015
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10/26/2015 08:31 PM, Ulrich Küttler wrote:
 On Wednesday, 21 October 2015 at 18:49:26 UTC, Andrei Alexandrescu wrote:
 On 10/21/2015 12:25 PM, Jonathan M Davis wrote:
 My experience with immutable containers is that their performance is
 trash precisely because you can't mutate them.
That's actually the experience in the Scala community. Over and again people start with immutable containers all over the place because they're cool, and end up with mutable containers because they work. -- Andrei
Ranges and loops. Same story. Ranges are cool, loops get stuff done.
This kind of reasoning sounds cool but is ultimately misguided. (I don't think the stories are even analogous.) Persistent containers have a /different interface/ than mutable containers and hence can be used in different algorithms, where they can help getting low asymptotic resource usage. Obviously there is not much point in using persistent containers just because one considers them "cool" if what one really wants is a mutable container. Ranges can be iterated, loops iterate them. If one wants to get stuff done, one uses library primitives when they apply and implements the remaining functionality oneself. When one notices that certain patterns begin to repeat, one will sometimes take a short time to factor them out in order to make progress faster. If they are patterns of iteration, this means writing an opApply or sometimes a range.
Oct 26 2015
parent Ulrich =?UTF-8?B?S8O8dHRsZXI=?= <kuettler gmail.com> writes:
On Monday, 26 October 2015 at 20:46:21 UTC, Timon Gehr wrote:
 On 10/26/2015 08:31 PM, Ulrich Küttler wrote:
 On Wednesday, 21 October 2015 at 18:49:26 UTC, Andrei 
 Alexandrescu wrote:
 On 10/21/2015 12:25 PM, Jonathan M Davis wrote:
 My experience with immutable containers is that their 
 performance is
 trash precisely because you can't mutate them.
That's actually the experience in the Scala community. Over and again people start with immutable containers all over the place because they're cool, and end up with mutable containers because they work. -- Andrei
Ranges and loops. Same story. Ranges are cool, loops get stuff done.
This kind of reasoning sounds cool but is ultimately misguided. (I don't think the stories are even analogous.)
Nobody argues against ranges. The argument is: Designing range-based code results in something very different from traditional loop-based code. There are very good reasons why the effort is worthwhile, still, the effort is real. (See the calendar example.) Even those library primitives do not come for free. The same is true about containers. The container variant is a design choice, not an implementation detail. Now, are persistent containers worth the effort? What would a design based on persistent containers look like? Is there a good way to implement them in D? Who knows.
Oct 26 2015
prev sibling next sibling parent rsw0x <anonymous anonymous.com> writes:
On Monday, 26 October 2015 at 19:31:26 UTC, Ulrich Küttler wrote:
 On Wednesday, 21 October 2015 at 18:49:26 UTC, Andrei 
 Alexandrescu wrote:
 On 10/21/2015 12:25 PM, Jonathan M Davis wrote:
 My experience with immutable containers is that their 
 performance is
 trash precisely because you can't mutate them.
That's actually the experience in the Scala community. Over and again people start with immutable containers all over the place because they're cool, and end up with mutable containers because they work. -- Andrei
Ranges and loops. Same story. Ranges are cool, loops get stuff done.
Heavily disagree. If ranges are only cool, java 8 streams wouldn't be so massively successful and ranges wouldn't be part of C++17. D's ranges are one of the main reasons I use D.
Oct 26 2015
prev sibling parent lobo <swamplobo gmail.com> writes:
On Monday, 26 October 2015 at 19:31:26 UTC, Ulrich Küttler wrote:
 On Wednesday, 21 October 2015 at 18:49:26 UTC, Andrei 
 Alexandrescu wrote:
 On 10/21/2015 12:25 PM, Jonathan M Davis wrote:
 My experience with immutable containers is that their 
 performance is
 trash precisely because you can't mutate them.
That's actually the experience in the Scala community. Over and again people start with immutable containers all over the place because they're cool, and end up with mutable containers because they work. -- Andrei
Ranges and loops. Same story. Ranges are cool, loops get stuff done.
You are conflating ranges and iteration. A range needs something to drive it, whether it be an explicit loop or some higher abstraction from std.algorithm. bye, lobo
Oct 26 2015
prev sibling parent Kagamin <spam here.lot> writes:
On Wednesday, 21 October 2015 at 16:25:19 UTC, Jonathan M Davis 
wrote:
 My experience with immutable containers is that their 
 performance is trash precisely because you can't mutate them.
Well, in context of concurrency immutable containers compete with concurrent containers, not with mutable single-threaded ones. On Wednesday, 21 October 2015 at 14:06:43 UTC, Jonathan M Davis wrote:
 3. Eager value containers.
_Maybe_ this makes sense for specific container types, but in general, it's a horrible idea IMHO. Almost all containers involve allocating something on the heap internally, so the fact that they're treated as values doesn't avoid heap allocations, and reference-counting reference containers solves the problem of the containers living past the end of the lifetime of whatever owns them. And having value type containers is incredibly error-prone - both from an efficiency standpoint and correctness standpoint.
I suppose stl containers are value types because everything is value type in C++, they're just consistent. And then you have 3 or so ways to create a value type and 6 ways to pass it around by reference, and you choose what you want.
Oct 22 2015
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10/21/2015 01:05 PM, Andrei Alexandrescu wrote:
 I'm finally getting the cycles to get to thinking about Design by
 Introspection containers. First off, there are several general
 categories of containers. I think D should support all properly. One
 question is which we go for in the standard library.

 1. Functional containers.

 These are immutable; once created, neither their topology nor their
 elements may be observably changed. Manipulating a container entails
 creating an entire new container, often based on an existing container
 (e.g. append takes a container and an element and creates a whole new
 container).

 Internally, functional containers take advantage of common substructure
 and immutability to share actual data. The classic resource for defining
 and implementing functional containers is
 http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.

 ...
I still think those should be mutable by default in order to have painless interchangeability with other value type containers. Why should corresponding ephemeral and persistent containers have different interfaces? I assume you envision code using those to look as follows? FunSet!int a; a=a.with_(1); auto b=a; a=a.with_(2); a=a.with_(3); // b = {1}, a={1,2,3}; I think this should be allowed too: FunSet!int a; a.insert(1); auto b=a; a.insert(2); a.insert(3); // b = {1}, a={1,2,3}; One of the two versions should be automatically implemented via UFCS.
 2. Reference containers.

 These have classic reference semantics (à la Java). Internally, they may be
implemented either as class objects or as reference counted structs.

 They're by default mutable. Qualifiers should apply to them gracefully.

 3. Eager value containers.

 These are STL-style. Somewhat surprisingly I think these are the worst of the
pack; they expensively duplicate at the drop of a hat and need to be carefully
passed around by reference lest performance silently drops. Nevertheless, when
used as members inside other data structures value semantics might be the
appropriate choice. Also, thinking of them as values often makes code simpler.

 By default eager value containers are mutable. They should support immutable
and const meaningfully.
 4. Copy-on-write containers.

 These combine the advantages of value and reference containers: you get
 to think of them as values, yet they're not expensive to copy. Copying
 only occurs by necessity upon the first attempt to change them.
 ...
IMO "1." ought to combine the advantages of value and reference containers as well, just without any expensive copying at all, even when updates happen.
 The disadvantage is implementations get somewhat complicated. Also, they
 are shunned in C++ because there is no proper support for COW; for
 example, COW strings have been banned starting with C++11 which is quite
 the bummer.

 Together with Scott Meyers, Walter figured out a way to change D to
 support COW properly. The language change consists of two attributes.

 =======

 I'll attempt to implement a few versions of each and see what they look
 like. The question here is what containers are of interest for D's
 standard library.
 ...
List: - forward iteration - bidirectional iteration Stack: - basic stack - ordered stack [0] Queue: - basic queue - heap Set: - hash set - ordered set - accumulating set [1] - trie/radix tree + multiset versions Map: - hash map - ordered map - accumulating map [1] - accumulating map with range update [2] - trie/radix tree - accumulating trie [1] - accumulating trie with range update [2] + multimap versions - array - accumulating array [1] - accumulating array with range update [2] + O(1) reset versions [3] - rope - accumulating rope [1] - accumulating rope with range update [2] [0] ordered stack: Push operations automatically pop the minimal number of elements off the stack prior to pushing, such as to guarantee that the elements on the stack remain ordered. The stack should expose a sorted range in order to support binary search. [1] accumulation: The (ordered!) data structure allows fast queries for the result of some binary associative operations on the elements in a certain range. (the allowed operations are determined in advance and some intermediate results are automatically maintained). (for map, the operation would be just on the values, not on the keys.) This is usually quite easy support, but very useful. [2] range update: here, the idea is that the data structure allows all elements in a certain range to be updated. the updates are performed lazily and have to be compatible with the associative operations (if any). [3] fast reset: here the idea is that the map allows fast reset of its values at the cost of some small additional overhead per lookup. (destructors are called lazily.)
Oct 21 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 10:21 AM, Timon Gehr wrote:

 I still think those should be mutable by default in order to have
 painless interchangeability with other value type containers. Why should
 corresponding ephemeral and persistent containers have different
 interfaces?

 I assume you envision code using those to look as follows?

 FunSet!int a;
 a=a.with_(1);
 auto b=a;
 a=a.with_(2);
 a=a.with_(3);
 // b = {1}, a={1,2,3};

 I think this should be allowed too:

 FunSet!int a;
 a.insert(1);
 auto b=a;
 a.insert(2);
 a.insert(3);
 // b = {1}, a={1,2,3};

 One of the two versions should be automatically implemented via UFCS.
I recall you and I discussed this briefly in the past, but forgot the conclusion. So are you saying that a.insert(1) is really rebinding a to be its former value plus a new slot? I.e a.insert(1) is the same as a = a.with_(1)? That would work, but only if former reads of a refer to the old data. E.g.: FunSet!int a; auto b = a; assert(a.empty && b.empty); a.insert(1); assert(!a.empty && b.empty); Right? Andrei
Oct 21 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10/21/2015 04:36 PM, Andrei Alexandrescu wrote:
 On 10/21/2015 10:21 AM, Timon Gehr wrote:

 I still think those should be mutable by default in order to have
 painless interchangeability with other value type containers. Why should
 corresponding ephemeral and persistent containers have different
 interfaces?

 I assume you envision code using those to look as follows?

 FunSet!int a;
 a=a.with_(1);
 auto b=a;
 a=a.with_(2);
 a=a.with_(3);
 // b = {1}, a={1,2,3};

 I think this should be allowed too:

 FunSet!int a;
 a.insert(1);
 auto b=a;
 a.insert(2);
 a.insert(3);
 // b = {1}, a={1,2,3};

 One of the two versions should be automatically implemented via UFCS.
I recall you and I discussed this briefly in the past, but forgot the conclusion. ...
IIRC the conclusion was postponed. :-)
 So are you saying that a.insert(1) is really rebinding a to be its
 former value plus a new slot? I.e a.insert(1) is the same as a =
 a.with_(1)? That would work, but only if former reads of a refer to the
 old data. E.g.:

 FunSet!int a;
 auto b = a;
 assert(a.empty && b.empty);
 a.insert(1);
 assert(!a.empty && b.empty);

 Right?


 Andrei
Exactly. There would be no mutable aliasing. This way, the persistent data type can behave like a mutable value type, such as a COW or eager copy variant, but with nicer/different performance characteristics. It would be great if exchanging different implementation strategies for value semantics will be as seamless as possible. (If the initially chosen strategy turns out to be wrong, this makes the fix easy.) Of course, the implementation of the persistent data structure will be in terms of non-mutating and possibly O(1)-COW operations only.
Oct 21 2015
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10/21/2015 05:08 PM, Timon Gehr wrote:
 There would be no mutable aliasing.
Here, I mean within the data structure itself. There is nothing wrong with: class Cell{ int x=0; } FunSet!Cell a; a.insert(new Cell()); auto b=a; foreach(c;a) c.x=1; assert(b.x==1); This is analogous to: struct SingletonFunSet(T){ T element; } auto a=SingletonFunSet!Cell(new Cell()); auto b=a; a.element.x=1; assert(b.x==1); Here, SingletonFunSet!Cell is a value type, but it's constituents might not be.
Oct 21 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 11:13 AM, Timon Gehr wrote:
 On 10/21/2015 05:08 PM, Timon Gehr wrote:
 There would be no mutable aliasing.
Here, I mean within the data structure itself. There is nothing wrong with: class Cell{ int x=0; } FunSet!Cell a; a.insert(new Cell()); auto b=a; foreach(c;a) c.x=1; assert(b.x==1); This is analogous to: struct SingletonFunSet(T){ T element; } auto a=SingletonFunSet!Cell(new Cell()); auto b=a; a.element.x=1; assert(b.x==1); Here, SingletonFunSet!Cell is a value type, but it's constituents might not be.
It seems to me that's a departure from traditional persistent data structures. Those have immutable elements; far as I can tell you discuss containers that only have immutable topology. -- Andrei
Oct 21 2015
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 10/21/2015 07:25 PM, Andrei Alexandrescu wrote:
 It seems to me that's a departure from traditional persistent data
 structures.
I don't think so.
 Those have immutable elements;
Immutable insofar as the elements themselves don't change. It is easy to create a persistent list of immutable references to mutable data in Haskell, for instance.
 far as I can tell you discuss
 containers that only have immutable topology. -- Andrei
The topology as well as all the elements are immutable, just not in the 'transitive qualifier' way. Immutable references to mutable data are useful, they just don't have built-in language support. Persistent data structures work perfectly fine with those.
Oct 21 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 11:08 AM, Timon Gehr wrote:
 Exactly. There would be no mutable aliasing. This way, the persistent
 data type can behave like a mutable value type, such as a COW or eager
 copy variant, but with nicer/different performance characteristics. It
 would be great if exchanging different implementation strategies for
 value semantics will be as seamless as possible. (If the initially
 chosen strategy turns out to be wrong, this makes the fix easy.) Of
 course, the implementation of the persistent data structure will be in
 terms of non-mutating and possibly O(1)-COW operations only.
Makes sense. Now that we got to talk - did you submit the bugs you found with DIP25? -- Andrei
Oct 21 2015
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 10/21/2015 07:24 PM, Andrei Alexandrescu wrote:
 On 10/21/2015 11:08 AM, Timon Gehr wrote:
 Exactly. There would be no mutable aliasing. This way, the persistent
 data type can behave like a mutable value type, such as a COW or eager
 copy variant, but with nicer/different performance characteristics. It
 would be great if exchanging different implementation strategies for
 value semantics will be as seamless as possible. (If the initially
 chosen strategy turns out to be wrong, this makes the fix easy.) Of
 course, the implementation of the persistent data structure will be in
 terms of non-mutating and possibly O(1)-COW operations only.
Makes sense. Now that we got to talk - did you submit the bugs you found with DIP25? -- Andrei
Yup: https://issues.dlang.org/buglist.cgi?email1=timon&emailreporter1=1&emailtype1=substring&list_id=204001&query_format=advanced&resolution=---&short_desc=DIP25&short_desc_type=allwordssubstr
Oct 21 2015
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10/21/2015 01:05 PM, Andrei Alexandrescu wrote:
 2. Reference containers.

 These have classic reference semantics (à la Java). Internally, they may
 be implemented either as class objects or as reference counted structs.

 They're by default mutable. Qualifiers should apply to them gracefully.

 3. Eager value containers.

 These are STL-style. Somewhat surprisingly I think these are the worst
 of the pack; they expensively duplicate at the drop of a hat and need to
 be carefully passed around by reference lest performance silently drops.
 Nevertheless, when used as members inside other data structures value
 semantics might be the appropriate choice. Also, thinking of them as
 values often makes code simpler.

 By default eager value containers are mutable. They should support
 immutable and const meaningfully.
For which containers we want to support is "2." not a (wrapper around a) pointer to "3."?
Oct 21 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 11:58 AM, Timon Gehr wrote:
 For which containers we want to support is "2." not a (wrapper around a)
 pointer to "3."?
For those that need reference counting. -- Andrei
Oct 21 2015
prev sibling next sibling parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
5. Lock-free data structures.
Oct 21 2015
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 21-Oct-2015 19:13, Ola Fosheim Grøstad wrote:
 5. Lock-free data structures.
More generally - concurrent. It may have fine-grained locking, it may be obstruction-free or even wait-free. -- Dmitry Olshansky
Oct 21 2015
prev sibling next sibling parent reply Brad Anderson <eco gnuk.net> writes:
On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
Alexandrescu wrote:
[snip]
 2. Reference containers.

 These have classic reference semantics (à la Java). Internally, 
 they may be implemented either as class objects or as reference 
 counted structs.

 They're by default mutable. Qualifiers should apply to them 
 gracefully.

 3. Eager value containers.

 These are STL-style. Somewhat surprisingly I think these are 
 the worst of the pack; they expensively duplicate at the drop 
 of a hat and need to be carefully passed around by reference 
 lest performance silently drops. Nevertheless, when used as 
 members inside other data structures value semantics might be 
 the appropriate choice. Also, thinking of them as values often 
 makes code simpler.

 By default eager value containers are mutable. They should 
 support immutable and const meaningfully.
Having both reference and value semantics for containers would be great. I don't understand why reference semantics would be implemented by the container themselves though. Why not a general purpose RC! (or RefCounted! if the current design is deemed sufficient) that can apply to anything, including containers? Then you'd only need to implement the value semantic containers (and maybe throw in some RC version aliases to promote the use of the RC versions so the option isn't overlooked). It seems kind of crazy that anything in D that wants to be reference counted would need to implement the logic themselves. If there are performance advantages (I haven't thought of any but perhaps there are) to bake the RC right into the container it might also be possible to use DbI take advantage of it in RC! when appropriate. It just seems so wrong to implement reference counting dozens of times independently, especially when that means implementing all the containers twice too. Perhaps I'm misreading what you meant though and this is what you intended all along.
 4. Copy-on-write containers.

 These combine the advantages of value and reference containers: 
 you get to think of them as values, yet they're not expensive 
 to copy. Copying only occurs by necessity upon the first 
 attempt to change them.

 The disadvantage is implementations get somewhat complicated. 
 Also, they are shunned in C++ because there is no proper 
 support for COW; for example, COW strings have been banned 
 starting with C++11 which is quite the bummer.

 Together with Scott Meyers, Walter figured out a way to change 
 D to support COW properly. The language change consists of two 
 attributes.
Nice to have this option. I don't think I'd use it much though.
Oct 21 2015
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, 21 October 2015 at 16:36:46 UTC, Brad Anderson 
wrote:
 On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
 Alexandrescu wrote:
 [snip]
 2. Reference containers.

 These have classic reference semantics (à la Java). 
 Internally, they may be implemented either as class objects or 
 as reference counted structs.

 They're by default mutable. Qualifiers should apply to them 
 gracefully.

 3. Eager value containers.

 These are STL-style. Somewhat surprisingly I think these are 
 the worst of the pack; they expensively duplicate at the drop 
 of a hat and need to be carefully passed around by reference 
 lest performance silently drops. Nevertheless, when used as 
 members inside other data structures value semantics might be 
 the appropriate choice. Also, thinking of them as values often 
 makes code simpler.

 By default eager value containers are mutable. They should 
 support immutable and const meaningfully.
Having both reference and value semantics for containers would be great. I don't understand why reference semantics would be implemented by the container themselves though. Why not a general purpose RC! (or RefCounted! if the current design is deemed sufficient) that can apply to anything, including containers? Then you'd only need to implement the value semantic containers (and maybe throw in some RC version aliases to promote the use of the RC versions so the option isn't overlooked). It seems kind of crazy that anything in D that wants to be reference counted would need to implement the logic themselves. If there are performance advantages (I haven't thought of any but perhaps there are) to bake the RC right into the container it might also be possible to use DbI take advantage of it in RC! when appropriate. It just seems so wrong to implement reference counting dozens of times independently, especially when that means implementing all the containers twice too.
If we had value type containers and reference type containers, I would assume that they would at least share implementation, and maybe the reference types would just be wrappers around the value types. However, I completely fail to understand why you'd ever want a container that was a value type. In my experience, it's very error-prone and adds no value. It just makes it too easy to accidentally copy a container, and it can be pretty easy to have an iterator, range, etc. referring to a container that's already been destroyed (similar to having a dynamic array referring to a static array that's left scope). As long as the containers have a dup method (or whatever we call it) so that they can be copied when you do want to copy them, I would think that that was more than enough. What do you get with a value type container that you consider better than a reference type? It's not like it lives on the stack as a value type. Most of the container's guts are on the heap regardless. - Jonathan M Davis
Oct 21 2015
next sibling parent reply jmh530 <john.michael.hall gmail.com> writes:
On Wednesday, 21 October 2015 at 18:05:07 UTC, Jonathan M Davis 
wrote:
 However, I completely fail to understand why you'd ever want a 
 container that was a value type. In my experience, it's very 
 error-prone and adds no value.
Are you saying there isn't a reason to use static arrays?
Oct 21 2015
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, 21 October 2015 at 18:14:39 UTC, jmh530 wrote:
 On Wednesday, 21 October 2015 at 18:05:07 UTC, Jonathan M Davis 
 wrote:
 However, I completely fail to understand why you'd ever want a 
 container that was a value type. In my experience, it's very 
 error-prone and adds no value.
Are you saying there isn't a reason to use static arrays?
A static array is of a fixed size, which almost no other containers are. It also lives entirely on the stack, which almost no other containers do. If there's a container that lives entirely on the stack, then maybe it would make sense for it to be a value type, but _very_ few containers fall in that category, and all of the classic containers like vector, linked list, map, etc. have no business being value types IMHO. It's just error-prone. Heck, static arrays are quite error-prone thanks to the fact that they convert to dynamic arrays, but they do serve a purpose. So, maybe there are containers that fall in the same category, but I expect that such containers are pretty obviously value types and not reference types, because their nature makes them that way. Regardless, I don't see how it's reasonable in general to make a container be a value type. It's just asking for trouble. If there's any question at all whether a container should be a value type or a reference type, IMHO, it should be a reference type. - Jonathan M Davis
Oct 21 2015
next sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Wed, Oct 21, 2015 at 06:38:08PM +0000, Jonathan M Davis via Digitalmars-d
wrote:
 On Wednesday, 21 October 2015 at 18:14:39 UTC, jmh530 wrote:
[...]
Are you saying there isn't a reason to use static arrays?
A static array is of a fixed size, which almost no other containers are. It also lives entirely on the stack, which almost no other containers do.
[...] You forget that static arrays can also be struct/class members, and in the latter case they are not necessarily on the stack. You do have a point that they are of fixed size, though, and as such are of limited use as containers. T -- "I'm running Windows '98." "Yes." "My computer isn't working now." "Yes, you already said that." -- User-Friendly
Oct 21 2015
prev sibling parent reply jmh530 <john.michael.hall gmail.com> writes:
On Wednesday, 21 October 2015 at 18:38:10 UTC, Jonathan M Davis 
wrote:
 A static array is of a fixed size, which almost no other 
 containers are. It also lives entirely on the stack, which 
 almost no other containers do. If there's a container that 
 lives entirely on the stack, then maybe it would make sense for 
 it to be a value type, but _very_ few containers fall in that 
 category, and all of the classic containers like vector, linked 
 list, map, etc. have no business being value types IMHO. It's 
 just error-prone. Heck, static arrays are quite error-prone 
 thanks to the fact that they convert to dynamic arrays, but 
 they do serve a purpose. So, maybe there are containers that 
 fall in the same category, but I expect that such containers 
 are pretty obviously value types and not reference types, 
 because their nature makes them that way. Regardless, I don't 
 see how it's reasonable in general to make a container be a 
 value type. It's just asking for trouble. If there's any 
 question at all whether a container should be a value type or a 
 reference type, IMHO, it should be a reference type.
I do find myself mixing up static and dynamic arrays... I'll generally defer to you. I suppose within the context of Andrei working on containers with std.allocator, then containers that only live on the stack seems beyond the scope anyway. Your statement just had struck me as weird as I had thought of people like manu saying at various points that they only kept data structures on the stack. My next thought was that static arrays are usually on the stack and are value types. So I figured that whatever the performance people are using were similar.
Oct 21 2015
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, 21 October 2015 at 20:13:31 UTC, jmh530 wrote:
 On Wednesday, 21 October 2015 at 18:38:10 UTC, Jonathan M Davis 
 wrote:
 A static array is of a fixed size, which almost no other 
 containers are. It also lives entirely on the stack, which 
 almost no other containers do. If there's a container that 
 lives entirely on the stack, then maybe it would make sense 
 for it to be a value type, but _very_ few containers fall in 
 that category, and all of the classic containers like vector, 
 linked list, map, etc. have no business being value types 
 IMHO. It's just error-prone. Heck, static arrays are quite 
 error-prone thanks to the fact that they convert to dynamic 
 arrays, but they do serve a purpose. So, maybe there are 
 containers that fall in the same category, but I expect that 
 such containers are pretty obviously value types and not 
 reference types, because their nature makes them that way. 
 Regardless, I don't see how it's reasonable in general to make 
 a container be a value type. It's just asking for trouble. If 
 there's any question at all whether a container should be a 
 value type or a reference type, IMHO, it should be a reference 
 type.
I do find myself mixing up static and dynamic arrays... I'll generally defer to you. I suppose within the context of Andrei working on containers with std.allocator, then containers that only live on the stack seems beyond the scope anyway. Your statement just had struck me as weird as I had thought of people like manu saying at various points that they only kept data structures on the stack. My next thought was that static arrays are usually on the stack and are value types. So I figured that whatever the performance people are using were similar.
Static arrays are a bit of a special case, because they're essentially a chunk of memory on the stack. They can be extremely useful and efficient, but you have to be careful with them. Most containers don't act anything like them. But like I said, there are some container types which inherently make sense on a stack, but most don't. For the most part, the kinds of containers that we're talking about here - vectors/array lists, linked lists, maps, sets, etc. - have to have most of their guts living on the heap. You'd have to _really_ contort things to put them entirely on the stack, and you'd be seriously limiting how many elements that they could hold if you did. If you make a vector or a linked list a value type, then it'll have a few members on the stack, but most of them will be on the heap, and it'll be a value type only because its postblit constructor explicitly copies the portion that's on the heap. It's not really naturally a value type. It's naturally more of a reference type or pseudo-reference type. If the vector is implemented as a reference type, then the few member variables that were on the stack in the value type version end up on the heap with the rest of the container's guts, so you use slightly more memory for them, but it's much more natural that way, since the main guts of the container were on the heap anyway. And if the container is a value type, you risk copying unnecessarily and/or keeping around references/pointers/iterators/ranges to its elements after it's been destroyed, whereas with a reference type, it'll only be copied when you specifically request it. Treating them as value types is inefficient, error-prone, and unnatural. Now, folks like Manu do do some crazy stuff eke out every bit of performance that they can, and they do sometimes use stuff like alloca to put stuff that would otherwise be on the heap on the stack. But a lot of what they do isn't very general purpose either, and they generally avoid stuff like the containers in standard libraries, because they use the heap too much and/or aren't tailored to their needs. They also tend to do stuff that's way more error-prone in an effort to eke out that extra bit of performance. If we can do stuff to support them, then great, but in general - especially when you're talking about the library and not the language - the kinds of stuff that they want don't work for other folks. If someone like Manu wants an efficient container, he _might_ want one that's not a full-on reference type simply so that less of it is on the heap, but he sure isn't going to want to copy it except when he absolutely has to. So, the fact that it's a value type isn't necessarily useful. Having it simply live where it's constructed (be it on the stack or as a member variable) with only the stuff that has to be on the heap on the heap but have the container have a disabled postblit would probably be just as useful in most cases, and scoped or region allactors should be able to help with that. I'm not super familiar with all of the tricks that they pull to make their container use efficient, but I have a hard time seeing how std::vector's semantics are desirable to them. Certainly, when they care about efficiency to the point that they're using static arrays everywhere, the fact that vector has its guts on the heap means that it's in a different class of containers entirely from static arrays and does not have the same desirable properties, even if it is a value type like static arrays. And even then, the fact that static arrays are value types isn't really the gain. It's more that they're on the stack, and that naturally turns them into value types. In any case, I'm pretty sure that we do have a region allocator in std.experimental.allocator, so if someone wants to try and put a container that normally lives on the heap on the stack, it should be possible (at least, with a limited number of elements). And it might actually be easier to do that with a container that's entirely on the heap instead of part of it living on the stack and part of it living on the heap (as occurs with the C++ containers). If Manu (or others like him) have strong feelings about what kinds of containers would be best for them, they can speak up and point out what they need, but I don't see how having value type containers would generally be useful to them except in the cases where the container actually, fully lives on the stack (which is almost never the case), and it seems even more questionable for everyone else. - Jonathan M Davis
Oct 21 2015
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 10/21/2015 11:02 PM, Jonathan M Davis wrote:
 Static arrays are a bit of a special case, because they're essentially a
 chunk of memory on the stack. They can be extremely useful and
 efficient, but you have to be careful with them. Most containers don't
 act anything like them.

 But like I said, there are some container types which inherently make
 sense on a stack, but most don't. For the most part, the kinds of
 containers that we're talking about here - vectors/array lists, linked
 lists, maps, sets, etc. - have to have most of their guts living on the
 heap. You'd have to _really_ contort things to put them entirely on the
 stack,
In many applications, most containers are small. Small containers can have all their guts on the stack.
 and you'd be seriously limiting how many elements that they could
 hold if you did.
Not really. Just allocate on the heap only if there are too many elements.
 If you make a vector or a linked list a value type,
 then it'll have a few members on the stack, but most of them will be on
 the heap, and it'll be a value type only because its postblit
 constructor explicitly copies the portion that's on the heap. It's not
 really naturally a value type.
Value semantics does not mean slow copy, I assume you conflate value semantics and eager copy?
 It's naturally more of a reference type
 or pseudo-reference type.
What you describe is "naturally" (which I interpret to mean: if postblit must be O(1)) a unique reference type. I.e. the most natural way out would be to add disable this(this). But implicit copy can be convenient. Maybe have implicit copy as a wrapper?
Oct 21 2015
prev sibling next sibling parent reply Brad Anderson <eco gnuk.net> writes:
On Wednesday, 21 October 2015 at 18:05:07 UTC, Jonathan M Davis 
wrote:
 On Wednesday, 21 October 2015 at 16:36:46 UTC, Brad Anderson 
 wrote:
 On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
 Alexandrescu wrote:
 [snip]
 2. Reference containers.

 These have classic reference semantics (à la Java). 
 Internally, they may be implemented either as class objects 
 or as reference counted structs.

 They're by default mutable. Qualifiers should apply to them 
 gracefully.

 3. Eager value containers.

 These are STL-style. Somewhat surprisingly I think these are 
 the worst of the pack; they expensively duplicate at the drop 
 of a hat and need to be carefully passed around by reference 
 lest performance silently drops. Nevertheless, when used as 
 members inside other data structures value semantics might be 
 the appropriate choice. Also, thinking of them as values 
 often makes code simpler.

 By default eager value containers are mutable. They should 
 support immutable and const meaningfully.
Having both reference and value semantics for containers would be great. I don't understand why reference semantics would be implemented by the container themselves though. Why not a general purpose RC! (or RefCounted! if the current design is deemed sufficient) that can apply to anything, including containers? Then you'd only need to implement the value semantic containers (and maybe throw in some RC version aliases to promote the use of the RC versions so the option isn't overlooked). It seems kind of crazy that anything in D that wants to be reference counted would need to implement the logic themselves. If there are performance advantages (I haven't thought of any but perhaps there are) to bake the RC right into the container it might also be possible to use DbI take advantage of it in RC! when appropriate. It just seems so wrong to implement reference counting dozens of times independently, especially when that means implementing all the containers twice too.
If we had value type containers and reference type containers, I would assume that they would at least share implementation, and maybe the reference types would just be wrappers around the value types. However, I completely fail to understand why you'd ever want a container that was a value type.
Well they are more efficient when used correctly (no inc/decs). Using them correctly does take some additional knowledge and consideration though. C++11 did take care of a whole class of implicit copying and RVO has long taken care of another class of them. I don't think it happens (in C++) quite as often as you are making it out to be (at least in my experience) but I'll admit I have had a bug or two caused by modifying a copy when I thought I was changing a reference. I could just as easily have bugs caused by modifying a reference when I thought I was modifying a copy though. Either approach comes with its own considerations.
 In my experience, it's very error-prone and adds no value.
Unless we end up with compiler assisted inc/dec elision they are always going to be faster. Perhaps marginally faster but still faster and the realtime guys are always going to demand the fastest option.
 It just makes it too easy to accidentally copy a container, and 
 it can be pretty easy to have an iterator, range, etc. 
 referring to a container that's already been destroyed (similar 
 to having a dynamic array referring to a static array that's 
 left scope).
Having the ranges of a container keep the reference count would make the speed advantage of the value types even more of a factor. That might actually change the performance advantage away from being just subtle to being strong. We'd need to benchmark to say for sure, of course. Just a sidenote regarding iterator invalidation: C++, when following the new C++ Core Guidelines, is actually able to do static analysis of iterators for memory safety without ref count overhead. Herb Sutter showed a preview version of MSVC doing it during his keynote this month at CppCon[1]. It blew me away that they were about to do that with C++.
 As long as the containers have a dup method (or whatever we 
 call it) so that they can be copied when you do want to copy 
 them, I would think that that was more than enough. What do you 
 get with a value type container that you consider better than a 
 reference type? It's not like it lives on the stack as a value 
 type. Most of the container's guts are on the heap regardless.

 - Jonathan M Davis
All that said, I agree with you that the implicit copying isn't really all that desirable. Perhaps there is a better way. What if instead of value semantics we had unique containers (akin to std.typecons.Unique or unique_ptr in C++) and required people to always state whether it was a copy or move? That takes care of the error prone implicit copying while retaining the performance characteristics. 1. https://www.youtube.com/watch?v=hEx5DNLWGgA
Oct 21 2015
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, 21 October 2015 at 18:48:18 UTC, Brad Anderson 
wrote:
 All that said, I agree with you that the implicit copying isn't 
 really all that desirable. Perhaps there is a better way. What 
 if instead of value semantics we had unique containers (akin to 
 std.typecons.Unique or unique_ptr in C++) and required people 
 to always state whether it was a copy or move? That takes care 
 of the error prone implicit copying while retaining the 
 performance characteristics.
Well, we could always have a wrapper for reference type containers that turns them into a value type, though I'm not sure that that really does much in terms of the efficiency you were talking about. But it could means that you'd end up passing around a pointer to that rather than the container itself, in which case, maybe that solves the problem for those who don't want a container to be managed by the GC and don't want it to be ref-counted when passing it around? I don't know. Even if we're talking about a reference type container that's just straight up ref-counted or managed by the GC, there are still ways to pass around pointers or pseudo pointers to it which don't involve ref-counting if that's the real concern. Though honestly, I'd be concerned if a container was being passed around so much that ref-counting was a concern. A range would be better in most cases - but you really wouldn't want to be passing around the container as a value type in either case, because that would just copy it. So, if ref-counting is the concern, I wouldn't think that it would be all that hard for someone who cares to pass around something else which referred to the container and wasn't ref-counted. - Jonathan M Davis
Oct 21 2015
parent Ice Cream Man <thegreatone google.com> writes:
On Wednesday, 21 October 2015 at 19:07:50 UTC, Jonathan M Davis 
wrote:
 On Wednesday, 21 October 2015 at 18:48:18 UTC, Brad Anderson 
 wrote:
 All that said, I agree with you that the implicit copying 
 isn't really all that desirable. Perhaps there is a better 
 way. What if instead of value semantics we had unique 
 containers (akin to std.typecons.Unique or unique_ptr in C++) 
 and required people to always state whether it was a copy or 
 move? That takes care of the error prone implicit copying 
 while retaining the performance characteristics.
Well, we could always have a wrapper for reference type containers that turns them into a value type,
ugh...that sounds horrible.
Oct 21 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 02:05 PM, Jonathan M Davis wrote:
 If we had value type containers and reference type containers, I would
 assume that they would at least share implementation, and maybe the
 reference types would just be wrappers around the value types.
Well, I thought the same. I was surprised.
 However,
 I completely fail to understand why you'd ever want a container that was
 a value type.
Sometimes you want a value container as a member of a struct which in turn is a value type. Andrei
Oct 21 2015
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, 21 October 2015 at 19:16:28 UTC, Andrei 
Alexandrescu wrote:
 Sometimes you want a value container as a member of a struct 
 which in turn is a value type.
Sure, but at least in theory, the struct's postblit should be able to copy a reference type container via dup or whatnot if that's what you really want (though the issues with const and immutable interacting badly with postblit remain), and creating a whole set of value type variants of containers just for cases like that (which are sometimes useful but usually a bad idea) seems like overkill. - Jonathan M Davis
Oct 21 2015
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 12:36 PM, Brad Anderson wrote:
 I don't understand why reference semantics would be implemented by the
 container themselves though. Why not a general purpose RC! (or
 RefCounted! if the current design is deemed sufficient) that can apply
 to anything, including containers?
Two reasons: 1. A generic RC wrapper cannot be made safe (or at least I don't know how). 2. A container designed for RC can make advantageous layout decisions. Andrei
Oct 21 2015
prev sibling next sibling parent reply Ulrich Kuettler <kuettler gmail.com> writes:
On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
Alexandrescu wrote:
 I'm finally getting the cycles to get to thinking about Design 
 by Introspection containers. First off, there are several 
 general categories of containers. I think D should support all 
 properly. One question is which we go for in the standard 
 library.

 1. Functional containers.
Very much in favor of functional (or persistent) containers. Immutable. Value semantics. This might take some getting used to, but if properly designed these containers would be killer for D. A dream come true.
 These are immutable; once created, neither their topology nor 
 their elements may be observably changed. Manipulating a 
 container entails creating an entire new container, often based 
 on an existing container (e.g. append takes a container and an 
 element and creates a whole new container).

 Internally, functional containers take advantage of common 
 substructure and immutability to share actual data. The classic 
 resource for defining and implementing functional containers is 
 http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.
An insanely beautiful example is clojure's PersistantVector. AFAIK it made its way into Scala, too.
Oct 21 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 01:42 PM, Ulrich Kuettler wrote:
 On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei Alexandrescu wrote:
 I'm finally getting the cycles to get to thinking about Design by
 Introspection containers. First off, there are several general
 categories of containers. I think D should support all properly. One
 question is which we go for in the standard library.

 1. Functional containers.
Very much in favor of functional (or persistent) containers. Immutable. Value semantics. This might take some getting used to, but if properly designed these containers would be killer for D. A dream come true.
I agree they're cool.
 These are immutable; once created, neither their topology nor their
 elements may be observably changed. Manipulating a container entails
 creating an entire new container, often based on an existing container
 (e.g. append takes a container and an element and creates a whole new
 container).

 Internally, functional containers take advantage of common
 substructure and immutability to share actual data. The classic
 resource for defining and implementing functional containers is
 http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.
An insanely beautiful example is clojure's PersistantVector. AFAIK it made its way into Scala, too.
Far as I understand from http://hypirion.com/musings/understanding-persistent-vector-pt-1, it's that tree thing with carefully chosen slot sizes for cache friendliness? Andrei
Oct 21 2015
parent Ulrich =?UTF-8?B?S8O8dHRsZXI=?= <kuettler gmail.com> writes:
On Wednesday, 21 October 2015 at 18:55:10 UTC, Andrei 
Alexandrescu wrote:
 On 10/21/2015 01:42 PM, Ulrich Kuettler wrote:
 On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
 Alexandrescu wrote:
 I'm finally getting the cycles to get to thinking about 
 Design by
 Introspection containers. First off, there are several general
 categories of containers. I think D should support all 
 properly. One
 question is which we go for in the standard library.

 1. Functional containers.
Very much in favor of functional (or persistent) containers. Immutable. Value semantics. This might take some getting used to, but if properly designed these containers would be killer for D. A dream come true.
I agree they're cool.
 These are immutable; once created, neither their topology nor 
 their
 elements may be observably changed. Manipulating a container 
 entails
 creating an entire new container, often based on an existing 
 container
 (e.g. append takes a container and an element and creates a 
 whole new
 container).

 Internally, functional containers take advantage of common
 substructure and immutability to share actual data. The 
 classic
 resource for defining and implementing functional containers 
 is
 http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.
An insanely beautiful example is clojure's PersistantVector. AFAIK it made its way into Scala, too.
Far as I understand from http://hypirion.com/musings/understanding-persistent-vector-pt-1, it's that tree thing with carefully chosen slot sizes for cache friendliness?
Yes. It is about cache friendliness, memory efficiency and speed. Since each node consists of 32 pointers, there are just three inner levels to store 1M values. The bit operations to navigate to the leaf node are a thing of beauty: https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentVector.java#L147-L163 It is a remarkable design on the JVM. Of course, it serves a very particular purpose. D's design space is very different. Obviously.
Oct 21 2015
prev sibling next sibling parent reply Zz <zz nospam.com> writes:
On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
Alexandrescu wrote:
 I'm finally getting the cycles to get to thinking about Design 
 by Introspection containers. First off, there are several 
 general categories of containers. I think D should support all 
 properly. One question is which we go for in the standard 
 library.

 1. Functional containers.

 These are immutable; once created, neither their topology nor 
 their elements may be observably changed. Manipulating a 
 container entails creating an entire new container, often based 
 on an existing container (e.g. append takes a container and an 
 element and creates a whole new container).

 Internally, functional containers take advantage of common 
 substructure and immutability to share actual data. The classic 
 resource for defining and implementing functional containers is 
 http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.

 2. Reference containers.

 These have classic reference semantics (à la Java). Internally, 
 they may be implemented either as class objects or as reference 
 counted structs.

 They're by default mutable. Qualifiers should apply to them 
 gracefully.

 3. Eager value containers.

 These are STL-style. Somewhat surprisingly I think these are 
 the worst of the pack; they expensively duplicate at the drop 
 of a hat and need to be carefully passed around by reference 
 lest performance silently drops. Nevertheless, when used as 
 members inside other data structures value semantics might be 
 the appropriate choice. Also, thinking of them as values often 
 makes code simpler.

 By default eager value containers are mutable. They should 
 support immutable and const meaningfully.

 4. Copy-on-write containers.

 These combine the advantages of value and reference containers: 
 you get to think of them as values, yet they're not expensive 
 to copy. Copying only occurs by necessity upon the first 
 attempt to change them.

 The disadvantage is implementations get somewhat complicated. 
 Also, they are shunned in C++ because there is no proper 
 support for COW; for example, COW strings have been banned 
 starting with C++11 which is quite the bummer.

 Together with Scott Meyers, Walter figured out a way to change 
 D to support COW properly. The language change consists of two 
 attributes.

 =======

 I'll attempt to implement a few versions of each and see what 
 they look like. The question here is what containers are of 
 interest for D's standard library.


 Andrei
While looking at containers take a look at Jiri Soukup's work some good ideas could come from there. http://www.amazon.ca/Serialization-Persistent-Objects-Structures-Efficient/dp/3642393225/ref=sr_1_1?ie=UTF8&;qid=1386946808&amp;sr=8-1&amp;keywords=SERIALIZATION+AND+PERSISTENT+OBJECTS#productPromotions%22%20target=%22_blank Intrusive Data Structures. http://www.codefarms.com/home http://www.codefarms.com/dol http://www.codefarms.com/ppf http://www.codefarms.com/ptl Zz
Oct 21 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 02:18 PM, Zz wrote:
 While looking at containers take a look at Jiri Soukup's work some good
 ideas could come from there.

 http://www.amazon.ca/Serialization-Persistent-Objects-Structures-Efficient/dp/3642393225/ref=sr_1_1?ie=UTF8&;qid=1386946808&amp;sr=8-1&amp;keywords=SERIALIZATION+AND+PERSISTENT+OBJECTS#productPromotions%22%20target=%22_blank


 Intrusive Data Structures.
 http://www.codefarms.com/home
 http://www.codefarms.com/dol
 http://www.codefarms.com/ppf
 http://www.codefarms.com/ptl
Ah, Codefarms is still around. Nice. I remember I've been reading Soukup's articles back in the days of the C++ Report magazine. I couldn't make sense of them, nor could any of my friends. -- Andrei
Oct 21 2015
parent reply Zz <zz nospam.com> writes:
On Wednesday, 21 October 2015 at 19:17:52 UTC, Andrei 
Alexandrescu wrote:
 On 10/21/2015 02:18 PM, Zz wrote:
 While looking at containers take a look at Jiri Soukup's work 
 some good
 ideas could come from there.

 http://www.amazon.ca/Serialization-Persistent-Objects-Structures-Efficient/dp/3642393225/ref=sr_1_1?ie=UTF8&;qid=1386946808&amp;sr=8-1&amp;keywords=SERIALIZATION+AND+PERSISTENT+OBJECTS#productPromotions%22%20target=%22_blank


 Intrusive Data Structures.
 http://www.codefarms.com/home
 http://www.codefarms.com/dol
 http://www.codefarms.com/ppf
 http://www.codefarms.com/ptl
Ah, Codefarms is still around. Nice. I remember I've been reading Soukup's articles back in the days of the C++ Report magazine. I couldn't make sense of them, nor could any of my friends. -- Andrei
The following links give an out line of DOL (The main library), most of the articles talked about the newer PTL (at that time). For DOL http://www.codefarms.com/dolclasses http://www.codefarms.com/docs/dol/index.htm for the list of available organisations. As for PTL the following gives an outline. http://www.codefarms.com/docs/ptl/chap4.htm DOL was Macro based while PTL used templates. Zz
Oct 21 2015
parent reply Zz <zz nospam.com> writes:
On Wednesday, 21 October 2015 at 22:12:32 UTC, Zz wrote:
 On Wednesday, 21 October 2015 at 19:17:52 UTC, Andrei 
 Alexandrescu wrote:
 On 10/21/2015 02:18 PM, Zz wrote:
 While looking at containers take a look at Jiri Soukup's work 
 some good
 ideas could come from there.

 http://www.amazon.ca/Serialization-Persistent-Objects-Structures-Efficient/dp/3642393225/ref=sr_1_1?ie=UTF8&;qid=1386946808&amp;sr=8-1&amp;keywords=SERIALIZATION+AND+PERSISTENT+OBJECTS#productPromotions%22%20target=%22_blank


 Intrusive Data Structures.
 http://www.codefarms.com/home
 http://www.codefarms.com/dol
 http://www.codefarms.com/ppf
 http://www.codefarms.com/ptl
Ah, Codefarms is still around. Nice. I remember I've been reading Soukup's articles back in the days of the C++ Report magazine. I couldn't make sense of them, nor could any of my friends. -- Andrei
The following links give an out line of DOL (The main library), most of the articles talked about the newer PTL (at that time). For DOL http://www.codefarms.com/dolclasses http://www.codefarms.com/docs/dol/index.htm for the list of available organisations. As for PTL the following gives an outline. http://www.codefarms.com/docs/ptl/chap4.htm DOL was Macro based while PTL used templates. Zz
Sorry the list of available organisations is here: http://www.codefarms.com/docs/dol/ch11aorg.htm Zz
Oct 21 2015
parent reply KlausO <oberhofer users.sf.net> writes:
Am 22.10.2015 um 00:15 schrieb Zz:
 On Wednesday, 21 October 2015 at 22:12:32 UTC, Zz wrote:
 On Wednesday, 21 October 2015 at 19:17:52 UTC, Andrei Alexandrescu wrote:
 On 10/21/2015 02:18 PM, Zz wrote:
 While looking at containers take a look at Jiri Soukup's work some good
 ideas could come from there.

 http://www.amazon.ca/Serialization-Persistent-Objects-Structures-Efficient/dp/3642393225/ref=sr_1_1?ie=UTF8&;qid=1386946808&amp;sr=8-1&amp;keywords=SERIALIZATION+AND+PERSISTENT+OBJECTS#productPromotions%22%20target=%22_blank



 Intrusive Data Structures.
 http://www.codefarms.com/home
 http://www.codefarms.com/dol
 http://www.codefarms.com/ppf
 http://www.codefarms.com/ptl
Ah, Codefarms is still around. Nice. I remember I've been reading Soukup's articles back in the days of the C++ Report magazine. I couldn't make sense of them, nor could any of my friends. -- Andrei
The following links give an out line of DOL (The main library), most of the articles talked about the newer PTL (at that time). For DOL http://www.codefarms.com/dolclasses http://www.codefarms.com/docs/dol/index.htm for the list of available organisations. As for PTL the following gives an outline. http://www.codefarms.com/docs/ptl/chap4.htm DOL was Macro based while PTL used templates. Zz
Sorry the list of available organisations is here: http://www.codefarms.com/docs/dol/ch11aorg.htm Zz
Intrusive data structures have their strengths especially when nodes are part of several containers. I implemented some of the intrusive containers back in D1 times. See http://dsource.org/projects/nova/browser/trunk/nova/ds/intrusive KlausO
Oct 22 2015
parent reply safety0ff <safety0ff.dev gmail.com> writes:
On Thursday, 22 October 2015 at 07:13:58 UTC, KlausO wrote:
 Intrusive data structures have their strengths especially when 
 nodes are
 part of several containers.
 I implemented some of the intrusive containers back in D1 times.
 See

 http://dsource.org/projects/nova/browser/trunk/nova/ds/intrusive

 KlausO
I also like having an intrusive container library in my toolbox: they don't limit membership to one container and they don't "bake" memory management into the container type. http://www.boost.org/doc/libs/1_59_0/doc/html/intrusive.html
Oct 22 2015
parent safety0ff <safety0ff.dev gmail.com> writes:
On Thursday, 22 October 2015 at 14:14:09 UTC, safety0ff wrote:
 I also like having an intrusive container library in my 
 toolbox: they don't limit membership to one container and they 
 don't "bake" memory management into the container type.
Also wanted to mention that this allows you to store variable sized data directly in the container without being forced to use a fixed size structure with a pointer to the variable portion. Which is useful for improving cache locality and reducing memory usage.
Oct 22 2015
prev sibling next sibling parent ponce <contact gam3sfrommars.fr> writes:
On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
Alexandrescu wrote:
 The question here is what containers are of interest for D's 
 standard library.
I think the ones in the STL work well. So I'd like something along these lines. Something like std::vector would fit 90% of my needs (eg: a slice using allocators). No interest in lock-free or immutable containers from here.
Oct 21 2015
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10/21/2015 01:05 PM, Andrei Alexandrescu wrote:
 I'll attempt to implement a few versions of each and see what they look
 like. The question here is what containers are of interest for D's
 standard library.
There should probably also be wrappers that implement optimizations for small containers.
Oct 21 2015
parent reply Brad Anderson <eco gnuk.net> writes:
On Wednesday, 21 October 2015 at 20:19:27 UTC, Timon Gehr wrote:
 On 10/21/2015 01:05 PM, Andrei Alexandrescu wrote:
 I'll attempt to implement a few versions of each and see what 
 they look
 like. The question here is what containers are of interest for 
 D's
 standard library.
There should probably also be wrappers that implement optimizations for small containers.
I think the allocators can probably deal with that detail. If I remember correctly there is an in-place allocator. I've been using Boost.Container's small_vector lately (basically a generalization of the now ubiquitous short string optimization...though I'm not sure if it repurposes the pointer when the item count is sufficiently small). It's a nice option to have. The Container library now also has static_vector (fixed capacity, changeable size) that fills a use gap between std::array and std::vector;
Oct 21 2015
next sibling parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Wednesday, 21 October 2015 at 21:53:11 UTC, Brad Anderson 
wrote:
 to have. The Container library now also has static_vector 
 (fixed capacity, changeable size) that fills a use gap between 
 std::array and std::vector;
Yes, in C++ I reimplement this over and over... Trivial, but boring.
Oct 21 2015
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10/21/2015 11:53 PM, Brad Anderson wrote:
 On Wednesday, 21 October 2015 at 20:19:27 UTC, Timon Gehr wrote:
 On 10/21/2015 01:05 PM, Andrei Alexandrescu wrote:
 I'll attempt to implement a few versions of each and see what they look
 like. The question here is what containers are of interest for D's
 standard library.
There should probably also be wrappers that implement optimizations for small containers.
I think the allocators can probably deal with that detail. If I remember correctly there is an in-place allocator. ...
Good point, but might it not be the case that alternative implementations of some operations are faster for a small number of elements?
Oct 21 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/21/2015 06:04 PM, Timon Gehr wrote:
 Good point, but might it not be the case that alternative
 implementations of some operations are faster for a small number of
 elements?
A container could take advantage of the knowledge for both layout and primitives implementation. As I like to say in one of my seminar: "Few elements mean structure". -- Andrei
Oct 21 2015
prev sibling next sibling parent reply bitwise <bitwise.pvt gmail.com> writes:
I needed containers, so I implemented a few:
https://github.com/bitwise-github/d-collections

Currently included:

List(T) - contiguous list like std::vector
LinkedList(T) - doubly linked list like std::list
Queue(T) - double-ended queue/contiguous circular buffer
Stack(T) - contiguous fifo stack

I would like to eventually add some kind(s) of hash table(s), but 
it's a huge topic, and I don't immediately need one.

I wrote all of the containers from scratch, so they are an 
accurate/current representation of what I would like to see.

The highlights:

1) both value and reference usage is possible.

example: <list.d>
struct ListBase { ... }   // value type list
alias RefCounted!ListBase List;   // ref counted list

List!int  list1;             // list1 is ref counted
ListBase!int  list2;    // list2 is a value type

I initially had this reversed, where List(T) was a value type, 
and ListRef(T) was a reference type, but I flipped it the other 
way to avoid unneeded copying for naive usage. I'm still not sure 
this is the right direction though. Optimization is a job of it's 
own, and it's a job for a pro. I believe the amount of effort 
spent to idiot-proof(for lack of a better term) the containers 
should be limited. Especially with the power of D's ranges, I 
think containers should generally(and in my code, usually do) 
stay put. IMO, If someone wants to pass something around, they 
should pass a range, not the container itself. My solution, 
however, does support both(ref/value), if needed.

What's currently being done in std.container.Array(T) is very 
limiting. With my approach, you have the option of value type or 
reference type. You do not have this option with the current 
"reference type" containers. Also, while you're okay if you get a 
range to the container, there is extra indirection every time you 
access the container through opIndex(), back(), front(), etc.. I 
shouldn't have to pay for this extra indirection/allocation, 
especially when the containers are about to be designed from 
scratch with this issue fully known. By embedding a reference 
count in the container, you limit the maximum achievable 
performance for what should be(IMO) an obscure use case(passing a 
container around). Again though, my solution allows both usages.

2) Cursors(iterators)

My Cursors are similar to C++ iterators, but have several key 
differences.

a) There is no begin/end/rbegin/rend/cbegin/cend/crbegin/crend... 
The cursor knows it limits, and is considered "alive" until it 
has been advanced(by one) beyond either end of the container. 
Similar to an empty range, an invalidated Cursor is gone for 
good, but can be copied ahead of time, before iteration.

b) cursors can be joined to form a range. Unlike C++ however, 
both cursors must point to elements in the container since there 
is no begin/end, and the join is inclusive. There is no "past the 
end of the container" type of Cursor to refer to. Joining two 
cursors can, at the minimum, result in a Range with a length of 1.

example:

List!int a = [1, 2, 3];
auto cur1 = a.first;
auto cur2 = a.last;
auto rng1 = cur1 ~ cur2; // join two cursors
assert(rng1.equal([1, 2, 3]));
auto rng2 = ~cur1; // convert cursor to range
assert(rng2.equal([1]));
assert(cur1 && cur1.alive);
--cur1;
assert(!cur1 && !cur1.alive);

for(auto c = a.first; c; ++c)
	writeln(*c);

My containers' find() methods return cursors, not ranges. The 
result is that code like this actually removes the element you 
intended to remove, and nothing else:

a.remove( a.find(1) );

find() should not return elements that do not match the query the 
programmer supplied as an argument, which is currently the case 
with range-based find().

I'm still considering whether the traditional C++ 
approach(begin/end/etc..) is a better idea, but haven't reach a 
conclusion. I do know, however, that ranges alone are not enough.

3) Gravy.

My containers contain, by default, most of what you'll need to 
use them. The counter argument is code-reuse, but my containers 
are lightyears away from prohibitively complex, so I think the 
way I've done things is fine. Including core functionality into 
containers allows for more efficient implementations in some 
cases. For example, a LinkedList(T) sort. This approach is also 
much friendlier to documentation and intellisense, and allows a 
programmer to find everything they need in one place.

--

There is still work to do, of course.


On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
Alexandrescu wrote:
Design by Introspection.
I prefer simple, predictable constructs.
 2. Reference containers.
 3. Eager value containers.
Both. Bit
Oct 21 2015
parent reply deadalnix <deadalnix gmail.com> writes:
On Thursday, 22 October 2015 at 02:13:12 UTC, bitwise wrote:
 I needed containers, so I implemented a few:
 https://github.com/bitwise-github/d-collections

 Currently included:

 List(T) - contiguous list like std::vector
 LinkedList(T) - doubly linked list like std::list
 Queue(T) - double-ended queue/contiguous circular buffer
 Stack(T) - contiguous fifo stack
You got such a good start with the first 2 ones, but somehow missed on consistency. You should name the 2 other ones QueueList and StackList.
 I initially had this reversed, where List(T) was a value type, 
 and ListRef(T) was a reference type, but I flipped it the other 
 way to avoid unneeded copying for naive usage. I'm still not 
 sure this is the right direction though. Optimization is a job 
 of it's own, and it's a job for a pro. I believe the amount of 
 effort spent to idiot-proof(for lack of a better term) the 
 containers should be limited. Especially with the power of D's 
 ranges, I think containers should generally(and in my code, 
 usually do) stay put. IMO, If someone wants to pass something 
 around, they should pass a range, not the container itself. My 
 solution, however, does support both(ref/value), if needed.
Reference types or COW are definitively the way to go for the naive road. Think about it, 40% to 50% of chrome memory is std::string . Eager copy is not a healthy default.
 There is still work to do, of course.
The elephant in the room: make the template parameter's type qualifier transitive with the collection's qualifier.
Oct 21 2015
next sibling parent reply bitwise <bitwise.pvt gmail.com> writes:
On Thursday, 22 October 2015 at 05:09:38 UTC, deadalnix wrote:
 On Thursday, 22 October 2015 at 02:13:12 UTC, bitwise wrote:
 I needed containers, so I implemented a few:
 https://github.com/bitwise-github/d-collections

 Currently included:

 List(T) - contiguous list like std::vector
 LinkedList(T) - doubly linked list like std::list
 Queue(T) - double-ended queue/contiguous circular buffer
 Stack(T) - contiguous fifo stack
You got such a good start with the first 2 ones, but somehow missed on consistency. You should name the 2 other ones QueueList and StackList.
Actually, I was thinking of calling them QueueSeq and StackSeq ;)
 I initially had this reversed, where List(T) was a value type, 
 and ListRef(T) was a reference type, but I flipped it the 
 other way to avoid unneeded copying for naive usage. I'm still 
 not sure this is the right direction though. Optimization is a 
 job of it's own, and it's a job for a pro. I believe the 
 amount of effort spent to idiot-proof(for lack of a better 
 term) the containers should be limited. Especially with the 
 power of D's ranges, I think containers should generally(and 
 in my code, usually do) stay put. IMO, If someone wants to 
 pass something around, they should pass a range, not the 
 container itself. My solution, however, does support 
 both(ref/value), if needed.
Reference types or COW are definitively the way to go for the naive road. Think about it, 40% to 50% of chrome memory is std::string . Eager copy is not a healthy default.
I can't ignore how many times I've heard people talking about eager-copy containers in C++ and how they're a pain. I believe the value-type option should be available though. Maybe the idea of default-ref-type containers could be taken a step further to hide the value types from casual users: struct List(T) { struct Core { ... } // specified as a fully useable container on it's own RefCounted!Core core; alias core this; } List!int.Core list; // value type container Unlike the current std.container.Array(T) though, the payload inside the container should be fully useable on it's own. I don't understand exactly how a COW container would work. Is this what's done with D strings right now? I've got a bad feeling about this idea. Containers have been around a long time, and I don't think it would be prudent to stray to far from traditional approaches.
 There is still work to do, of course.
The elephant in the room: make the template parameter's type qualifier transitive with the collection's qualifier.
Not sure exactly what you mean by this. Currently, Ranges and Cursors are templated on the type of the container, so If the container is const, you get a const Range or Cursor. I haven't gone over the containers with a fine tooth comb yet, so if you can point anything out, it would be helpful. Bit
Oct 22 2015
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, 22 October 2015 at 15:26:30 UTC, bitwise wrote:
 On Thursday, 22 October 2015 at 05:09:38 UTC, deadalnix wrote:
 The elephant in the room: make the template parameter's type 
 qualifier transitive with the collection's qualifier.
Not sure exactly what you mean by this. Currently, Ranges and Cursors are templated on the type of the container, so If the container is const, you get a const Range or Cursor. I haven't gone over the containers with a fine tooth comb yet, so if you can point anything out, it would be helpful.
LOL. const and ranges do _not_ mix well - in part because popFront inherently requires that the range be mutable - but mostly because of templates. If you have const(T)[], and you then you slap another const on it - const(const(T)[]) - the compiler knows full-well that that's equivalent to const(T[]). In fact, it even knows that if you slice a const(T[]), it's perfectly safe for the result to be const(T)[], because it's a different array, and by keeping the elements const, it won't screw with the elements of the one it was sliced from (since they're the same elements). But what about with ranges? If you have Range!(const T) and then you do const Range!(const T), is that equivalent to const(Range!T)? Maybe, maybe not. The compiler certainly doesn't treat it as such - and it can't. Similarly, if you have const(Range!T) or const(Range!(const T)), and you slice the range, the compiler doesn't magically know that the slice can be Range!(const T). As far as the compiler is concerned, we're dealing with different types here. After all, what if the Range type had something like this in it struct Range(T) { static if(is(T == const)) { // do something differently here } } The entire guts of Range could be completely different simply due to a difference in constness. Template constraints could also be used to overload on constness. So, unlike with arrays, there really is no guarantee that two instantiations of the same template are at all related to one another even when they seem to only differ by constness. Heck, to even attempt to have a range type which has an opSlice which returns a tail-const slice _requires_ that you have static ifs checking for constness, or you end up with a recursive template instantiation. So, even without getting containers involved, const and ranges do _not_ mix well, even though const and arrays get along fantastically. And when you have to start considering what a containers opSlice is going to return an how it's going to deal with const, things get that much worse (e.g. is it even going to work to have opSlice be const). And depending on the container's internals, having a range only have const access to its underlying container could be problematic. IIRC, std.container.Array has had some issues with const related to its internals not having been designed in a way that worked well with D's const. So, const throws a very interesting wrench into the mix when dealing with either ranges or containers, and the fact that const(Foo!T) is not necessarily the same as const(Foo!(const T)) can definitely be problematic. - Jonathan M Davis
Oct 22 2015
parent reply bitwise <bitwise.pvt gmail.com> writes:
On Thursday, 22 October 2015 at 15:53:21 UTC, Jonathan M Davis 
wrote:
 On Thursday, 22 October 2015 at 15:26:30 UTC, bitwise wrote:
 On Thursday, 22 October 2015 at 05:09:38 UTC, deadalnix wrote:
 The elephant in the room: make the template parameter's type 
 qualifier transitive with the collection's qualifier.
Not sure exactly what you mean by this. Currently, Ranges and Cursors are templated on the type of the container, so If the container is const, you get a const Range or Cursor. I haven't gone over the containers with a fine tooth comb yet, so if you can point anything out, it would be helpful.
LOL. const and ranges do _not_ mix well - in part because popFront inherently requires that the range be mutable - but mostly because of templates. If you have const(T)[], and you then you slap another const on it - const(const(T)[]) - the compiler knows full-well that that's equivalent to const(T[]). In fact, it even knows that if you slice a const(T[]), it's perfectly safe for the result to be const(T)[], because it's a different array, and by keeping the elements const, it won't screw with the elements of the one it was sliced from (since they're the same elements). But what about with ranges? If you have Range!(const T) and then you do const Range!(const T), is that equivalent to const(Range!T)? Maybe, maybe not. The compiler certainly doesn't treat it as such - and it can't. Similarly, if you have const(Range!T) or const(Range!(const T)), and you slice the range, the compiler doesn't magically know that the slice can be Range!(const T). As far as the compiler is concerned, we're dealing with different types here. After all, what if the Range type had something like this in it struct Range(T) { static if(is(T == const)) { // do something differently here } } The entire guts of Range could be completely different simply due to a difference in constness. Template constraints could also be used to overload on constness. So, unlike with arrays, there really is no guarantee that two instantiations of the same template are at all related to one another even when they seem to only differ by constness. Heck, to even attempt to have a range type which has an opSlice which returns a tail-const slice _requires_ that you have static ifs checking for constness, or you end up with a recursive template instantiation. So, even without getting containers involved, const and ranges do _not_ mix well, even though const and arrays get along fantastically. And when you have to start considering what a containers opSlice is going to return an how it's going to deal with const, things get that much worse (e.g. is it even going to work to have opSlice be const). And depending on the container's internals, having a range only have const access to its underlying container could be problematic. IIRC, std.container.Array has had some issues with const related to its internals not having been designed in a way that worked well with D's const. So, const throws a very interesting wrench into the mix when dealing with either ranges or containers, and the fact that const(Foo!T) is not necessarily the same as const(Foo!(const T)) can definitely be problematic. - Jonathan M Davis
Maybe look at the code next time before you LOL...... Bit
Oct 22 2015
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, 22 October 2015 at 16:29:19 UTC, bitwise wrote:
 Maybe look at the code next time before you LOL......
My point would be the same regardless. Range!(const T) and const(Range!T) - and Container!(const T) and const(Container!T) - have no relation as far as the compiler is concerned, and that makes dealing with const correctly a royal pain - particularly if you want a range to act like an array like it's supposed to be able to do (at least insofar as they have the same operations). You asked what deadalnix meant by
 The elephant in the room: make the template parameter's type 
 qualifier transitive
 with the collection's qualifier.
and I tried to explain. - Jonathan M Davis
Oct 22 2015
parent bitwise <bitwise.pvt gmail.com> writes:
On Thursday, 22 October 2015 at 17:13:48 UTC, Jonathan M Davis 
wrote:
 On Thursday, 22 October 2015 at 16:29:19 UTC, bitwise wrote:
 Maybe look at the code next time before you LOL......
My point would be the same regardless. Range!(const T) and const(Range!T) - and Container!(const T) and const(Container!T) - have no relation as far as the compiler is concerned, and that makes dealing with const correctly a royal pain - particularly if you want a range to act like an array like it's supposed to be able to do (at least insofar as they have the same operations). You asked what deadalnix meant by
 The elephant in the room: make the template parameter's type 
 qualifier transitive
 with the collection's qualifier.
and I tried to explain. - Jonathan M Davis
I'm not even sure you're talking about the same thing as deadalnix, and I think I have already done what he's asking. example: List!int a = [1, 2]; writeln( typeof(a[]).stringof ); writeln( typeof(a[].front).stringof ); writeln( is(typeof({ a[].popFront(); })).stringof ); const(List!int) b = [1, 2]; writeln( typeof(b[]).stringof ); writeln( typeof(b[].front).stringof ); writeln( is(typeof({ b[].popFront(); })).stringof ); output: Range!(ListBase!int) int true Range!(const(ListBase!int)) const(int) true Of course, neither of the following are possible because of the design of D's const. import std.container; Array!(const(int)) a; import collections; List!(const(int)) b; Both will produce compilation errors. Bit
Oct 22 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/22/15 1:09 AM, deadalnix wrote:
 The elephant in the room: make the template parameter's type qualifier
 transitive with the collection's qualifier.
Could you please give more detail on this? Thanks! -- Andrei
Oct 23 2015
parent reply deadalnix <deadalnix gmail.com> writes:
On Friday, 23 October 2015 at 11:03:37 UTC, Andrei Alexandrescu 
wrote:
 On 10/22/15 1:09 AM, deadalnix wrote:
 The elephant in the room: make the template parameter's type 
 qualifier
 transitive with the collection's qualifier.
Could you please give more detail on this? Thanks! -- Andrei
Sure. We have a problem when it come to collection in the fact that type qualifier do not turtle down as one would expect. Collection!T and Collection!const(T) are 2 completely different types. There is a good reason for this : static if (is(T == const)) { ... } . As a result thing like : void foo(T)(const Collection!const(T) c) {} void main() { Collection!T c; foo(c); // Error, GTFO ! } With the different qualifiers and implicit conversion, thing become quite tricky. You can simulate them partially with a set of carefully crafted alias this (but not having multiple alias this doesn't make things any simpler) but there is the monster of mutually recursive template instanciation that is lurking. As far as i know, jmdavis had some good work done on this, but it was far from perfect.
Oct 23 2015
next sibling parent bitwise <bitwise.pvt gmail.com> writes:
On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:

 Sure. We have a problem when it come to collection in the fact 
 that type qualifier do not turtle down as one would expect.

 Collection!T and Collection!const(T) are 2 completely different 
 types. There is a good reason for this : static if (is(T == 
 const)) { ... } . As a result thing like :

 void foo(T)(const Collection!const(T) c) {}
 void main() {
   Collection!T c;
   foo(c); // Error, GTFO !
 }

 With the different qualifiers and implicit conversion, thing 
 become quite tricky. You can simulate them partially with a set 
 of carefully crafted alias this (but not having multiple alias 
 this doesn't make things any simpler) but there is the monster 
 of mutually recursive template instanciation that is lurking.

 As far as i know, jmdavis had some good work done on this, but 
 it was far from perfect.
Why not just pass a range to foo?
Oct 23 2015
prev sibling next sibling parent reply bigsandwich <bigsandwich gmail.com> writes:
On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
 On Friday, 23 October 2015 at 11:03:37 UTC, Andrei Alexandrescu 
 wrote:
 [...]
Sure. We have a problem when it come to collection in the fact that type qualifier do not turtle down as one would expect. [...]
Its not just type qualifiers. Containers of derived types have the same problem. This is also a problem in C++.
Oct 23 2015
next sibling parent reply bitwise <bitwise.pvt gmail.com> writes:
On Friday, 23 October 2015 at 23:21:31 UTC, bigsandwich wrote:
 On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
 On Friday, 23 October 2015 at 11:03:37 UTC, Andrei 
 Alexandrescu wrote:
 [...]
Sure. We have a problem when it come to collection in the fact that type qualifier do not turtle down as one would expect. [...]
Its not just type qualifiers. Containers of derived types have the same problem. This is also a problem in C++.
Thinking deeper about this, it _should_ be the case that deadalnix's example doesn't compile. struct Container(T) { static if(is(T == const)) int changesLayout; // etc... int stuff; } Bit
Oct 23 2015
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 10/24/2015 01:36 AM, bitwise wrote:
 On Friday, 23 October 2015 at 23:21:31 UTC, bigsandwich wrote:
 On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
 On Friday, 23 October 2015 at 11:03:37 UTC, Andrei Alexandrescu wrote:
 [...]
Sure. We have a problem when it come to collection in the fact that type qualifier do not turtle down as one would expect. [...]
Its not just type qualifiers. Containers of derived types have the same problem. This is also a problem in C++.
Thinking deeper about this, it _should_ be the case that deadalnix's example doesn't compile. struct Container(T) { static if(is(T == const)) int changesLayout; // etc... int stuff; } Bit
One could introduce a way to indicate that const-conversions should be performed for instantiations of a given templated aggregate with identical layouts.
Oct 24 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/23/2015 07:21 PM, bigsandwich wrote:
 On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
 On Friday, 23 October 2015 at 11:03:37 UTC, Andrei Alexandrescu wrote:
 [...]
Sure. We have a problem when it come to collection in the fact that type qualifier do not turtle down as one would expect. [...]
Its not just type qualifiers. Containers of derived types have the same problem. This is also a problem in C++.
This is something easy to live with. In fact, mutable containers are not supposed to even convert to containers of base objects. -- Andrei
Oct 25 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10/25/2015 08:31 PM, Andrei Alexandrescu wrote:
 On 10/23/2015 07:21 PM, bigsandwich wrote:
 On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
 On Friday, 23 October 2015 at 11:03:37 UTC, Andrei Alexandrescu wrote:
 [...]
Sure. We have a problem when it come to collection in the fact that type qualifier do not turtle down as one would expect. [...]
Its not just type qualifiers. Containers of derived types have the same problem. This is also a problem in C++.
This is something easy to live with. In fact, mutable containers are not supposed to even convert to containers of base objects. -- Andrei
This is true for containers with reference semantics, but not for containers with value semantics. This compiles (D code): class A{} class B: A{} void main(){ A[2] a; B[2] b; a=b; } This does not compile (C++ code): class A{}; class B: A{}; int main(){ vector<A*> a; vector<B*> b; a=b; } However, the conversion would be safe. For persistent and COW containers, the copy would even be fast.
Oct 25 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/25/2015 05:06 PM, Timon Gehr wrote:
 class A{};
 class B: A{};

 int main(){
      vector<A*> a;
      vector<B*> b;
      a=b;
 }

 However, the conversion would be safe.
Agreed. I don't see that as an important matter though; it's after all a coercion so a function call is plenty fine. -- Andrei
Oct 25 2015
prev sibling next sibling parent reply David Nadlinger <code klickverbot.at> writes:
On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
 Collection!T and Collection!const(T) are 2 completely different 
 types.
Isn't this also required anyway because of covariance vs. contravariance considerations? — David
Oct 24 2015
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 10/24/2015 09:33 PM, David Nadlinger wrote:
 On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
 Collection!T and Collection!const(T) are 2 completely different types.
Isn't this also required anyway because of covariance vs. contravariance considerations? — David
(I'm assuming 'this' is referring to a solution to the problem.) Yes, basically one often wants bit-by-bit conversions between structs whose fields corecursively convert to each other bit-by-bit. If we had opImplicitCastTo, this could probably be implemented (somewhat inefficiently) in the library, but a targeted language feature might be in order.
Oct 24 2015
prev sibling parent reply deadalnix <deadalnix gmail.com> writes:
On Saturday, 24 October 2015 at 19:33:03 UTC, David Nadlinger 
wrote:
 On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
 Collection!T and Collection!const(T) are 2 completely 
 different types.
Isn't this also required anyway because of covariance vs. contravariance considerations? — David
It is close, but not exactly the same. Covariance/contravariance can be emutalted via alias this without too much trouble for a container (however, it is hard to ensure correctness, but I'd assume not too hard). On the other hand, the qualifier thing turtle from the collection to the element in the collection, which is not that easy to achieve.
Oct 24 2015
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, 25 October 2015 at 05:37:02 UTC, deadalnix wrote:
 On Saturday, 24 October 2015 at 19:33:03 UTC, David Nadlinger 
 wrote:
 On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
 Collection!T and Collection!const(T) are 2 completely 
 different types.
Isn't this also required anyway because of covariance vs. contravariance considerations? — David
It is close, but not exactly the same. Covariance/contravariance can be emutalted via alias this without too much trouble for a container (however, it is hard to ensure correctness, but I'd assume not too hard). On the other hand, the qualifier thing turtle from the collection to the element in the collection, which is not that easy to achieve.
The bigger problem is probably ranges rather than containers. We get tail-const slices from arrays all the time, but opSlice with no arguments isn't really a range operation (none of the range traits require it), and it's pretty painful to get it to make tail-const work with opSlice anyway (though I know that the EMSI guys were jumping through all kinds of hoops to make it work, so their containers make actually handle it reasonably well). Plus there's the fun problem of how declaring opSlice on a range causes foreach to call it, which essentially means that your range can get saved accidentally, which can be problematic (especially for ranges like RefRange). It's been a while since I sat down and worked through the various issues that we have here. I should probably do that soon and see if I can distill them down well enough to come up with a DIP to resolve them - or at least to clearly present them so that they can be discussed. What we have right now mostly works, but it falls apart in some corner cases - especially if you want to be able to operate on a range like you would an array. - Jonathan M Davis
Oct 25 2015
prev sibling next sibling parent Kagamin <spam here.lot> writes:
On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
 void foo(T)(const Collection!const(T) c) {}
 void main() {
   Collection!T c;
   foo(c); // Error, GTFO !
 }
How about this? void f(T)(const Collection!T c) { const Collection!(Unqual!T) cc = c; }
Oct 24 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/23/2015 01:44 PM, deadalnix wrote:
 On Friday, 23 October 2015 at 11:03:37 UTC, Andrei Alexandrescu wrote:
 On 10/22/15 1:09 AM, deadalnix wrote:
 The elephant in the room: make the template parameter's type qualifier
 transitive with the collection's qualifier.
Could you please give more detail on this? Thanks! -- Andrei
Sure. We have a problem when it come to collection in the fact that type qualifier do not turtle down as one would expect. Collection!T and Collection!const(T) are 2 completely different types. There is a good reason for this : static if (is(T == const)) { ... } . As a result thing like : void foo(T)(const Collection!const(T) c) {} void main() { Collection!T c; foo(c); // Error, GTFO ! }
Makes sense. The way I like to think about it is in terms of compatibility with built-in types such slices. This code works: void foo(T)(const T[] c) {} void main() { int[] c; foo(c); // fine }
 With the different qualifiers and implicit conversion, thing become
 quite tricky. You can simulate them partially with a set of carefully
 crafted alias this (but not having multiple alias this doesn't make
 things any simpler) but there is the monster of mutually recursive
 template instanciation that is lurking.

 As far as i know, jmdavis had some good work done on this, but it was
 far from perfect.
Thanks, I see. The way I see it is as the work of "alias this"; any failure can be ascribed as a burden on the alias this definition. Jonathan, do you have a link to your work? Andrei
Oct 25 2015
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, 25 October 2015 at 15:42:02 UTC, Andrei Alexandrescu 
wrote:
 Jonathan, do you have a link to your work?
Sorry, but no. I haven't mucked around with this issue recently, and whatever I have left on the topic is either buried in a newsgroup post somewhere or buried on my hard drive somewhere where I wouldn't know where to find it. Searching on the newsgroup for discussions on tail-const would find stuff related to this if you want to go spelunking, since it's the tail-const issues where the fact that const(Foo!T) and Foo!(const T) aren't related typically comes up and likely causes the largest problems. The EMSI containers may have some interesting stuff with regards to the problem, since I know that those guys tried very hard to be able to support tail-const ranges. The main thing that I recall is that if you want to be able to get a tail-const range from a const range, you have to use a static if to protect the const opSlice declaration so that you don't end up with a recursive template instantiation (since it has to return another instantiation of the range's template). And even then, an opSlice with no arguments isn't technically a standard range function, because none of the range traits require it (so you can't rely on a range having it). Rather, it's a container function for getting a range. And even if it were a range function, it wouldn't get the special treatment that arrays get when being passed to a templated function (IFTI infers an array's type as being a tail-const slice, which doesn't happen with anything else), and even if it did, a const range wouldn't implicitly convert to its tail-const variant without an alias this, which is likely to create a whole other set of problems - particularly since implicit conversions tend to wreak havoc in generic code. Handling tail-const with ranges in a manner consistent with arrays and supporting $ with ranges are probably the two big places that ranges can't currently emulate the behavior of arrays. The $ problem is technically solvable as-is, but without some form of https://issues.dlang.org/show_bug.cgi?id=7177 being implemented, changing hasSlicing or isRandomAccessRange to require that a range works with $ would likely break too much code, so no range-based code can really using $ unless it explicitly checks for it. However, I'm not sure that the tail-const problems is solvable without further language improvements. We likely need some sort of standard way to convert a const(Foo!T) to a Foo!(const T) - possibly via opSlice, since it wouldn't make sense for something that wasn't emulating an array. And we might need to make changes to IFTI so that it infers tail-const for ranges (at least if they provide such a conversion), but I'm not sure what the implications of that are. There's also the issue of accidentally slicing ranges (e.g. https://issues.dlang.org/show_bug.cgi?id=14619 ) which can cause incorrect behavior in at least some cases, depending on the range type - and if a range is a reference type, then slicing it would be akin to saving it, which could mean allocating. So, unlike with arrays, we probably don't want ranges in general to get sliced just because they're passed to a function, meaning that we may just want IFTI to not play fun games with ranges and let arrays be special there. In any case, I should probably try and find time soon to sit down and at least go over the issues in detail again so that I'm clearer on them and could possibly present a DIP intended to resolve them. I haven't dug through them recently, and my general approach up until now when I've needed to actually get work done has been to just not use const or inout with ranges. - Jonathan M Davis
Oct 25 2015
prev sibling next sibling parent =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
Alexandrescu wrote:
 Andrei
Exiting, times ahead! One thing that has caught my attention lately: I believe one way of making `std.experimental.allocator` usage (more) automatic is to add subtypes of containers for specific limited access patterns. For instance, some graph algorithms, such a calculating subgraphs, for instance: https://github.com/nordlow/justd/blob/master/knet/setops.d#L10 internally uses hashsets (currently implemented as a bool[Value]) for instance: https://github.com/nordlow/justd/blob/master/knet/setops.d#L15 only require the two primitives: - bool insert(Value value): returns true if value was stored, not already existed - bool contains(Value value) In this case (when no references are leaked), `HashSet` could be sub-typed to, say `ExpandableConstantHashSet`, which can safely and automatically make use of a `RegionAllocator` for super-performance. In this way, even complete beginners in D, could safely use Phobos containers to beat C++ performance. Destroy!
Oct 22 2015
prev sibling next sibling parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
Alexandrescu wrote:
 Internally, functional containers take advantage of common 
 substructure and immutability to share actual data. The classic 
 resource for defining and implementing functional containers is 
 http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.
Online at: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
Oct 22 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/22/2015 03:39 AM, Nordlöw wrote:
 On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei Alexandrescu wrote:
 Internally, functional containers take advantage of common
 substructure and immutability to share actual data. The classic
 resource for defining and implementing functional containers is
 http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.
Online at: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
That's the doctoral dissertation; I assume the book is more approachable. -- Andrei
Oct 22 2015
prev sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2015-10-21 13:05, Andrei Alexandrescu wrote:

 1. Functional containers.

 These are immutable; once created, neither their topology nor their
 elements may be observably changed. Manipulating a container entails
 creating an entire new container, often based on an existing container
 (e.g. append takes a container and an element and creates a whole new
 container).

 Internally, functional containers take advantage of common substructure
 and immutability to share actual data. The classic resource for defining
 and implementing functional containers is
 http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.
Can these be implemented by the user just declaring a regular container as immutable? The implement will recognize if it's declared as immutable and adapt. -- /Jacob Carlborg
Oct 24 2015
next sibling parent TheFlyingFiddle <kurtyan student.chalmers.se> writes:
On Saturday, 24 October 2015 at 09:22:37 UTC, Jacob Carlborg 
wrote:
 Can these be implemented by the user just declaring a regular 
 container as immutable? The implement will recognize if it's 
 declared as immutable and adapt.
How can a type know it's qualifier? struct Container(T) { //.... access qualifier somehow do stuff with it } alias SM = Container!int; alias SIM = immutable Container!int; It was my understanding that S!int only gets instantiated one time here? Or does the compiler instantiate (immutable S!int) and (S!int)? Or were you thinking of something else?
Oct 24 2015
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10/24/2015 11:22 AM, Jacob Carlborg wrote:
 On 2015-10-21 13:05, Andrei Alexandrescu wrote:

 1. Functional containers.

 These are immutable; once created, neither their topology nor their
 elements may be observably changed. Manipulating a container entails
 creating an entire new container, often based on an existing container
 (e.g. append takes a container and an element and creates a whole new
 container).

 Internally, functional containers take advantage of common substructure
 and immutability to share actual data. The classic resource for defining
 and implementing functional containers is
 http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.
Can these be implemented by the user just declaring a regular container as immutable? The implement will recognize if it's declared as immutable and adapt.
Even if this was possible, it would not be a very good idea. Persistent data structures have use cases that would be hindered by required transitive immutability.
Oct 24 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/24/15 3:19 PM, Timon Gehr wrote:
 Even if this was possible, it would not be a very good idea. Persistent
 data structures have use cases that would be hindered by required
 transitive immutability.
This part I don't quite get. Are there any languages that offer containers with immutable topology but mutable slots, and call them persistent data structures? -- Andrei
Oct 24 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10/24/2015 09:22 PM, Andrei Alexandrescu wrote:
 On 10/24/15 3:19 PM, Timon Gehr wrote:
 Even if this was possible, it would not be a very good idea. Persistent
 data structures have use cases that would be hindered by required
 transitive immutability.
This part I don't quite get.
The slots are not mutable, but they are not /transitively/ immutable either. Note that this does not require any special effort, nor does it /prevent/ stored elements from being (transitively) immutable. Scala does it this way. (Haskell as well, basically.)
 Are there any languages that offer
 containers with immutable topology but mutable slots, and call them
 persistent data structures? -- Andrei
Not that I know of, unless you count the hidden updates Haskell implementations may perform in order to provide lazy semantics (which 'immutable' in D prevents, this alone is a sufficient reason not to force it on users). However, that would be useful as well (as a potential performance optimization if the identity of the stored elements does not matter). This paper of Sarnak and Tarjan discusses a version of what they call persistent rb-trees that only allows updates on the last version (which is often sufficient). (The point of the restriction is to lower space usage.) It changes color information on existing nodes and it keeps mutable lists in the nodes (i.e. making the nodes immutable would not work.) http://www.link.cs.cmu.edu/15859-f07/papers/point-location.pdf One might now say that those implementation details don't matter, and that the slots should still be transitively immutable. Well, one may want to use such data structures _within_ other persistent data structures. (Just consider e.g. the case where, given a 3D point cloud of size n, and a number of axis-aligned boxes, you want a way to count the number of points in each box, given that the boxes arrive in an online fashion, while the points are known from the start. (Here, we want O(n log² n) preprocessing time, O(n log n) space and O(log² n) query time). One way to achieve that involves storing instances of an augmented version of their persistent rb-tree (they should support the range queries I have mentioned in my list of useful data structures) within a persistent augmented tree with predetermined O(log n)-depth topology (this container I had missed to mention).) You can't do that if slots are transitively immutable.
Oct 24 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/24/2015 07:03 PM, Timon Gehr wrote:
 On 10/24/2015 09:22 PM, Andrei Alexandrescu wrote:
 On 10/24/15 3:19 PM, Timon Gehr wrote:
 Even if this was possible, it would not be a very good idea. Persistent
 data structures have use cases that would be hindered by required
 transitive immutability.
This part I don't quite get.
The slots are not mutable, but they are not /transitively/ immutable either. Note that this does not require any special effort, nor does it /prevent/ stored elements from being (transitively) immutable. Scala does it this way. (Haskell as well, basically.)
I see. Well, this will be unpleasant to implement in D. One simple way to do so would be to have accessors return rvalues: T front() { ... } Then you get to change the indirections of T, if any, but not what's stored in the container directly. Problem is accessing every element by rvalue is likely to be inefficient in the general case (even on data without copy ctors). Andrei
Oct 25 2015
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 10/25/2015 08:33 PM, Andrei Alexandrescu wrote:
 On 10/24/2015 07:03 PM, Timon Gehr wrote:
 On 10/24/2015 09:22 PM, Andrei Alexandrescu wrote:
 On 10/24/15 3:19 PM, Timon Gehr wrote:
 Even if this was possible, it would not be a very good idea. Persistent
 data structures have use cases that would be hindered by required
 transitive immutability.
This part I don't quite get.
The slots are not mutable, but they are not /transitively/ immutable either. Note that this does not require any special effort, nor does it /prevent/ stored elements from being (transitively) immutable. Scala does it this way. (Haskell as well, basically.)
I see. Well, this will be unpleasant to implement in D. One simple way to do so would be to have accessors return rvalues: T front() { ... } Then you get to change the indirections of T, if any, but not what's stored in the container directly. Problem is accessing every element by rvalue is likely to be inefficient in the general case (even on data without copy ctors). Andrei
As I mentioned, the cheap way out for performance would be to provide what you suggested (persistent topology, arbitrary reference access to slots). Users can then use type qualifiers at their own discretion. There could probably even be short aliases to automatically have immutable elements. What's important is that use cases for mutable elements are not ruled out. They don't necessarily need to be on the path of least resistance.
Oct 25 2015