String.prototype.x slowness

[visnup]

anyone know why String.prototype.x is so slow in node (or V8?)?
https://gist.github.com/845827

1.5 orders of magnitude?! k-razy.

[Marcel Laverdet]

Your benchmarks aren't fair. The plain function doesn't accept any arguments, whereas the prototype arguments are getting an implicit `this` argument. Additionally calling string prototype methods will construct a temporary String object (not to be confused with a string literal). This has an upfront cost but should theoretically make calls to other String.prototype methods from within that method faster.

Your benchmark should look more like this:

function a(str) {

  new String(str);

}

...

  "plain function": function() {

    a(str)

  },

--
You received this message because you are subscribed to the Google Groups "nodejs" group.
To post to this group, send email to nod...@googlegroups.com.
To unsubscribe from this group, send email to nodejs+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/nodejs?hl=en.

[Marcel Laverdet]

Furthermore microbenchmarks of this variety are extremely dangerous. Your results may not reflect real-world behavior, and there may be non-obvious cost/benefit tradeoffs by trying to adjust your application for infinitesimal performance gains.

[visnup]

I only micro-benchmarked it because it came up in a real-world app and
I narrowed it down to the prototype code. I had initially implemented
a "count # of occurrences in this string" using a regex, then decided
to just do a simpler indexOf count (https://gist.github.com/846082),
which ended up being much slower so I dug a little and tried a plain
function that wasn't on String.prototype, which led to this example.

I don't understand your "implicit this argument" argument. Array and
RegExp both are extendable and don't suffer from significant slow-
downs. those I had in there just to make sure I wasn't going crazy.

I didn't know about the temporary String object thing. I don't quite
understand how it works though, can you explain further? I updated the
gist with the new String() change and that version is still an order
of magnitude faster. so, I'm still confused about what it could be
doing: https://gist.github.com/845827

implicit String function
Raw:
> 17566.433566433567
> 17736.263736263736
> 17790.20979020979
> 17711.28871128871
> 17320.67932067932
Average (mean) 17624.975024975025

string prototype function
Raw:
> 1160.8391608391607
> 1500.4995004995005
> 1455.5444555444556
> 1486.5134865134864
> 1417.5824175824175
Average (mean) 1404.195804195804

[visnup]

I updated https://gist.github.com/846082 with the more original count
code that I had in my script. I'm using it for parsing lots of CSVs,
so yes this benchmark reflects real-world slow-downs for me. I only
reduced it for the first benchmark to illustrate the root of my
problem.

[Marcel Laverdet]

What I was saying about the implicit argument was that your original function was getting less information than the prototype functions.

    function foo() {}

    foo();

In this example `foo` gets no information about anything. It just gets invoked and then returns. But in the case of..

    String.prototype.foo = function() {}

    "bar".foo();

The function will be able to access `this` and get "bar". So from the start your prototype functions had more functionality than the plain function.

About the temporary String object, be sure you're familiar with the differences between string primitives and String objects.

Consider this example:

    function type(v) {

      return typeof v;

    }

    String.prototype.type = function() {

      return typeof this;

    }

    var foo = "foo";

    console.log(type(foo));

    console.log(foo.type());

This will print "string, object". When you call a method on a string primitive it will coerce it into a String object. Actually I believe the coercion happens when you access the property, before the function call, but that's splitting hairs.

If you change `tasty = "jelly"` in your gist to `tasty = new String("jelly")` the benchmarks are within 1% of each other.

[JeanHuguesRobert]

What, oo style calls 10+ times slower than functional style calls?!

If the case you point out is not pathological (and it does not look
like it is), the only logical conclusion is that Javascript is the new
C, forget oo (for short lived objects at least). Bad news.

I hope that, as Marcel says, objects that live longer don't incur such
a big cost. I would be happy to have a confirmation about that.

OTOH it looks like it is a fairly simple thing to optimize, so there
is hope. But still not optimized yet... That tells something about
where the focus is on regarding optimizations by the V8 team I guess
and it's not about making oo polymorphism cheap apparently.

Or am I missing something?

[JeanHuguesRobert]

> Marcel:

> What I was saying about the implicit argument was that your original
> function was getting less information than the prototype functions.
>     function foo() {}
>     foo();
> In this example `foo` gets no information about anything. It just gets
> invoked and then returns. But in the case of..
>     String.prototype.foo = function() {}
>     "bar".foo();
> The function will be able to access `this` and get "bar". So from the start
> your prototype functions had more functionality than the plain function.

In all fairness, the comparison would make more sense with:
function foo( bar ){}
foo( "bar")

BTW, foo() gets a "this" too I think, ie foo() is equivalent to
global.foo(), isn't it?

[Marcel Laverdet]

> I hope that, as Marcel says, objects that live longer don't incur such
> a big cost. I would be happy to have a confirmation about that.

They don't incur the same cost. The cost is in the coercion (construction) and not the invocation. In many cases OO will be faster than procedural (this is a characteristic which is unique to v8). Primitives are a special case here.

> OTOH it looks like it is a fairly simple thing to optimize, so there
> is hope. But still not optimized yet... That tells something about
> where the focus is on regarding optimizations by the V8 team I guess
> and it's not about making oo polymorphism cheap apparently.

v8 is very very fast. The problem is Javascript, the object has to come from somewhere; it's in the spec. I'm sure there's ways to optimize many common cases, but there's likely bigger projects the v8 team is working on.

--

[Vyacheslav Egorov]

> What, oo style calls 10+ times slower than functional style calls?!

No. You are misinterpreting results. Invocations of methods defined on
prototypes of objects cost roughly the same as invocations of local
functions (it's just a couple of additional checks/loads). V8 goes to
a great lengths to make such calls as fast as possible.

But the benchmark is measuring something completely different: cost of
calls of a non-builtin method defined on String.prototype with a
primitive receiver.

According to the ECMA-262 spec receiver has to be coerced to an
Object, so a temporary String object has to be created for each such
call.

String.prototype.foo = function () { };
var a = ""; for (var i = 0; i < 1e7; i++) a.foo();

actually does something like:

String.prototype.foo = function () { };
var a = ""; for (var i = 0; i < 1e7; i++) new String(a).foo();

Even more: V8 does not handle this neither in generated code nor does
it use specialized ICs or stubs for this case, so execution just falls
through to the runtime system for every foo invocation. This (memory
allocation + GCs + going to runtime system for each call) is quite
expensive.

There is of course an optimization in place that avoids such overhead
for built-in methods of String (like indexOf etc). But optimizing away
overhead in the general case is difficult (or even impossible for
certain cases): it requires proving that call target can operate on a
primitive receiver without noticing that it was not coerced to an
object.

--
Vyacheslav Egorov

[JeanHuguesRobert]

> According to the ECMA-262 spec receiver has to be coerced to an
> Object, so a temporary String object has to be created for each such
> call.

I bet these allocations are expensive! So, why doing them over and
over?

Considering that (thankfully) Javascript Strings are immutable, what's
the point in creating a whole brand new object over and over, instead
of, say, attaching the "coerced" String object to the string once for
all.

Again, this is possible because strings are immutable. But maybe
ECMA-232 does not explicitly states it, maybe one can get access to
the "temporary" String object (that would be better called
"CoercedString" at the implementation level I guess) and add
properties to it, but how?

And even if this were to happen, the interpreter could detect it and
change the object's "type" to make it become more like a "mutable"
String object and less like an immutable "CoercedString", and this
could be done in a way that is totally invisible to the user.

"could be done" but "not done" is quite a difference and it's the
reason why I wonder about V8 not being very oo "friendly", at least
regarding primitive types.

I understand that it makes sense to optimize the low hanging fruits
first, but in doing so V8 creates an even bigger gap between
functional versus oo programming, in favor of the functional style.

Not that I don't like functional style, it's just that I don't enjoy
adding a prefix to all my functions depending on what type of objects
they operate on. ie. I'd rather define String.prototypes.starts =
function( other ){...} than function str_starts( that, other) and I'd
prefer to call "hello".starts( "hello world") instead of
str_starts( "hello", "hello world")... That later style is basically
what I used to do back in C, and stopped doing with C++, hence my
"Javascript is the new C"(in a bad way) complaint :)

I guess this discussion would better fit in the V8 group, but
considering the recent questions about node 4 performances compared to
node 2 performances, I think that talking about performance matters.

[Vyacheslav Egorov]

> I bet these allocations are expensive!

Well. Actually they are much less expensive then falling though to the
runtime system on each call [try https://gist.github.com/846213].

> So, why doing them over and over?

While strings are immutable String objects are not. So you can't just
reuse the same wrapper all the time.

> maybe one can get access to
> the "temporary" String object (that would be better called
> "CoercedString" at the implementation level I guess) and add
> properties to it, but how?

Easily:

String.prototype.foo = function (a) {
if (this.bar) { throw new Error ("OMG! Somebody is not following
ECMA-262 and caching String objects!"); }
this.bar = true;
};

var a = "a";
a.foo(); // foo will set property "bar" on the implicitly created String object
a.foo(); // if we reuse the String object here it will have "bar"
property, but it should be fresh String object according to the spec.

But as I said above the performance penalty mostly comes from the fact
that call has to go through the runtime system.

I've filed an issue: http://code.google.com/p/v8/issues/detail?id=1212.

--
Vyacheslav Egorov

[JeanHuguesRobert]

Thanks for the clarification Vyacheslav, your OMG example shows a case
where the cached "coerced" string must be invalidated, that's a basic
"copy on write", let's hope it gets implemented, resulting in the
speed of "str".foo() beeing in range with the one of foo( "str")...

...because it is not at all the case today. I wanted to be sure, so I
made a benchmark using jsperf.com

http://jsperf.com/oo-vs-functional-calls-str

Results: "str".foo() is 200 times slower than foo("str"), 30 times
slower in some less pathological cases.

About 7x due to coerce, 4x due to dynamic dispatch.

This is rather disappointing.

So, for now, I stand by the unfortunate conclusion that "Javascript is
the new C"(in a bad way), ie: not OO friendly.

Put differently: want good perf? stick with primitive types and avoid
dynamic dispatch... basically "avoid OO"

So sad.

[Vyacheslav Egorov]

> Thanks for the clarification Vyacheslav, your OMG example shows a case
> where the cached "coerced" string must be invalidated, that's a basic
> "copy on write", let's hope it gets implemented, resulting in the
> speed of "str".foo() beeing in range with the one of foo( "str")...

Copy-on-write looks as something basic until you try to implement it.
And as I tried to point in my previous messages: there are some more
serious performance pitfalls here than wrapper allocation.

> Put differently: want good perf? stick with primitive types and avoid
> dynamic dispatch... basically "avoid OO"

You are again misinterpreting results of the benchmark. As I said
earlier: V8 goes to a great length to optimize dispatch and property
accesses through prototype chain. 2 benchmarks in the V8 Benchmark
Suite (Richards and DeltaBlue) heavily use OO programming, inheritance
and polymorphism; their score highly depends on the quality of
dispatch mechanisms used by VM.

Back to your benchmark. Take a look at
http://jsperf.com/oo-vs-functional-calls-str/2.

I have fixed a small typo in str_starts (replaced 'this' by 'that')
and more importantly added another test-case "functional style with
coerced that."

You can notice that it shows the same performance (at least on the
recent Chrome 11) as your test case "oo style, more coerce". So
dynamic dispatch virtually costs no more than what looks like a
"direct" call --- the difference comes from the wrapping around 'that'
object.

My recommendation is: don't avoid OO, it's cheap --- avoid wrappers
around primitive types, they are expensive.

--
Vyacheslav Egorov

[Jorge]

On 27/02/2011, at 19:08, Vyacheslav Egorov wrote:

> (...) avoid wrappers

> around primitive types, they are expensive.

In strict mode this will run faster :-)
--
Jorge.

[Vyacheslav Egorov]

Oh, yes. That is true. Shame on me, I forgot that this part of strict
mode has been implemented recently in V8.

So I can extend my recommendation: when adding functions to prototypes
of String/Number define them as strict to avoid overhead with wrapping
and unwrapping on VMs that support strict mode.

I have extended http://jsperf.com/oo-vs-functional-calls-str/2 with an
appropriate test case. It will show good results on browsers with VMs
that implement this part of strict mode.

--
Vyacheslav Egorov

[visnup]

got it. now I understand the difference between the literal and the
coerced object: https://gist.github.com/845827

On Feb 27, 12:08 pm, Vyacheslav Egorov <vego...@chromium.org> wrote:
> Oh, yes. That is true. Shame on me, I forgot that this part of strict
> mode has been implemented recently in V8.
>
> So I can extend my recommendation: when adding functions to prototypes
> of String/Number define them as strict to avoid overhead with wrapping
> and unwrapping on VMs that support strict mode.
>

> I have extendedhttp://jsperf.com/oo-vs-functional-calls-str/2with an

[visnup]

thanks Marcel and all you guys. so, is there any best practice to
extending String.prototype and still call it on string literals? also,
I now need to investigate what I ended up calling these methods on in
my original project.

[Marcel Laverdet]

Jean please stop with the alarmist comments about v8 if you do not understand the benchmarks. In most cases "dynamic dispatch" invocations are FASTER than function calls. The cost is 100% in the coercion, and like others mentioned, this is a cost that may go away with strict mode (I didn't notice a difference in node 0.4.1 \ v8 3.1.5 but this will likely change very soon). This is exactly the danger of microbenchmarking I mentioned in my 2nd email. Visnup has been responsible with his benchmarking and you're running around telling people that objects are too slow to use. This is just not the case; v8 is a very very fast runtime.

Please look at this:

https://gist.github.com/846719

`stringObject.method()` is FASTER than `func(stringPrimitive)`

> got it. now I understand the difference between the literal and the
> coerced object: https://gist.github.com/845827

Your "string (coerced literal) prototype" case seems to be wrong. Calling String() on a string primitive doesn't do anything. new String() will coerce it to an object. Also I tend to use "literal" and "primitive" interchangeably, but that's incorrect. A string literal is the actual unit that gets parsed. A string primitive is the value that yields from it.

> thanks Marcel and all you guys. so, is there any best practice to
> extending String.prototype and still call it on string literals?

Be sure to try it on the latest node version with "use strict"; on your prototyped functions. If you're noticing substantial performance problems in your application right now, and you observe non-trivial speedups by switching to a non-prototype string function then use the functional version for now. Check back in a few months and see if it sped up and you may want to consider switching back.

[JeanHuguesRobert]

On Feb 28, 1:21 am, Marcel Laverdet <mar...@laverdet.com> wrote:
> Jean please stop with the alarmist comments about v8 if you do not
> understand the benchmarks.

Sorry if anybody was "alarmed" that "str".foo() is 30x slower than
foo("str").

This is due to coercion and implementing a "copy on write"
optimization is not trivial.
But "in a few months" things may get better.

I feel relieved.