www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - string manipulation performance

reply "Lloyd Dupont" <ld-REMOVE galador.net> writes:
I have a method like that:
===
public string repeat(string s, int num)
{
    string result = s;
    for (int  i=1; i<num; i++)
        result ~= s;
    return result;
}
===
basically it will create num string, each a little longer...
is there a more efficient way to go about that?
thanks! :)
Jun 12 2011
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 12 Jun 2011 12:49:25 -0400, Lloyd Dupont <ld-REMOVE galador.net>  
wrote:

 I have a method like that:
 ===
 public string repeat(string s, int num)
 {
     string result = s;
     for (int  i=1; i<num; i++)
         result ~= s;
     return result;
 }
 ===
 basically it will create num string, each a little longer...
 is there a more efficient way to go about that?
 thanks! :)

The runtime tries its best to avoid allocating a new string on each append. Please read the manual on appending, and you also might want to check out an article I wrote about slices that deals with appending. The runtime also provides functions to pre-allocate an array for appending. For example: public string repeat(string s, int num) { string result = s; result.reserve(s.length * num); // ensure result can append all the repeated data without reallocating for (int i=1; i<num; i++) result ~= s; return result; } http://www.digitalmars.com/d/2.0/arrays.html#resize http://www.digitalmars.com/d/2.0/phobos/object.html#reserve http://www.dsource.org/projects/dcollections/wiki/ArrayArticle -Steve
Jun 12 2011
parent reply "Lloyd Dupont" <ld-REMOVE galador.net> writes:
But... string being immutable I don't see the point of allocating some space 
for one..
Am I missing something?

"Steven Schveighoffer"  wrote in message 
news:op.vwy503w4eav7ka localhost.localdomain...

On Sun, 12 Jun 2011 12:49:25 -0400, Lloyd Dupont <ld-REMOVE galador.net>
wrote:

 I have a method like that:
 ===
 public string repeat(string s, int num)
 {
     string result = s;
     for (int  i=1; i<num; i++)
         result ~= s;
     return result;
 }
 ===
 basically it will create num string, each a little longer...
 is there a more efficient way to go about that?
 thanks! :)

The runtime tries its best to avoid allocating a new string on each append. Please read the manual on appending, and you also might want to check out an article I wrote about slices that deals with appending. The runtime also provides functions to pre-allocate an array for appending. For example: public string repeat(string s, int num) { string result = s; result.reserve(s.length * num); // ensure result can append all the repeated data without reallocating for (int i=1; i<num; i++) result ~= s; return result; } http://www.digitalmars.com/d/2.0/arrays.html#resize http://www.digitalmars.com/d/2.0/phobos/object.html#reserve http://www.dsource.org/projects/dcollections/wiki/ArrayArticle -Steve
Jun 12 2011
parent "Lloyd Dupont" <ld-REMOVE galador.net> writes:
Thanks Steven, that was very informative!

"Steven Schveighoffer"  wrote in message 
news:op.vwzrwdmteav7ka localhost.localdomain...

On Sun, 12 Jun 2011 21:02:05 -0400, Lloyd Dupont <ld-REMOVE galador.net>
wrote:

 But... string being immutable I don't see the point of allocating some 
 space for one..
 Am I missing something?

Reserving space for appending does not make that space immutable, yet. As far as the runtime is concerned, that space is unallocated. Although it can only ever be allocated to have immutable string data, it's not allocated yet, so it can be modified in the future. Observe: string s; assert(s.ptr is null); // string is unallocated s.reserve(100); assert(s.length == 0); // reserve doesn't alter the actual string, it just sets up space for it to grow into assert(s.ptr !is null); // but now it points to a memory block! auto sptr = s.ptr; // save pointer for later proof... for(i; 0..20) s ~= "hello"; // make a bunch of hellos assert(s.length == 100); // yep, we added some data, but assert(s.ptr is sptr); // it didn't move, so essentially, it "grew" into the existing memory block, that was previously unused. The reason it works is because the unused space in the block has no references, therefore, even though it is potentially immutable, it doesn't matter that we change it because nobody else knows about it yet. Note that without the reserve call, s.ptr would not be equal to sptr at the end of the operation, because the runtime would have chosen smaller memory blocks to begin with to store the string. -Steve
Jun 12 2011
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On 2011-06-12 11:08, Steven Schveighoffer wrote:
 On Sun, 12 Jun 2011 12:49:25 -0400, Lloyd Dupont <ld-REMOVE galador.net>
 
 wrote:
 I have a method like that:
 ===
 public string repeat(string s, int num)
 {
 
     string result = s;
     for (int  i=1; i<num; i++)
     
         result ~= s;
     
     return result;
 
 }
 ===
 basically it will create num string, each a little longer...
 is there a more efficient way to go about that?
 thanks! :)

The runtime tries its best to avoid allocating a new string on each append. Please read the manual on appending, and you also might want to check out an article I wrote about slices that deals with appending. The runtime also provides functions to pre-allocate an array for appending. For example: public string repeat(string s, int num) { string result = s; result.reserve(s.length * num); // ensure result can append all the repeated data without reallocating for (int i=1; i<num; i++) result ~= s; return result; } http://www.digitalmars.com/d/2.0/arrays.html#resize http://www.digitalmars.com/d/2.0/phobos/object.html#reserve http://www.dsource.org/projects/dcollections/wiki/ArrayArticle

Also, std.string.repeat has been scheduled for deprecation. You should use std.array.replicate instead. It does the same thing but for all arrays instead of just strings. - Jonathan M Davis
Jun 12 2011
parent "Lloyd Dupont" <ld-REMOVE galador.net> writes:
Thanks!

"Jonathan M Davis"  wrote in message 
news:mailman.851.1307909610.14074.digitalmars-d-
Also, std.string.repeat has been scheduled for deprecation. You should use
std.array.replicate instead. It does the same thing but for all arrays 
instead
of just strings.

- Jonathan M Davis 
Jun 12 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On 2011-06-12 18:02, Lloyd Dupont wrote:
 But... string being immutable I don't see the point of allocating some
 space for one..
 Am I missing something?

Just because it's immutable doesn't mean that it doesn't need to exist at runtime. All immutable means is that you can't change it. It could have been created entirely at runtime with values decided entirely at runtime. An immutable variable takes up just as much space as a mutable one. The differences are that you can never change it and that it's implicitly shared. Now, manifest constants don't exist per se. e.g. enum str = "hello world"; str doesn't exist at runtime, and you can't take its address. But that's because every place that you use str, it gets replaced with its value. So, every place that it's used takes up just as much space as if you'd put the value there directly. immutable variables, however, very much exist just as much as mutable ones. - Jonathan M davis
Jun 12 2011
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 12 Jun 2011 21:02:05 -0400, Lloyd Dupont <ld-REMOVE galador.net>  
wrote:

 But... string being immutable I don't see the point of allocating some  
 space for one..
 Am I missing something?

Reserving space for appending does not make that space immutable, yet. As far as the runtime is concerned, that space is unallocated. Although it can only ever be allocated to have immutable string data, it's not allocated yet, so it can be modified in the future. Observe: string s; assert(s.ptr is null); // string is unallocated s.reserve(100); assert(s.length == 0); // reserve doesn't alter the actual string, it just sets up space for it to grow into assert(s.ptr !is null); // but now it points to a memory block! auto sptr = s.ptr; // save pointer for later proof... for(i; 0..20) s ~= "hello"; // make a bunch of hellos assert(s.length == 100); // yep, we added some data, but assert(s.ptr is sptr); // it didn't move, so essentially, it "grew" into the existing memory block, that was previously unused. The reason it works is because the unused space in the block has no references, therefore, even though it is potentially immutable, it doesn't matter that we change it because nobody else knows about it yet. Note that without the reserve call, s.ptr would not be equal to sptr at the end of the operation, because the runtime would have chosen smaller memory blocks to begin with to store the string. -Steve
Jun 12 2011