6 ms·

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

241 points by azhenley 6y ago

deleted 6y ago
[deleted]
tylerhou 6y ago
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).
- falcolas 6y ago
  Well, you could probably abuse preprocessor macros and make something similar in C.
  - azhenley 6y ago
    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 https://codegolf.stackexchange.com/a/69413/4270 The C++ template answers are particularly scary...
    - mey 6y ago
      Template meta-programming is essentially its own language
    - StillBored 6y ago
      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.
  - shakna 6y ago
    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.
    - colejohnson66 6y ago
      How is this supposed to work?
      - phoe-krk 6y ago
        Try compiling it. The compiler will scream at you for a long long time. Also see https://codegolf.stackexchange.com/questions/1956/generate-the-longest-error-message-in-c https://codegolf.stackexchange.com/questions/1956/generate-t...
        colejohnson66 6y ago
        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.
        phoe-krk 6y ago
        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.
        Sharlin 6y ago
        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.
  - Karliss 6y ago
    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.
    - shakna 6y ago
      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};
- analog31 6y ago
  >>> 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.
eesmith 6y ago
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 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!
- chias 6y ago
  I am also unable to reproduce it (Python 3.8.5)
- jwilk 6y ago
  I can reproduce it with Python 3.5, but indeed not with 3.6.
- PartiallyTyped 6y ago
  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
  - eesmith 6y ago
    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.
chrisseaton 6y ago
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?
- wizzwizz4 6y ago
  They're not redefinable on the built-in types. (Well, they are, but not officially.)
fernly 6y ago
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...
- deleted 6y ago
  [deleted]

241 points by azhenley 6y ago

deleted 6y ago

[deleted]

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).

falcolas 6y ago
Well, you could probably abuse preprocessor macros and make something similar in C.
- azhenley 6y ago
  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 https://codegolf.stackexchange.com/a/69413/4270 The C++ template answers are particularly scary...
  - mey 6y ago
    Template meta-programming is essentially its own language
  - StillBored 6y ago
    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.
- shakna 6y ago
  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.
  - colejohnson66 6y ago
    How is this supposed to work?
    - phoe-krk 6y ago
      Try compiling it. The compiler will scream at you for a long long time. Also see https://codegolf.stackexchange.com/questions/1956/generate-the-longest-error-message-in-c https://codegolf.stackexchange.com/questions/1956/generate-t...
      - colejohnson66 6y ago
        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.
        phoe-krk 6y ago
        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.
        Sharlin 6y ago
        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.
- Karliss 6y ago
  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.
  - shakna 6y ago
    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};
analog31 6y ago
>>> 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.

eesmith 6y ago

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 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!

chias 6y ago
I am also unable to reproduce it (Python 3.8.5)
jwilk 6y ago
I can reproduce it with Python 3.5, but indeed not with 3.6.
PartiallyTyped 6y ago
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
- eesmith 6y ago
  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.

chrisseaton 6y ago

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?

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

fernly 6y ago

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

deleted 6y ago
[deleted]