16 bytes of Python that compile to 32 terabytes of bytecode (2016) | Hacker News Reader

16 bytes of Python that compile to 32 terabytes of bytecode (2016)

codegolf.stackexchange.com

241 pointsazhenley23 comments

Someone asked (and deleted their comment while I was writing my reply):

> How does this compile in another language such as C?

It doesn't; the C language doesn't implement arbitrary size integers, and therefore most C compilers won't fold constants of such large size.

If you used a library that provided BigInts (arbitrary size integers), and and the library also provided a compiler extension to fold BigInt expressions at compile time, then you would likely get a large executable as well (most of the size would come from the data section).

>>> Someone asked (and deleted their comment while I was writing my reply):

Oops, that was me. Sorry! I realized that it doesn't, and didn't want to leave what seemed possibly like a snarky question in the discussion, but I'm glad you picked it up and clarified the answer.

Well, you could probably abuse preprocessor macros and make something similar in C.

Not entirely of the same vein, but this C++ stacktrace bomb is one of my favourites:

    struct x struct z<x(x(x(x(x(x(x(x(x(x(x(x(x(x(x(x(x(y,x(y><y*,x(y*w>v<y*,w,x{}

A tiny 79 bytes that explodes into a huge stacktrace that takes an inordinate amount of time to finish processing.

How is this supposed to work?

Try compiling it. The compiler will scream at you for a long long time.

Also see https://codegolf.stackexchange.com/questions/1956/generate-t...

Ah. I was confused by your usage of the word "stacktrace" which, to me, means an exception stack trace, not an error message. For those curious:

    $ g++ test.cpp 2>&1 > /dev/null | wc -l
    10223622

Ten million lines.

Wasn't "my" usage per se since I'm not the original comment author, but yes, I too find this term confusing in this context. A stack trace to me usually means a textual dump of a call stack printed from some point of the program execution (usually an error site and/or a breakpoint), not compiler output that contains no information about the compiler's runtime stack.

I would say that 'stacktrace' is appropriate.

The template expansion machinery is pretty much a purely functional language and the compiler is the interpreter. The stacktrace in this case is not of the interpreter itself but of the program being executed.

In fact understanding that template error messages are none other than execution stack traces is key to making sense them.

In this case the error message contains information about the compiler's template instantiation stack which is rather analogous to the stack trace of a recursive function. But yeah, a somewhat nonstandard usage.

Even without abusing preprocessor or C++ templates you do something as simple as global array char a[1ULL<<30]={1};

Initialize at least one member so that it gets placed in data section instead of bss resulting in binary size more or less the same as array. Although at least on my system various parts of toolchain start to break down once you reach 2GB limit.

The plain C equivalent to the above, changing the "command" part to be something valid:

    const main[255<<21]={195};

You can also get around the 2Gb limit by using the -mcmodel flag, such as 'gcc -mcmodel=medium FILE'. But then actually compiling the thing takes a long time and a heck of a lot of memory:

    const main[-1u]={195};

I can't find my favorite C macro bomb, but this same post has a C answer using defines: https://codegolf.stackexchange.com/a/69413/4270

The C++ template answers are particularly scary...

g++ has gotten a lot better in the ~10 years since I wrote a bignum library with nested template parameters. Back when I initially did it, gcc would literally try and expand everything, resulting in insane compile times (and out of memory issues/crashes). If it did manage to compile it, the resulting exe's were also massive.

At some point (to lazy to look up the flag) gcc added a template recursion parameter that stops trying to unroll everything at some sane depth. Now the code compiles quickly the .exes are reasonably sized/etc.

Template meta-programming is essentially its own language

I thought that problem got fixed a few releases ago. Maybe 3.7, when some of the peephole optimizer logic was moved to the AST?

At the very least, I can't reproduce it.

  % cat tmp.py
  (1<<19**8,)*4**7
  % python -m compileall tmp.py
  % ls -l __pycache__/tmp.cpython-39.pyc
  -rw-r--r--  1 eesmith  admin  167 Feb 16 12:21 __pycache__/tmp.cpython-39.pyc

Python 3.6 generates a 144 byte file. One of the comments says it caused a problem in Python 3.3.5.

Another peephole optimizer gotcha that caused problems with older Pythons is at https://bugs.python.org/issue30416 :

  def tuple20():
      return ((((((((1,)*20,)*20,)*20,)*20,)*20,)*20,)*20,)*20

If you have Python 2.7 hanging about, try simply defining that function - you can't even ^C it!

I can't reproduce in 2.7.16 and 3.7 either. The tuple20 is an interesting one, using lists instead of tuples it doesn't explode in size, at least in 2.7

That's because the peephole optimizer only looks at constants, and lists aren't constant while tuples are.

It doesn't explode in size.

The peephole optimizer is checking for uniqueness, via a dict, and evaluating hash() of that constant takes a very long time.

I can reproduce it with Python 3.5, but indeed not with 3.6.

I am also unable to reproduce it (Python 3.8.5)

How is Python able to constant-fold at bytecode compile-time like that? I thought operators were redefineable in Python? So could they be redefined next time you load the bytecode and the constant now invalid? Is that not the case?

They're not redefinable on the built-in types. (Well, they are, but not officially.)

Taking the simple core of it would be a good teaching exercise for a beginner class.

  >>> 1<<2**8
  115792089237316195423570985008687907853269984665640564039457584007913129639936
  >>> 1<<3**8
 
 114235622173779374328348175648643910549218134760744031862028761
  ...quite a few lines later...
  52363416415356114173952

Ask students to explain wtf is going on...

Reply on news.ycombinator.com