On Wednesday, 7 February 2024 at 11:46:11 UTC, Richard (Rikki) Andrew Cattermole wrote:
> My conclusion was that you really only have two use cases for composable allocators:
>
> 1. You know about memory patterns, locking, type sizes ext. Use composable directly.
> 2. Otherwise, use virtual.
>
> There doesn't seem to be anything in between.

The relevant constraint here isn't composability, it's safety.

In order to make allocators @safe (which is the goal of my proposal), you have to guarantee somehow that memory blocks can only be deallocated by the same allocator that originally allocated them.

It is possible to do this with a polymorphic allocator, but it incurs an enormous amount of runtime overhead, which rules out making it the default approach.

Of course, if you don't care about @safe, you can ignore all of this and use a much simpler design. Personally, I think Phobos V3 should support @safe as much as possible, but ultimately that choice is up to project leadership.

On Wednesday, February 7, 2024 9:54:49 AM MST Atila Neves via Digitalmars-d wrote:
> On Wednesday, 7 February 2024 at 16:20:31 UTC, Paul Backus wrote:
> > On Wednesday, 7 February 2024 at 10:10:27 UTC, Atila Neves
> >
> > wrote:
> >> [...]
> >
> > Yes, I'm aware of this problem, but I don't see a way around it.
> >
> > [...]
>
> All good points, thanks. I like the "just use ranges" approach, algorithms really shouldn't have to care what allocation strategy is backing the range they just got, and this is an insight I won't soon forget.
>
> Appending from a "different" vector will mean element copies, I guess. Or OOP. Trade offs. Trade offs everywhere.

Well, stuff that actually has to operate on the container itself is likely going to care about the exact container type (particularly things like removing an element or a range of elements based on an iterator/cursor/range), but algorithm code generally isn't going to care, because it's all going to be templatized anyway, and it'll infer the attributes as appropriate. While our container situation in Phobos needs work, I wouldn't expect things to change much with regards to algorithms. If you want to operate on the elements of a container, then you get a range from it and then all of the algorithm stuff doesn't care what kind of container you're dealing with.

But egardless of what exactly we do with allocators, I would fully expect that we're going to end up with container types that are not just templated on the element type but which are also templated on requirements that you've placed on them (i.e. Design by Introspection), and that's clearly what Robert is proposing with what he's discussed on the topic in the DLF meetings and will be talking about in his dconf online talk. There will probably be a default choice where you don't tell the container much of what you want and just get the default (e.g. GC-allocated, @safe, etc.), but I don't think that code in general is going to be passing around specific container types. Most of the time, what you really want is to pass around ranges - and when you do need to pass around an actual container, well, that's probably specific to what you're doing in your code, and then you can assume that you're using whatever it is you're using without templatizing the code using it. But in general, I wouldn't expect a library like Phobos to be passing containers around.

- Jonathan M Davis

On Wednesday, February 7, 2024 9:38:38 AM MST Paul Backus via Digitalmars-d wrote:
> On Wednesday, 7 February 2024 at 11:46:11 UTC, Richard (Rikki)
>
> Andrew Cattermole wrote:
> > My conclusion was that you really only have two use cases for composable allocators:
> >
> > 1. You know about memory patterns, locking, type sizes ext. Use
> > composable directly.
> > 2. Otherwise, use virtual.
> >
> > There doesn't seem to be anything in between.
>
> The relevant constraint here isn't composability, it's safety.
>
> In order to make allocators @safe (which is the goal of my proposal), you have to guarantee somehow that memory blocks can only be deallocated by the same allocator that originally allocated them.
>
> It is possible to do this with a polymorphic allocator, but it incurs an enormous amount of runtime overhead, which rules out making it the default approach.
>
> Of course, if you don't care about @safe, you can ignore all of this and use a much simpler design. Personally, I think Phobos V3 should support @safe as much as possible, but ultimately that choice is up to project leadership.

Allocators should be @safe where they can be, but I think that a number of us came to the conclusion a while ago that they couldn't be @safe in the general case. So, it'll be interesting to see what you can come up with, but if @safe is a requirement, I would expect that certain kinds of allocators simply won't work. But that's no reason not to support @safe as much as possible (particularly when code is templated).

But with regards to virtual vs templated, we don't necessarily have to decide in that we could design allocators so that they can be used with either approach. The templated ones would be more flexible with regards to attributes and could be better optimized, whereas there could then be virtual ones that wrapped those in classes but put harder requirements on the attributes (be it by requiring more or allowing fewer), because they're then supposed to work with most or all of the various allocator types. Then both approaches would be available.

That being said, I would expect most D code to go with the templated approach. It's what D typically does, and the kind of folks who want to use allocators are usually also the kind of folks who aren't going to be very happy about passing classes around.

And based on both what has historically been done with containers in D and the few discussions that we've had on it recently, I expect that they're very much going to be taking the Design by Introspection approach and be templated based on their capabilities (of which the allocator would be only one, though one of the possible approaches there is for one of the options be to choose between a statically chosen alocator and a dynamically chosen one).

- Jonathan M Davis

On 08/02/2024 11:00 AM, Jonathan M Davis wrote:
> That being said, I would expect most D code to go with the templated
> approach. It's what D typically does, and the kind of folks who want to use
> allocators are usually also the kind of folks who aren't going to be very
> happy about passing classes around.

I do not.

There isn't enough of a win to introducing allocators, unless you have knowledge of internals.

At which point you don't need to template your container upon the composable allocator. You'll have a dedicated one internally that isn't virtual.

This is one of my key take aways, don't pretend you need to customize the memory allocator to its usage if you don't know how it would be used. Go slower, go virtual, it'll keep you sane and allow you to build cool things.

Remember to profile. Not guess.

On Wednesday, 7 February 2024 at 22:00:49 UTC, Jonathan M Davis wrote:
> Allocators should be @safe where they can be, but I think that a number of us came to the conclusion a while ago that they couldn't be @safe in the general case. So, it'll be interesting to see what you can come up with, but if @safe is a requirement, I would expect that certain kinds of allocators simply won't work. But that's no reason not to support @safe as much as possible (particularly when code is templated).

With -preview=dip1000 and -preview=systemVariables, it is possible to make pretty much any allocator @safe--although for some of them, the safety checking adds a little bit of runtime overhead.

The main obstacle is that both of these -preview features are still very much unfinished, and will need a lot of work before they are ready to be used in real library code.

By the way, one of the key techniques that makes this work is having the allocators wrap each void[] they return in a non-copyable struct, so that it can only be deallocated once. So you can probably understand why I'm so concerned about support for non-copyable types in Phobos v3. :)

> But with regards to virtual vs templated, we don't necessarily have to decide in that we could design allocators so that they can be used with either approach.

Yes, that's the idea.

> And based on both what has historically been done with containers in D and the few discussions that we've had on it recently, I expect that they're very much going to be taking the Design by Introspection approach and be templated based on their capabilities (of which the allocator would be only one, though one of the possible approaches there is for one of the options be to choose between a statically chosen alocator and a dynamically chosen one).

This is also how I'd expect containers to work.

On Wednesday, 7 February 2024 at 22:00:49 UTC, Jonathan M Davis wrote:
> That being said, I would expect most D code to go with the templated approach. It's what D typically does,

We are here, we said we don't like them templated


> and the kind of folks who want to use allocators are usually also the kind of folks who aren't going to be very happy about passing classes around.

"classes"? the kind of people who want to use allocators are not the kind of people to make them "classes" another red flag..

Passing them around? yes, if you care about using allocators, you won't mind doing this, besides, it's limited to the places you want to control your allocations, it's not a kind of type you pass around _everywhere_

On Wednesday, February 7, 2024 10:12:06 PM MST Paul Backus via Digitalmars-d wrote:
> On Wednesday, 7 February 2024 at 22:00:49 UTC, Jonathan M Davis
>
> wrote:
> > Allocators should be @safe where they can be, but I think that a number of us came to the conclusion a while ago that they couldn't be @safe in the general case. So, it'll be interesting to see what you can come up with, but if @safe is a requirement, I would expect that certain kinds of allocators simply won't work. But that's no reason not to support @safe as much as possible (particularly when code is templated).
>
> With -preview=dip1000 and -preview=systemVariables, it is possible to make pretty much any allocator @safe--although for some of them, the safety checking adds a little bit of runtime overhead.
>
> The main obstacle is that both of these -preview features are still very much unfinished, and will need a lot of work before they are ready to be used in real library code.
>
> By the way, one of the key techniques that makes this work is having the allocators wrap each void[] they return in a non-copyable struct, so that it can only be deallocated once. So you can probably understand why I'm so concerned about support for non-copyable types in Phobos v3. :)

Well, regardless of what we end up doing iwth non-copyable types in Phobos, it's clear that the language needs improvements with regards to moving objects, which we discussed in one of the recent DLF planning meetings. DIP 1048 (move constructors) was approved ages ago, but it still hasn't been implemented yet, and to really make moving objects around even sort of user-friendly, we need the compiler to start doing things like do a move instead of a copy when it's the last use of a variable. And in particular, if we decide that making basic input ranges non-copyable is the best approach, then that's going to put pressure on getting that sorted out. The range situation in Phobos v3 is still very much in the air though.

- Jonathan M Davis