Issue 150 - [Typed objects] Implement string type

lib/typedObjects/stringType.js

 /*
  * This file is part of Adblock Plus <http://adblockplus.org/>,
  * Copyright (C) 2006-2014 Eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 "use strict";
 
 let {uint16} = require("typedObjects/primitiveTypes");

[René Jeschke, 2014/05/19 08:15:28]

Have you already thought about trading some CPU power for even lesser memory
consumption? Currently the strings are stored as UTF-16, which is easy to
implement but not optimal when it comes to memory consumption. 

UTF-8 would be the way to go here but this would need some en-/decoding steps
(also diacritics would need to get converted to UTF-32 first). (I've done this
for a living at my previous employer and could assist you here)

Still, this might me a good thing for future enhancements as our filter lists
contain mostly latin chars we could roughly half the memory consumption.

[tschuster, 2014/05/19 11:31:29]

I think a good idea would be to have "ASCII" strings. Basically strings that
just need one byte. That would be the best of both worlds. Most strings are
already ascii so we save memory, and there is no CPU overhead. Most JS engines
do that internally.

[René Jeschke, 2014/05/19 13:55:01]

Sorry, but this doesn't work. If we plan to support anything besides standard
latin character set (speak cyrillic, arabic, CJK, ...) either inside the
easylists or generally for typed objects we can't use 'ASCII'-like charsets.

Besides: ASCII is also only 7-bit, anything beyond that is implementation
defined. There are hundreds of encodings/codepages out there.

I've been in text conversion hell and you don't want to go there, trust me.

As for the overhead: you always have the CPU overhead. Strings in JavaScript are
defined to be UTF-16 encoded, so you always have an uint16_t underneath.
SpiderMonkey uses uint16_t internally, v8 has a 'single-byte' format (I bet for
primitive strings) and a 'two-byte' (UTF-16) (I bet for String objects).

My advice (as a guy who really _knows_ Unicode and its different encoding
types): if you want to reduce memory requirements further, stick with the
standard, and this standard is called 'utf-8'. 

And again: you can't avoid the CPU overhead as having a 'special' string type
would require a 'special' JS VM which we can't provide (and wouldn't make sense
(see above)) -> so we don't have any other string than JS provides -> which is
by default UTF-16.

[Wladimir Palant, 2014/05/19 15:16:39]

Actually, a cstring type might make sense in some cases - but thinking about the
data we are usually dealing with, pretty much every string *could* have
non-ASCII data in it. So simply using cstring in some places won't help us much.
If anything, we would need a string type that dynamically switches between ASCII
and UTF-16 but I couldn't think of any way to implement this without introducing
lots of complexity/overhead.

As to UTF-8, the overhead here was my main concern when I tested Emscripten. It
might be ok if most of the time you need strings to display them - but we want
to do multiple pattern search and accessing individual characters efficiently
was the main issue with implementing these algorithms in JavaScript.

To sum up, IMHO UTF-16 is good enough as a solution for now, I'm not aiming for
high optimization with the first version of this code (premature optimization
and everything). We can still optimize things later.

[René Jeschke, 2014/05/19 15:26:24]

Yep, right. Just wanted to hear if you already considered UTF-8 and didn't
address an immediate issue. (And, yep, the overhead for load/save would be quite
huge, also you loose the easy indexing into the string).

 let string = exports.string = uint16.Array({
   toString: function()
   {
     let buffer = this.getArrayBuffer();
     if (!buffer)
       return "";
     let array = new Uint16Array(buffer, this.arrayByteOffset, this.length);
     return String.fromCharCode.apply(null, array);
   }
 }, {
   constructor: function(value, offset, length)
   {
     let type = typeof value;
     if (type == "number")
       this.length = value | 0;
     else if (type == "string" || (value && string.isInstance(value)))
     {
       let sourceLength = value.length | 0;
       offset = Math.min(sourceLength, offset | 0)
       length = (typeof length == "number" ? length | 0 : sourceLength);
       length = Math.min(length, sourceLength - offset);
       this.length = length;
 
       if (length > 0)
       {
         let dest = new Uint16Array(this.getArrayBuffer(), this.arrayByteOffset, length);
         if (type == "string")

[René Jeschke, 2014/05/19 08:15:28]

For readability and to enable error free future improvements I strongly suggest
putting braces around this if's body.

+        {
           for (let i = 0; i < length; i++, offset++)
-            dest[i] = value.charCodeAt(offset) | 0;

[tschuster, 2014/05/19 11:31:29]

|0 doesn't really make a difference if you are writing into an uint array.

+            dest[i] = value.charCodeAt(offset);
+        }
         else
         {
           let src = new Uint16Array(value.getArrayBuffer(),
               value.arrayByteOffset + offset * (uint16.referenceLength | 0),
               length);
           dest.set(src);
         }
       }
     }
   }
 });