www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Better way to append to array than ~= ?

reply Vladimirs Nordholm <v vladde.net> writes:
Hello people.

I currently have a function which multiple times per second takes 
in arguments, and appends the argument as my special type. The 
following code should explain what I do more properly:

     struct MySpecialType { char c; }

     auto foo(Args...)(Args args)
     {
         MySpecialType[] bar;

         foreach(ref arg; args)
         {
             static if(is(typeof(arg) == MySpecialType))
             {
                 bar ~= arg;
             }
             else
             {
                 foreach(c; to!string(arg))
                 {
                     bar ~= MySpecialType(c);
                 }
             }
         }

         // do more stuff
     }

Now, from my trace.log, some of the topmost things on the timing 
list are `std.array.Appender!(immutable(char).<more stuff>`. I 
also remember reading some years ago that ~= isn't optimal for 
speed.

So my question is: Is there a better and/or faster way of doing 
this, or is this the best approach?
Apr 03 2018
next sibling parent reply Meta <jared771 gmail.com> writes:
On Tuesday, 3 April 2018 at 19:02:25 UTC, Vladimirs Nordholm 
wrote:
 Hello people.

 I currently have a function which multiple times per second 
 takes in arguments, and appends the argument as my special 
 type. The following code should explain what I do more properly:

     struct MySpecialType { char c; }

     auto foo(Args...)(Args args)
     {
         MySpecialType[] bar;

         foreach(ref arg; args)
         {
             static if(is(typeof(arg) == MySpecialType))
             {
                 bar ~= arg;
             }
             else
             {
                 foreach(c; to!string(arg))
                 {
                     bar ~= MySpecialType(c);
                 }
             }
         }

         // do more stuff
     }

 Now, from my trace.log, some of the topmost things on the 
 timing list are `std.array.Appender!(immutable(char).<more 
 stuff>`. I also remember reading some years ago that ~= isn't 
 optimal for speed.

 So my question is: Is there a better and/or faster way of doing 
 this, or is this the best approach?
In this specific case, since you know the length of `Args`, you can pre-allocate an array of that size and loop through it doing your initialization. However, if you want really performant code, you should allocate a static array on the stack outside of the function and pass it in as a buffer.
Apr 03 2018
parent reply Vladimirs Nordholm <v vladde.net> writes:
On Tuesday, 3 April 2018 at 19:53:11 UTC, Meta wrote:
 On Tuesday, 3 April 2018 at 19:02:25 UTC, Vladimirs Nordholm 
 wrote:
 [...]
In this specific case, since you know the length of `Args`, you can pre-allocate an array of that size and loop through it doing your initialization. However, if you want really performant code, you should allocate a static array on the stack outside of the function and pass it in as a buffer.
I don't think I know the size of the arguments. If I pass in "123" and MySpecialType('a'), the result should be: assert(foo("123", MySpecialType('a')) == [MySpecialType('1'), MySpecialType('2'), MySpecialType('3'), MySpecialType('a')]); What should the length of the pre-allocated array be?
Apr 03 2018
next sibling parent Meta <jared771 gmail.com> writes:
On Tuesday, 3 April 2018 at 20:02:46 UTC, Vladimirs Nordholm 
wrote:
 On Tuesday, 3 April 2018 at 19:53:11 UTC, Meta wrote:
 On Tuesday, 3 April 2018 at 19:02:25 UTC, Vladimirs Nordholm 
 wrote:
 [...]
In this specific case, since you know the length of `Args`, you can pre-allocate an array of that size and loop through it doing your initialization. However, if you want really performant code, you should allocate a static array on the stack outside of the function and pass it in as a buffer.
I don't think I know the size of the arguments. If I pass in "123" and MySpecialType('a'), the result should be: assert(foo("123", MySpecialType('a')) == [MySpecialType('1'), MySpecialType('2'), MySpecialType('3'), MySpecialType('a')]); What should the length of the pre-allocated array be?
You know the static types of the arguments, so it is not impossible. However, the more flexible you need to be, the more complex your code will have to be, and it probably won't be worth the added complexity. Anyway, sorry for derailing a bit. That's not really your question. Using Appender!MySpecialType might be marginally faster than ~=, but from the looks of it you are already using Appender. I don't know if there's much more you can do to speed up appending without just rolling your own solution or restructuring your code.
Apr 03 2018
prev sibling parent reply Alex <sascha.orlov gmail.com> writes:
On Tuesday, 3 April 2018 at 20:02:46 UTC, Vladimirs Nordholm 
wrote:
 On Tuesday, 3 April 2018 at 19:53:11 UTC, Meta wrote:
 On Tuesday, 3 April 2018 at 19:02:25 UTC, Vladimirs Nordholm 
 wrote:
 [...]
In this specific case, since you know the length of `Args`, you can pre-allocate an array of that size and loop through it doing your initialization. However, if you want really performant code, you should allocate a static array on the stack outside of the function and pass it in as a buffer.
I don't think I know the size of the arguments. If I pass in "123" and MySpecialType('a'), the result should be: assert(foo("123", MySpecialType('a')) == [MySpecialType('1'), MySpecialType('2'), MySpecialType('3'), MySpecialType('a')]); What should the length of the pre-allocated array be?
In my try, I iterate the args twice. The first time to calculate the number of elements, then preallocate and then iterate them again and constructing the proper objects. It is not nice, but about 1/3 of time, compared to original version, compiled in release mode. https://run.dlang.io/is/E6ckog
Apr 03 2018
parent Vladimirs Nordholm <v vladde.net> writes:
On Tuesday, 3 April 2018 at 20:41:01 UTC, Alex wrote:
 On Tuesday, 3 April 2018 at 20:02:46 UTC, Vladimirs Nordholm 
 wrote:
 On Tuesday, 3 April 2018 at 19:53:11 UTC, Meta wrote:
 [...]
I don't think I know the size of the arguments. If I pass in "123" and MySpecialType('a'), the result should be: assert(foo("123", MySpecialType('a')) == [MySpecialType('1'), MySpecialType('2'), MySpecialType('3'), MySpecialType('a')]); What should the length of the pre-allocated array be?
In my try, I iterate the args twice. The first time to calculate the number of elements, then preallocate and then iterate them again and constructing the proper objects. It is not nice, but about 1/3 of time, compared to original version, compiled in release mode. https://run.dlang.io/is/E6ckog
Yeah, I will probably need to iterate twice. Thanks a bunch 👍
Apr 04 2018
prev sibling parent Jordan Wilson <wilsonjord gmail.com> writes:
On Tuesday, 3 April 2018 at 19:02:25 UTC, Vladimirs Nordholm 
wrote:
 Hello people.

 I currently have a function which multiple times per second 
 takes in arguments, and appends the argument as my special 
 type. The following code should explain what I do more properly:

     struct MySpecialType { char c; }

     auto foo(Args...)(Args args)
     {
         MySpecialType[] bar;

         foreach(ref arg; args)
         {
             static if(is(typeof(arg) == MySpecialType))
             {
                 bar ~= arg;
             }
             else
             {
                 foreach(c; to!string(arg))
                 {
                     bar ~= MySpecialType(c);
                 }
             }
         }

         // do more stuff
     }

 Now, from my trace.log, some of the topmost things on the 
 timing list are `std.array.Appender!(immutable(char).<more 
 stuff>`. I also remember reading some years ago that ~= isn't 
 optimal for speed.

 So my question is: Is there a better and/or faster way of doing 
 this, or is this the best approach?
I believe you are right to question the ~= in regards to performance. So, what I would do is replace this loop: foreach(c; to!string(arg)) { bar ~= MySpecialType(c); } with this one liner: bar ~= arg.map!(a => MySpecialType(a.to!char)).array; To my mind, you replace multiple appends with just the one append (to be fair, I don't know what the .array is doing internally, but I'm sure whatever it does is nice and optimised). Jordan
Apr 04 2018