www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Round VII. COW in the city, myths.

reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
Here is real test of two functions doing
the same:

char[] tolower_cow(char[] s)
char[] tolower(char[] s)

tolower_cow - simplified copy of Phobos tolower
implementing COW.

tolower - my version. no-COW - always allocates
string up front.

Results (less time - better) :

100000  strings:

  9968ms - COW
  9750ms - no-COW

50000  strings:

  2062ms - COW
  2015ms - no-COW

25000 strings:

  546ms - COW
  484ms - no-COW

10000 strings:

  140ms - COW
  125ms - no-COW

Conclusion:
In given pretty realistic example

1) COW is always slower
2) In cases when no GC involved
    COW is 12% slower then no-COW.

To Ben: probably this is the reason why Java does not use COW?

All above does not mean that COW is wrong.
It is useful in some particular situations. But far not always.

Andrew.

Source of the test - attached.
Jul 17 2005
next sibling parent reply Holger <Holger_member pathlink.com> writes:
Seems to be an interesting test.
Unfortunately, i'm unable to download the attached source.
I'm using Webbrowser (IE) to access this NG. How does one
download attachments here?

TIA,
Holger



In article <dbeli8$16e6$1 digitaldaemon.com>, Andrew Fedoniouk says...
Here is real test of two functions doing
the same:

char[] tolower_cow(char[] s)
char[] tolower(char[] s)

tolower_cow - simplified copy of Phobos tolower
implementing COW.

tolower - my version. no-COW - always allocates
string up front.

Results (less time - better) :

100000  strings:

  9968ms - COW
  9750ms - no-COW

50000  strings:

  2062ms - COW
  2015ms - no-COW

25000 strings:

  546ms - COW
  484ms - no-COW

10000 strings:

  140ms - COW
  125ms - no-COW

Conclusion:
In given pretty realistic example

1) COW is always slower
2) In cases when no GC involved
    COW is 12% slower then no-COW.

To Ben: probably this is the reason why Java does not use COW?

All above does not mean that COW is wrong.
It is useful in some particular situations. But far not always.

Andrew.

Source of the test - attached.



begin 666 cow.d
M#0H-"FEM<&]R="!S=&0N<W1D:6\[#0II;7!O<G0 <W1D+G!E<F8[#0II;7!O
M<G0 <W1D+F-T>7!E.PT*#0H-"G!U8FQI8R!I;G0 <F%N9&]M*"D-"GL-"B  
M<W1A=&EC(&EN="!R86YD;VU3965D(#T ,3(S-#L-"B  <F5T=7)N(" H<F%N
M9&]M4V5E9" ](')A;F1O;5-E960 *B R,30P,3, *R R-3,Q,#$Q*2 ^/B Q
M-BD )B P>#=&1D9&1D9&.PT*?0T*#0IP=6)L:6, :6YT(')A;F1O;2AI;G0 
M;6%X*0T*>PT*("!R971U<FX <F%N9&]M*"D )2!M87 [#0I]#0H-" T*+RHJ
M*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ* T*("H 0V]N=F5R
M="!S=')I;F< =&\ ;&]W97( 8V%S92X-"B J+PT*#0IC:&%R6UT =&]L;W=E
M<E]C;W<H8VAA<EM=(',I#0I[#0H ("  :6YT(&-H86YG960[#0H ("  :6YT
M(&D[#0H ("  8VAA<EM=('( /2!S.PT*#0H ("  8VAA;F=E9" ](# [#0H 
M("  9F]R("AI(#T ,#L :2 \(',N;&5N9W1H.R!I*RLI#0H ("  >PT*"0EC
M:&%R(&, /2!S6VE=.PT*"0EI9B H)T$G(#P](&, )B8 8R \/2 G6B<I#0H)
M"7L-" D)"6EF(" A8VAA;F=E9"D-" D)"7L)#0H)"0D)<B ](',N9'5P.PT*
M"0D)"6-H86YG960 /2 Q.PT*"0D)?0T*"0D)<EMI72 ](&, *R H8V%S="AC
M:&%R*2=A)R M("=!)RD[#0H)"7T-"B  ("!]#0H ("  <F5T=7)N('([#0I]
M#0H-"F-H87);72!T;VQO=V5R*&-H87);72!S*0T*>PT*"6-H87( =&]L;W=E
M<F,H8VAA<B!C*0T*"7L-" D)<F5T=7)N(" G02< /#T 8R F)B!C(#P]("=:
M)RD_#0H)"0D 8R K("AC87-T*&-H87(I)V$G("T )T$G*2 Z(&,[#0H)?0D)
M#0H-" EC:&%R6UT 9'-T(#T <RYD=7 [#0H)8VAA<BH <" ](&1S="YP='([
M#0H)8VAA<BH <%]E;F0 /2!P("L 9'-T+FQE;F=T:#L-" D-" EW:&EL92  
M<" \('!?96YD("D-" E[#0H)("  *G  /2!T;VQO=V5R8R J<"D[( T*"2  
M("LK<#L-" E]#0H)<F5T=7)N(&1S=#L-"GT-" T*8VAA<EM=(')A;F1O;5]S
M=')I;F<H*0T*>PT*("!I;G0 ;&5N(#T <F%N9&]M*#(P-# I.R!I9BAL96X 
M/3T ,"D ;&5N(#T ,3L-"B  8VAA<B!T6UT /2!N97< 8VAA<EML96Y=.R -
M"B  9F]R*"!I;G0 :2 ](# [(&D /"!L96X[("LK:2 I#0H ('L-"B  ("!T
M6VE=(#T <F%N9&]M*#$I/PT*"2  ("=A)R K(')A;F1O;2 G>B< +2 G82<I
M. T*"2  ("=!)R K(')A;F1O;2 G6B< +2 G02<I.PT*("!]#0H (')E='5R
M;B!T.R  #0I]#0H-" T*:6YT(&UA:6XH8VAA<EM=6UT 87)G<RD-"GL-"B  
M("!0<F]C97-S5&EM97-#;W5N=&5R(&-O=6YT97( /2!N97< 4')O8V5S<U1I
M;65S0V]U;G1E<B I.PT*"6-O;G-T(&EN="!N=6U?<W1R:6YG<R ](#(U,# P
M.PT*"0T*"6-H87);72!S=')I;F=S6VYU;5]S=')I;F=S73L-" EF;W(H(&EN
M="!I(#T ,#L :2 \(&YU;5]S=')I;F=S.R K*VD *0T*"2  ('-T<FEN9W-;
M:5T /2!R86YD;VU?<W1R:6YG*"D[#0H)"0T*"0T*("  (&-O=6YT97(N<W1A
M<G0H*3L-" D-" EF;W(H(&EN="!I(#T ,#L :2 \(&YU;5]S=')I;F=S.R K
M*VD *0T*"2  ("\O<W1R:6YG<UMI72 ]('1O;&]W97)?8V]W*'-T<FEN9W-;
M:5TI.PT*"2  ('-T<FEN9W-;:5T /2!T;VQO=V5R*'-T<FEN9W-;:5TI.PT*
M("  (&-O=6YT97(N<W1O<" I.PT*("  (%!R;V-E<W-4:6UE<T-O=6YT97(N
M:6YT97)V86Q?='EP92  ;7,Q(#T 8V]U;G1E<BYM:6QL:7-E8V]N9',H*3L-
M"B  ("!W<FET968H(FUS/25D7&XB+&US,2D[#0H)#0H)+R]F;W(H:6YT(&D 
M/2 P.R!I(#P <VEZ93L *RMI*0T*"2\O("!W<FET968H(FD])61<;B(L9&%T
A85MI72D[#0H)#0H ("  <F5T=7)N(# [#0I]#0H-" T*
`
end

Jul 17 2005
parent "Andrew Fedoniouk" <news terrainformatica.com> writes:
Here it is:


import std.stdio;
import std.perf;
import std.ctype;


public int random()
{
  static int randomSeed = 1234;
  return ((randomSeed = randomSeed * 214013 + 2531011) >> 16) & 0x7FFFFFFF;
}

public int random(int max)
{
  return random() % max;
}


/************************************
 * Convert string to lower case.
 */

char[] tolower_cow(char[] s)
{
    int changed;
    int i;
    char[] r = s;

    changed = 0;
    for (i = 0; i < s.length; i++)
    {
  char c = s[i];
  if ('A' <= c && c <= 'Z')
  {
   if (!changed)
   {
    r = s.dup;
    changed = 1;
   }
   r[i] = c + (cast(char)'a' - 'A');
  }
    }
    return r;
}

char[] tolower(char[] s)
{
 char tolowerc(char c)
 {
  return ('A' <= c && c <= 'Z')?
    c + (cast(char)'a' - 'A') : c;
 }

 char[] dst = s.dup;
 char* p = dst.ptr;
 char* p_end = p + dst.length;

 while( p < p_end )
 {
    *p = tolowerc(*p);
    ++p;
 }
 return dst;
}

char[] random_string()
{
  int len = random(2048); if(len == 0) len = 1;
  char t[] = new char[len];
  for( int i = 0; i < len; ++i )
  {
    t[i] = random(1)?
    'a' + random('z' - 'a'):
    'A' + random('Z' - 'A');
  }
  return t;
}


int main(char[][] args)
{
    ProcessTimesCounter counter = new ProcessTimesCounter();
 const int num_strings = 25000;

 char[] strings[num_strings];
 for( int i = 0; i < num_strings; ++i )
    strings[i] = random_string();


    counter.start();

 for( int i = 0; i < num_strings; ++i )
    //strings[i] = tolower_cow(strings[i]);
    strings[i] = tolower(strings[i]);
    counter.stop();
    ProcessTimesCounter.interval_type  ms1 = counter.milliseconds();
    writef("ms=%d\n",ms1);

 //for(int i = 0; i < size; ++i)
 //  writef("i=%d\n",data[i]);

    return 0;
}
Jul 17 2005
prev sibling next sibling parent Holger <Holger_member pathlink.com> writes:
Thanx a lot, quite interestind indeed.
Just one question:

2) In cases when no GC involved
    COW is 12% slower then no-COW.

How did you determine, that GC didn't kick in? Number of tolower() calls simply? Cheers, Holger In article <dbeli8$16e6$1 digitaldaemon.com>, Andrew Fedoniouk says...
Here is real test of two functions doing
the same:

char[] tolower_cow(char[] s)
char[] tolower(char[] s)

tolower_cow - simplified copy of Phobos tolower
implementing COW.

tolower - my version. no-COW - always allocates
string up front.

Results (less time - better) :

100000  strings:

  9968ms - COW
  9750ms - no-COW

50000  strings:

  2062ms - COW
  2015ms - no-COW

25000 strings:

  546ms - COW
  484ms - no-COW

10000 strings:

  140ms - COW
  125ms - no-COW

Conclusion:
In given pretty realistic example

1) COW is always slower
2) In cases when no GC involved
    COW is 12% slower then no-COW.

To Ben: probably this is the reason why Java does not use COW?

All above does not mean that COW is wrong.
It is useful in some particular situations. But far not always.

Andrew.

Source of the test - attached.



begin 666 cow.d
M#0H-"FEM<&]R="!S=&0N<W1D:6\[#0II;7!O<G0 <W1D+G!E<F8[#0II;7!O
M<G0 <W1D+F-T>7!E.PT*#0H-"G!U8FQI8R!I;G0 <F%N9&]M*"D-"GL-"B  
M<W1A=&EC(&EN="!R86YD;VU3965D(#T ,3(S-#L-"B  <F5T=7)N(" H<F%N
M9&]M4V5E9" ](')A;F1O;5-E960 *B R,30P,3, *R R-3,Q,#$Q*2 ^/B Q
M-BD )B P>#=&1D9&1D9&.PT*?0T*#0IP=6)L:6, :6YT(')A;F1O;2AI;G0 
M;6%X*0T*>PT*("!R971U<FX <F%N9&]M*"D )2!M87 [#0I]#0H-" T*+RHJ
M*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ* T*("H 0V]N=F5R
M="!S=')I;F< =&\ ;&]W97( 8V%S92X-"B J+PT*#0IC:&%R6UT =&]L;W=E
M<E]C;W<H8VAA<EM=(',I#0I[#0H ("  :6YT(&-H86YG960[#0H ("  :6YT
M(&D[#0H ("  8VAA<EM=('( /2!S.PT*#0H ("  8VAA;F=E9" ](# [#0H 
M("  9F]R("AI(#T ,#L :2 \(',N;&5N9W1H.R!I*RLI#0H ("  >PT*"0EC
M:&%R(&, /2!S6VE=.PT*"0EI9B H)T$G(#P](&, )B8 8R \/2 G6B<I#0H)
M"7L-" D)"6EF(" A8VAA;F=E9"D-" D)"7L)#0H)"0D)<B ](',N9'5P.PT*
M"0D)"6-H86YG960 /2 Q.PT*"0D)?0T*"0D)<EMI72 ](&, *R H8V%S="AC
M:&%R*2=A)R M("=!)RD[#0H)"7T-"B  ("!]#0H ("  <F5T=7)N('([#0I]
M#0H-"F-H87);72!T;VQO=V5R*&-H87);72!S*0T*>PT*"6-H87( =&]L;W=E
M<F,H8VAA<B!C*0T*"7L-" D)<F5T=7)N(" G02< /#T 8R F)B!C(#P]("=:
M)RD_#0H)"0D 8R K("AC87-T*&-H87(I)V$G("T )T$G*2 Z(&,[#0H)?0D)
M#0H-" EC:&%R6UT 9'-T(#T <RYD=7 [#0H)8VAA<BH <" ](&1S="YP='([
M#0H)8VAA<BH <%]E;F0 /2!P("L 9'-T+FQE;F=T:#L-" D-" EW:&EL92  
M<" \('!?96YD("D-" E[#0H)("  *G  /2!T;VQO=V5R8R J<"D[( T*"2  
M("LK<#L-" E]#0H)<F5T=7)N(&1S=#L-"GT-" T*8VAA<EM=(')A;F1O;5]S
M=')I;F<H*0T*>PT*("!I;G0 ;&5N(#T <F%N9&]M*#(P-# I.R!I9BAL96X 
M/3T ,"D ;&5N(#T ,3L-"B  8VAA<B!T6UT /2!N97< 8VAA<EML96Y=.R -
M"B  9F]R*"!I;G0 :2 ](# [(&D /"!L96X[("LK:2 I#0H ('L-"B  ("!T
M6VE=(#T <F%N9&]M*#$I/PT*"2  ("=A)R K(')A;F1O;2 G>B< +2 G82<I
M. T*"2  ("=!)R K(')A;F1O;2 G6B< +2 G02<I.PT*("!]#0H (')E='5R
M;B!T.R  #0I]#0H-" T*:6YT(&UA:6XH8VAA<EM=6UT 87)G<RD-"GL-"B  
M("!0<F]C97-S5&EM97-#;W5N=&5R(&-O=6YT97( /2!N97< 4')O8V5S<U1I
M;65S0V]U;G1E<B I.PT*"6-O;G-T(&EN="!N=6U?<W1R:6YG<R ](#(U,# P
M.PT*"0T*"6-H87);72!S=')I;F=S6VYU;5]S=')I;F=S73L-" EF;W(H(&EN
M="!I(#T ,#L :2 \(&YU;5]S=')I;F=S.R K*VD *0T*"2  ('-T<FEN9W-;
M:5T /2!R86YD;VU?<W1R:6YG*"D[#0H)"0T*"0T*("  (&-O=6YT97(N<W1A
M<G0H*3L-" D-" EF;W(H(&EN="!I(#T ,#L :2 \(&YU;5]S=')I;F=S.R K
M*VD *0T*"2  ("\O<W1R:6YG<UMI72 ]('1O;&]W97)?8V]W*'-T<FEN9W-;
M:5TI.PT*"2  ('-T<FEN9W-;:5T /2!T;VQO=V5R*'-T<FEN9W-;:5TI.PT*
M("  (&-O=6YT97(N<W1O<" I.PT*("  (%!R;V-E<W-4:6UE<T-O=6YT97(N
M:6YT97)V86Q?='EP92  ;7,Q(#T 8V]U;G1E<BYM:6QL:7-E8V]N9',H*3L-
M"B  ("!W<FET968H(FUS/25D7&XB+&US,2D[#0H)#0H)+R]F;W(H:6YT(&D 
M/2 P.R!I(#P <VEZ93L *RMI*0T*"2\O("!W<FET968H(FD])61<;B(L9&%T
A85MI72D[#0H)#0H ("  <F5T=7)N(# [#0I]#0H-" T*
`
end

Jul 17 2005
prev sibling next sibling parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
Function below should be changed to

char[] random_string()
{
  int len = random(2048); if(len == 0) len = 1;
  char t[] = new char[len];
  for( int i = 0; i < len; ++i )
  {
    t[i] = random(2)? // WAS: random(1)
    'a' + random('z' - 'a'):
    'A' + random('Z' - 'A');
  }
  return t;
}

Old version were always allocating string in upper case.
Interesting fact that this does not change big picture:
COW is slower in the given example.


COW is really better
when all strings are in lower case so no reallocation
happens in cow version:

char[] random_string()
{
  int len = random(2048); if(len == 0) len = 1;
  char t[] = new char[len];
  for( int i = 0; i < len; ++i )
  {
    t[i] =  'a' + random('z' - 'a'):
  }
  return t;
}

In this case COW is significantly better:
10000 strings: 15ms  (COW) versus 125ms (no-COW)

No-COW here is loosing time in D heap allocation.
In Java/.NET where memory allocation costs
pretty much "nothing" no-COW version
will be faster than COW.

"nothing" in quotes means it does have a hidden cost -
time spent in garbage collection.

All above means that strictly speaking effectivenes
of COW depends - in given
example on frequency of upper / lower strings
in the input set.

Andrew.
Jul 17 2005
parent "Ben Hinkle" <ben.hinkle gmail.com> writes:
 All above means that strictly speaking effectivenes
 of COW depends - in given
 example on frequency of upper / lower strings
 in the input set.

agreed. tolower when fed enough upper-case data will spend time figuring out if it should dup when it would be faster to just always dup. Personally I think one can only conclude that there's no silver bullet that works in all situations :-) When used for programs that deal with ordinary sentances where most words are lower case I would expect that COW comes out ahead and that toUpper would be slower.
Jul 17 2005
prev sibling next sibling parent reply Mike Capp <mike.capp gmail.com> writes:
In article <dbeli8$16e6$1 digitaldaemon.com>, Andrew Fedoniouk says...

To Ben: probably this is the reason why Java does not use COW?

I don't know about Java, but I believe the major reason why COW for std::string has been dropped by most C++ implementations is the synchronization overhead in multithreaded contexts. cheers Mike
Jul 17 2005
parent "Andrew Fedoniouk" <news terrainformatica.com> writes:
"Mike Capp" <mike.capp gmail.com> wrote in message 
news:dbeu34$1efi$1 digitaldaemon.com...
 In article <dbeli8$16e6$1 digitaldaemon.com>, Andrew Fedoniouk says...

To Ben: probably this is the reason why Java does not use COW?

I don't know about Java, but I believe the major reason why COW for std::string has been dropped by most C++ implementations is the synchronization overhead in multithreaded contexts.

Yes, I heard those rumors too. The problem is that STL is anyway not thread safe strictly speaking. So... I am personally using home-brewed string implementation. It is auto-COW and capable to use Doug's Lea MSPACEs - thread can have local string memory space - fast).
Jul 17 2005
prev sibling next sibling parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
... function which is doing inplace tolower. Obviously.

100000 strings:

Best for COW case (all strings are in lower case - no allocations):

170ms - COW tolower
156ms - inplace tolower

Worst COW case (all strings are in uppar case - dup always):

11250ms - COW tolower
234ms - inplace tolower

inplace behaves *48* times better then COW tolower
In real data (50/50) *24* times better.

Conclusions:

1) COW everywhere and anytime could degrade your app dramaticly.
2) Phobos shall include three versions of such functions.

char[] tolower( char[#] str )
void  tolower( char[] str )
char[]# tolower_cow( char[#] str )

Andrew.


--------------
void tolower_inplace(char[] s)
{
 char* p =s.ptr;
 char* p_end = p + s.length;
 while( p < p_end )
 {
    int c = *p;
    if('A' <= c && c <= 'Z')
       *p = c + (cast(char)'a' - 'A');
    ++p;
 }
}
Jul 17 2005
next sibling parent reply Chris Sauls <ibisbasenji gmail.com> writes:
Andrew Fedoniouk wrote:
 void tolower_inplace(char[] s)
 {
  char* p =s.ptr;
  char* p_end = p + s.length;
  while( p < p_end )
  {
     int c = *p;
     if('A' <= c && c <= 'Z')
        *p = c + (cast(char)'a' - 'A');
     ++p;
  }
 }

Is this any better than: # void tolower_inplace(inout char[] s) { # foreach (inout char c; s) # if ('A' <= c && c <= 'Z') # c |= 32; # } -- Chris Sauls
Jul 17 2005
parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
"Chris Sauls" <ibisbasenji gmail.com> wrote in message 
news:dbfi82$295v$1 digitaldaemon.com...
 Andrew Fedoniouk wrote:
 void tolower_inplace(char[] s)
 {
  char* p =s.ptr;
  char* p_end = p + s.length;
  while( p < p_end )
  {
     int c = *p;
     if('A' <= c && c <= 'Z')
        *p = c + (cast(char)'a' - 'A');
     ++p;
  }
 }

Is this any better than: # void tolower_inplace(inout char[] s) { # foreach (inout char c; s) # if ('A' <= c && c <= 'Z') # c |= 32; # }

Thanks, Chris, but I don't see it as improvement as *p = c + 32; and *p = c | 32; I suspect, will be executed with the same number of instructions and result.
Jul 18 2005
next sibling parent AJG <AJG_member pathlink.com> writes:
 void tolower_inplace(char[] s)
 {
  char* p =s.ptr;
  char* p_end = p + s.length;
  while( p < p_end )
  {
     int c = *p;
     if('A' <= c && c <= 'Z')
        *p = c + (cast(char)'a' - 'A');
     ++p;
  }
 }

Is this any better than: # void tolower_inplace(inout char[] s) { # foreach (inout char c; s) # if ('A' <= c && c <= 'Z') # c |= 32; # }

Thanks, Chris, but I don't see it as improvement

Other than in, say, readability... ;) --AJG.
Jul 18 2005
prev sibling parent "Walter" <newshound digitalmars.com> writes:
"Andrew Fedoniouk" <news terrainformatica.com> wrote in message
news:dbgk82$52q$1 digitaldaemon.com...
 but I don't see it as improvement
 as *p = c + 32; and *p = c | 32;
 I suspect, will be executed with the same
 number of instructions and result.

You suspect correctly. On modern CPUs, there's no difference.
Jul 21 2005
prev sibling next sibling parent reply Nick <Nick_member pathlink.com> writes:
In article <dbf67r$1sn1$1 digitaldaemon.com>, Andrew Fedoniouk says...
... function which is doing inplace tolower. Obviously.

100000 strings:

Best for COW case (all strings are in lower case - no allocations):

170ms - COW tolower
156ms - inplace tolower

Err.. no. COW is intended for when you are not supposed to change the original string. When you are not the owner of the data, you would _ALWAYS_ have to make a copy before calling the inplace version. So change your best-case code to this: // COW: char[] str = tolower_COW(original); // Inplace: char[] str = original.dup; tolower_inplace(str); and then see what happens. Nick
Jul 18 2005
parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
"Nick" <Nick_member pathlink.com> wrote in message 
news:dbftkp$2k3t$1 digitaldaemon.com...
 In article <dbf67r$1sn1$1 digitaldaemon.com>, Andrew Fedoniouk says...
... function which is doing inplace tolower. Obviously.

100000 strings:

Best for COW case (all strings are in lower case - no allocations):

170ms - COW tolower
156ms - inplace tolower

Err.. no. COW is intended for when you are not supposed to change the original string. When you are not the owner of the data, you would _ALWAYS_ have to make a copy before calling the inplace version. So change your best-case code to this:

True. This example shows just one simple thing: COW is not always such tasty as stated by COW fellowship here. COW is a technic which may help but if used blindly can degrade you app significantly. To be short: COW cannot be used as a universal principle. And phrases like "D has GC and COW" (C) Ben, scares me. I would like to highlight again - COW has practically nothing common with readonly arrays and slices problem discussed in all other Rounds. Andrew.
Jul 18 2005
next sibling parent reply Nick <Nick_member pathlink.com> writes:
In article <dbgpv6$afj$1 digitaldaemon.com>, Andrew Fedoniouk says...
This example shows just one simple thing:
COW is not always such tasty as stated by
COW fellowship here. COW is a technic
which may help but if used blindly can degrade
you app significantly.
To be short: COW cannot be used as a
universal principle.

That is of course true. In all cases where you know *with certainty* that you are the only owner, COW will always underperform compared to in-place modifications. But COW _is_ the most efficient method in the general case, where data may or may not be shared. I would guess both cases (shared data vs. single-owner data) are pretty common, so yes, maybe phobos should have two versions of each function. But I think overloading the same function names, eg. tolower(), for both cases probably isn't a good idea, though. How about using the prefix to- for the COW cases, and make- for the in-place case, as a general principle? Eg. char[] newStr = tolower(oldStr); // COW - oldStr is never changed makeLower(oldStr); // Convert in-place Nick
Jul 19 2005
parent Derek Parnell <derek psych.ward> writes:
On Tue, 19 Jul 2005 20:51:05 +0000 (UTC), Nick wrote:

 How about using the prefix to- for the COW cases, and
 make- for the in-place case, as a general principle? Eg.
 
 char[] newStr = tolower(oldStr); // COW - oldStr is never changed
 makeLower(oldStr); // Convert in-place

Nice idea. Since COW is just a convention in D, then this naming convention also makes sense. -- Derek Parnell Melbourne, Australia 20/07/2005 8:05:14 AM
Jul 19 2005
prev sibling parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
Forgive me for prolonging this thread but I feel like I have to respond. I 
would let it drop if it weren't so important to get at a solution.

 And phrases like "D has GC and COW" (C) Ben, scares me.

I'm not sure what is so interesting about what I wrote. It seems like an uncontroversial statement to me. See http://www.digitalmars.com/d/garbage.html and http://www.digitalmars.com/d/memory.html#copyonwrite for what I was referring to. Do you want to get into what is scary exactly?
Jul 19 2005
parent reply Derek Parnell <derek psych.ward> writes:
On Tue, 19 Jul 2005 20:28:03 -0400, Ben Hinkle wrote:

 Forgive me for prolonging this thread but I feel like I have to respond. I 
 would let it drop if it weren't so important to get at a solution.
 
 And phrases like "D has GC and COW" (C) Ben, scares me.

I'm not sure what is so interesting about what I wrote. It seems like an uncontroversial statement to me. See http://www.digitalmars.com/d/garbage.html and http://www.digitalmars.com/d/memory.html#copyonwrite for what I was referring to. Do you want to get into what is scary exactly?

The phrase "D has ... COW" implies that COW is built-in and automatic; that the coder doesn't have to do anything special to get it to operate. This is the 'scary' or misleading impression. -- Derek Melbourne, Australia 20/07/2005 10:48:09 AM
Jul 19 2005
parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Derek Parnell" <derek psych.ward> wrote in message 
news:15fhron8l28hr.ar386310lxno$.dlg 40tude.net...
 On Tue, 19 Jul 2005 20:28:03 -0400, Ben Hinkle wrote:

 Forgive me for prolonging this thread but I feel like I have to respond. 
 I
 would let it drop if it weren't so important to get at a solution.

 And phrases like "D has GC and COW" (C) Ben, scares me.

I'm not sure what is so interesting about what I wrote. It seems like an uncontroversial statement to me. See http://www.digitalmars.com/d/garbage.html and http://www.digitalmars.com/d/memory.html#copyonwrite for what I was referring to. Do you want to get into what is scary exactly?

The phrase "D has ... COW" implies that COW is built-in and automatic; that the coder doesn't have to do anything special to get it to operate. This is the 'scary' or misleading impression.

oh, ok. Naturally I didn't mean to imply that. I assumed we all knew D's COW wasn't built-in. Funny how the last time (or at least a recent time) COW came up http://www.digitalmars.com/d/archives/digitalmars/D/15924.html is also was a long thread with a few mis-communications. I guess my messages are write-only :-)
Jul 19 2005
parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
"Ben Hinkle" <ben.hinkle gmail.com> wrote in message 
news:dbkabn$15u9$1 digitaldaemon.com...
 "Derek Parnell" <derek psych.ward> wrote in message 
 news:15fhron8l28hr.ar386310lxno$.dlg 40tude.net...
 On Tue, 19 Jul 2005 20:28:03 -0400, Ben Hinkle wrote:

 Forgive me for prolonging this thread but I feel like I have to respond. 
 I
 would let it drop if it weren't so important to get at a solution.

 And phrases like "D has GC and COW" (C) Ben, scares me.

I'm not sure what is so interesting about what I wrote. It seems like an uncontroversial statement to me. See http://www.digitalmars.com/d/garbage.html and http://www.digitalmars.com/d/memory.html#copyonwrite for what I was referring to. Do you want to get into what is scary exactly?

The phrase "D has ... COW" implies that COW is built-in and automatic; that the coder doesn't have to do anything special to get it to operate. This is the 'scary' or misleading impression.

oh, ok. Naturally I didn't mean to imply that. I assumed we all knew D's COW wasn't built-in.

Sure I understand what you mean. But any language has COW - it is just one of many design patterns. I don't understand why D is it so ummm ... let's say ... palpitating.
 Funny how the last time (or at least a recent time) COW came up 
 http://www.digitalmars.com/d/archives/digitalmars/D/15924.html is also was 
 a long thread with a few mis-communications. I guess my messages are 
 write-only :-)

Yep. "Harry Potter. Reborn of the Horse" I guess we will see a lot of those... Andrew.
Jul 19 2005
parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Andrew Fedoniouk" <news terrainformatica.com> wrote in message 
news:dbki8s$1ct2$1 digitaldaemon.com...
 "Ben Hinkle" <ben.hinkle gmail.com> wrote in message 
 news:dbkabn$15u9$1 digitaldaemon.com...
 "Derek Parnell" <derek psych.ward> wrote in message 
 news:15fhron8l28hr.ar386310lxno$.dlg 40tude.net...
 On Tue, 19 Jul 2005 20:28:03 -0400, Ben Hinkle wrote:

 Forgive me for prolonging this thread but I feel like I have to 
 respond. I
 would let it drop if it weren't so important to get at a solution.

 And phrases like "D has GC and COW" (C) Ben, scares me.

I'm not sure what is so interesting about what I wrote. It seems like an uncontroversial statement to me. See http://www.digitalmars.com/d/garbage.html and http://www.digitalmars.com/d/memory.html#copyonwrite for what I was referring to. Do you want to get into what is scary exactly?

The phrase "D has ... COW" implies that COW is built-in and automatic; that the coder doesn't have to do anything special to get it to operate. This is the 'scary' or misleading impression.

oh, ok. Naturally I didn't mean to imply that. I assumed we all knew D's COW wasn't built-in.

Sure I understand what you mean. But any language has COW - it is just one of many design patterns.

Agreed. But I can't name another ... computer programming language and standard library runtime system ... that prefers COW over all the others. Let me make another analogy (the crowd groans): people learn how to speak French, English, Japanese, etc but when in France it is preferred to speak French. By analogy when in D speak COW unless there's a situation that warrents something else.
 I don't understand why D is it so ummm ... let's say ... palpitating.

I don't know what you mean by palpitating - you mean it gives you palpitations or that COW is palpating.
Jul 20 2005
parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
"Ben Hinkle" <ben.hinkle gmail.com> wrote in message 
news:dble7p$30j4$1 digitaldaemon.com...
 "Andrew Fedoniouk" <news terrainformatica.com> wrote in message 
 news:dbki8s$1ct2$1 digitaldaemon.com...
 "Ben Hinkle" <ben.hinkle gmail.com> wrote in message 
 news:dbkabn$15u9$1 digitaldaemon.com...
 "Derek Parnell" <derek psych.ward> wrote in message 
 news:15fhron8l28hr.ar386310lxno$.dlg 40tude.net...
 On Tue, 19 Jul 2005 20:28:03 -0400, Ben Hinkle wrote:

 Forgive me for prolonging this thread but I feel like I have to 
 respond. I
 would let it drop if it weren't so important to get at a solution.

 And phrases like "D has GC and COW" (C) Ben, scares me.

I'm not sure what is so interesting about what I wrote. It seems like an uncontroversial statement to me. See http://www.digitalmars.com/d/garbage.html and http://www.digitalmars.com/d/memory.html#copyonwrite for what I was referring to. Do you want to get into what is scary exactly?

The phrase "D has ... COW" implies that COW is built-in and automatic; that the coder doesn't have to do anything special to get it to operate. This is the 'scary' or misleading impression.

oh, ok. Naturally I didn't mean to imply that. I assumed we all knew D's COW wasn't built-in.

Sure I understand what you mean. But any language has COW - it is just one of many design patterns.

Agreed. But I can't name another ... computer programming language and standard library runtime system ... that prefers COW over all the others. Let me make another analogy (the crowd groans): people learn how to speak French, English, Japanese, etc but when in France it is preferred to speak French. By analogy when in D speak COW unless there's a situation that warrents something else.

Ok. Poetical enough :) Can I get a "Lingua Franca" somewhere here?
 I don't understand why D is it so ummm ... let's say ... palpitating.

I don't know what you mean by palpitating - you mean it gives you palpitations or that COW is palpating.

Sorry for my english. Intention was to say "COW is such crucial in/for D". Simple question: Is it possible to not to write into what is not designed to be written/changed? Why D needs such COW props?
Jul 20 2005
parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
 Simple question:
 Is it possible to not to write into what is not designed to be 
 written/changed?

I'm not sure what you mean. Are you asking if D already has C/C++ const somewhere? I thought that was the point of the proposals.
 Why D needs such COW props?

I'm not sure what you mean by props. It brings to mind "stage props" or something that stands in for a real object - like a knife in a play is not a real knife. Is that what you mean?
Jul 20 2005
parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
"Ben Hinkle" <bhinkle mathworks.com> wrote in message 
news:dbmb0a$pd1$1 digitaldaemon.com...
 Simple question:
 Is it possible to not to write into what is not designed to be 
 written/changed?

I'm not sure what you mean. Are you asking if D already has C/C++ const somewhere? I thought that was the point of the proposals.

Usually effective COW implementations use reference counting to do copy only when it is really needed. Surprisingly but in case of D string package I think it is better to do not use COW at all. See: Caller of toupper or replace knows better if it owns the string or not. If it is an owner of the string then toupper don't need to allocate anything. If caller is not owner then it should create temp buffer for that. Caller may decide to allocate such buffer on stack eliminating need of any heap operations. In case of heap caller shall delete this buffer explicitly and do not left garbage after itself. As a rule operations like toupper used in various sort of parsers which are reading streams in token buffers. These token buffers are preallocated strings and in most cases allow such manipulations / modifications. In any case it is better to give a choice in the library: void makelower(char[]) char[] tolower(char[#]) But, again, to do not use COW here. Not too much gain in D anyway. COW perfectly works for strings using reference counting but in D COW used so blindly is not optimal.
 Why D needs such COW props?

I'm not sure what you mean by props. It brings to mind "stage props" or something that stands in for a real object - like a knife in a play is not a real knife. Is that what you mean?

I mean this: prop (n.) 1. An object placed beneath or against a structure to keep it from falling or shaking; a support. 2. One that serves as a means of support or assistance. Andrew.
Jul 20 2005
next sibling parent "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Andrew Fedoniouk" <news terrainformatica.com> wrote in message 
news:dbmd3g$r3n$1 digitaldaemon.com...
 "Ben Hinkle" <bhinkle mathworks.com> wrote in message 
 news:dbmb0a$pd1$1 digitaldaemon.com...
 Simple question:
 Is it possible to not to write into what is not designed to be 
 written/changed?

I'm not sure what you mean. Are you asking if D already has C/C++ const somewhere? I thought that was the point of the proposals.

Usually effective COW implementations use reference counting to do copy only when it is really needed. Surprisingly but in case of D string package I think it is better to do not use COW at all. See: Caller of toupper or replace knows better if it owns the string or not. If it is an owner of the string then toupper don't need to allocate anything. If caller is not owner then it should create temp buffer for that. Caller may decide to allocate such buffer on stack eliminating need of any heap operations. In case of heap caller shall delete this buffer explicitly and do not left garbage after itself. As a rule operations like toupper used in various sort of parsers which are reading streams in token buffers. These token buffers are preallocated strings and in most cases allow such manipulations / modifications. In any case it is better to give a choice in the library: void makelower(char[]) char[] tolower(char[#]) But, again, to do not use COW here. Not too much gain in D anyway. COW perfectly works for strings using reference counting but in D COW used so blindly is not optimal.

If one wants to program in D as one would in C one can - just that the standard library is designed for COW. Personally I prefer the benefits of COW (simplicity, maintenance, usability, good performance) and I'll do the memory micromanaging after profiling to see if the performance needs tweaking. Should phobos get an inplace upper/lower? Walter can decide if he wants to or not. A user-supplied inplace upper/lower case converter would be a nice download for those who want it. Creating a GC-free version of phobos is what some people are doing on dsource so that might have some of the functionality you're looking for.
 Why D needs such COW props?

I'm not sure what you mean by props. It brings to mind "stage props" or something that stands in for a real object - like a knife in a play is not a real knife. Is that what you mean?

I mean this: prop (n.) 1. An object placed beneath or against a structure to keep it from falling or shaking; a support. 2. One that serves as a means of support or assistance.

ok. I'm still not sure what you meant then but it probably isn't important.
Jul 20 2005
prev sibling parent reply "Walter" <newshound digitalmars.com> writes:
"Andrew Fedoniouk" <news terrainformatica.com> wrote in message
news:dbmd3g$r3n$1 digitaldaemon.com...
 Usually effective COW implementations use reference
 counting to do copy only when it is really needed.

These methods work reasonably well in a single threaded environment. In multithreaded environments, however, ref-counted COW behaves poorly. This is because the ref counting has to be protected with locks, mutexes, etc. I've written projects using mark/sweep that beat the pants off of ref-counting code written by others for multi-threaded environments.
Jul 21 2005
next sibling parent reply Jan-Eric Duden <jeduden whisset.com> writes:
Walter wrote:
 "Andrew Fedoniouk" <news terrainformatica.com> wrote in message
 news:dbmd3g$r3n$1 digitaldaemon.com...
 These methods work reasonably well in a single threaded environment. In
 multithreaded environments, however, ref-counted COW behaves poorly. This is
 because the ref counting has to be protected with locks, mutexes, etc.

How about for example the Win32 function InterlockedIncrement for ref counting? I think it doesn't use locks, mutexes and so forth. Jan-Eric
Jul 21 2005
parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
"Jan-Eric Duden" <jeduden whisset.com> wrote in message 
news:42DFAB33.7040407 whisset.com...
 Walter wrote:
 "Andrew Fedoniouk" <news terrainformatica.com> wrote in message
 news:dbmd3g$r3n$1 digitaldaemon.com...
 These methods work reasonably well in a single threaded environment. In
 multithreaded environments, however, ref-counted COW behaves poorly. This 
 is
 because the ref counting has to be protected with locks, mutexes, etc.

How about for example the Win32 function InterlockedIncrement for ref counting? I think it doesn't use locks, mutexes and so forth. Jan-Eric

That would indeed synchronize the inc/dec but it would still have problems that after reading the count it can be changed. For example the pseudo-code if (count > 1) duplicate write value fails if the count is incremented to 2 after the if condition is tested but before the write happens. So to be safe one needs more synchronization than just the count inc/dec - the entire operation of checking the count and reading/writing needs to be atomic.
Jul 21 2005
next sibling parent Jan-Eric Duden <jeduden whisset.com> writes:
Ben Hinkle wrote:
 "Jan-Eric Duden" <jeduden whisset.com> wrote in message 
 news:42DFAB33.7040407 whisset.com...
 
Walter wrote:

"Andrew Fedoniouk" <news terrainformatica.com> wrote in message
news:dbmd3g$r3n$1 digitaldaemon.com...
These methods work reasonably well in a single threaded environment. In
multithreaded environments, however, ref-counted COW behaves poorly. This 
is
because the ref counting has to be protected with locks, mutexes, etc.

How about for example the Win32 function InterlockedIncrement for ref counting? I think it doesn't use locks, mutexes and so forth. Jan-Eric

That would indeed synchronize the inc/dec but it would still have problems that after reading the count it can be changed. For example the pseudo-code if (count > 1) duplicate write value fails if the count is incremented to 2 after the if condition is tested but before the write happens. So to be safe one needs more synchronization than just the count inc/dec - the entire operation of checking the count and reading/writing needs to be atomic.

I'm not sure, but may be with some careful thinking one can find some shortcuts here. A feeling in my gut says it shouldn't be that expensive. ;) Jan-Eric
Jul 21 2005
prev sibling parent reply "Uwe Salomon" <post uwesalomon.de> writes:
 the entire operation of checking the count and
 reading/writing needs to be atomic.

And there are machine instructions for this problem. The Qt library uses this "atomic reference counting" for its containers. These are a few lines of assembler for every target platform. Ciao uwe
Jul 21 2005
parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Uwe Salomon" <post uwesalomon.de> wrote in message 
news:op.st9qmlt06yjbe6 sandmann.maerchenwald.net...
 the entire operation of checking the count and
 reading/writing needs to be atomic.

And there are machine instructions for this problem. The Qt library uses this "atomic reference counting" for its containers. These are a few lines of assembler for every target platform. Ciao uwe

There are machine instructions to test and set (or increment) a memory location but I was referring to testing the count and setting some array content which would require using two memory locations. Glancing over the QString it looks like RAII is used to avoid the problem - though I haven't looked at the details.
Jul 21 2005
parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Ben Hinkle" <ben.hinkle gmail.com> wrote in message 
news:dbp9bj$fc$1 digitaldaemon.com...
 "Uwe Salomon" <post uwesalomon.de> wrote in message 
 news:op.st9qmlt06yjbe6 sandmann.maerchenwald.net...
 the entire operation of checking the count and
 reading/writing needs to be atomic.

And there are machine instructions for this problem. The Qt library uses this "atomic reference counting" for its containers. These are a few lines of assembler for every target platform. Ciao uwe

There are machine instructions to test and set (or increment) a memory location but I was referring to testing the count and setting some array content which would require using two memory locations. Glancing over the QString it looks like RAII is used to avoid the problem - though I haven't looked at the details.

Actually looking more closely an expression like str[i]='a' isn't thread-safe. The thread safety only applies to the memory management.
Jul 21 2005
parent reply "Uwe Salomon" <post uwesalomon.de> writes:
 Actually looking more closely an expression like str[i]='a' isn't
 thread-safe. The thread safety only applies to the memory management.

Yes. The refcounting itself is thread-safe. But that's enough if you don't modify strings that are referenced more than once. Ciao uwe
Jul 22 2005
next sibling parent "Regan Heath" <regan netwin.co.nz> writes:
On Fri, 22 Jul 2005 09:55:40 +0200, Uwe Salomon <post uwesalomon.de> wrote:
 Actually looking more closely an expression like str[i]='a' isn't
 thread-safe. The thread safety only applies to the memory management.

Yes. The refcounting itself is thread-safe. But that's enough if you don't modify strings that are referenced more than once.

IMO that's all we need in D to do COW with surety, an indication that we are the owner of the string, the only reference holder, etc. Regan
Jul 22 2005
prev sibling parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Uwe Salomon" <post uwesalomon.de> wrote in message 
news:op.sua1m2y56yjbe6 sandmann.maerchenwald.net...
 Actually looking more closely an expression like str[i]='a' isn't
 thread-safe. The thread safety only applies to the memory management.

Yes. The refcounting itself is thread-safe. But that's enough if you don't modify strings that are referenced more than once. Ciao uwe

Agreed. I was thinking of code like QString s; thread 1: s[0] = 'a'; thread 2: QString y(s); y[0]; y[0]; which can result in the y[0] returning different values in thread 2. Granted the code has a race condition anyway so the best one could hope for is that the y[0] return either their initial value or 'a' consitently. The code QString s; thread 1: QString x(s); x[0] = 'a'; thread 2: QString y(s); y[0]; y[0]; is fine since the copy-on-write would detect x reference and dup before changing the value. I guess my (nit-picking) beef is that the implicit sharing is visible to multi-threaded users so that it isn't completely implicit.
Jul 22 2005
parent reply "Uwe Salomon" <post uwesalomon.de> writes:
 Agreed. I was thinking of code like
   QString s;
   thread 1: s[0] = 'a';
   thread 2: QString y(s); y[0]; y[0];
 which can result in the y[0] returning different values in thread 2.

Yes, of course. As a char[] is not implicitly shared, you cannot expect thread-safety here. You have to work with QStrings throughout to play safe. But, personally, i don't like this programming paradigm. I normally think in terms of "ownership", and dup when the owner changes. Ciao uwe
Jul 22 2005
parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
"Uwe Salomon" <post uwesalomon.de> wrote in message 
news:op.subinjm26yjbe6 sandmann.maerchenwald.net...
 Agreed. I was thinking of code like
   QString s;
   thread 1: s[0] = 'a';
   thread 2: QString y(s); y[0]; y[0];
 which can result in the y[0] returning different values in thread 2.

Yes, of course. As a char[] is not implicitly shared, you cannot expect thread-safety here. You have to work with QStrings throughout to play safe. But, personally, i don't like this programming paradigm. I normally think in terms of "ownership", and dup when the owner changes.

These are QStrings everywhere - no char[]'s. Use "at" or any modifying operator if operator[] looks too much like char[].
Jul 22 2005
parent reply "Uwe Salomon" <post uwesalomon.de> writes:
   QString s;
   thread 1: s[0] = 'a';
   thread 2: QString y(s); y[0]; y[0];
 which can result in the y[0] returning different values in thread 2.

Yes, of course. As a char[] is not implicitly shared, you cannot expect thread-safety here. You have to work with QStrings throughout to play safe. But, personally, i don't like this programming paradigm. I normally think in terms of "ownership", and dup when the owner changes.

These are QStrings everywhere - no char[]'s. Use "at" or any modifying operator if operator[] looks too much like char[].

Ok i see. Well, in this case the above example will return the same values even in a multithreaded environment. That's because s[0] = 'a' takes a copy of the string (there are 2 references on it). Ciao uwe
Jul 22 2005
parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
"Uwe Salomon" <post uwesalomon.de> wrote in message 
news:op.subsrszr6yjbe6 sandmann.maerchenwald.net...
   QString s;
   thread 1: s[0] = 'a';
   thread 2: QString y(s); y[0]; y[0];
 which can result in the y[0] returning different values in thread 2.

Yes, of course. As a char[] is not implicitly shared, you cannot expect thread-safety here. You have to work with QStrings throughout to play safe. But, personally, i don't like this programming paradigm. I normally think in terms of "ownership", and dup when the owner changes.

These are QStrings everywhere - no char[]'s. Use "at" or any modifying operator if operator[] looks too much like char[].

Ok i see. Well, in this case the above example will return the same values even in a multithreaded environment. That's because s[0] = 'a' takes a copy of the string (there are 2 references on it). Ciao uwe

The "s" is global reference. Here's what I'm arguing happens: 1) s is constructed and filled with some data. It is the sole owner of the data so the ref count is 1. 2) Thread 1 enters the s[0] = 'a' statement. The operator[] makes and returns a QCharRef (which contains a field str of type QString& not a QString so it does not increment the ref count for s). 3) Thread 1 starts to evaluate the assignment. The QCharRef assignment operator has the following code if (str.count > 1) expand(); // dup if multiple refs str.data[i] = val; so since the ref count is 1 it does not duplicate the data. Now between the if statement and the std.data[i]=val suppose a thread context switch happens and 4) Thread 2 enters the constructor QString y(s) which increments the ref count and shares the data pointer with s. 5) Thread 2 evaluates the y[0] statement which reads the shared array item 0. Note that reading a string does not check the ref count. 6) Thread 1 switches back in and evaluates the assignment str.data[i] = val 7) Thread 2 switches and evaluates the y[0] which now picks up the new value in the shared data. So I'm arguing it can be pretty subtle just what is allowed with QString and what isn't. The documentation for QString is correct and the case I've described above is not contradicting their documentation since the threading switches involve a shared reference "s".
Jul 22 2005
parent "Uwe Salomon" <post uwesalomon.de> writes:
 So I'm arguing it can be pretty subtle just what is allowed with QString  
 and
 what isn't. The documentation for QString is correct and the case I've
 described above is not contradicting their documentation since the  
 threading switches involve a shared reference "s".

You are right, of course. Well, quirky tricks always come with some caveats... Ciao uwe
Jul 22 2005
prev sibling parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
"Walter" <newshound digitalmars.com> wrote in message 
news:dbnn3j$1raf$1 digitaldaemon.com...
 "Andrew Fedoniouk" <news terrainformatica.com> wrote in message
 news:dbmd3g$r3n$1 digitaldaemon.com...
 Usually effective COW implementations use reference
 counting to do copy only when it is really needed.

These methods work reasonably well in a single threaded environment. In multithreaded environments, however, ref-counted COW behaves poorly. This is because the ref counting has to be protected with locks, mutexes, etc. I've written projects using mark/sweep that beat the pants off of ref-counting code written by others for multi-threaded environments.

No doubts. I am personally using COW strings in multithreading environments without any locking. Sharing strings as any other dynamic data between threads needs special design strategies. I mean - string is too atomic object to lock each instance of it. Andrew.
Jul 21 2005
parent reply "Walter" <newshound digitalmars.com> writes:
"Andrew Fedoniouk" <news terrainformatica.com> wrote in message
news:dboh94$2ed8$1 digitaldaemon.com...
 No doubts.
 I am personally using COW strings in multithreading
 environments without any locking.
 Sharing strings as any other dynamic data between threads
 needs special design strategies. I mean - string is
 too atomic object to lock each instance of it.

Special design strategies can be very effective on an application by application basis, but almost by definition won't work for a general purpose library.
Jul 21 2005
parent "Andrew Fedoniouk" <news terrainformatica.com> writes:
"Walter" <newshound digitalmars.com> wrote in message 
news:dbon46$2jgs$1 digitaldaemon.com...
 "Andrew Fedoniouk" <news terrainformatica.com> wrote in message
 news:dboh94$2ed8$1 digitaldaemon.com...
 No doubts.
 I am personally using COW strings in multithreading
 environments without any locking.
 Sharing strings as any other dynamic data between threads
 needs special design strategies. I mean - string is
 too atomic object to lock each instance of it.

Special design strategies can be very effective on an application by application basis, but almost by definition won't work for a general purpose library.

Sure. Walter, I am not convincing anybody to use refcounted strings in D. They are good for specific cases and task domains. Under the GC it is just possible to use immutable character arrays as strings. Not always optimal (for specific tasks) but possible. Without GC refcounted or auto string as a solution is more valuable. But again string is an immutable character array - it is a type. Let's don't mix this problem with "immutable in" - this is from other opera.
Jul 21 2005
prev sibling next sibling parent "Ben Hinkle" <ben.hinkle gmail.com> writes:
 Conclusions:

 1) COW everywhere and anytime could degrade your app dramaticly.

No-one was suggesting inplace is slower than COW. One can rephrase this conclusion as "allocating memory can dramatically slow down your app".
 2) Phobos shall include three versions of such functions.

 char[] tolower( char[#] str )
 void  tolower( char[] str )
 char[]# tolower_cow( char[#] str )

Who knows what the future holds but personally I hope phobos doesn't bloat with three versions of any COW function. If one determines that in an application a particular function is a bottleneck code up one tailered for the application and use that instead of the standard one.
Jul 18 2005
prev sibling parent reply AJG <AJG_member pathlink.com> writes:
Hi,

2) Phobos shall include three versions of such functions.
char[] tolower( char[#] str )
void  tolower( char[] str )
char[]# tolower_cow( char[#] str )

I think, if the recent proposal to make in/out/inout mandatory at the call site is taken seriously (which I think would be a _good_ thing), then phobos could probably get away with 2 versions: string tolower(in /* readonly */ string str); // Returns a lowered _dup_ of the string. // If no changes made, it can be made to return the same reference. string tolower(inout string str); // Changes the string in place, and returns the same reference. No duping ever. I think this kind of overloading would be fairly useful, if only for this purpose. I don't think it would bloat, because the first one could be easily implemented in terms of the second one: # string tolower(in /* readonly */ string str) { # string buf = str.dup; # if (str == tolower(inout buf)) { // No changes made. # delete buf; # return (str); # } else return (buf); // Changes were made. # } And: # string tolower(inout string str) { # foreach (inout char c; str) if ('A' <= c && c <= 'Z') c |= 32; # return (str); // This is simply for convenience. # } Cheers, --AJG.
Jul 18 2005
parent "Andrew Fedoniouk" <news terrainformatica.com> writes:
"AJG" <AJG_member pathlink.com> wrote in message 
news:dbgc5t$2vsa$1 digitaldaemon.com...
 Hi,

2) Phobos shall include three versions of such functions.
char[] tolower( char[#] str )
void  tolower( char[] str )
char[]# tolower_cow( char[#] str )

I think, if the recent proposal to make in/out/inout mandatory at the call site is taken seriously (which I think would be a _good_ thing), then phobos could probably get away with 2 versions: string tolower(in /* readonly */ string str); // Returns a lowered _dup_ of the string. // If no changes made, it can be made to return the same reference. string tolower(inout string str); // Changes the string in place, and returns the same reference. No duping ever. I think this kind of overloading would be fairly useful, if only for this purpose. I don't think it would bloat, because the first one could be easily implemented in terms of the second one: # string tolower(in /* readonly */ string str) { # string buf = str.dup; # if (str == tolower(inout buf)) { // No changes made. # delete buf; # return (str); # } else return (buf); // Changes were made. # } And: # string tolower(inout string str) { # foreach (inout char c; str) if ('A' <= c && c <= 'Z') c |= 32; # return (str); // This is simply for convenience. # }

inout is one more level of indirection and obviously is not needed here. BTW: "foreach (inout char c; str) if ('A' <= c && c <= 'Z') c |= 32;" such cycle will not work for UTF-8 - use with care.
 Cheers,
 --AJG.

 

Jul 18 2005
prev sibling next sibling parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
"Andrew Fedoniouk" <news terrainformatica.com> wrote in message 
news:dbeli8$16e6$1 digitaldaemon.com...
 Here is real test of two functions doing
 the same:

 char[] tolower_cow(char[] s)
 char[] tolower(char[] s)

 tolower_cow - simplified copy of Phobos tolower
 implementing COW.

 tolower - my version. no-COW - always allocates
 string up front.

I modified the parameters slightly to 1) allocate strings of length between 1 and 20 instead of 1 and 2048 2) eye-balling English text I changed the probability of upper case to 1 in 40 instead of 1 in 2. With those parameters cow gives ~3187ms and dup gives ~3218ms. So with strings that are roughly the length of a word or two with upper-case roughly what happens in regular text I can't tell a difference between cow and always duping. YMMV
Jul 18 2005
parent "Ben Hinkle" <bhinkle mathworks.com> writes:
"Ben Hinkle" <bhinkle mathworks.com> wrote in message 
news:dbgb5g$2utt$1 digitaldaemon.com...
 "Andrew Fedoniouk" <news terrainformatica.com> wrote in message 
 news:dbeli8$16e6$1 digitaldaemon.com...
 Here is real test of two functions doing
 the same:

 char[] tolower_cow(char[] s)
 char[] tolower(char[] s)

 tolower_cow - simplified copy of Phobos tolower
 implementing COW.

 tolower - my version. no-COW - always allocates
 string up front.

I modified the parameters slightly to 1) allocate strings of length between 1 and 20 instead of 1 and 2048 2) eye-balling English text I changed the probability of upper case to 1 in 40 instead of 1 in 2. With those parameters cow gives ~3187ms and dup gives ~3218ms. So with strings that are roughly the length of a word or two with upper-case roughly what happens in regular text I can't tell a difference between cow and always duping. YMMV

oops - I made a mistake. The numbers posted above were for upper-case 40-to-1 not 1-to-40. I didn't pay enough attention to the ?: logic. When I get the ratio right the cow version becomes ~610ms so it is significantly faster than always-dup. still YMMV.
Jul 18 2005
prev sibling parent reply "Walter" <newshound digitalmars.com> writes:
"Andrew Fedoniouk" <news terrainformatica.com> wrote in message
news:dbeli8$16e6$1 digitaldaemon.com...
 Conclusion:
 In given pretty realistic example

It's an interesting benchmark, but I don't agree it is realistic. The strings presented by the test program to the tolower_cow() function will need to .dup the string essentially 100% of the time (as the string length is evenly distributed between 1 and 2048, and each character will be uppercase 50% of the time). Duping the string with a test 100% of the time will, inevitably, be slower than simply duping 100% of the time and skipping the test. COW is an effective optimization only when the data doesn't need to change a significant percentage of the time. Real text tends to be 100% lower case most of the time (just look at this post, for example). So, I suggest feeding the program some real text, such as splitting into words the complete text of "Alice in Wonderland" which is linked to from www.digitalmars.com/d/cppstrings.html. It'll be fun to see what the relative timings are for that. Of course, as always, when tuning for speed one must tune to the actual data expected. std.string.tolower(), being a library function, doesn't have the luxury of knowing this in advance, so we just make the best guess we can and go from there.
Jul 21 2005
parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
"Walter" <newshound digitalmars.com> wrote in message 
news:dbnmh1$1qu3$1 digitaldaemon.com...
 "Andrew Fedoniouk" <news terrainformatica.com> wrote in message
 news:dbeli8$16e6$1 digitaldaemon.com...
 Conclusion:
 In given pretty realistic example

It's an interesting benchmark, but I don't agree it is realistic. The strings presented by the test program to the tolower_cow() function will need to .dup the string essentially 100% of the time (as the string length is evenly distributed between 1 and 2048, and each character will be uppercase 50% of the time). Duping the string with a test 100% of the time will, inevitably, be slower than simply duping 100% of the time and skipping the test. COW is an effective optimization only when the data doesn't need to change a significant percentage of the time.

Agreed. This is just a demonstration of the fact that COW cannot be used as a "silver bullet".
 Real text tends to be 100% lower case most of the time (just look at this
 post, for example). So, I suggest feeding the program some real text, such
 as splitting into words the complete text of "Alice in Wonderland" which 
 is
 linked to from www.digitalmars.com/d/cppstrings.html. It'll be fun to see
 what the relative timings are for that.

 Of course, as always, when tuning for speed one must tune to the actual 
 data
 expected. std.string.tolower(), being a library function, doesn't have the
 luxury of knowing this in advance, so we just make the best guess we can 
 and
 go from there.

In those C RTLs which have strlwr functions it is implemented as in-place function. In C++ libraries it usually implemented as: void strlwr(string &s); void strupr(string &s); string strlwr(const string &s); string strupr(const string &s); And for me this makes much more sense than then Phobos "dcowed" version - gives me more choices for optimisations.
Jul 21 2005
parent reply Sean Kelly <sean f4.ca> writes:
In article <dbp0i4$2rph$1 digitaldaemon.com>, Andrew Fedoniouk says...
In those C RTLs which have strlwr functions it is implemented as in-place
function.

In C++ libraries it usually implemented as:

void strlwr(string &s);
void strupr(string &s);
string strlwr(const string &s);
string strupr(const string &s);

For C++, why not just use: std::transform(str.begin(),str.end(),str.begin(),tolower); Is there really any reason to wrap this in a function? Sean
Jul 21 2005
parent "Andrew Fedoniouk" <news terrainformatica.com> writes:
"Sean Kelly" <sean f4.ca> wrote in message 
news:dbp4ou$2usq$1 digitaldaemon.com...
 In article <dbp0i4$2rph$1 digitaldaemon.com>, Andrew Fedoniouk says...
In those C RTLs which have strlwr functions it is implemented as in-place
function.

In C++ libraries it usually implemented as:

void strlwr(string &s);
void strupr(string &s);
string strlwr(const string &s);
string strupr(const string &s);

For C++, why not just use: std::transform(str.begin(),str.end(),str.begin(),tolower); Is there really any reason to wrap this in a function?

Reason is to have them both. void strlwr(string &s); string strlwr(const string &s);
Jul 21 2005