On 8/31/21 1:21 PM, deadalnix wrote:

This is the crux of the tail-const problem. The language allows tail-const for only 2 types, T[] and T*. Everything else is fully const or fully mutable.

I had an idea a long time ago, but ashamedly never brought it to fruition. But long story short, I think we need a way to specify "tail" for modifiers, and allow implicitly casting the head. Then you'd have tailconst(Vector!int), and you are good. I actually had a decent syntax for it, but I'm not sure it would fly anyway.

Null vs. empty isn't a problem for non-class reference types. Of course, without tail-const, you are kinda screwed.

I don't agree that COW is a good idea for generic collections. IIRC, C++ tried this with std::string and it was a disaster.

I think this is a great idea.

Feel free to copy any of my ideas from dcollections for this. See https://github.com/schveiguy/dcollections/blob/master/concepts.txt

Also note that Dcollections were strictly reference types, but had struct-based implementations (which could actually be swapped out with a different implementation if anyone had ever developed any). It came in handy in some cases, like the hash bucket collision linked list was just the implementation for the standard linked list.

Feel free to ping, maybe on slack. We can discuss the tail-const problem.

-Steve

On Tuesday, 31 August 2021 at 23:56:51 UTC, Steven Schveighoffer wrote:

One problem I can forsee with this approach is that, from the compiler's point of view, there is not necessarily any predictable relationship between qualifier(Template!T) and Template!(qualifier(T)). For all it knows, you could have written code like the following:

struct Vector(T)
{
    static if (is(T == const)) {
        // do one thing
    } else {
        // do something completely different
    }
}

Maybe in some restricted cases it could examine the uninstantiated template, determine that there's no funny business going on, and conclude that the implicit conversion is valid--but this kind of heuristic-based approach tends to be very brittle and compose poorly (exhibit A: issue 1807).

In general, if we want the compiler to know that a conversion from one template instantiation to another is valid, we are going to have to prove it by construction--which is to say, by writing a function (like a constructor or an opCast overload) that actually performs the conversion.

On Tuesday, 31 August 2021 at 23:56:51 UTC, Steven Schveighoffer wrote:

You seem to be confused. The C++11 standard prohibits std::string from using COW. Existing C++ implementations were using COW, and getting out of it was what was a disaster (notably, there were breaking ABI changes, which the C++ ecosystem is not well suited to handle).

On Wednesday, 1 September 2021 at 00:26:33 UTC, Paul Backus wrote:

struct Vector(T)
{
    static if (is(T == const)) {
        // do one thing
    } else {
        // do something completely different
    }
}

I think you make some good points here.

My recollection is that opHeadMutable 1 was intended as a way to inform the compiler that the conversion is valid.

On issue 1807, as much as I want that enhancement, I just hope that there is a general solution to resolve it and not just a heuristic-based one.

1 https://forum.dlang.org/post/cpxfgdmklgusodqouqdr@forum.dlang.org

On Tuesday, 31 August 2021 at 17:21:02 UTC, deadalnix wrote:

It's good that you are doing this Amaury, thanks.

We need better containers to compete with other languages. On top of that, there are patterns that other languages cannot do. One thing that comes to mind is how D is one of not many languages (languages with macros or similar probably can), that can easily allow one to write containers which lie about their layout. The most profitable example of that I can think of is automatically switching arrays of POD types to be a struct of arrays internally. This transformation makes random access to elements slower, however (say) loops where access to a subset of the elements dominates then this is much faster due to improved cache efficiency.

On Wednesday, 1 September 2021 at 01:38:49 UTC, jmh530 wrote:

It looks like opHeadMutable is basically a restricted form of "implicit opCast"--that is, rather than allowing the programmer to define arbitrary implicit conversions, it lets them define implicit conversions of the form qual(Template!(Args)) -> Template!(qual(Args)).

IMO it is a compromise that both sides would find unsatisfying. Those who want convenient implicit conversions will not be happy with it because there are important cases it does not cover (e.g. qual(Template!(qual(T))) -> qual(Template!T)), but it is still flexible enough that anyone opposed to user-defined implicit conversions in general will likely find it hard to stomach.

On Tuesday, 31 August 2021 at 23:24:57 UTC, deadalnix wrote:

Yes, and I would really like it to come of use upstream. :)

Yes. No objections afaict. All good points.

• CoW: sounds like the future direction in other languages such as Swift so no objections on that matter:

  • Should we enforce CoW or make it opt-in via storages fed as template parameters?
  • Will you be supporting

• Will you be using ranges or iterators?

• What about allocators? If you do can you please use std.experimental.allocator instead of stdx.allocator (used by emsi-containers and libdparse and dsymbol) is more than 2 years old now. std.experimental.allocator has received much love since, for instance allocateZeroed for the allocators that support it.

• An interesting emsi container that was new to me is UnrolledList. It's used extensively in dsymbol.

You should probably use robin-hood hashing if you pick open-addressing. I'm not using that (yet) in my hash sets/maps. It has very good asymptotic complexity. You should probably have a look at the state-of-the-art robin-hood implementations in C++ aswell. To run my own C++-benchmark for containers you can do

./test

under

benchmarks/containers-cxx

.

On Wednesday, 1 September 2021 at 02:08:40 UTC, max haughton wrote:

Speaking of which, here's my D implementation of struct of arrays (SoA):

https://github.com/nordlow/phobos-next/blob/master/src/nxt/soa.d

Peter Kirov has an alternative implementation providing some benefits. I've copied it into

https://github.com/nordlow/phobos-next/blob/master/src/nxt/soa_petar_kirov.d

The two implementations should be united.

Note that Petar's SoA-implementation has its capacity-property functionally deduced from the length property as

/** Returns the current capacity - the current length rounded up to a power
    of two. This assumption allows us to save on having a separate field.
*/
size_t capacity() const pure @safe
{
    return _length.roundUpToPowerOf2;
}

thereby saving a word of (stack) space. That behaviour could be opt-in aswell via a template parameter.

On Tuesday, 31 August 2021 at 17:21:02 UTC, deadalnix wrote:

You give Razvan and Andrei a ping aswell. They have done deep work on the topic of specifically trying to make RC-backed containers/collections @safe pure nothrow @nogc. One of Andrei's conclusion was that a run-time flag is needed to reveal whether a const parameter is fed an immutable argument or not.

On Wednesday, 1 September 2021 at 10:12:23 UTC, Per Nordlöw wrote:

I think COW should be the default. It is not difficult to build reference container from COW ones, so we probably don't need it to be optional, simply provide wrappr around the COW container to provide references ones.

I'm not sure what you mean here. If it is bugfixes and all, I don't have much problem with that. Container are fairly straightforward, so I don't expect the workload to be very high anyways.

This is D, we must provide ranges. But in operator and similar kind forces us to do both.

I have to admit I have not put too much thought into this.

I have no idea what that is.

Yes, that being said, I would like to not expose the implementation. PHP and python were able to move from a tree based approach to open addressing for dictionaries, for great benefit. They could do so because they didn't expose the innards of the container.

There are very interesting approach leveraging vector capabilities of modern CPU such as F14: https://engineering.fb.com/2019/04/25/developer-tools/f14/ and exposing the innards would prevent moving to them later on.