3

I have read the V8 engine source code before. And I can find the JavaScript-implemented code in it, e.g. Array.js.

Recently, I want to find the source code for array sorting again, and found that the JS part has been removed. All I can find is array-sort.tq, which is in [v8/third_party/v8/builtins].

Is there a problem with the method I am looking for? Or is it that just the JS part has been removed? It's hard for a JavaScript developer to know the details of the implementation.

ggorlen
  • 44,755
  • 7
  • 76
  • 106
Eriice
  • 147
  • 1
  • 7
  • 1
    *Why* do you want to know the details of the sort implementation? It can change any time, and the only guarantees for it are the guarantees in the specification (which did recently change -- sort became stable). – T.J. Crowder Jul 19 '19 at 14:11
  • I also noticed this recently. It seems like a pretty self-evident question from a motivation standpoint: a typical JS developer would want to look at the implementation to learn that, say, insertion sort is used instead of quick sort when `arr.length < 10` which might explain various program behaviors, that kind of stuff. At the very least, it seems a bit surprising that entire files previously written in JS are gone, so it's worth asking why/where/what happened? – ggorlen Jul 19 '19 at 14:14
  • @ggorlen: If your program's behaviour changes as a result of that, your program is wrong. – Lightness Races in Orbit Jul 19 '19 at 14:20
  • (But it's an interesting question if only academically) – Lightness Races in Orbit Jul 19 '19 at 14:20
  • Certainly fair enough to wonder why the JavaScript implementations disappeared. :-) And/or to want to see the implementation details just for curiousity's sake and educational reasons. – T.J. Crowder Jul 19 '19 at 14:24
  • Yeah, [I answered a question](https://stackoverflow.com/questions/52671125) awhile ago that had an incorrect comparator implementation which was asking why it worked on certain array lengths and not on others, and this was the answer. I recently went to update the answer, noticed array.js disappeared and moved on with life, but now I'm interested again. – ggorlen Jul 19 '19 at 14:24
  • it has changed to the [Timsort](https://twitter.com/mathias/status/1036626116654637057?lang=en). So I want to know the Timsort's implementation in JavaScript. Obviously, I failed:( – Eriice Jul 19 '19 at 14:59
  • @Eriice - :-) Well, Torque is tolerably readable even if you don't know it (I don't). But if you want a TimSort in JavaScript, [SO has you covered](https://stackoverflow.com/questions/15606290/how-to-use-timsort-in-javascript). I have no idea if that implementation is any good, but... – T.J. Crowder Jul 19 '19 at 15:19
  • You save my life! Thank you. – Eriice Jul 20 '19 at 03:04

1 Answers1

5

Some builtins (such as Array.prototype.sort) are now written in Torque rather than C++ or JavaScript. Torque is a language built for V8:

The language was designed to be simple enough to make it easy to directly translate the ECMAScript specification into an implementation in V8, but powerful enough to express the low-level V8 optimization tricks in a robust way, like creating fast-paths based on tests for specific object-shapes.

...

Torque provides language constructs to represent high-level, semantically-rich tidbits of V8 implementation, and the Torque compiler converts these morsels into efficient assembly code using the CodeStubAssembler.

(More about CodeStubAssembler here.)

More in the Torque builtins blog post.

So yes, Array.prototype.sort and many other Array methods are written in Torque now, which is compiled to efficient assembly code, which is used by V8's JavaScript interpreter (Ignition) and JavaScript compiler (TurboFan). (Yes, V8 has both. :-) More here, but briefly: V8 parses JavaScript to bytecode, then interprets it with Ignition. Hotspots [areas that are run a lot] get compiled to native code via TurboFan as and when needed.)

T.J. Crowder
  • 1,031,962
  • 187
  • 1,923
  • 1,875