constness for arrays

[xs0]

Don Clugston wrote:
> xs0 wrote:
>> - the top bit of arrays' .length becomes an indicator of the 
>> readonlyness of the array reference
> 
> This is a really interesting idea. You're essentially chasing a 
> performance benefit, rather than program correctness. Some benchmarks 
> ought to be able to tell you if the performance benefit is real:
> 
> instead of char[], use
> 
> struct CharArray {
>  char [] arr;
>  bool readOnly;
> }
> 
> for both the existing and proposed behaviour (for the existing one, 
> readonly is ignored, but include it to make the parameter passing fair).
> 
> For code that makes heavy use of COW, I suspect that the benefit could 
> be considerable. You probably don't need to eliminate many .dups to pay 
> for the slightly slower .length.

Well, I did a (admittedly biased :) test, and there do seem to be 
potential large benefits..

I wrote an app that counts different words in the 5.6MB ASCII text from
http://www.gutenberg.org/etext/1581

The text was read and duplicated 10 times (so I could do 10 runs). Then, 
words were extracted (word := a sequence of alnum chars), lowercased and 
placed into an AA. I ran each version about 20 times, and here are the 
fastest results for each:

bib_current    : 3641ms
bib_str        : 3031ms
bib_str (old)  : 3625ms
bib_str (ugly) : 3109ms

Commenting out the AA stuff, the results become

bib_current    : 1281
bib_str        : 812
bib_str (old)  : 1234
bib_str (ugly) : 812

About 11% of the calls to toLower would result in .duping currently, and 
none do with the new system, as it's not necessary in this particular 
case. Had I used toUpper, ... :)

bib_current is exactly the same code, except it uses Phobos' tolower and 
char[] instead of string.

For some reason, bib_current is (slightly) slower even than the string 
version that does exactly the same thing.. my guess would be that some 
more inlining/optimization was done in my code..

For some other reason, toLowerUgly is slower than toLowerNew, even 
though it potentially does less checks.. Probably the benefit of that 
was lost completely, as words tend to only have the first character 
uppercase, and more code just slowed the thing down.

Well, anyway, the conclusion would be that using that bit for readonly 
indication does not cause slowdowns even for code that doesn't use it. 
If used for COW-only-when-necessary, speed gains can be considerable.


xs0


The code was this (I snipped boring code in the interest of brevity, I 
can post the full code if someone wants it)

struct string {
     char* ptr;
     uint _length;

     public static string opCall(char[] bu, int readonly) { ... }
     public int length() { return _length & 0x7fffffff }
     public void length(int newlen) { ... }
     public string dup() { ... }
     public char opIndex(int i) { return ptr[i]; }
     public char opIndexAssign(char c, int i) { return ptr[i] = c; }
     public char[] toString() { return ptr[0..length()]; }
     public void wantToWrite() { if (_length & 0x80000000 } { ... } }
     public string slice(int start, int end) { ... }
}

string toLowerOld(string txt)
{
     int l = txt.length;
	
     for (int a=0; a<l; a++) {
         char c = txt[a];
         if (c>='A' && c<='Z') {
             txt = txt.dup;
             txt[a] = c+32;
             for (int b=a+1; b<l; b++) {
                 c = txt[b];
                 if (c>='A' && c<='Z')
                     txt[b]=c+32;
             }
             return txt;
         }
     }
     return txt;
}

string toLowerNew(string txt)
{
     int l = txt.length;
     for (int a=0; a<l; a++) {
         char c = txt[a];
         if (c>='A' && c<='Z') {	
             txt.wantToWrite();
             txt[a]=c+32;
         }
     }
     return txt;
}

string toLowerUgly(string txt)
{
     int l = txt.length;
     for (int a=0; a<l; a++) {
         char c = txt[a];
         if (c>='A' && c<='Z') {
             txt.wantToWrite();
             txt[a]=c+32;
             for (int b=a+1; b<l; b++) {
                 c = txt[b];
                 if (c>='A' && c<='Z')
                     txt[b]=c+32;
             }
             return txt;
         }
     }
     return txt;
}

void main()
{
     string[] bible;
     bible.length = 10;
     for (int a=0; a<bible.length; a++) {
         if (a==0) {
             bible[a] = string(cast(char[])read("bible.txt"), 0);
         } else {
             bible[a] = bible[a-1].dup;
         }
     }
     long start = getUTCtime();

     uint result;

     for (int q=0; q<bible.length; q++) {
         string txt = bible[q];

         int[char[]] count;

         int pos = 0;
         while (pos<txt.length) {
             if (!isalnum(txt[pos])) {
                 pos++;
                 continue;
             }
             int len = 1;
             while (pos+len < txt.length && isalnum(txt[pos+len]))
                 len++;

             //string word = toLowerOld(txt.slice(pos, pos+len));
             string word = toLowerNew(txt.slice(pos, pos+len));
             //string word = toLowerUgly(txt.slice(pos, pos+len));
             pos+=len;

             if (auto c = word.toString() in count) {
                 (*c)++;
             } else {
                 count[word.toString()]=1;
             }
         }
         result = count.length;
     }
     long end = getUTCtime();

     writefln("Different words found: ", result);
     writefln("Time taken: ", (end-start));
}