Issue 150 - [Typed objects] Implement string type

Issue 150 - [Typed objects] Implement string type

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

http://codereview.adblockplus.org/5665229014827008/diff/5629499534213120/lib/...
File lib/typedObjects.js (right):

http://codereview.adblockplus.org/5665229014827008/diff/5629499534213120/lib/...
lib/typedObjects.js:168: *    str4.get(0);                    // 111 - ASCII
code of "o"
Note: 'ASCII' is not the right term here, the value returned is Unicode encoded
as UTF-16.

http://codereview.adblockplus.org/5665229014827008/diff/5629499534213120/lib/...
File lib/typedObjects/stringType.js (right):

http://codereview.adblockplus.org/5665229014827008/diff/5629499534213120/lib/...
lib/typedObjects/stringType.js:20: let {uint16} =
require("typedObjects/primitiveTypes");
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.

http://codereview.adblockplus.org/5665229014827008/diff/5629499534213120/lib/...
lib/typedObjects/stringType.js:48: if (type == "string")
For readability and to enable error free future improvements I strongly suggest
putting braces around this if's body.

[tschuster, 2014-05-19 11:31:28]

http://codereview.adblockplus.org/5665229014827008/diff/5629499534213120/lib/...
File lib/typedObjects/stringType.js (right):

http://codereview.adblockplus.org/5665229014827008/diff/5629499534213120/lib/...
lib/typedObjects/stringType.js:21: 
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.

http://codereview.adblockplus.org/5665229014827008/diff/5629499534213120/lib/...
lib/typedObjects/stringType.js:50: dest[i] = value.charCodeAt(offset) | 0;
|0 doesn't really make a difference if you are writing into an uint array.

[René Jeschke, 2014-05-19 13:55:00]

http://codereview.adblockplus.org/5665229014827008/diff/5629499534213120/lib/...
File lib/typedObjects/stringType.js (right):

http://codereview.adblockplus.org/5665229014827008/diff/5629499534213120/lib/...
lib/typedObjects/stringType.js:21: 
On 2014/05/19 11:31:29, tschuster wrote:
> 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.

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:38]

Fixed the nits. Concerning internal storage of strings see below.

http://codereview.adblockplus.org/5665229014827008/diff/5629499534213120/lib/...
File lib/typedObjects/stringType.js (right):

http://codereview.adblockplus.org/5665229014827008/diff/5629499534213120/lib/...
lib/typedObjects/stringType.js:21: 
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]

LGTM

http://codereview.adblockplus.org/5665229014827008/diff/5629499534213120/lib/...
File lib/typedObjects/stringType.js (right):

http://codereview.adblockplus.org/5665229014827008/diff/5629499534213120/lib/...
lib/typedObjects/stringType.js:21: 
On 2014/05/19 15:16:39, Wladimir Palant wrote:
> 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.

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).