Seeing this for the first time (! Important)

The following are the snippets in four different languages. They all are intended to do the same. But I find weird behaviour of Java Code when executed. Can anyone explain what is actually happening?

// C - Code
#include <stdio.h>
int main() {
    int HELL = ((int)(1e9));
    for(int i=0;i<HELL;i++) {
        for(int j=0;j<HELL;j++) {
            int k = i + j;
            k++;
        }
    }
    return 0;
}
// C++ Code
#include <bits/stdc++.h>
using namespace std;
int main() {
    int HELL = ((int)(1e9));
    for(int i=0;i<HELL;i++) {
        for(int j=0;j<HELL;j++) {
            int k = i + j;
            k++;
        }
    }
    return 0;
}
// Java Code
class Main {
    public static void main(String[] args) {
        int HELL = ((int)(1e9));
        for(int i=0;i<HELL;i++) {
            for(int j=0;j<HELL;j++) {
                int k = i + j;
                k++;
            }
        }
    }
}
# Python Code
def main():
    HELL = 10**9
    for i in range(HELL):
        for j in range(HELL):
            k = i + j
            k += 1

main()

I started executing those snippets one by one. If the program is executing for more than 3 seconds, I used ctrl + c key combo to stop the program. Surprisingly, the Java Program executed in less than 1 second.

Since its time complexity is O(N^2), and N is very huge, I thought it would take eternity to execute. But it didn’t happen like that. Can anyone explain?

None of the snippets actually have an observable effects, and a smart enough compiler will figure this out and compile everything away.

With -O3, g++ with the .cpp version exits immediately:

[simon@simon-laptop][09:53:55]
[~/devel/hackerrank/otherpeoples]>g++ -o program -O3 suman_18733097.cpp 
[simon@simon-laptop][09:53:59]
[~/devel/hackerrank/otherpeoples]>time -p ./program 
real 0.00
user 0.00
sys 0.00
[simon@simon-laptop][09:54:05]
[~/devel/hackerrank/otherpeoples]>g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/7/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 7.5.0-3ubuntu1~18.04' --with-bugurl=file:///usr/share/doc/gcc-7/README.Bugs --enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++ --prefix=/usr --with-gcc-major-version-only --program-suffix=-7 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --enable-bootstrap --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-gnu-unique-object --disable-vtable-verify --enable-libmpx --enable-plugin --enable-default-pie --with-system-zlib --with-target-system-zlib --enable-objc-gc=auto --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-offload-targets=nvptx-none --without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04) 
2 Likes

It means there is some implicit optimisation taking place when we use -03?
Then why aren’t Python and C codes exiting immediately?
Are we supposed to use any extra arguments to make it happen?

PS: I am curious to know the reason. Do not ignore if it isn’t useful

Just found this. it explains about the “-O3” flag. Thank you @ssjgz, for looking into this.

1 Like

Just to reiterate what @ssjgz said, here’s the assembly when you compile with -O3:

❯ cc temp.c -S -masm=intel -O3
❯ cat temp.s
	.file	"temp.c"
	.intel_syntax noprefix
	.text
	.section	.text.startup,"ax",@progbits
	.p2align 4,,15
	.globl	main
	.type	main, @function
main:
.LFB23:
	.cfi_startproc
	xor	eax, eax
	ret
	.cfi_endproc
.LFE23:
	.size	main, .-main
	.ident	"GCC: (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0"
	.section	.note.GNU-stack,"",@progbits

= return 0.

2 Likes