Prev: FAQ Topic - How do I open a new window with javascript? (2010-06-30)
Next: How to trigger two events with 2 document.locations?
From: Lasse Reichstein Nielsen on 5 Jul 2010 01:10
"Richard Cornford" <Richard(a)litotes.demon.co.uk> writes:

> It turned out that
> charCodeAt was not useful as the application of the bitwise operations
> soon turns all the string digits into the corresponding numbers.

From a performance standpoint, I think charCodeAt can be significantly
faster than charAt + (effectively) parseInt. Reading the character
code at a string position returns a number (easily, reading from the
internal representation of the string), whereas charAt returns a
singleton string (which at least can be cached) that requires parsing
to turn into a number.

I'm guessing the fastest approach would be
str.charCodeAt(i) & 0x0F

/L
--
Lasse Reichstein Holst Nielsen
'Javascript frameworks is a disruptive technology'

From: Richard Cornford on 5 Jul 2010 04:12
Lasse Reichstein Nielsen wrote:
> Richard Cornford writes:
>
>> It turned out that charCodeAt was not useful as the application
>> of the bitwise operations soon turns all the string digits into
>> the corresponding numbers.
>
> From a performance standpoint, I think charCodeAt can be
> significantly faster than charAt + (effectively) parseInt.

Comparing those two, yes.

> Reading the character code at a string position returns a number
> (easily, reading from the internal representation of the string),
> whereas charAt returns a singleton string (which at least can
> be cached) that requires parsing to turn into a number.
>
> I'm guessing the fastest approach would be
> str.charCodeAt(i) & 0x0F

The other factor is looping over the characters in the string to build
the array of numbers. That is necessary for both of - charCodeAt - and -
charCode -, but with - split - the implied loop is handled internally by
native code.

Richard.

From: RobG on 5 Jul 2010 19:54
On Jul 5, 6:12 pm, "Richard Cornford" <Rich...(a)litotes.demon.co.uk>
wrote:
> Lasse Reichstein Nielsen wrote:
> > Richard Cornford writes:
>
> >> It turned out that charCodeAt was not useful as the application
> >> of the bitwise operations soon turns all the string digits into
> >> the corresponding numbers.
>
> > From a performance standpoint, I think charCodeAt can be
> > significantly faster than charAt + (effectively) parseInt.
>
> Comparing those two, yes.
>
> > Reading the character code at a string position returns a number
> > (easily, reading from the internal representation of the string),
> > whereas charAt returns a singleton string (which at least can
> > be cached) that requires parsing to turn into a number.
>
> > I'm guessing the fastest approach would be
> > str.charCodeAt(i) & 0x0F
>
> The other factor is looping over the characters in the string to build
> the array of numbers. That is necessary for both of - charCodeAt - and -
> charCode -, but with - split - the implied loop is handled internally by
> native code.


While reading characters from a string might be faster for that
particular operation, replacing other array operations with their
string equivalents means that overall, the program runs slower than
its equivalent using an array. Below is a small test script, there may
be other optimisations to the string version. Replacing substring and
charAt operations with equivalent regular expression operations has a
negligable affect on performance.

As far as I can see, having to create a new string several times on
each loop negates any advantage of charAt or charCodeAt for getting a
digit. Browsers that have slow string manipulation are particularly
affected.

In the test code, I re-use chunks of previously generated strings to
speed things up a bit.


// toBinary using string and charCodeAt
function toBin_swlrn(numStr) {
var bigInt = '',
len = numStr.length,
result = '',
re = /^0/,
rem, digit, i;
do {
for (rem = i = 0; i < len; ++i) {
digit = (numStr.charCodeAt(i) & 0x0F) + rem * 10;
rem = digit & 1;
bigInt += (digit - rem) / 2;
}
if (bigInt.charAt(0) == '0') {
bigInt = bigInt.replace(re,'');
--len;
}
result += rem;
numStr = bigInt;
bigInt = '';
} while (len);
return result.split('').reverse().join("");
}

// toBinary using array
function toBin_sw(numStr) {
var bigInt = numStr.split(""),
len = bigInt.length,
result = [],
rem, digit, i;
do {
for (rem = i = 0; i < len; ++i) {
digit = +bigInt[i] + rem * 10;
rem = digit & 1;
bigInt[i] = (digit - rem) / 2; // or (digit / 2) | 0
}
if (!bigInt[0]) {
bigInt.shift();
--len;
}
result.push(rem);
} while (len);
return result.reverse().join("");
}

function speedTest() {
var n = 50, // Number of integers to generate
m = 50, // Length of each integer
numArray = [], // Array of integer strings to process
result = [], // Test results
r = '', // Random number string
s, f, fn,
toRun = ['toBin_swlrn', 'toBin_sw'];

// Generate an array of n integers of m digits each
do {
while (r.length < m) {
r += '' + Math.random()*1e8|0;
}
r = r.substring(0,m)
numArray.push(r);
--n;
// Reverse and reuse
numArray.push(r.split('').reverse().join(''));
--n;
// Reuse middle bit
r = r.substring((m/4|0), (3*m/4|0));
--n;
} while (n>0)

// Run tests
for (var i=0, iLen=toRun.length; i<iLen; i++) {
fn = window[toRun[i]];
s = new Date();
for (var j=0, jLen=numArray.length; j<jLen; j++) {
fn(numArray[j]);
}
f = new Date();
result.push(toRun[i] + ': ' + (f-s));
}
result.push(numArray[0])

return result;
}

document.write( speedTest().join('<br>') );


--
Rob
From: Stefan Weiss on 5 Jul 2010 22:29
On 06/07/10 01:54, RobG wrote:
> On Jul 5, 6:12 pm, "Richard Cornford" <Rich...(a)litotes.demon.co.uk>
> wrote:
>> Lasse Reichstein Nielsen wrote:
>> > I'm guessing the fastest approach would be
>> > str.charCodeAt(i) & 0x0F
>>
>> The other factor is looping over the characters in the string to build
>> the array of numbers. That is necessary for both of - charCodeAt - and -
>> charCode -, but with - split - the implied loop is handled internally by
>> native code.
>
> While reading characters from a string might be faster for that
> particular operation, replacing other array operations with their
> string equivalents means that overall, the program runs slower than
> its equivalent using an array.

I've noticed the same thing. At least with the engine I'm using,
charAt() and charCodeAt() are both about 30-40 times slower than
splitting the string and iterating over the array elements (I tested
this with just the loops, no conversions or return values). That's a
much bigger performance hit than all of the previously mentioned
optimizations together.

> As far as I can see, having to create a new string several times on
> each loop negates any advantage of charAt or charCodeAt for getting a
> digit. Browsers that have slow string manipulation are particularly
> affected.

It's not just the concatenation; reading the digits itself is slower
with the string methods. Maybe it's the method calls, or the fact that
the engine has to start counting characters from 0 every time, while
property access in an array is likely optimized. I don't know.
I was hoping it would be faster, or at least not much slower. AFAIK,
strings use up less memory than arrays (in JavaScript). It probably
won't matter much for the toBin() example, but it might present a
problem for a more generalized arbitrary precision math library.

I made a few optimizations to the previous version I posted:

- I replaced the result array with a string. This turned out to be
faster with SpiderMonkey, but it might be slower in other engines (maybe
in JScript, IIRC), or if the input strings are _very_ long.

- I eliminated the unnecessary shift() operation on the bigInt array,
so that the array length remains constant now.

- Richard's suggestion about using the right shift operator instead of
dividing by 2 was a big improvement. I actually had this in an earlier
test version of the function, but it got lost along the way. Oh, and >>>
appears to be slightly faster than >>, but that could very well be an
artifact of the benchmark.
I couldn't find a way to try out the "substract 3" suggestion without
introducing at least one if-statement.


function toBin (numStr) {
var bigInt = numStr.split(""),
len = bigInt.length,
result = "",
offset = 0,
rem, divPart, i;
do {
for (rem = 0, i = offset; i < len; ++i) {
divPart = +bigInt[i] + rem * 10;
rem = divPart & 1;
bigInt[i] = divPart >>> 1;
}
if (!bigInt[offset]) {
++offset;
}
result = rem + result;
} while (offset < len);
return result;
}


With my test input strings, this one is about 70-80% faster than the
previous version.


--
stefan
From: Richard Cornford on 6 Jul 2010 08:54
On Jul 6, 3:29 am, Stefan Weiss wrote:
> On 06/07/10 01:54, RobG wrote:
>> On Jul 5, 6:12 pm, Richard Cornford wrote:
>>> Lasse Reichstein Nielsen wrote:
>>>> I'm guessing the fastest approach would be
>>>> str.charCodeAt(i) & 0x0F
>
>>> The other factor is looping over the characters in the string
>>> to build the array of numbers. That is necessary for both of
>>> - charCodeAt - and - charCode -, but with - split - the implied
>>> loop is handled internally by native code.
>
>> While reading characters from a string might be faster for that
>> particular operation, replacing other array operations with their
>> string equivalents means that overall, the program runs slower
>> than its equivalent using an array.
>
> I've noticed the same thing. At least with the engine I'm using,
> charAt() and charCodeAt() are both about 30-40 times slower than
> splitting the string and iterating over the array elements (I
> tested this with just the loops, no conversions or return values).

Is that a reasonable comparison? - charAr - gets you what - split -
does; an array of string, but charCodeAt gives you an array of
numbers, possibly avoiding a later type-converting step.

> That's a much bigger performance hit than all of the previously
> mentioned optimizations together.

In the past it has been shown that attempting to avoid the implied
object creation when calling a method on a string primitive by first
turning that primitive into its corresponding object (so - x = new
String(x) -, and calling the methods on the resulting object) is not
nearly the optimisation that ECMA 262 suggests it might be. I is
proposed that calling methods on string primitives is so common that
the engine already does a great deal to optimise that type of action.
On the other hand, calling - carAt - and/or - charCodeAt - on each
character in a long string might be influenced by first turning the
string into an object (probably at least wroth a test).

<snip>
> I couldn't find a way to try out the "substract 3" suggestion
> without introducing at least one if-statement.
<snip>

What is wrong with the - if - statement?

Richard.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7
Prev: FAQ Topic - How do I open a new window with javascript? (2010-06-30)
Next: How to trigger two events with 2 document.locations?