Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

MikeMirzayanov's blog

By MikeMirzayanov, 5 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  

»
5 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.

»
5 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?

  • »
    »
    5 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.
    • »
      »
      »
      5 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. :(

»
5 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 ^_^)

»
5 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.

»
5 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.

»
5 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.

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

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

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

»
5 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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what does d8 mean in this blog?

»
3 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...

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

    And I wanna to see the benchmark too ;)

    • »
      »
      »
      2 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
      • »
        »
        »
        »
        2 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.

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

        I am able to build V8 for Windows right from their master branch (as of this moment it is V8 5.6) with MSVC 2015 Update 3. OS must be at least Windows 7 due to the dependency of Universal C Runtime Library (ucrtbase.dll, included in Windows Update).

        As usual, use readline to read from stdin, print/write to output to stdout, printErr for stderr. Use read(filename) to read text content.

        I can provide my built 64-bits d8.

        Note: Chrome Stable currently uses V8 5.4 while Chrome Canary uses V8 5.6.

»
13 days 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.