If I have an array:

int[] arr = [1, 2, 3];

And I use it in a concatenation chain:

auto newArr = [0] ~ arr ~ [4, 5, 6];

The compiler calls a single function to allocate these together (_d_arraycatnTX).

However, if I define a struct instead:

struct S
{
   int [] x;
   S opBinary(string s : "~")(S other) {return S(x ~ other.x); }
}

Now, if I do:

S arr = S([1, 2, 3]);

auto newArr = S([0]) ~ arr ~ S([4, 5, 6]);

I get one call PER operator, in other words, it gets translated to:

S([0])opBinary!"~"(arr).opBinary!"~"(S([4, 5, 6]));

Which means one separate allocation for each field. If you have a lot of these all put together, it could add up to a lot of allocations, with most of the allocations as temporaries.

What about an opConcatAll (or other possible name), which can accept all the following concatenations as parameters?

in other words, given:

a ~ b ~ c ~ d

will translate to

a.opConcatAll(b, c, d)

if possible.


Would that make sense?

-Steve

On Thursday, 2 July 2020 at 15:47:39 UTC, Steven Schveighoffer wrote:
> If I have an array:
>
> int[] arr = [1, 2, 3];
>
> And I use it in a concatenation chain:
>
> auto newArr = [0] ~ arr ~ [4, 5, 6];
>
> [snip]

With a few small changes, you could just as easily have written

int[] newArr;
newArr[] = [0, 0, 0] + arr[] + [4, 5, 6];

which is similar to the traditional type of problem that expression templates were designed to solve.

On 7/2/20 12:20 PM, jmh530 wrote:
> On Thursday, 2 July 2020 at 15:47:39 UTC, Steven Schveighoffer wrote:
>> If I have an array:
>>
>> int[] arr = [1, 2, 3];
>>
>> And I use it in a concatenation chain:
>>
>> auto newArr = [0] ~ arr ~ [4, 5, 6];
>>
>> [snip]
> 
> With a few small changes, you could just as easily have written
> 
> int[] newArr;
> newArr[] = [0, 0, 0] + arr[] + [4, 5, 6];
> 
> which is similar to the traditional type of problem that expression templates were designed to solve.

Hm.. I think you misunderstand the example.

-Steve

On Thursday, 2 July 2020 at 18:40:21 UTC, Steven Schveighoffer wrote:
>> [snip]
>> 
>> With a few small changes, you could just as easily have written
>> 
>> int[] newArr;
>> newArr[] = [0, 0, 0] + arr[] + [4, 5, 6];
>> 
>> which is similar to the traditional type of problem that expression templates were designed to solve.
>
> Hm.. I think you misunderstand the example.
>
> -Steve

I think I understand the example, but I may not have made my point clear enough...

You are concerned about a ~ b ~ c and avoiding unnecessary allocations.

Expression templates are concerned with problems like a + b + c and avoiding the use of unnecessary temporaries.

They seem like similar problems to me. Temporaries and allocations are obviously different, but the structure of the problem is similar. You yourself note that "most of the allocations as temporaries".

If my point makes sense, then the implication is that this is a problem that is not unique to concatenation and also applies to the mathematical operators, in their own way.

On Thursday, 2 July 2020 at 15:47:39 UTC, Steven Schveighoffer wrote:
> a ~ b ~ c ~ d
>
> will translate to
>
> a.opConcatAll(b, c, d)

Sounds good, although I think multiple other operations beside concatenation could benefit from being intercepted:

opNary(string op, T...)(T args)

E.g. perhaps BigInt can avoid one or more reallocations for >2 args. The compiler would try opNary first in that case, and fallback to successive calls to opBinary as now.

In fact, maybe some types could benefit from intercepting different operations at once:

opNary(string[] ops, T...)(T args)

On 7/2/20 3:28 PM, Nick Treleaven wrote:
> On Thursday, 2 July 2020 at 15:47:39 UTC, Steven Schveighoffer wrote:
>> a ~ b ~ c ~ d
>>
>> will translate to
>>
>> a.opConcatAll(b, c, d)
> 
> Sounds good, although I think multiple other operations beside concatenation could benefit from being intercepted:
> 
> opNary(string op, T...)(T args)
> 
> E.g. perhaps BigInt can avoid one or more reallocations for >2 args. The compiler would try opNary first in that case, and fallback to successive calls to opBinary as now.
> 
> In fact, maybe some types could benefit from intercepting different operations at once:
> 
> opNary(string[] ops, T...)(T args)

That would be awesome, and cover my case!

-Steve

On 7/2/20 3:18 PM, jmh530 wrote:
> On Thursday, 2 July 2020 at 18:40:21 UTC, Steven Schveighoffer wrote:
>>> [snip]
>>>
>>> With a few small changes, you could just as easily have written
>>>
>>> int[] newArr;
>>> newArr[] = [0, 0, 0] + arr[] + [4, 5, 6];
>>>
>>> which is similar to the traditional type of problem that expression templates were designed to solve.
>>
>> Hm.. I think you misunderstand the example.
>>
> 
> I think I understand the example, but I may not have made my point clear enough...
> 
> You are concerned about a ~ b ~ c and avoiding unnecessary allocations.
> 
> Expression templates are concerned with problems like a + b + c and avoiding the use of unnecessary temporaries.
> 
> They seem like similar problems to me. Temporaries and allocations are obviously different, but the structure of the problem is similar. You yourself note that "most of the allocations as temporaries".
> 
> If my point makes sense, then the implication is that this is a problem that is not unique to concatenation and also applies to the mathematical operators, in their own way.

OK, I see what you are saying. And yes, a generalized mechanism to handle this would be useful for both avoiding allocations and avoiding temporaries (among other things).

Nick's idea is pretty good for both.

-Steve

On Thursday, 2 July 2020 at 20:29:59 UTC, Steven Schveighoffer wrote:
> [snip]
>
> OK, I see what you are saying. And yes, a generalized mechanism to handle this would be useful for both avoiding allocations and avoiding temporaries (among other things).
>
> Nick's idea is pretty good for both.
>
> -Steve

Nick's idea only handles the case where all the operators are the same, e.g. a + b + c and not a + b - c.

On Thursday, 2 July 2020 at 20:33:47 UTC, jmh530 wrote:
> [snip]
>
> Nick's idea only handles the case where all the operators are the same, e.g. a + b + c and not a + b - c.

Oh, sorry, I didn't see that last bit. Nevermind.

On Thursday, 2 July 2020 at 19:28:15 UTC, Nick Treleaven wrote:
> On Thursday, 2 July 2020 at 15:47:39 UTC, Steven Schveighoffer wrote:
>> a ~ b ~ c ~ d
>>
>> will translate to
>>
>> a.opConcatAll(b, c, d)
>
> Sounds good, although I think multiple other operations beside concatenation could benefit from being intercepted:
>
> opNary(string op, T...)(T args)
>
> E.g. perhaps BigInt can avoid one or more reallocations for >2 args. The compiler would try opNary first in that case, and fallback to successive calls to opBinary as now.
>
> In fact, maybe some types could benefit from intercepting different operations at once:
>
> opNary(string[] ops, T...)(T args)

One typical case that this would do great for is BigInt modular exponentiation (a ^^ b) % c.

One problem with this idea is with order of operations - there's no way to distinguish (a*b)+c from a*(b+c).

I wrote[0] a suggestion two years ago for something I called rvalue types, which might be interesting for the use cases described here. Essentially, it's a type for a temporary value that will decay to a regular value whenever it's assigned to something - somewhat like an alias this that is preferred to using the actual type.

--
  Simen

[0]: https://forum.dlang.org/post/sfvqxnnibgbuebbxweqb@forum.dlang.org