Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

MikeMirzayanov's blog

Support of JavaScript V8 and Some Benchmarks
By MikeMirzayanov, 11 years ago, translation, In English

I've found some time to support JavaScript, which is so popular now. I chose V8 as the most developed implementation of JavaScript.

With the help of a tambourine and a liter of cola I successfully compiled it on Windows. Funny, I was ready to implement workaround to support reading from stdin in JavaScript, but d8 already supports it! Just use readline() to read line from the input.

Here is an example of A+B:

var line = readline().split(' ')
print(parseInt(line[0]) + parseInt(line[1]))

Interesting fact, that if there is no line-break (\r\n) at the end of line, then readline() returns undefined. So it is one more reason for good rule: each line should end with eoln.

As a tiny research I've implemented HeapSort on C++, Java and JavaScript. I have an opinion that all dynamic typed languages are very slow. But...

I've implemented HeapSort on 107 elements from 0 to 9999999. I think it is good benchmark to show how fast can be your code if you write like in Pascal or pure C. The result have surprised me:

Language Compiler Running time, ms
C++ MinGW 4.7.2 32-bit 630
C++ MS VS 2010 32-bit 650
Java Oracle Java 6 32-bit 1060
Java Oracle Java 7 32-bit 1050
JavaScript V8 3.23.0 32-bit 1700
Pascal Delphi 7 32-bit 630
Pascal FreePascal 2.6.2 32-bit 730
Python 2 Python 2.7.4 32-bit 12500
Python 3 Python 3.3.2 32-bit 20000
Ruby Ruby 1.9.3p0 (2011-10-30, i386-mingw32) 32-bit 520000
Ruby Ruby 2.0.0p353 (2013-11-22, i386-mingw32) 32-bit 345000
Scala Scala 2.10.3 (over Oracle Java 7 32-bit) 1550
Go Go 1.2 32-bit 1780
D DMD v2.064.2 32-bit 800
C# Mono 2.10.9 32-bit 850
C# MS CSC .Net 4.5.1 64-bit 850
Perl Perl v5.12.2 for MSWin32-x86-multi-thread 195000

JavaScript shows very good performance! I understand that such kind of code is very good for optimization and jit-compilation, but I'm impressed. By the way, Java with its optimized JIT is not as good as it can be.

Actually, I posted the codes in github. You may implement the same algorithm on your favorite language. Here are links to current implementations:

You may post links to pastebin in comments or give submission id. Better to do a pull request.

If you are planning to write implementation, please write it neat and tidy. Write it as closer to the C++, Java and JavaScript as possible.

UPD 1. With the help of alexei-zayakin, Pascal has been added.

UPD 2. With the help of gchebanov Wizmann and juancate I've added Python 2, Python 3, Ruby, Scala, Go.

UPD 3. Here is V8 (Windows binaries).

UPD 4. I've updated some compilers and the benchmark results.

UPD 5. Added D. Thanks Gassa.

UPD 6. Added C#. Thanks gmogelashvili.

  • Vote: I like it
  • +139
  • Vote: I do not like it

Comments Comments (24)
| Write comment?
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It would be interesting running Python 2 version in PyPy, in my computer (which is worst than codeforces computers) it has almost the same runtime.

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

10^7 elements from 0 to 9999999 or 10^7 elements from 0 to 999999?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    from 0 to 999999

    that looks like 10^6 only.

    • 10^1 are from 0 to 9;
    • 10^2 are from 0 to 99;
    • etc.
    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      sorry, my mistake. i count the number of 9's wrong. i should have confirmed before commenting. :(

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    this or the same thing?

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Hi, Mike.

I'm Wizmann in UPD 2.

I run the initial version of the Scala heap in Codeforces CUSTOM TEST.

The code use @tailrec only take 1157(ms) to finish the job, much faster than the one use while ... break which cost 2070(ms).

I guess there must be some performance problem with the break command in Scala. Because raising an exception with Scala break is much slower than a simple jump command with C++ break.

I have to say it not quite fair for Scala if you choice to use while ... break in the code. :)

See: http://daily-scala.blogspot.com/2010/04/break-performance.html

(Sorry for my poor English ^_^)

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow I wonder why ruby is so slow? I will try and improve the solution to see if I can get it to perform better.

→ Reply
»
11 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Hi!

Unfortunately, the Ruby implementation is not only very non-idiomatic in terms of code, but it does abuse the assignment operator to perform the exchange. This is why it is slower in the benchmarks. You'll find it performs way better if you take this into account.

Here's a pull request: https://github.com/MikeMirzayanov/binary-heap-benchmark/pull/10

In my testing, this version outperforms Python3 by a factor of 2. No clever tricks added.

→ Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Here's an implementation in Haskell: http://pastebin.com/cuFZ6eMi I tried to be very close to the C++ version, but I had to use tail recursion instead of loops. Should perform somewhere between Java and Scala.

→ Reply
»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

http://mirror.codeforces.com/blog/entry/10594

Hi everyone, I wrote a blog post on my experience using JavaScript on Codeforces.

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Could you please add Java 8 result? Looks like it has ~10% imprevement over 6&7 in this test. Edit: it would also be interesting to see how Scala performs on JVM 8.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what does d8 mean in this blog?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

@MikeMirzayanov is it possible to added support at least ECMAScript 5.1? Current version on server is JavaScript 1.8.1 which is already 6 years old...

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    And I wanna to see the benchmark too ;)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Do you know that they to support it? We need version which:

      1. has support of Windows,
      2. can read from stdin (readLine() or similar functions support)
      3. can write to stdout
      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        obvious node.js, no? If you concerned with security you can use node's standart vm package. For example you can expose process.stdin and process.stdout for user scripts (also fs.create(Read|Write)Stream for file I/O) and block everything else.

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, BigInt primitives are supported in recent V8 engines: https://v8.dev/blog/bigint

I wish it could be added to Codeforces. It's very helpful.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    It's actually not possible to solve some of the problems without BigInt. I've already gave up on a couple of contests.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank for the information. Why is it? is the performance very bad?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Some of the tests that get applied on a JS-based solution contain very large integers that the old version of the JS runner on this platform simply cannot handle.

        JS regular integer manipulation is only accurate up to 2^53, anything beyond that and the calculations do not make sense anymore. (example: 10000000000000000 — 9999999999999999 yields 0 instead of 1) This has been addressed by adding the BigInt library (which is now integrated in most browsers and newer versions of V8) that can handle those big numbers, a library that is not present in the current version of JS in this platform.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You're right. That's why I was wishing Codeforces platform to update the V8 engine.

          → Reply